1
$\begingroup$

For this example of my problem I used $2$ and $7$ for $p$ and $q$, and $2$ for my plaintext... but I have tried this with many different numbers and they all have the same problem. Phi of $n$ was $6$. My public key was $m^5~mod~14$ and my private key was $m^{11}~mod~14$. This all worked fine. If I encrypted my plaintext $2$ with my public key, $2^5~mod~14$, I got $4$. If I took my ciphertext, $4$, and sent it through the same equation again, $4^5~mod~14$, I get back $2$. How can it be that my RSA public key can decrypt the ciphertext it encrypted?

$\endgroup$
8
$\begingroup$

The prime 2 is special, and too small.

You happened to choose an $e$ which is equal to $d,$ as I explain below. For a proper choice of large primes, it is extremely unlikely that $d=e,$ but if it is, one can simply choose another $e$ and compute the corresponding $d.$

Also, a correction, you public key is $(n,e)=(14,5)$. It is your ciphertext which is $c=m^5~mod~14.$ For this tiny example it happens that $e=5$ satisfies $$e^2=1~(mod~\phi(14))$$ so $d=e$, thus your public and private exponents are the same, not a good thing.

Also you say your private key is $m^{11}~mod~14$, which I interpret to mean your private key $(d,p,q)$ has $d=11.$ This is a valid $d$ since $5\times 11=55=1~mod~\phi(14).$ The correct terminology is $$m=c^d~(mod ~n)$$since the letter $m$ is reserved for the message.

$\endgroup$
  • $\begingroup$ Nit pick: If you end up with $e^2 = 1 \pmod {\phi(n)}$ for any small constant $e$, you should probably regenerate the modulus and not just pick a different $e$. $\endgroup$ – Henrick Hellström Aug 28 '16 at 13:08
  • $\begingroup$ Extremely unlikely is putting it mildly. There won't be many - if any - implementations of RSA that would test for $d \neq e$. Maybe some implementations test that $d$ is not very small, but even that would probably be spurious. $\endgroup$ – Maarten Bodewes Aug 28 '16 at 13:10
  • 1
    $\begingroup$ @MaartenBodewes: Actually, I think a lot of RSA implementations will indirectly "test" for this, by only picking random prime number candidates that would make it impossible. After all, $e^2 \equiv 1 \pmod{\phi(n)}$ is impossible if $e^2 \lt p_{min}-1$ for the least prime factor $p_{min}$ of the modulus. $\endgroup$ – Henrick Hellström Aug 28 '16 at 15:51
  • $\begingroup$ @HenrickHellström Ah, I'll have to revisit the RSA key pair generation from time to time I guess. Thanks for the heed; I guess in that case the explicit check is not needed. $\endgroup$ – Maarten Bodewes Aug 28 '16 at 18:03

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.