Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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$.

share|improve this question
    
Typically $e$ is the public key, not the private key. –  CodesInChaos Feb 12 at 17:30
3  
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. –  poncho Feb 12 at 17:42
2  
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)$ –  poncho Feb 12 at 17:51
1  
Take a look at this SO question and this Crypto question –  mikeazo Feb 12 at 18:26
1  
@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 at 14:17

1 Answer 1

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)$.

I've probably said too much already, given that this is a homework assignment.

share|improve this answer

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.