Question

In the RSA public-key encryption scheme, each user has a public key, e, and a private key, d. Suppose Alice leaks her private key. Rather than generating a new modulus, she decides to generate a new public key and a new private key. Is this safe? why or why not?

Answer 1

It is not safe. The procedure of the RSA encryption and decryption is as followings:

1. Choose two prime numbers p and q.

2. Computer n=p*q.

3. Choose a public key e, where e>1 and coprime to j(n) = (p-1)*(q-1).

4. Computer the private key. Where e*d = 1(mod j(n)).

5. The public key is (e, n) and the private key is (d, n).

6. The ciphertext is ci=mi^e (mod n).

7. The plaintext is mi=ci^d (mod n).

When we know the private key d₁, the public key e₁ and the other public e₂, we can computer the private key d₂ related to e₂ in the same modulus. First we assume that k=y j(n), where y is an integer. Since j(n) = (p-1)*(q-1), and the p, q are the prime number, so the result of j(n) is an even number. Hence, we can denote k=2^t *r, where r is odd number and t>=1.

Then we choose a random number g from the Zn*, where g^k≡ 1 (mod n). g^k/2 is result of g^k to the power of 1/2. That is to say g^k/2 is result of 1(mod n) to the power of 1/2. According to the Chinese remainder theorem, we know that there are 4 results for that calculation, two of which are +1 and -1. We denoted the other two as +x and –x. Hence, x satisfies: x≡ 1 mod p and

x≡ -1 mod q. so p=gcd (x-1, n), q= gcd(x+1, n).

After knowing the p and q, we can compute j(n), then d₂. And then we will know the ciphertext and plaintext. Thereby, it is not safe if Alice generate a new public and a new private key based on the old modulus.