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