3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ There are few multiples of $\lambda(n)$ and you can at least try them. $\endgroup$
    – kelalaka
    Jan 31 at 10:18
  • $\begingroup$ So you mean since $\varphi(n)=\lambda(n)\dot gcd(p-1, q-1)$, it would add just a few more check with multiples? Is it true? I would like to see some examples. $\endgroup$
    – Zixi Sean
    Jan 31 at 18:13
  • $\begingroup$ Here a code to find examples where $\phi(n) \neq \lambda(n)$. This doesn't mean that checking all of them is effective. $\endgroup$
    – kelalaka
    Jan 31 at 18:15
4
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Thanks Samul, so this means the answer is YES. Though I need to digest more on this with Saga code. $\endgroup$
    – Zixi Sean
    Feb 1 at 6:49
  • 1
    $\begingroup$ Well, more like for typical parameters yes, but you can come up with contrived parameters (mainly using large $e$) where one method works and the other doesn't. $\endgroup$ Feb 1 at 6:53
0
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ We know that the probabilistic method always works - the question is about the deterministic method $\endgroup$
    – poncho
    Jan 31 at 22:47
  • 1
    $\begingroup$ @poncho talking about probabilistic method may be we can also use the classical part of Shor's algorithm. Sincle $\lambda (n)$ is sure to be even and we just need to find suitable $a$, such that $a^{(\lambda (n) /2)} + 1$ and $a^{(\lambda (n) /2)} - 1$ each are multiples of $p$ and $q$ $\endgroup$ Feb 1 at 4:12

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.