Prime factorization of RSA modulus

Consider RSA public-key encryption with public modulus $N=3953$.

Suppose we know that the public keys $e_1=337$ and $e_2=23$ correspond with the decryption information $d_1=3385$ and $d_2=2663$. That is: $e_1d_1=e_2d_2=1$ mod $\phi(N)$ and $m^{e_1d_1}=m^{e_2d_2}=m$ mod $N$, for all integers $m$ that are relatively prime to $N$.

How do I find the prime factorization of $N$ from the above information? I want to find the prime factorization without any brute-force method.

I have noticed that $m^{e_1d_1-e_2d_2}=1$ mod $N$. I have also noted that $e_1d_1-1$ is a multiple of $\phi(N)$. Does this say somehting about the prime factorization of $N$?

Edit:

$gcd(e_i,\phi(N))=1$ and $e_id_i=1$ mod $\phi(N)$ by assumption, for $i=1,2$.

• Typically $e$ is the public key, not the private key. Feb 12 '14 at 17:30
• An important correction; it is not neccesarily true that $e_1 d_1 = e_2 d_2 - 1 \bmod \phi(N)$. With the $e_1, d_1, e_2, d_2$ you picked, it will be true, however it would not be if we picked (for example) $e_1=337, d_1 = 1471, e_2=23, d_2 = 749$. Instead, the relationship that is guaranteed to hold is $e_1 d_1 = e_2 d_2 = 1 \bmod lcm(p-1,q-1)$, where $p$, $q$ are the prime factors of $N$. This changes how you approach this question. Feb 12 '14 at 17:42
• If your textbook says $e_1d_1 = 1 \bmod \phi(N)$, you might want to consider getting another textbook. Such an $e_1, d_1$ will work as RSA public/private exponents, however not all valid exponents will satisfy the equation; for example, consider the $e_1=337, d_1=1471$ example I gave previously; we have $(x^{337})^{1471} = x \bmod 3953$ for all $x$, but $337 \times 1471 \not\equiv 1 \bmod \phi(3953)$ Feb 12 '14 at 17:51
• Take a look at this SO question and this Crypto question Feb 12 '14 at 18:26
• @Moses: If you insist on using both private keys, it may help that $\operatorname{lcm}(p-1,q-1)$, and perhaps also $\phi(N)$, divides $e_j\cdot d_j-1$. However in a logician's or cryptographer's view, it is fine to use just one $(e_j,d_j,N)$ to factor $N$ when two are known; and with just one, the method in the proof of fact 1 in Dan Boneh's Twenty Years of Attacks on the RSA Cryptosystem works.
– fgrieu
Feb 13 '14 at 14:17

If you knew $pq$ and $p+q$, you could find $p$ and $q$ by algebra. If you knew $pq$ and $(p-1)(q-1)$, you could find $p+q$. Now $e_1d_1-1$ and $e_2d_2-1$ are both said to be multiples of $\phi(n)$, so their greatest common divisor should be a (smaller) multiple of $\phi(n)$, from which you could easily guess $\phi(n)$.