0
$\begingroup$

I'm curious if is it possible to recover a private key from insecure RSA implementation - each letter of the plaintext is encrypted separately (and no padding).

Let's say I have plain-letters, cipher-letters (for every value of plain-letters), public key $(e, n)$.

I know that it is insecure usage of RSA, but I want to know if it is possible to somehow calculate the private key which was used to encrypting.

If I understand RSA correctly we could have 256 equations (for every ASCII character):

\begin{align} m_0 &= {c_0}^d \bmod \\ m_1 &= {c_1}^d \bmod \\ m_2 &= {c_2}^d \bmod \\ \vdots & \quad \vdots\\ m_{254} &= {c_{254}}^d \bmod \\ m_{255} &= {c_{255}}^d \bmod \\ \end{align}

We only don't know d. I read about CRT but seems like not applicable here. Can somebody explain/point if is it possible?

$\endgroup$

1 Answer 1

0
$\begingroup$

Encryption letter by letter without padding is very insecure, at best as a mono-alphabetic substitution cipher. But no, it practically does not help one recover a private key matching a known public key. As far as we know, the least costly general method involves factoring the public modulus $n$ part of the public key.

An exception: for extremely small $n$ and/or pathological choices of $(n,e)$, a working private key $(n,d)$ sometime is $(n,e^k)$ for some small integer $k\ge0$. Thus trying a few small $k$ with the help of a few plaintext/ciphertext pairs might be a viable strategy. Silly exercises where $d=e$ or even $d=1$ works are not unseen. And it's common that $d=e^2$ or $d=e^3$ works in exercises that encrypt letter by letter using a 3-digit $n$.


Recovering a working private key $(n,d)$ is not the same a recovering the private key $(n,d)$. For the later, we must factor $n$, and know something about how the private key was computed, or have some other hint (like examining side channel information from a device using the private key). When $n$ is the product of two distinct odd primes $p$ and $q$, methods to obtain $d$ include:

  • Computing $d=e^{-1}\bmod((p-1)\,(q-1)/\gcd(p-1,q-1))$ (the common modern practice and the one mathematicians prefer, for it gives the smallest working positive $d$).
  • Computing $d=e^{-1}\bmod((p-1)\,(q-1))$ (still commonly taught).
  • Computing $d=e^{-1}\bmod((p-1)\,(q-1)/2)$ (that saves the GCD operation while often offering the same minor performance benefit).
  • Choosing a prime $d$ at random in some interval like $]\max(p,q),p\,q[$, and computing $e$ from that (as in the original RSA article). Now we can find $d$ for sure, or not, depending on what we know about how $e$ was computed, and what the interval really was.

More generally, it is generally believed that no amount of known or chosen plaintext or ciphertext helps recover an RSA private key. But we have no proof of that statement, despite efforts of literally generations of researchers. See this question.

$\endgroup$

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.