RSA Encryption: Theory and Python Implementation

What is RSA Encryption?

RSA is a public-key cryptosystem published in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman. In a public-key cryptosystem, the key used for encryption (public key) differs from the key used for decryption (private key), and security is maintained even when the public key is widely distributed.

The security of RSA is based on the fact that factoring large composite numbers is computationally intractable. It remains widely used today for key exchange, digital signatures, and other applications.

Mathematical Foundations

To understand RSA, several mathematical concepts need to be established.

Integer Factorization Problem

Multiplying two large primes \(p\) and \(q\) to compute \(N = p \times q\) is straightforward. However, recovering the original \(p\) and \(q\) from a given \(N\) (integer factorization) is extremely difficult with current computers when \(N\) is sufficiently large. This asymmetry in computational complexity forms the basis of RSA’s security.

Euler’s Totient Function

Euler’s totient function \(\varphi(N)\) represents the count of integers from \(1\) to \(N\) that are coprime to \(N\). When \(N = p \times q\) (where \(p\) and \(q\) are distinct primes), the following holds:

\[ \varphi(N) = (p - 1)(q - 1) \tag{1} \]

Euler’s Theorem

When \(\gcd(a, N) = 1\) (i.e., \(a\) and \(N\) are coprime), the following holds:

\[ a^{\varphi(N)} \equiv 1 \pmod{N} \tag{2} \]

This theorem is the core foundation for proving the correctness of RSA.

Modular Inverse

When integers \(e\) and \(\varphi(N)\) are coprime, there exists a unique integer \(d\) satisfying:

\[ e \cdot d \equiv 1 \pmod{\varphi(N)} \tag{3} \]

This \(d\) is called the modular inverse of \(e\) modulo \(\varphi(N)\), written as \(d \equiv e^{-1} \pmod{\varphi(N)}\). It can be efficiently computed using the extended Euclidean algorithm.

RSA Algorithm

Key Generation

Randomly select two large primes \(p\) and \(q\)
Compute \(N = p \times q\)
Compute \(\varphi(N) = (p - 1)(q - 1)\)
Choose an integer \(e\) such that \(1 < e < \varphi(N)\) and \(\gcd(e, \varphi(N)) = 1\) (commonly \(e = 65537\))
Compute \(d = e^{-1} \bmod \varphi(N)\) using the extended Euclidean algorithm
Public key: \((N, e)\), Private key: \((N, d)\)

Encryption

Represent the plaintext as an integer \(m\) (\(0 \le m < N\)) and encrypt using the public key \((N, e)\):

\[ c = m^e \bmod N \tag{4} \]

Decryption

Decrypt the ciphertext \(c\) using the private key \((N, d)\):

\[ m = c^d \bmod N \tag{5} \]

Proof of Correctness

We show that decryption correctly recovers the original plaintext. Consider the case where \(\gcd(m, N) = 1\).

From \(e \cdot d \equiv 1 \pmod{\varphi(N)}\), there exists an integer \(k\) such that \(e \cdot d = 1 + k \cdot \varphi(N)\).

\[ c^d = (m^e)^d = m^{ed} = m^{1 + k \cdot \varphi(N)} = m \cdot (m^{\varphi(N)})^k \tag{6} \]

By Euler’s theorem (equation \(\text{(2)}\)), \(m^{\varphi(N)} \equiv 1 \pmod{N}\), therefore:

\[ c^d \equiv m \cdot 1^k \equiv m \pmod{N} \tag{7} \]

This proves that decryption correctly recovers the original message.

Python Implementation

[WARNING] The following program is an educational implementation to understand the principles of RSA encryption. Do NOT use it for actual cryptographic communications.

import random
import math


def is_prime_miller_rabin(n, k=20):
    """Miller-Rabin primality test"""
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False
    # Decompose n-1 as 2^r * d
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True


def generate_prime(bits):
    """Generate a random prime of specified bit length"""
    while True:
        # Set MSB and LSB to 1 to ensure odd number of correct bit length
        p = random.getrandbits(bits) | (1 << (bits - 1)) | 1
        if is_prime_miller_rabin(p):
            return p


