12
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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 ∈ ℤ$ $\endgroup$ – user86295 Jan 17 at 17:53
19
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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) $\endgroup$ – Hagen von Eitzen Jan 18 at 12:20
10
$\begingroup$

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)
$\endgroup$
4
  • $\begingroup$ 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$. $\endgroup$ – fgrieu Jan 18 at 11:17
  • $\begingroup$ @fgrieu both FIPS 186-4 and PKCS#1 v2.2 only mentions $\lambda$. $\endgroup$ – kelalaka Jan 18 at 11:28
  • $\begingroup$ @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. $\endgroup$ – fgrieu Jan 18 at 14:27
  • 1
    $\begingroup$ @fgrieu I see, the boundary makes the allowance. Thanks, $\endgroup$ – kelalaka Jan 18 at 14:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.