RSA Encryption

The world's most common , named after its founders: Rivest, Shamir, and Adleman.

Where it's used

RSA is found anywhere an protocol is needed, such as securing HTTPS connections via TLS/SSL certificates, authenticating SSH sessions, and encrypting email and software signatures through PGP/GPG.

Why it's used

Asymmetric encryption schemes like RSA involve a which anyone can see and use, and a only the holder can use. The inherent asymmetry eliminates the need to create a in advance. The security of RSA relies on the extreme difficulty of factoring the product of two large 

 1import random
 2

▼3def is_probably_prime(n, k=20):
 4    """Miller-Rabin primality test."""
▼5    if n < 2:
 6        return False
▼7    if n == 2 or n == 3:
 8        return True
▼9    if n % 2 == 0:
 10        return False
 11

 12    # Write n-1 as 2^r * d
 13    r, d = 0, n - 1
▼14    while d % 2 == 0:
 15        r += 1
 16        d //= 2
 17

 18    # Witness loop
▼19    for _ in range(k):
 20        a = random.randrange(2, n - 1)
 21        x = pow(a, d, n)  # a^d mod n
 22

▼23        if x == 1 or x == n - 1:
 24            continue
 25

▼26        for _ in range(r - 1):
 27            x = pow(x, 2, n)
▼28            if x == n - 1:
 29                break
▼30        else:
 31            return False
 32    return True
 33

▼34def generate_prime(bits=512):
 35    """Generate a random prime of given bit length."""
▼36    while True:
 37        # Generate random odd number of correct bit length
 38        n = random.getrandbits(bits)
 39        n |= (1 << bits - 1) | 1  # Set MSB and LSB
▼40        if is_probably_prime(n):
 41            return n
 42

 43p = generate_prime(512)
 44q = generate_prime(512)
 45print(f"p = {p}")
 46print(f"q = {q}")
Step 1 of 6

1. Generate Large Primes

Select two large random p and q. In practice these are 1024+ bits. We use a to probabilistically verify p and q are prime.

Create Public and Private Keys

  1. 1.Generate large primes p and q
  2. 2.Compute n = p × q and φ(n) = (p-1)(q-1)
  3. 3.Choose public exponent e = 65537
  4. 4.Derive private key d = e⁻¹ mod φ(n)