# More than one private key for RSA

In an RSA-encryption scenario, Bob's public key pair $$(n, e)$$ is $$(143, 43)$$. An attacker Mallory tries brute-force and comes to $$d = 7$$ as the private key.

The value of $$φ(143) = 120$$ is not known to Mallory.

However from $$43 \cdot d \equiv 1 \bmod 120)$$, one can calculate the first positive element $$d = 67$$ from multiplicative group $$d = 120 + 67n$$ and $$n \in \mathbb{Z}$$

$$d = 7$$ clearly doesn't fit in that multiplicative group, so how come it can successfully decrypt the encryption?

• I was doing some RSA math trying different numbers. I noticed that $d = 7$ can decrypt at least for messages in $1 ≤ x ≤ 142$ and $n ∈ ℤ$ – user86295 Jan 17 at 17:53

This question can be summarized: the attacker found a $$d$$ that did not satisfy $$e \cdot d \equiv 1 \pmod{ \phi(n) }$$, but it works; what's going on.

It turns out that $$e \cdot d \equiv 1 \pmod{ \phi(n) }$$ is not necessary (it is sufficient).

The necessary and sufficient conditions are:

$$e \cdot d \equiv 1 \pmod{p-1}$$ $$e \cdot d \equiv 1 \pmod{q-1}$$

If both of these hold, then $$d$$ will always work [1]; conversely if $$d$$ always works, then both of these hold.

These two conditions can be summarized as a single relation:

$$e \cdot d \equiv 1 \pmod{\text{lcm}(p-1, q-1)}$$

This $$\text{lcm}(p-1, q-1)$$ modulus is known as the Carmichael function of $$n$$.

In the specific example you have, $$\text{lcm}(p-1, q-1) = 60$$, and we have $$7 \cdot 43 \equiv 1 \pmod{60}$$, and hence $$d = 7$$ works

[1]: Assuming $$p, q$$ are distinct primes.

• Consequently, we want to avoid simple relations between $p$ and $q$. For example if $q=3p-2$ then $\operatorname{lcm}(p-1,q-1)=p-1\ll \phi(n)$. (And apart from that, such bad choices of primes are also easily factored wiht standard algorithms) – Hagen von Eitzen Jan 18 at 12:20

RSA private key can be found in two ways with $$n = p\cdot q$$, $$p = 11$$ and $$q = 13$$

1. if Euler's totient function is used as in RSA paper: $$\varphi(n)= (p-1)(q-1) = 120$$ is used then
• $$d = 67 = e^{-1} \bmod 120$$
2. If Carmichael Function used as requried in FIPS 180.4and allowed in PKCS#1 v2.2 standards: $$\lambda(n) = \text{LCM}(p-1,q-1) = 60$$ is used then
• $$d= 7 = e^{-1} \bmod 60$$

Both are valid and Carmichael Function provides always the smallest $$d$$. The easy relation between both of them is that $$\lambda(n)| \varphi(n)$$. Therefore this indicates that in some setups we can have more than one valid private key where each of them $$\leq \varphi(n)$$. Actually, in the two distinct prime case we have the relation;

$$\varphi(n) = \lambda(n) \cdot \gcd(p-1,q-1).$$ This is due to the fact that $$a \cdot b = \operatorname{lcm}(a,b) \times \gcd(a,b)$$

Since RSA primes are distinct odd primes $$p$$ and $$q$$, then $$\gcd(p-1,q-1) \geq 2$$ and this implies that there is always at least two $$d$$ in the range $$[1,\varphi(n)]$$

This is your case and you have the $$\varphi(n)$$ and the attacker has $$\lambda(n)$$.

The PKCS#1 standard requires the Carmichael Function to be used for the calculation of $$d$$. Original RSA paper used Euler's totient function. Using shorter $$d$$ will decrease the signature time and less used decryption time.

