The RSA Algorithm

The RSA Algorithm#

The Ron Rivest, Adi Shamir, and Leonard Adleman (RSA) algorithm is a public-key cryptosystem that is widely used for secure data transmission. It is based on the principle that it is easy to multiply large prime numbers together, however it is extremely difficult to factor the product of two large prime numbers. The RSA algorithm is based on the mathematical properties of prime numbers and the Euler’s totient function.

Let’s break down the mathematics behind the RSA algorithm:

Algorithm 20 (RSA Key Generation)

Input:

  • Two distinct prime numbers \(p\) and \(q\).

Objective: Generate the public and private keys for RSA encryption.

Procedure:

  1. Choose Two Primes:

    • Select two distinct prime numbers \(p\) and \(q\).

  2. Compute \(n\):

    • Calculate the product of \(p\) and \(q\):

    \[ n = p \times q \]

  3. Compute the Totient Function \(\phi(n)\):

    • Calculate the totient function:

    \[ \phi(n) = (p-1) \times (q-1) \]

  4. Choose \(e\):

    • Select an integer \(e\) such that \(1 < e < \phi(n)\) and \(e\) is coprime with \(\phi(n)\). Typically, \(e = 65537\) is chosen.

  5. Compute \(d\):

    • Calculate the modular multiplicative inverse of \(e\) modulo \(\phi(n)\) to get \(d\):

    \[ d \equiv e^{-1} \mod \phi(n) \]

Output:

  • Public key \((e, n)\)

  • Private key \((d, n)\)

Explanation

In RSA key generation, two distinct prime numbers \(p\) and \(q\) are chosen to compute the modulus \(n\). The totient function \(\phi(n)\) is then calculated. An integer \(e\) is selected such that it is coprime with \(\phi(n)\), and the modular multiplicative inverse of \(e\) is computed to obtain \(d\). The public key is \((e, n)\), and the private key is \((d, n)\).

Algorithm 21 (RSA Encryption)

Input:

  • Plaintext message \(M\).

  • Public key \((e, n)\).

Objective: Encrypt the plaintext message using the RSA algorithm.

Procedure:

  1. Convert Plaintext to Integer:

    • Convert the plaintext message \(M\) into an integer \(m\) such that \(0 \leq m < n\).

  2. Compute Ciphertext:

    • Calculate the ciphertext \(c\) using the public key \((e, n)\):

    \[ c \equiv m^e \mod n \]

Output:

  • Ciphertext \(c\)

Explanation

To encrypt a plaintext message using RSA, the message is first converted into an integer \(m\) within the range \(0 \leq m < n\). The ciphertext \(c\) is then computed using the public key \((e, n)\) by raising \(m\) to the power of \(e\) and taking the result modulo \(n\).

Algorithm 22 (RSA Decryption)

Input:

  • Ciphertext \(c\).

  • Private key \((d, n)\).

Objective: Decrypt the ciphertext using the RSA algorithm.

Procedure:

  1. Compute Plaintext Integer:

    • Calculate the plaintext integer \(m\) from the ciphertext \(c\) using the private key \((d, n)\):

    \[ m \equiv c^d \mod n \]

  2. Convert Integer to Plaintext:

    • Convert the integer \(m\) back to the original plaintext message \(M\).

Output:

  • Plaintext message \(M\)

Explanation

To decrypt a ciphertext using RSA, the ciphertext \(c\) is raised to the power of \(d\) and taken modulo \(n\) using the private key \((d, n)\). The resulting integer \(m\) is then converted back to the original plaintext message \(M\).

RSA Algorithm Implementation#

Function Generation#

The Euler’s Totient function is calculated as follows:

  • If \(n\) is a prime number, then \(φ(n) = n - 1\)

  • If \(n\) is a product of two prime numbers, then \(φ(n) = (p - 1)(q - 1)\)

  • If \(n\) is a product of three prime numbers, then \(φ(n) = (p - 1)(q - 1)(r - 1)\)

  • And so on…

Hide code cell source 
import numpy as np
import sympy
from sympy import mod_inverse, isprime
import random
from math import gcd

def euler_phi(n):
    result = n
    p = 2
    while p * p <= n:
        if n % p == 0:
            while n % p == 0:
                n //= p
            result -= result // p
        p += 1
    if n > 1:
        result -= result // n
    return result

def power_mod(base, exp, mod):
    return pow(base, exp, mod)

We will define the following functions:

  • find_private_key: To find the private key \(d\) using the public key exponent \(e\) and the totient of \(n\)

  • encrypt_message: To encrypt the message using the public key exponent \(e\) and the modulus \(n\)

  • decrypt_message: To decrypt the message using the private key \(d\) and the modulus \(n\)

# def power_mod(base, exp, mod):
def find_private_key(e, totient_n):
    if gcd(e, totient_n) != 1:
        raise ValueError("e and totient_n are not coprime")
    return power_mod(e, -1, totient_n)

# def find_private_key(e, totient_n):
def encrypt_message(message, e, n):
    return power_mod(message, e, n)

