The RSA Algorithm

Author: Dan Wright
Last Revised: April 6th, 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.



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.


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 cyphertext C is found by the equation 'C = Me mod n' where M is the original message.


The message M can be found form the cyphertext C by the equation 'M = Cd 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.

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

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

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:

Signature verification

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


See also

External links