Carmichael Function: For a positive integer $$n$$, $$\lambda(n)$$ is defined to be the smallest positive integer $$k$$ such that $$a^k \equiv 1 \pmod n$$ for all $$a$$ such that $$\gcd(a,n)=1$$

Little proof of $$\lambda(n)| \varphi(n)$$:

The proof relies on the exponent definition of group theory.

Let $$G$$ be group then the non-negative generator of the ideal $$\{z \in \mathbb{Z}: \forall g \in G (g^z=1)\}$$ is called the exponent of the group $$G$$. For finite groups like RSA groups, it is finite and positive, and then it is the smallest positive natural number $$z$$ such that $$g^z=1$$ for all $$g \in G$$.

The exponent of any finite group must divide the order of the group. $$\lambda(n)$$ is the exponent by the definition and the order of the group is $$\varphi(n)$$ also by definition. This clearly implies $$\lambda(n)| \varphi(n)$$.

More than 2 private key example;

• $$n = 6901$$
• factors $$6901 = 103 \cdot 67$$, $$p=103,q=67$$
• $$\varphi(n) = 6732$$
• $$\lambda(n) = 1122$$
• $$e = 43$$
• $$g =\gcd(p-1,q-1)=6$$
• inverse of $$e$$ by $$d = \varphi(n) = 5323$$
• inverse of $$e$$ by $$d' =\lambda(n) = 835$$

Now all $$d+k\cdot \lambda(n)$$ are valid private key where $$k \in [0,g]$$, listing;

1. 835
2. 1957
3. 3079
4. 4201
5. 5323
6. 6445

SageMath code to find the above example;

p = random_prime(200, 400) #upper and lower range
q = random_prime(200, 400)
n = p*q
e = 43
print("n = ",n)
print("factors %s = " % n, factor(n))

phi = (p-1)*(q-1) # or call euler_phi(n)
print("phi    = ",phi)

if gcd(e,phi) != 1:
print( gcd(e,phi))

lmd = lcm(p-1,q-1) #or call carmichael_lambda(n)

print("lambda = ",lmd)

print("gcd(%s,%s) = " % (p-1,q-1), gcd(p-1,q-1))

print("inverse of %s by phi   " %e, inverse_mod(43,phi))
print("inverse of %s by lambda" %e, inverse_mod(43,lmd))

d = inverse_mod(43,lmd)

for k in range(gcd(p-1,q-1)):
print(d+k*lmd)

• The PKCS#1 standard does not require that the Carmichael function $\lambda$ be used for the calculation of $d$. It allows it, and allows any $d$ with $e\,d\equiv1\pmod{\lambda(N)}$ and $0<d<p$. AFAIK, only FIPS 186-4 requires use of $\lambda$, leading to a single $d$. – fgrieu Jan 18 at 11:17
• @fgrieu both FIPS 186-4 and PKCS#1 v2.2 only mentions $\lambda$. – kelalaka Jan 18 at 11:28
• @kelaka. Yes. But FIPS 186-4 (B.3.1. step 3.a) tequires $d=e^{-1}\bmod{\lambda(N)}$ thus $d<\lambda(N)$ (and $2^{\left\lceil\log_2(N)\right\rceil/2}<d<\lambda(N)$ in step 3.b), thus uniquely defines $d$, and requires computing $\lambda(N)$. While PKCS#1 requires $d\equiv e^{-1}\pmod{\lambda(N)}$ and $0<d<n$, thus does not require computing $\lambda(N)$ since we can get away with $d\gets d=e^{-1}\bmod{\varphi(N)}$. That's a common way to compute $d$, is PKCS#1 conformant since $d\equiv e^{-1}\bmod{\varphi(N)}\implies d\equiv e^{-1}\bmod{\lambda(N)}$, but often is not FIPS 186-4 conformant. – fgrieu Jan 18 at 14:27
• @fgrieu I see, the boundary makes the allowance. Thanks, – kelalaka Jan 18 at 14:34