def extended_gcd(a, b):
    """Extended Euclidean algorithm: returns gcd, x, y such that ax + by = gcd"""
    if a == 0:
        return b, 0, 1
    gcd, x1, y1 = extended_gcd(b % a, a)
    return gcd, y1 - (b // a) * x1, x1


def mod_inverse(e, phi):
    """Compute modular inverse of e mod phi"""
    gcd, x, _ = extended_gcd(e % phi, phi)
    if gcd != 1:
        raise ValueError("Modular inverse does not exist")
    return x % phi


def generate_keypair(bits=512):
    """Generate RSA key pair"""
    p = generate_prime(bits)
    q = generate_prime(bits)
    n = p * q
    phi = (p - 1) * (q - 1)
    e = 65537
    d = mod_inverse(e, phi)
    return (n, e), (n, d)


def encrypt(message, public_key):
    """Encrypt a message using the public key"""
    n, e = public_key
    return pow(message, e, n)


def decrypt(ciphertext, private_key):
    """Decrypt a ciphertext using the private key"""
    n, d = private_key
    return pow(ciphertext, d, n)

Python’s built-in pow(base, exp, mod) function internally performs fast modular exponentiation equivalent to exponentiation by squaring (binary method).

Function Explanations

is_prime_miller_rabin: Performs probabilistic primality testing using the Miller-Rabin algorithm. With \(k = 20\) rounds, the probability of falsely identifying a composite as prime is below \(4^{-20} \approx 10^{-12}\).
generate_prime: Generates a random bit string of the specified length, sets the most significant and least significant bits to 1 (ensuring an odd number of the correct bit length), and repeats until the number passes the primality test.
extended_gcd: A recursive implementation of the extended Euclidean algorithm. Finds \(x\) and \(y\) satisfying \(ax + by = \gcd(a, b)\).
mod_inverse: Uses the extended Euclidean algorithm to compute \(d\) satisfying \(e \cdot d \equiv 1 \pmod{\varphi(N)}\).
generate_keypair: Combines the above functions to generate an RSA key pair (public key and private key). \(e = 65537\) (\(2^{16} + 1\)) is chosen because it has only two bits set in binary, making modular exponentiation faster.

Usage Example

# --- Encrypting and decrypting a number ---
public_key, private_key = generate_keypair(bits=512)

message = 12345
ciphertext = encrypt(message, public_key)
decrypted = decrypt(ciphertext, private_key)
print(f"Original:  {message}")
print(f"Encrypted: {ciphertext}")
print(f"Decrypted: {decrypted}")
assert message == decrypted

# --- Encrypting and decrypting a string ---
text = "Hello RSA"
# Convert string to bytes, then interpret as an integer
m = int.from_bytes(text.encode(), "big")
c = encrypt(m, public_key)
d = decrypt(c, private_key)
# Convert integer back to bytes, then decode to string
result = d.to_bytes((d.bit_length() + 7) // 8, "big").decode()
print(f"Original:  {text}")
print(f"Decrypted: {result}")

Security Considerations

This implementation is for educational purposes and should not be used in production for the following reasons:

Lack of padding: Real-world RSA uses padding schemes such as OAEP (Optimal Asymmetric Encryption Padding). Textbook RSA (without padding) is vulnerable to several attacks, including chosen-ciphertext attacks.
Key size: The default 512-bit key in this implementation is no longer considered secure. A minimum of 2048 bits is recommended for practical use.
Quantum computing threat: Shor’s algorithm can factor integers in polynomial time on a sufficiently large quantum computer. This means RSA may become insecure in the future, driving the transition toward Post-Quantum Cryptography.

Fast Modular Exponentiation by Squaring in Python - Explains the exponentiation by squaring algorithm used in RSA encryption and decryption.
Elliptic Curve ElGamal Encryption: Principles and Simplified Python Implementation - A public-key cryptosystem based on a different mathematical foundation (discrete logarithm problem on elliptic curves).
Diffie-Hellman Key Exchange Protocol: Theory and Python Implementation - A protocol that achieves secure key exchange using a different approach from RSA.
Security Certification Comparison: CISSP vs Registered Information Security Specialist - Compares security certifications whose exam scope includes cryptographic technologies.

Hash Generator (DevToolBox) - Hash generation tool supporting MD5 and SHA

References

Rivest, R. L., Shamir, A., & Adleman, L. (1978). “A method for obtaining digital signatures and public-key cryptosystems”. Communications of the ACM, 21(2), 120-126.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.