Question

Suppose we have an oracle (as in Turing Machine terminology, not the company) which can 4. tell us the factors of any composite number. Given our discussion on RSA, what advantage would such an oracle give to the code breaker? Explain how it would be used to compromise the RSA based public key authentication used in ssh.

Answer 1

The security of RSA algorithm surely lies on the difficulty to factorize large composite numbers, for this reason the robustness of the RSA algorithm highly depends on the length of the key. If Oracle can tell us the factors of any composite number and each composite number can be expressed as a unique product of primes. Then the code breaker can factorize the public key and discover prime numbers, through which he/she can find the private key.

Mathematical Explanation:

Let us assume n be the product of two prime numbers p and q, and e be the public exponent.
The least common multiple (L) of p-1 and q-1 is calculated as

L = LCM (p-1, q-1).

Then d for the RSA cryptosystem is some integer solution to the congruence

de ≡ 1 mod L.

The value of d can be obtained as inverse of e modulo L. If Oracle can tell us the factors of any composite number then the code breaker can factorize the public key and discover prime numbers,

Where m lies between 0 and n-1,

and m ≡ (m^e)^d mod n .

we know that n be the product of two prime numbers p and q

Thus for all m,

m ≡ (m^e)^d mod p

and

m ≡ (m^e)^d mod q .