RSA Background:

The RSA cryptosystem was invented in 1978 by Ron Rivest, Adi Shamir, and Len Adelman. The purpose of the RSA cryptosystem is to allow users to quickly encrypt and decrypt information with the aid of a computer while supplying a sufficient amount of security to the message. RSA is related to the Diffie and Hellman algorithm for public key encryption, which is summarized as follows:

Given a large () prime p, a message X, which is an integer less than p, and an integer a such that , define Y, the encrypted message as follows:

[1.1]

Then the decrypted message X can be obtained from Y, a, and p.

[1.2]

Using Diffie and Hellman, with a computer, encrypting X to get Y is quick. However, there is no general algorithm yet available for decoding Y to find X in any reasonable timeframe (< 100 years) without knowing a and p.

While the RSA cryptosystem uses a modified form of this basic algorithm to encrypt messages, the user needs to be able to decode incoming messages quickly for RSA to be considered a viable and useful security solution. To accomplish this, each RSA user has his/her public encryption key and secret decrypting key . Here, r is a composite of two carefully selected primes, p and q.

[1.3]

[1.4]

is Euler’s totient function, the number of numbers between 0 and r that are relatively prime to r.

The keys must be selected such that each is relatively prime to and the keys must be inverses modulo . This allows encryption and decryption of the message X, again as an integer with the above constraints, in the following way:

Encryption:

[1.5] ,

where is the encrypted message.

Decryption:

[1.6] , because

This congruence is true because and are inverses modulo , which by definition means that . Number theory tells us that

,

provided that X and r are relatively prime. Multiplying by X gives us

.

Hence , as desired.

To “break” RSA, one must be able to factor r into its primes. Factoring r allows one to find , which leads to finding , and decrypting the message, thereby violating the security of the encryption. Therefore, we must be sure to choose p and q in such a way that their product is not easily factorable. The easiest way for us to do this is to choose large primes for p and q, as difficulty in factoring grows rapidly with respect to the number of digits in the integer.

Sources:

Man Young Rhee, Cryptography and Secure Communications. McGraw-Hill

Book Co., Singapore, 1994.