Skip to content

Same modulus - k approximation

Introduction

Find the private key of another user, if you have a private and a public key with the same modulus than him.

Prerequisites

  • pubKey1(n, e1) and privKey1(n, d1)
  • pubKey2(n, e2)

The goal is to find : privKey2(n, d2)

Maths

$$e * d \equiv 1 [\phi(n)]$$

So, with 𝑘 ∈ ℤ :

$$ e * d - 1 = k * \phi(n) $$

If you know k, you can calcultate phi(n) :

$$ \phi(n) = \frac{(e * d - 1)}{k} $$

To calculate k, you can approximate :

$$ \phi(n) \approx n $$ $$ (p - 1) * (q - 1) \approx p * q $$

So :

$$ k = \frac{(e * d - 1)}{\phi(n)} $$

$$ k \approx \frac{(e * d - 1)}{n} $$

Now, you can come back and calculate phi(n) :

$$ \phi(n) = \frac{(e * d - 1)}{k} $$

You can verify your calcul by using this formula :

$$ e * d - 1 = k * \phi(n) $$

If the result is not correct, you need to add 1 to k and retry it. It is because of the approximation.

Example

Source code :

e_1 = 0x10001
e_2 = 491
n = 211231128460542766584141422369
d_1 = 6043278848032645765057870973

tmp_k = (d_1 * e_1 - 1) // n
tmp_phi_n = (d_1 * e_1 - 1) // tmp_k

while tmp_phi_n * tmp_k != (e_1 * d_1) - 1:
    tmp_k += 1
    tmp_phi_n = (d_1 * e_1 - 1) // tmp_k

phi_n = tmp_phi_n
print("phi(n) :", phi_n)
d_2 = pow(e_2, -1, phi_n)
print("d_2 :", d_2)

Output :

phi(n) : 211231128460541602935785434644
d_2 : 84750574962783494456924094959