2
$\begingroup$

In the article A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, the original RSA article, it is mentioned that Miller has shown that n (the modulus) can be factored using any multiple of φ(n).

Imagine I know the public and the private key. But what I really want is the factors of n, the p and q but I cannot use any factorization algorithm in a large number of n.

In the Miller's article it is suppose to say how I can find the two factors, knowing the public and private key. But I cannot understand how exactly it is done. Does someone know? Or have a small example?

Improve this question
$\endgroup$
2
  • $\begingroup$ Please do not cross-post questions on multiple sites. Even if it fits on multiple. Only post on one. $\endgroup$
    – mikeazo
    Commented Jan 13, 2015 at 20:23
  • $\begingroup$ Ok, thanks for the advise. I did not know in which one should I post the question. $\endgroup$
    – user3343768
    Commented Jan 14, 2015 at 11:11

2 Answers 2

Reset to default
7
$\begingroup$

While the way that Robert showed can work if $e$ is small (and if $e \cdot d \equiv 1 \pmod{\phi(n)}$ (which is not necessarily true), there is a slightly more complicated method which will work in any case.

What we do is compute $\lambda = (e \cdot d - 1)/ 2^k$ odd (and $k$ is the integer that makes $\lambda$ odd. The special property that $\lambda$ has is that $(m^\lambda)^{2^k} \equiv 1 \pmod{n}$ for any $m$ relatively prime to $n$.

Here's how we use it; we pick a random $m$, and compute $m^\lambda \mod n$. If it is 1 or $n-1$, we go back and select another $m$.

If it is not, we repeatedly square the value ($\mod n$), and check if the value becomes 1 or $n-1$ (and because of $\lambda$'s property, it'll turn into one of the two in at most $k$ squarings, unless we happened to pick an $m$ which wasn't relatively prime to $n$); if the value became $n-1$, we go back, and pick another $m$. However, if it became 1, that means that the immediately previous value $z$ had the property $z^2 \bmod n = 1$, that means that $gcd(n,z-1)$ and $gcd(n,z+1)$ are the factors of $n$.

And, at least 1/2 of the possible $m$ values will result in a factorization, hence this method is practical.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Is there a simple proof that at least 3/4 of the possible $m$ values will result in a factorization? $\endgroup$
    – fgrieu ♦
    Commented Jan 14, 2015 at 7:20
  • 1
    $\begingroup$ @fgrieu: actually, the real figure is 1/2, not 3/4 (I've corrected my answer). As for a simple proof, well, one won't fit on this response, however here's how it works: if we look at the behavior of $(m^\lambda)^{2^i}) \pmod p$, we see that it has a probability 0.5 of turning into 1 at step $j$ (where $j$ is such that $(p-1)/j$ is odd), and a probability 0.5 of turning into 1 at some earlier step; and similarly with $q$. Now, $m$ will reveal a factorization if $p$ and $q$ turn into 1 on different steps. $\endgroup$
    – poncho
    Commented Jan 14, 2015 at 14:43
  • $\begingroup$ then method showned by Poncho is in fact a corrollary of Miller-Rabin primality test. In case of RSA, the prime factors have passed MR test and hence we understand the method.Solving the quadratic polynomial $z^2-1=0$ in Z/nZ would lead to 4 solutions, from which only two give modulus factorization. (quadratic polynomials have at most 2 solutions only in fields). Then probability of success is 0,5. This can be linked with the general problems of quadratic residue and the the Rabin Cryptosystem. $\endgroup$
    – Robert NACIRI
    Commented Jan 14, 2015 at 16:58
3
$\begingroup$

Generally the public exponent is small. then if you know the public and private key, then you can compute $e.d=1+k.\phi(n)$. k is smaller than e and $\phi(n)$ is in the range of n. A direct method allow to make an exhaustive search on the small k which divide ed-1 in such a way that $\frac{e.d-1}{k}$ is an integer.

Then $\phi(n)= p.q -(p+q)+1$ allow to find $p+q$ and solving a quadratic equation gives directly p and q.

This is the simplest method, which can be easilly implemented.

Improve this answer
$\endgroup$

Your Answer

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

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