2
$\begingroup$

Given p = 7 and q = 13, one can obtain n = 91, d = 29, e = 5. However, for plaintext with values less than the modulus both the public and private keys (n, d) and (n, e) are reversible, i.e. encrypting a plaintext value with either key and then using the same key a second time returns the original value.

What is the reason for this and under what conditions will this occur?

This question notes that there are values of p and q which will generate a public key such that a message encrypted with the public key can also be decrypted with the public key for message values of less than the modulus. Likewise, the private key thereby generated can be used to decrypt a message which was encrypted with the same private key. This question does not ask whether a message can be encrypted with the public key and decrypted with the private key.

The answer from Daniel S provides the information I was seeking.

$\endgroup$
5

1 Answer 1

1
$\begingroup$

Although RSA keys are usually described as solutions to $de\equiv 1\pmod{\phi(N)}$, there is a more precise equation $de\equiv 1\pmod{\lambda(N)}$ where $\lambda$ is the Carmichael function. Any solution to the usual equation is a solution to the more precise equation.

In your case the Carmichael function is $\mathrm{LCM}(p-1,q-1)=12$. The choice of $e=5$ leads to the solution $d\equiv 5\pmod{12}$ to the precise equation, and $d=29$ is an equivalent decryption exponent.

Generically, this will occur when the choice of $e$ is a square root of one modulo the Carmichael function (in this case $5^2\equiv 1\pmod{12}$, but 1, 7 and 11 are other examples). In general, a number $n$ has $2^{\omega(n)}$ square roots of 1 where $\omega(n)$ is the number of distinct prime factors of $n$.

$\endgroup$
2
  • $\begingroup$ So in short, for $N=p\,q$ with $p$ and $q$ distinct odd primes : when $e^2\bmod\operatorname{lcm}(p-1,q-1)=1$. $\endgroup$
    – fgrieu
    Nov 3, 2022 at 17:37
  • $\begingroup$ @fgrieu Indeed. $\endgroup$
    – Daniel S
    Nov 3, 2022 at 18:19

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.