Under What Conditions Will the Public and Private Keys Produced by RSA Algorithm Be Reversible?

Question

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.

Answer 1

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$.