RSA public key and private key calculation: multiple answer

Given N = 91 public key (11, 91) Plaintext (88)

Ciphertext = 88 ^11 mod 91 = 30

to decrypt,
30 ^ 59 mod 91 = 88 (plaintext)
30 ^ 11 mod 91 = 88 (plaintext)
30 ^ 47 mod 91 = 88 (plaintext)

How can there be multiple suitable instance of private key such as 59/11/47?

Lastly, must public and private key always be a prime number?

migrated from security.stackexchange.comApr 13 '18 at 11:33

This question came from our site for information security professionals.

[M]ust public and private key always be a prime number?

No, they don't have to be. Usually the public key is chosen as an odd prime though because it must hold that $\gcd(e,\lambda(n))=1$, which simplifies to "$e$ must not divide $\lambda(n)$" if $e$ is prime.

How can there be multiple suitable instance of private key such as 59/11/47?

Recall that all we need for correctness for RSA is that for each possible $m$ it holds that $m^x\bmod n=m$. It turns out that the smallest possible $x$ here isn't the euler-phi function $\varphi(n)=(p-1)(q-1)$ (in the two-prime case) but rather the carmichael function $\lambda(n)=\operatorname{lcm}(p-1,q-1)$ (in the two-prime case), because it is defined to be the smallest such $x$.

Now what does this mean? It means that if $ed\equiv 1\pmod{\lambda(n)}$ then $e,d$ is a valid pair of RSA exponents. As you can individually reduce each factor in modular arithmetic this also means that for a fixed choice of $e,d$ for any integers $k,l$ the following is also a pair of valid exponents: $e+l\lambda(n),d+k\lambda(n)$ because $(e+l\lambda(n))(d+k\lambda(n))=ed+ek\underbrace{\lambda(n)}_{0}+dl\underbrace{\lambda(n)}_{0}+\underbrace{\lambda(n)}_{0}\lambda(n)\bmod\lambda(n)=ed$. What you have experienced was the choice $e=11,d=11$ and $k=0,3,4$.

It is mathematically possible because of the mod operator. Much like there are several solutions of x mod 91 = 88 (x=91*k+88), there are multiple solutions of C^d mod 91. Actually, the key can be thought of as an element of a multiplicative group which has multiple representations. For more technical details, see this answer: https://crypto.stackexchange.com/a/48829/57767.

must public and private key always be a prime number?

RSA keys are actually pairs of numbers: the private key is (N,d) and the public key is (N,e). N is clearly not a prime number, as it is the product of two primes. d, e are not necessarily primes.

For example, take N=29*41=1189. e=9, d=249 are perfectly valid RSA exponents, even if they are not primes.