Score:2

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

fr flag

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.

kelalaka avatar
in flag
Does this answer your question? [Is it more weak to encrypt with the private key RSA?](https://crypto.stackexchange.com/questions/76419/is-it-more-weak-to-encrypt-with-the-private-key-rsa). **Also**, [Using RSA public key as private key and vice-versa](https://crypto.stackexchange.com/q/76866/18298) **and** [Is RSA encryption with a private key the same as signature generation?](https://crypto.stackexchange.com/q/15997/18298)
Daniel S avatar
ru flag
More germane is [can a public key be same as private key](https://crypto.stackexchange.com/questions/71836/can-a-public-key-be-same-as-private-key) though none of these cover your question of when the circumstances can occur. For the answer to this, see below.
kelalaka avatar
in flag
[Does RSA work for any message M?](https://crypto.stackexchange.com/a/1006/18298)
kr flag
Does this answer your question? [Using RSA public key as private key and vice-versa](https://crypto.stackexchange.com/questions/76866/using-rsa-public-key-as-private-key-and-vice-versa)
fgrieu avatar
ng flag
The question is not a duplicate of any of the above Q. It's not (at least, only) asking if we can swap public and private exponents/keys. It asks if the public key is such that re-encrypting deciphers.
Score:1
ru flag

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

fgrieu avatar
ng flag
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$.
Daniel S avatar
ru flag
@fgrieu Indeed.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.