**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:**