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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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.
-
$\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$ Commented Aug 28, 2016 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 ♦Commented Aug 28, 2016 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$ Commented Aug 28, 2016 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 ♦Commented Aug 28, 2016 at 18:03