0
$\begingroup$

Simple question, Given c=$b$$e$ mod $m$, we all know finding $e$‎ is equivalent to solving the discrete logarithm.
But what about finding $b$ from c ; $e$ and the semi‑prime $m$ ? Is it something harder than factoring $m$ too ?

If yes as this is different from the ʀꜱᴀ problem, how to compute $b$ when $e$ is more than 128‑bits long (so not small) ? Is the possibility to set c to arbitrary values while changing prime $e$ is making things easier to get at least 1 example where $b$ is found ?

$\endgroup$
4
  • $\begingroup$ Related Is it proven that breaking RSA is equivalent to factoring as of 2021? $\endgroup$
    – kelalaka
    Mar 19 at 14:26
  • $\begingroup$ @kelalaka the exponent in my case if far larger than anything used for ʀꜱᴀ and there’s to be no special cases : $c$ can be arbitrary values and $e$ too if it’s a large prime. $\endgroup$ Mar 19 at 15:46
  • $\begingroup$ The only requirement for RSA's $e$ is $\textrm{gcd}(e,\lambda(m))=1$ so that the inverse exists and is unique. Choosing $e$ small is preferred to reduce the costs. $\endgroup$
    – kelalaka
    Mar 19 at 16:50
  • $\begingroup$ @kelalaka in my case, e is a random 256‒bits prime that can only be predicted, so it can’t be small. Does this makes things simpler that $gcd(e,λ(m))≥1$ which means several solutions exists ? $\endgroup$ Mar 19 at 17:06

1 Answer 1

2
$\begingroup$

This is equivalent to finding the RSA plaintext $b$ given the public key $(m,e)$. Usually called The RSA Problem. It is no harder than factoring $m$. There is however no evidence that it is easier than factoring.

Edit: As @DanielS points out I was a bit sloppy. For the mapping to be one-to-one, i.e., for the encryption to be reversible, we require $\textrm{gcd}(e,\lambda(m))=1$ and the term RSA problem denotes this case.

$\endgroup$
7
  • 2
    $\begingroup$ Slight quibble: it's the RSA problem when $(e,\lambda(m))=1$. Although not quite well-defined in the case $(e,\lambda(m))>1$, it is equivalent to factoring in such cases (at least in a PPT-sense for small $(p-1,q-1)$, though other results may be out there). $\endgroup$
    – Daniel S
    Mar 19 at 12:40
  • $\begingroup$ @kodlu even if the exponent is longer than 128‒bits large ? And if yes, how do it efficiently exactly ? $\endgroup$ Mar 19 at 15:39
  • $\begingroup$ @DanielS I don’t have this in the case of the ʀꜱᴀ problem but in the case of the adaptive root problem where the random exponent can be predicted… So does the fact e c can be arbitrary values don’t change anything ? The only requirement, I have if for e to be a large prime. What’s $λ(m)$ ? In my case, I’m almost sure (e,λ(m)) will be greater than 1. $\endgroup$ Mar 19 at 15:44
  • $\begingroup$ @user2284570: $λ$ is the Carmichael function. If $m=p\,q$ with $p$ and $q$ distinct primes, then $λ(n)=\operatorname{lcm}(p-1,q-1)$, and $b=c^{(e^{-1}\bmodλ(n))}\bmod m$. In python (3.8 or better): b=pow(c,pow(e,-1,math.lcm(p-1,q-1)),m). Or b=pow(c,pow(e,-1,m-p-q+1),m). Update: that's for $\gcd(e,\lambda(m))=1$. For $\gcd(e,\lambda(m))>1$ there might be several, or no solution. $\endgroup$
    – fgrieu
    Mar 19 at 16:16
  • $\begingroup$ @fgrieu-modelectiontime so this requires to factorize $m$? $\endgroup$ Mar 19 at 16:39

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.