# RSA

### Authors: Brain Hart '99 and Chris Savarese

### RSA

RSA is a form of *public
key encryption*. Its initialis stand for the three men who
invented it in 1977 at MIT: Ron Rivest, Adi Shamir, and Len Adleman.
In public key encryption, a key is divided into two halves, a public
and private half. The *public key* can
be distributed widely. It is used to encrypt messages which can then
only be decrypted using the *private key*.

The keys are constructed by using very large prime numbers. The
security behind RSA lies in the difficulty of factoring large numbers
into their primes. The process involves selecting two large (hundreds
of digits) prime numbers (*p* and *q*), and multiplying them together to get
the product, *n*. These numbers are
passed through a mathematical algorithm to determine the public key
*KU = {e,n}* and the private key *KR = {d,n}*, which are mathematically
related (the necessary equations are given at the bottom of the
page). It is extremely difficult to determine *e* and/or *d*
given *n*, thus the security of the
algorithm. Once the keys have been created a message can be encrypted
in blocks, and passed though the following equation:

(1) $C\; =\; Memod\; n$

Where C is the ciphertext, M is the plaintext, and e is the
recipient's public key. Similarly, the above message could be
decrypted by the following equation:

(2) $M\; =\; Cdmod\; n$

Where d is the recipient's private key.

For example: let's assume that our M is 19 (we will use smaller
numbers for simplicity, normally theses numbers would be MUCH
larger). We will use 7 as p and 17 as q. Thus, n = 7 * 17 = 119. Our e
is then calculated to be 5 and d is calculated to be 77. Thus our KU
is {5, 119} and our KR is {77, 119}. We can then pass the needed
values through equation (1) to compute C. In this case C is 66. We
could then decrypt C (66) to get back our original plain text. We pass
the needed values through equation (2) and get 19, our original
plaintext! Try it yourself with other numbers.

Note: To determine *e* and *d*, perform the following:

- Calculate
*f(n) = (p - 1)(q - 1)*
- Choose
*e* to be relatively prime
to *f(n)* and less than *f(n)*.
- Determine
*d* such that *de = 1 mod f(n)* and *d < f(n)*.

### For Further Study and Enjoyment

Information for this page was obtained from *Network and
Internetwork Security: Principles and Practice* by William
Stallings. Prentice Hall, 1995.