The following 617-digit number (all 617 digits starting with and ending in ) is a product of two prime numbers and . How long will it take to find these two prime factors?

25195908475657893494027183240048398571429282126204

03202777713783604366202070759555626401852588078440

69182906412495150821892985591491761845028084891200

72844992687392807287776735971418347270261896375014

97182469116507761337985909570009733045974880842840

17974291006424586918171951187461215151726546322822

16869987549182422433637259085141865462043576798423

38718477444792073993423658482382428119816381501067

48104516603773060562016196762561338441436038339044

14952634432190114657544454178424020924616515723350

77870774981712577246796292638635637328991215483143

81678998850404453640235273819513786365643912120103

97122822120720357

The above number is a challenge to the public to come up with the two prime factors (see RSA challenge number and RSA factoring challenge). No one has been able to successfully meet the challenge. In fact, even with the current state of the art in supercomputing technology, it could take millions of years to factor a number as big as the one shown above. According to the organization that posed the challenge (RSA Laboratories), barring fundamental algorithmic or computing advances, the above number or other similarly sized number is expected to stay unfactored in the decades to come.

RSA is a cryptographic algorithm that is used to send and receive sensitive data. The name RSA stands for the last names of the creators of the algorithm – Ron Rivest, Adi Shamir and Leonard Adleman.

The algorithm uses a pair of large prime numbers in setting up a public key to encrypt and a private key to decrypt data. The public key is known to the public and includes a large integer (such as the one indicated at the beginning of the post) that is a product of two prime numbers and . The private key is computed using two prime factors and and is needed to decrypt the messages encrypted by the public key. The RSA scheme is built on the monumental difficulty in factoring large numbers. Barring some system vulnerability that hackers can exploit, it is all but certain that messages sent via RSA scheme can only be read by the intended party – the legitimate party that possesses the private key.

This post gives an illustration of how the RSA algorithm work using much smaller prime numbers. The RSA algorithm is also an application of the Fermat’s Little Theorem (see the post Fermat’s Little Theorem and RSA Algorithm).

The example given below makes use of congruence arithmetic. If , and are integers, the symbol means that the difference is divisible by (we say that is congruent to modulo ). For example, (in terms of clock arithmetic, 6 hours after 9 o’clock is not 15th o’clock but is 3 o’clock). For more information about congruence relation and congruence arithmetic, see this blog post or this Wikipedia entry.

___________________________________________________________________________________________________________________

**Example of RSA**

The example uses small prime numbers to make the illustration easy to follow. The example has the following steps:

- Andy creates a public key and a private key. He gives the public key to Becky and keeps the private key to himself.
- Becky then uses the public key to encrypt a message and sends it to Andy.
- Andy then uses the private key to decrypt the message received from Becky.

______________________________________________________

**Step 1 – Generating the Public Key and Private Key**

Choose two prime numbers and . In this example, let and . Then calculate the following numbers:

Choose an integer with such that and are relatively prime (meaning the only common divisor is 1). For this example, Andy chooses .

The public key consists of and , which Andy passes to Becky. Becky will use the public key to encrypt any message that she wishes to send to Andy (see Step 2 below). The number is the encryption key.

Andy can also make the public key known to any one from whom Andy wishes to receive message.

The private key is the number such that:

In this example, find the number such that

Specifically, we need to find the number that satisfies for some integer . When , we have a solution .

The number will be used to decrypt any message that will come from Becky. So Andy needs to keep private and secure.

______________________________________________________

**Step 2 – Encrypting a Message using the Public Key**

Becky wishes to send a message (in text) to Andy. Becky first translates into an integer (e.g. using a mapping to translate strings of letters and other symbols into blocks of numbers). This same mapping will be used by Andy to translate the decrypted message back to the text message . Note that the mapping for translating letters into numbers and back is not part of the RSA algorithm, which only encrypts and decrypts numeric messages.

Suppose the message is . The following is the encryption function – the function that generates the encrypted message

In this example, the encryption function is:

The encrypted message is the number is the remainder that is obtained when is divided by . This can be done in a process using congruence arithemtic that can be described as “divide and conquer”. The process is to reduce the exponent by half in each step of the step by step approach.

First, note that since is the remainder when is divided by (i.e. division algorithm). Then use the division algorithm successively as shown in the following:

In the “divide and conquer” approach, a congruence calculation in done in each step to reduce the exponent (applying the division algorithm). For example, to go from the first line to the second line, the remainder is obtained when is divided by . The number is the remainder when is divided by .

______________________________________________________

**Step 3 – Decrypting the Message Receiving from Becky**

Andy receives the encrypted message . To decrypt , the private key that is calculated in Step 1 above is used. The following is the decryption function – the function that generates the decrypted message .

In particular, Any needs to find the number that satisfies the following:

The decrypted message is the remainder when is divided by . A “divide and conquer” approach can be used.

We just illustrates how Andy decrypts Becky’s message of to find the original message of . The calculation is tedious if done manually but is simple for a computer.

___________________________________________________________________________________________________________________

**Summary**

We summarize the main steps in the above example.

______________________________________________________

**Step 1 – Generating the Public Key and Private Key**

Choose two prime numbers and . Then calculate the following numbers:

Choose an integer with such that and are relatively prime (meaning the only common divisor is 1).

The public key consists of and , which Andy passes to Becky. Becky will use the public key to encrypt any message that she wishes to send to Andy. The number is the encryption key.

Andy can also make the public key known to any one from whom Andy wishes to receive message.

The private key is the number such that:

The number is the decryption key and will be used to decrypt any message that will come from Becky. So Andy needs to keep private and secure.

______________________________________________________

**Step 2 – Encrypting a Message using the Public Key**

Becky wishes to send a message (in text) to Andy. Becky first translates into an integer (e.g. using a mapping to translate strings of letters and other symbols into blocks of numbers). This same mapping will be used by Andy to translate the decrypted message back to the text message .

The following is the encryption function – the function that generates the encrypted message .

The encrypted message that Becky will send to Andy is .

______________________________________________________

**Step 3 – Decrypting the Message Receiving from Becky**

Andy receives the encrypted message . To decrypt , the private key that is calculated in Step 1 above is used. The following is the decryption function – the function that generates the decrypted message .

The original message sent from Becky is .

Note that . Thus the function is the inverse function of (and vice versa). This fact can be established by using Fermat’s Little Theorem (see the post Fermat’s Little Theorem and RSA Algorithm).

___________________________________________________________________________________________________________________

**RSA Exercise**

Suppose you are Andy. You set and . You also choose .

You give the public key and .

Becky sends you an encrypted message .

What is the original message?

**More Information about RSA**

A lot of information about RSA can be found online. Here’s a few useful links for introductory information.

A useful note about cryptography

A poster on primes from Clay Math Institute

Revised August 9, 2014.