Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I've been attending a series of lectures on Cryptography from an engineering perspective, which means that most of the assertions made are supplied without proof... here's one that the lecturer couldn't recall the reason for, nor original source of.

Given an unfactored $n=pq$, computing $\phi(n)$ is as hard as finding $p,q$; this is the key idea of various "RSA-like" cryptosystems. One presented had a step in which for a secret $k$ and a random $t$, $k-t\phi(n)$ is transmitted. The claim was then that this process should only be applied once, as if an attacker sees $k-t\phi(n)$ and $k-u\phi(n)$ then they can recover $(t-u)\phi(n)$, and it's alleged that this makes it easier to compute $\phi(n)$.

So my question is, why is it easier to compute $\phi(n)$ given a random multiple of it, assuming we're at "cryptographic size"? (that is, $p,q$ sufficiently large that it's not feasible to try and factor $n$ and $\phi(n)$)

share|improve this question
add comment

4 Answers 4

up vote 10 down vote accepted

While I cannot immediately see an easy way to find Φ(n) from (t-u)Φ(n), assuming t-u is also of "cryptographic size" of course, an attacker will probably not have to.

Depending on how RSA-like the cryptosystem is, knowing a multiple of Φ(n) might well be enough to decrypt. After all, given the public exponent e, the private key in RSA is only an integer d with the property that ed = 1 mod Φ(n). Knowing (t-u)Φ(n) will allow the attacker to find an integer d satisfying ed = 1 mod (t-u)Φ(n) as long as gcd(t-u,e)=1. This d will also satisfy ed = 1 mod Φ(n), so it will work as a private key.

share|improve this answer
add comment

If you know an even $m$ such that $a^m \equiv 1 \mod n, (a,n)=1$, e.g. a multiple of $\phi(n)$ then there is a standard probabilistic algorithm to factor $n=pq$. Write $m = 2^rs$ with $s$ odd. Pick a random $a$ and compute $a^s, a^{2s}, a^{4s},\ldots$. If $a^s \ne 1 \mod n$, then at some point in the calculation, you find $b \ne 1 \mod n$ with $b^2 \equiv 1 \mod n$. If $b \ne -1 \mod n$, then you factor $n$ by computing $(b-1,n)$. This will succeed with probability $> 1/2$, so if it fails, pick another $a$. By picking enough $a$'s, you make the probability of success as close to $1$ as you like.

share|improve this answer
add comment

I also don't see how to recover Φ(n) from (t-u)Φ(n). However, if you do the step in question a third time with the same k and a random v, then you can compute (t-u)Φ(n) and (t-v)Φ(n), and taking a gcd will very likely give you Φ(n) or a small multiple thereof.

share|improve this answer
add comment

One thought that is only one step worse than what you are suggesting is that if the message gets sent 3 times: $k- t\phi(n)$, $k-u\phi(n)$, and $k - s\phi(n)$, then one can recover 3 different differences, and easily perform the euclidean algorithm on the pairs. This well always result in a multiple of $\phi(n)$, and I expect that unless $s$, $t$, and $u$ have a lot of congruence relationships between themselves, then this will result in $\phi(n)$ itself.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.