As most of us know, RSA is an algorithm used for many of today’s security applications. It was invented by three computer scientists at MIT, Ron Rivest, Adi Shamir, and Leonard Adleman. The process involves:

choosing two large distinct primes p and q, with n = p*q.

Then choose an e such that e is 1 < e < (p-1)(q-1) and has no common factors with (p-1)(q-1). This e is the public key.

Finally compute d to satisfy Compute d to satisfy the congruence relation

This d is the private key.

For efficiency a different form of the private key d can be stored where p and q are the primes from key generation:

and

Using this algorithm we can encrypt messages by computing

Where m is the message, and c is the encrypted message.

We can decrypt the message by computing

This system is very effective, as long as the private key is kept private, along with the primes p and q. However, What if we can get p and q directly from n?

This is a question that has been posed by RSA laboratories, and as a result they started the RSA Challenge, which awarded computer scientists for finding the prime factorization of various RSA numbers. Their aim was to see which numbers took the most difficulty to factor, as these numbers would be harder for hackers to crack. The process in which they factored these numbers involved heavy matrix factorizations. Many of these factorizations of larger numbers took a very long time to calculate, with very dense matrices.

For example, the latest RSA number that was factored was RSA-640 which took approximately 30 2.2GHz-Opteron-CPU years according to the submitters, over five months of calendar time. Although the RSA Challenges have been discontinued, there are many numbers that have yet to have been factored.

Sources:

http://en.wikipedia.org/wiki/RSA

http://www.rsa.com/rsalabs/node.asp?id=2092

http://en.wikipedia.org/wiki/RSA_Factoring_Challenge