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.  The fastest known factoring algorithm takes something about like

time units to factor n.  (The size of the time unit depends on things like how fast the computer is!)   For the fastest single computer in 2001, it would probably take about 50 billion years to factor a number with 300 decimal digits. However, with networked computers, a large company might be able to improve this by a factor of as much as 1 million.

(More technically, it is estimated that factoring a number with 300 decimal digits would take about 10¹¹ MIPS-years. 1 MIPS-year is a million-instructions-per-second processor running for one year. A 1-GHz Pentium is about a 250-MIPS machine.)

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

time units.  This looks large, but it isn't really; for a 300-digit number this should only take a few minutes.  (Multiplying p and q together is even faster.)

Next Section