1
$\begingroup$

Assume given $g^X\equiv h\bmod p$ where $g$ is of order $\frac{\lambda(p)}2$ where $\lambda(p)$ is Carmichael Lambda function applied to prime $p$ (so $2$ is invertible in exponent) we can compute $X$ in polynomial time on an assumption $2$ is invertible in exponent (we can assume we take square roots and make the generator of order $\frac{\lambda(p)}2$ and we assume $2$ needs to be invertible in exponent).

Consider the scenario where $N=PQ$ and $P$ and $Q$ are equal bit primes and $e$ is encryption key and $d$ is decryption key satisfying $ed=1\bmod\varphi(N)$ where $\varphi(N)$ is Euler totient function applied to $N$:

Find $r$ such that $g^r\equiv1\bmod N$ where $r$ is period of the multiplicative group modulo $N$ and $g$ generates it.

In the above two cases since we do not know $\varphi(N)$ we cannot assume $2$ is invertible in exponent.

Is $RSA$ attackable if discrete logarithm is broken using an algorithm which makes essential utilization of $\lambda(p)$?

PLEASE DO NOT CONNECT TO Reduction of Integer factorization to Discrete logarithm problem and please see comments on reasons. Bach utilizes blackbox notions which encompasses knowledge of $\lambda(p)$.

$\endgroup$
11
  • $\begingroup$ Is this a homework question? $\endgroup$
    – poncho
    Dec 14 '20 at 17:56
  • 2
    $\begingroup$ Does this answer your question? Reduction of Integer factorization to Discrete logarithm problem $\endgroup$
    – Mark
    Dec 14 '20 at 18:10
  • $\begingroup$ @poncho no. Bach's paper gets discrete logarithm as a black box algorithm. It implicitly assumes all properties of $\lambda(p)$ can be exploited though we don't know it. $\endgroup$
    – Mr.
    Dec 14 '20 at 18:15
  • 1
    $\begingroup$ @Mark I am aware of Bach's algorithm. $\endgroup$
    – Mr.
    Dec 14 '20 at 18:16
  • 1
    $\begingroup$ @Mark: actually, for semi-primes, the relation is $\lambda(n) = \phi(n) / \gcd(p-1, q-1)$, and so there are more possibilities (especially if $\gcd(p-1, q-1)$ happens to be large). $\endgroup$
    – poncho
    Dec 14 '20 at 18:36

Your Answer

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

Browse other questions tagged or ask your own question.