The RSA Algorithm

Author: Dan Wright
Last Revised: April 6^th, 2007

Pictured from left to right: Adi Shamir, Ron Rivest and Len Adleman

The RSA algorithm is used for both public key encryption and digital signatures. It is the most widely used public key encryption algorithm. The basis of the security of the RSA algorithm is that it is mathematically infeasible to factor sufficiently large integers. The RSA algorithm is believed to be secure if its keys have a length of at least 1024-bits.

1 History
2 Technical
3 A simple example
4 Digital signatures

4.1 Digital signing
4.2 Signature verification

5 References
6 External links

History

The RSA algorithm was first published in the paper A Method for Obtaining Digital Signatures and Public-Key Cryptosystems in 1977 by Ron Rivest, Adi Shamir and Len Adleman. It is named after the initials of their surnames. The paper was published in the September 1977 issue of The Scientific American. The authors offered to send their full report to anyone who sent them a self-addressed stamped envelope. The NSA did not like the idea of distributing the crytography source code internationally and requested that it be stopped. However the distribution continued when the NSA failed to provide a legal basis for their request. The algorithm was published in The Communications of the ACM the following year.

Technical

Key Generation Algorithm

1. Choose two very large random prime integers:
p and q
2. Compute n and φ(n):
n = pq and φ(n) = (p-1)(q-1)
3. Choose an integer e, 1 < e < φ(n) such that:
gcd(e, φ(n)) = 1(where gcd means greatest common denominator)
4. Compute d, 1 < d < φ(n) such that:
ed ≡ 1 (mod φ(n))

the public key is (n, e) and the private key is (n, d)
the values of p, q and φ(n) are private
e is the public or encryption exponent
d is the private or decryption exponent

Encryption

The cyphertext C is found by the equation 'C = M^e mod n' where M is the original message.

Decryption

The message M can be found form the cyphertext C by the equation 'M = C^d mod n'.

A simple example

This is an extremely simple example and would not be secure using primes so small, normally the primes p and q would be much larger.

Select the prime integers q=11, q=3.
n=pq=33; φ(n)=(p-1)(q-1)=20
Choose e=3

Check gcd(3,20)=1

Compute d=7

(3)d ≡ 1 (mod 20)

Therefore the public key is (n, e) = (33, 3) and the private key is (n, d) = (33, 7).

Now say we wanted to encrypt the message M=7

C = M^e mod n
C = 7³ mod 33
C = 343 mod 33
C = 13

So now the cyphertext C has been found. The decryption of C is performed as follows.

M' = C^d mod n
M' = 13⁷ mod 33
M' = 62,748,517 mod 33
M' = 7

As you can see after the message has been encrypted and decrypted the final message M' is the same as the original message M. A more practical way to use the algorithm is to convert the message to hexadecimal and perform the encryption and decryption steps on each octet individually.

Digital signatures

Digital signing

In order to sign a message the sender does the following:

Produces a hash value of the message
Uses his/her private key (n, d) to compute the signature

S = M^d mod n

Sends the signature S to the recipient

Signature verification

The recipient does the following in order to verify the message:

Uses the senders public key (n, e) to compute the hash value

V = S^e mod n

Extracts the hash value from the message
If both hash values are identical then the signature is valid

References

R. Rivest, A. Shamir, L. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, Vol. 21 (2), pp.120-126. 1978. Previously released as an MIT "Technical Memo" in April 1977. Initial publication of the RSA scheme.