1
$\begingroup$

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

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

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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