Translate

2015-02-15

RSA – don’t reuse your primes !




As you probably know, the main inputs to RSA algorithm are the following;

p = random_prime_1
q = random_prime_2
n = p.q

RSA is based on the fact it is easy (in term of computation effort) to multiply large integers but very hard to factorize them.
It is easy to compute n if p and q are given, but very hard (can’t be solved in polynomial time) to find p and q if n is given (and n is long enough, for example 1024 bits).

It is why, to simplify (because it is not exactly the fact, RSA algorithm is a bit more complicated and very well explained here http://www.di-mgt.com.au/rsa_alg.html) ; n can be considered as the public key; we consider it unbreakable if enough long, so we don’t fear to publish it.

All that is beautiful and true if the “random” primes used are really random (true randomness is not an easy task), if *by mistake* primes are reused to build different n’s, a weird vulnerability appears, allowing to easily crack the key and discover p and q.

What have in common two numbers that uses same p or same q? The answer is: a greatest common divisor different from 1 (and equals p or q).

If so, the operation than an attacker has to do is to calculate the greatest common divisor (operation considered as easy in term of computation effort) between the different public keys, if for some of the pairs the result is different from 1 it means that the GCD found is as prime used in both public keys, meaning that both messages using these public keys can be cracked.

Indeed;

gcd_n1_n2 = gcd(n1,n2)

If (gcd_n1_n2 !=1)
               p = gcd_n1_n2
               q = n1 / p

You have p and q, now we understand easily how randomness is crucial in cryptography, even RSA is very vulnerable to lack of real randomness…

No comments: