Question

Say that two users use n₁, n₂ in the RSA and gcd(n₁, n₂) =/= 1. How can we break their system?

Answer 1

First we will understand RSA algorithm,As we know there are two type of cryptography:

i) Symmetric key cryptography: there is a single key for encryption and decryption)

ii) Asymmetric key cryptography: there are two different key for both the users (for encryption and decryption)

So one of the types of Asymmetric key cryptography is RSA:-

RSA algorithm works like:-

Select large prime numbers p, q

Compute

n = p * q

Φ = (p-1) * (q-1)

Select small odd integer k relatively prime to V

gcd (k, Φ) = 1

Compute d such that

(d* k) % Φ = (k * d ) % Φ = 1

Public key is (k, n)

Private key is (d, n)

For example if we have two large prime number as

P = 11, q = 29

n = p * q = 11 * 29 = 319

Φ = (p-1) * (q-1) = 10 * 28 = 280

Let , k = 3 (small odd integer relatively prime to 280

Now , we have

(d * k) % Φ = 1

(d * 3) % 280 = 1

d = 187

So, public key is ( 3, 319)

And private key is (187, 319)

Since, these are very small prime number, it was not tough. It’s very easy to multiply two primes together, but very difficult to find prime factors of a large number

RSA encryption is strong because factoring is a one-way problem. It’s very easy to multiply two primes together, but very difficult to find prime factors of a large number. That’s what the technology relies on. And the simplicity of RSA encryption made it very popular.

How can we break their system?

However, one technology can break RSA i. e Shor’s algorithm.

Shor’s algorithm can crack RSA

Shor’s algorithm doesn’t brute force the entire key by trying factors until it finds one, but instead uses the quantum computer to find the period of a function which contains the RSA key and classically computes the greatest common divisor.

But how does it really work?

It’s not about trying all prime factor possibilities simultaneously.

In (relatively) simple language: We can crack RSA if we have a fast way of finding the period of a known periodic function f(x) = m^x (mod N).

SHOR’S ALGORITHM:-

1. Pick a random number n1< n2 (which is given in question)

2. Compute gcd(n1, n2), the greatest common division of n1 and n2. This may be done using the Euclidean algorithm.

3. If gcd (n1, n2) ≠ 1, then this number is a nontrivial factor of n2, so we are done.

4. Otherwise , use the quantum period-finding subroutine (below) to find r, which denotes the period of the following function:

F(x) = n1^x mod n2.

This is the order r of n1 in the group (Zn2)* (where, the size of Zn2* is Φ(pq) = (p-1)(q-1) = n2-(p+q)+1), which is the smallest positive integer r for which f(x +r ) = f(x) , or f(x +r) = n1^(x+r) mod n2 ≡ n1^x mod n2. By Euler’s Theorum, r divides Φn2, where Φ denotes Euler’s totient function.

5. If r is odd , then go back to step 1.

6. If n1^r/2 ≡ -1 (mod n2), then go back to step1.

7. Otherwise, gcd(n1^r/2 + 1, n2) and gcd (n1^r/2 – 1, n2) are both nontrivial factor of n2, so we are done.

Note:-Two numbers are co-prime if they don’t have any common factors:

As given in question:

gcd(n1, n2) == 1

Hence, by using Shor’s algorithm we can break this system.