RSA Algorithm

The RSA algorithm is an asymmetric cryptography algorithm; this means that it uses a public key and a private key.

The RSA algorithm is named after those who invented it in 1978: Ron Rivest, Adi Shamir, and Leonard Adleman.

The following steps highlight how it works:

1. Generating the keys

1. Select two large prime numbers, x and y. The prime numbers need to be large so that they will be difficult for someone to figure out.


2. Calculate
   n = x x y.


3. Calculate
   the totient function: ϕ(n) = (x−1)(y−1).


4. Select an integer e, such that e is co-prime to
   ϕ(n) and 1< e < ϕ(n).
   The pair of numbers (n,e) makes up the public key.

5. Calculate d such
   that e.d=1 mod ϕ(n). The
   pair (n,d) makes up the private key.

2. Encryption

Given a plaintext P, represented as a number, the ciphertext C is calculated as:

C=P^e mod n.

3. Decryption

Using the private key (n,d), the plaintext can be found using:

P=C^d mod n.

RSA Algorithm Example

• Choose p = 3 and q = 11


• Compute
  n = p * q = 3 * 11 = 33


• Compute
  φ(n) = (p - 1) * (q - 1) = 2 * 10 = 20


• Choose e such that 1 < e < φ(n) and e and φ (n) are coprime. Let e = 7


• Compute a value for d such that (d * e) % φ(n) = 1.

One solution is d = 3    since [(3 * 7) % 20 = 1]

• Public key is (e, n) => (7, 33)


• Private key is (d, n) => (3, 33)


• The encryption of P = 2 is C = 2⁷ % 33 = 29


• The decryption of C = 29 is P = 29³ % 33 = 2