# def encrypt_message(message, e, n):
def decrypt_message(ciphertext, d, n):
    return power_mod(ciphertext, d, n)

Define the variables#

Let’s define the variables for the RSA algorithm:

  • \(p\) and \(q\): Two large prime numbers

  • \(n\): The product of two large prime numbers

  • \(e\): The public key exponent

We will calculate the totient of \(n\) using the Euler’s Totient function.

p = 97
q = 101

Find the Euler’s Totient function#

Let’s define a function find_totient to calculate the Euler’s Totient function \(\phi(n)\) using the prime numbers \(p\) and \(q\).

%%time
n = p * q
e = 17
totient_n = euler_phi(n)
print("Totient of n:", totient_n)

Totient of n: 9600
CPU times: user 119 μs, sys: 0 ns, total: 119 μs
Wall time: 112 μs

Euler’s totient function, \(\phi(n)\), is crucial for generating the RSA keys. It is calculated using the formula:

\[ \phi(n) = (p - 1) \times (q - 1) \]

where \(p\) and \(q\) are prime numbers.

Example

Given:

\[\begin{split} p = 97 \\ q = 101 \end{split}\]

Calculate \(n\):

\[ n = p \times q = 97 \times 101 = 9797 \]

Calculate \(\phi(n)\):

\[ \phi(n) = (97 - 1) \times (101 - 1) = 96 \times 100 = 9600 \]

Find the private key \(d\)#

We will find the private key \(d\) using the public key exponent \(e\) and the totient of \(n\).

This is done by solving the equation \(d * e ≡ 1 (mod~φ(pq))\) where \(0 ≤ d ≤ pq\).

%%time
d = find_private_key(e, totient_n)
print("Private key d:", d)

Private key d: 3953
CPU times: user 90 μs, sys: 0 ns, total: 90 μs
Wall time: 85.4 μs

The private key \(d\) is the modular multiplicative inverse of \(e\) modulo \(\phi(n)\). This means we need to find \(d\) such that:

\[ d \equiv e^{-1} \mod \phi(n) \]

Example

\[ e = 17 \]

Use the Extended Euclidean Algorithm to find \(d\):

\[ d \equiv 17^{-1} \mod 9600 \]

Using the algorithm, we find:

\[ d = 5657 \]

Encrypt the message#

We will encrypt the message \(1234\) using the public key exponent \(e\) and the modulus \(n\).

The ciphertext is calculated as \(c = M^e~(mod~n)\).

%%time
message = 1234
ciphertext = encrypt_message(message, e, n)
print("Original message:", message)
print("Ciphertext:", ciphertext)

Original message: 1234
Ciphertext: 8897
CPU times: user 126 μs, sys: 0 ns, total: 126 μs
Wall time: 117 μs

To encrypt a message \(M\), convert it to an integer \(m\) such that \(0 \leq m < n\). Then, use the public key \((e, n)\) to compute the ciphertext \(c\):

\[ c \equiv m^e \mod n \]

Example

Suppose the plaintext message \(M\) is represented as the integer \(m = 1234\).

Given the public key:

\[ (e, n) = (17, 9797) \]

Calculate the ciphertext \(c\):

\[ c \equiv 1234^{17} \mod 9797 = 4362 \]

Decrypt the message#

We will decrypt the ciphertext using the private key \(d\) and the modulus \(n\).

The message is calculated as \(M = C^d~(mod~n)\).

The decrypted message should be the same as the original message.

%%time
decrypted_message = decrypt_message(ciphertext, d, n)
print("Decrypted message:", decrypted_message)
print(f"Is the decrypted message the same as the original message? {message == decrypted_message}")

Decrypted message: 1234
Is the decrypted message the same as the original message? True
CPU times: user 123 μs, sys: 0 ns, total: 123 μs
Wall time: 116 μs

To decrypt the ciphertext \(c\), use the private key \((d, n)\) to compute the plaintext integer \(m\):

\[ m \equiv c^d \mod n \]

Example

Given the private key:

\[ (d, n) = (5657, 9797) \]

Calculate the plaintext integer \(m\) from the ciphertext \(c\):

\[ m \equiv 4362^{5657} \mod 9797 = 1234 \]

Convert \(m\) back to the original plaintext message.

Putting it all together#

We will put all the steps together to show how the RSA algorithm works.

print(f"Our original value of n was: {n}")
print(f"Our original value of e was: {e}")
print(f"Our calculated value of totient_n was: {totient_n}")
print(f"Our original message was: {message}")
print(f"Our encrypted message was: {ciphertext}")
print(f"Our decrypted message was: {decrypted_message}")
print(f"Is the decrypted message the same as the original message? {message == decrypted_message}")

Our original value of n was: 9797
Our original value of e was: 17
Our calculated value of totient_n was: 9600
Our original message was: 1234
Our encrypted message was: 8897
Our decrypted message was: 1234
Is the decrypted message the same as the original message? True
Contents