Breaking RSA:

So why do we think RSA is secure?  As far as we know,the only way to break RSA is to find p and q by factoring n.

Hard Problem #2: Factorization

Given n, find primes p and q (if they exist), each not equal to 1, such that n = p q.

The fastest known factoring algorithm again takes something about like

time units to factor n.

On the other hand, finding p and q and multiplying them together is very fast.  Finding a number p which is (probably) prime again takes about

time units, and multiplying p and q together is even faster.

(Breaking RSA is about as hard as breaking Diffie-Hellman.)

Next Section