3
$\begingroup$

I stumbled across this paragraph in a paper:

Hence, user b cannot decrypt C directly. But using e and d , user b can quickly factor N.

How is it possible to speedup the prime factorization when knowing e (public key) and d (private key)?

For clarification:

RSA provides us with these equations:

$n = pq$

$\phi = (p-1)(q-1)$

$gcd(e, \phi) = 1$

$de = 1\pmod{\phi}$

In order to determine $p$ and $q$ an attacker has to factor n which is not feasible. However the paper stated that it is easy to reconstruct $p$ and $q$ when a person knows both (his) private and public keys.

$\endgroup$
  • 2
    $\begingroup$ It might help if you told us what $d$ and $e$ are. $\endgroup$ – Robin Chapman Nov 29 '10 at 11:03
  • 1
    $\begingroup$ d is the private key and e is the public key $\endgroup$ – Chris Nov 29 '10 at 11:13
  • 1
    $\begingroup$ Chris means: N = pq, with p and q odd primes; and ed = 1 mod (p-1)(q-1). $\endgroup$ – TonyK Nov 29 '10 at 12:17
  • 4
    $\begingroup$ For "small" public exponents $e$ (i.e., $<\sqrt{n}$) you can rewrite your last equation as $de = 1 + k\varphi$ and divide this equation by $n$. As $\phi \approx n$ and as $k$ is an integer, you get $k$ by rounding $de/n$ and hence $\varphi$. For the general case see 8.2.2(i) in cacr.math.uwaterloo.ca/hac/about/chap8.pdf $\endgroup$ – j.p. Nov 29 '10 at 12:49
9
$\begingroup$

It is not difficult to prove that one can factor $\rm N$ in polynomial time given any multiple of $\rm \phi(N)$ (here $\rm \:de-1\:$).$\ $ See, for example, Gary Miller: Riemann's hypothesis and tests for primality. 1976

NOTE $\ $ This fact was well-known to the discoverers of RSA. Indeed they mention it explicitly in section IX of the original 1978 paper on RSA, which is quite readable.

$\endgroup$
2
$\begingroup$

Here is a probabilistic method that borrows ideas from an extension of the Rabin-Miller primality test which can be used for factoring pseudoprimes $n$ that are not strong pseudoprimes. The extension is described in Miller 1976, which is one of the references given in Bill Dubuque's answer.

It works when given some multiple $m$ of $\lambda(n)$ where $\lambda$ is Carmichael's lambda function. We assume that $n$ can be represented as $n=pq$ with unknown odd coprime $p,q>1$. The goal is to find a nontrivial factor of $n$.

  1. Set $h$ to the largest odd divisor of $m$ by dividing out $2$ as many times as possible.
  2. Choose a random $a\in\{2,3,\ldots,n-2\}$.
  3. Compute $g=\gcd(a,n)$. This is probably $1$ for most $a$, but if not, you have found a nontrivial factor $g$ of $n$, so you are done. More importantly, the following steps implicitly assume that $\gcd(a,n)=1$.
  4. Compute $b = a^h\bmod{n}$. We know that the multiplicative order of $b\pmod{n}$ is $1$ or some power of $2$. That order is also the least common multiple of the orders$\bmod{p}$ and$\bmod{q}$. We hope that those orders differ, which is likely (see below). In the following, we try to find the smallest order.
  5. Compute $g=\gcd(b-1,n)$. Remark: If $b\equiv1\pmod{p}$, then $g$ will be divisible by $p$. And if $b\not\equiv1\pmod{q}$ yet, then $g$ will not be divisible by $q$, so $g$ will be a nontrivial divisor.
  6. If $g=1$, replace $b$ with $b^2\bmod{n}$ and go to step 5. This will not loop forever because $b$ is known to reach $1\pmod{n}$ with a finite number of repetitions of step 6. That brings us to$\ldots$
  7. If $g=n$, the multiplicative orders of $a^h\pmod{p}$ and $a^h\pmod{q}$ are equal. Then go to step 2, we need another $a$.
  8. If you end up here, $g$ is a nontrivial factor of $n$.

How likely is it that the orders of $a^h$ are different$\bmod{p}$ and$\bmod{q}$?

Let $n=p_1^{e_1}\cdots p_k^{e_k}$ with pairwise distinct odd primes $p_i$ and positive integer exponents $e_i$. Write $\phi(p_i^{e_i}) = 2^{t_i} u_i$ with odd $u_i$ and set $t_{\text{min}} = \min\{t_1,\ldots,t_k\} \geq 1$. Note that $t_i$ does not depend on $e_i$. Note also that each $u_i$ divides the given $h$.

The $a$ that do not yield nontrivial factors of $n$ are those with order $\text{(odd number)}\cdot2^j$ in the unit group$\bmod{p_i^{e_i}}$, with the same $j$ for every $i$. Therefore such $j$ cannot exceed $t_{\text{min}}$.

For each such $j$, there are exactly $\phi(2^j)\,u_i = 2^{\max\{0,j-1\}} u_i$ non-yielding $a$ in the unit group$\bmod{p_i^{e^i}}$, namely, the primitive $2^j$-th roots of the $u_i$ solutions to $X^{u_i}\equiv 1\pmod{p_i^{e_i}}$. In the unit group$\bmod{p_i^{e_i}}$, those $a$ have a density of $2^{\max\{0,j-1\} - t_i}$. By chinese remaindering, we find that the non-yielding $a$ in the unit group$\bmod{n}$ have density $$\begin{align} \rho &= \sum_{j=0}^{t_{\text{min}}} \prod_{i=1}^k 2^{\max\{0,j-1\} - t_i} \\ &= \sum_{j=0}^{t_{\text{min}}} 2^{k\max\{0,j-1\} - (t_1 + \cdots + t_k)} \\ &= 2^{-(t_1 + \cdots + t_k)} \left(1 + \frac{2^{k\,t_{\text{min}}} - 1}{2^k - 1}\right) \\ &\leq 2^{-k\,t_{\text{min}}}\cdot 2^{k\,(t_{\text{min}}-1)+1} \\ &= 2^{-(k-1)} \end{align}$$ Thus for composite $n$, the success probability is at least $50\%$ for each $a$ that makes it to step 4.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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