Does Coron and May's paper for deterministically reducing finding 𝑑 to factoring 𝑛 work with $\lambda(n)$?

Question

Samuel Neves in his reply mentioned a method by Coron and May's 2004 paper for deterministically reduce finding 𝑑 to factoring 𝑛.

As you all know, we are using $\lambda(n)$ everywhere now for RSA. So question is, does this work for $d$ generated with $\lambda(n)$? The paper seems referring to $\varphi(n)$ only. If it does work, what is the proof?

Also, anybody knows some reference implementation of Coron and May's method in Python or other language?

If it does not, is there any probabilistic method/algorithm to factor $n$ if $e,d$ are known and $ed = k\lambda(n) + 1$ ?

Answer 1

As mentioned in the other answer, the probabilistic method always works, and I've described both of these methods before.

We'll deal exclusively with $p, q$ of approximately the same size here. Suppose $l = \gcd(p-1, q-1)$, the ratio between $\phi(n) = (p-1)(q-1)$ and $\lambda(n) = \mathrm{lcm}(p-1, q-1)$. As usual, let $n = pq$, $e$ be the public exponent, $d = e^{-1} \bmod \phi(n)$, and $d' = e^{-1} \bmod \lambda(n)$.

The original Coron-May reduction observes that $f(x) = n - x$ has a "small" root $p+q-1$ modulo $\phi(n)$, a "large" divisor of $ed - 1$. More specifically, as long as there's a $\beta \in [0, 1)$ such that $p+q-1 \le (ed - 1)^{\beta^2}$ and $\phi(n) \ge (ed - 1)^{\beta}$, the method works in polynomial time. Because $\phi(n) \approx n$, this effectively translates into the requirement $ed \le n^2$.

Without any changes to the method, replacing $\phi(n)$ by $\lambda(n)$ means that $f(x) = n - x$ has a small root $p+q-1$ modulo a large factor of $ed' - 1$. Because of the common factor $l$, $d'$ may be much smaller than $d$, and in particular the size is no longer neatly related to $n$, so as to achieve a bound like $ed' \le n^2$. However, the method still works under the more elaborate constraint that there be a $\beta$ such that $p+q \le (ed' - 1)^{\beta^2}$ and $\lambda(n) \ge (ed' - 1)^{\beta}$.

For typical $e = 65537$, we still have $\lambda(n) = (ed'-1)^{\beta}$ for a $\beta$ very close to $1$. As long as $2p < (ed' - 1)^{\beta^2}$, the reduction still works.

Here's a worked example using Sagemath, where $\phi(n) \approx 2^{130}\lambda(n)$.

sage: p = 30010719099306564150822479775631261956587370647517629976046542673406882291177
sage: q = 91932507744510266739810220416155764940049951037172916877150162469889273507869
sage: n = p * q
sage: l = gcd(p-1, q-1)
sage: l
1361129467683753853853498429727072846028
sage: e = 65537
sage: d = inverse_mod(e, lcm(p-1,q-1))
sage: P.<x> = Zmod(d*e-1)[]
sage: f = x - n
sage: beta = d.log(d*e).n()
sage: beta
0.959304860280816
sage: assert(p+q < (d*e-1)^(beta^2))
sage: f.small_roots(X=2^257, beta=beta, epsilon=0.05)
[121943226843816830890632700191787026896637321684690546853196705143296155799045]
sage: p+q-1
121943226843816830890632700191787026896637321684690546853196705143296155799045

With a larger $e$, it still works. Say, $e \approx 2^{180}$:

sage: e = next_prime(2^180)
sage: d = inverse_mod(e, lcm(p-1,q-1))
sage: P.<x> = Zmod(d*e-1)[]
sage: f = x - n
sage: beta = d.log(d*e).n()
sage: beta
0.677720040398063
sage: f.small_roots(X=2^257, beta=beta, epsilon=0.01)
[121943226843816830890632700191787026896637321684690546853196705143296155799045]

Here we are already pushing the limit, since $(ed' - 1)^{0.6777^2} \approx 2^{256.53}$. Going much higher with $e$ will fail. The original method with $\phi(n)$ would allow $e$ to go up to $\approx 2^{512}$ in this example.

Answer 2

The probabilistic method always works.

Let $p-1=2^a r, q-1=2^b s$, with $r,s$ odd. Without loss of generality, $a \le b$. We are given $f = k\lambda(n) = k 2^a lcm(r,s)$, where $k,a$ are unknown. First, divide $f$ by maximal power of 2, to get an odd multiple of $lcm(r, s)$, say $g$. Choose random $c \in \mathbb{Z}_n$, compute the sequence $c^g, c^{2g}, c^{4g}, c^{8g}, \ldots, 1$ and for each element $c_i=c^{g2^i}$ check if $gcd(c_i-1,n)$ is non-trivial. Note that the sequence length is at most $\log_2{p}$.

For $i=b-1$, if $c$ is a non-square-residue modulo $q$, and is a square residue modulo $p$, we get $c^{g2^i} \not\equiv 1 \pmod{q}$ and $c^{g2^i} \equiv 1 \pmod{p}$, yielding the factor $p$. The probability to sample such $c$ is 1/4. If $a < b$, we always get $c^{g2^i} \equiv 1 \pmod{p}$ and so the probability of a good $c$ increases to 1/2.