Lab 3 – RSA Encryption & Key Cracking

Overview

This lab explores the RSA cryptosystem across three scripts: key generation + sample encryption/decryption (Part 1), cracking a provided RSA instance by factoring the modulus (Part 2), and measuring how cracking time scales with prime bit length (Part 3). A probabilistic Miller–Rabin primality test (prime.py) underpins key generation. Below you'll find runnable concepts, sample output, and notes about performance.

Repository: GitHub – RSA-Key-Cracking

Parts Summary

python lab3-part1.py 64
public key is:  (n,e)
private key is: (n,d)
message:        b'test,message'
ciphered:       123456...
deciphered:     b'test,message'

python lab3-part2.py
p:  ...
q:  ...
lambda(n): ...
d: ...
decrypted message: b'YouDonePassed!!'

python lab3-part3.py
Testing 64-bit primes
   Test 1: 0.0021 s
   ...
Average for 64-bit
Time: 0.0020 s
...
Plot saved as rsa_crack_times.png

def gen_prime(nbits):
    while True:
        p = random.getrandbits(nbits)
        p |= 2**nbits | 1
        if miller_rabin(p):
            return p

📝 Example: RSA Encryption & Decryption Process

Using Python code from lab3-part1.py

Below is a walkthrough showing how the RSA encryption and decryption process works with the Python implementation:

# From lab3-part1.py
def make_key(bit_len):
    p = gen_prime(bit_len)  # Generate prime p
    q = gen_prime(bit_len)  # Generate prime q
    while q == p:
        q = gen_prime(bit_len)  # Ensure p ≠ q
    
    n = p * q
    lm = math.lcm(p-1, q-1)  # λ(n) = lcm(p-1, q-1)
    e = 65537                # Public exponent
    d = modinv(e, lm)        # Private exponent: d = e⁻¹ mod λ(n)
    
    return ((n,e), (n,d))    # public, private

# Example output:
public_key  = (3127, 65537)   # (n, e)
private_key = (3127, 2753)    # (n, d)

# From lab3-part1.py
msg = b'test,message'

def cipher(m, e, n):
    i = int.from_bytes(m)  # Convert bytes to integer
    return pow(i, e, n)    # C = M^e mod n

# Example:
message = b'test,message'
print("message:       ", message)
# Output: message:        b'test,message'

print("int from bytes:", int.from_bytes(message))
# Output: int from bytes: 35459967764488549030087532389

x = cipher(message, 65537, 3127)
print("ciphered:      ", x)
# Output: ciphered:       2391

# From lab3-part1.py
def dcipher(c, d, n):
    return pow(c, d, n)    # M = C^d mod n

# Example:
y = dcipher(2391, 2753, 3127)
print("deciphered:    ", y.to_bytes(12))
# Output: deciphered:     b'test,message'

$ python3 lab3-part1.py 64

public key is:  (3039956819131923800469303260782717053853, 65537)
private key is: (3039956819131923800469303260782717053853, 2834452675031667969382743586869863866433)

message:        b'test,message'
int from bytes: 35459967764488549030087532389

ciphered:       1315578006529763640141359009929019255795
deciphered:     b'test,message'

encrypted:      2597117990786094813922290830962878948057
decrypted:      b'test,message'

# From lab3-part1.py - Encrypt with PRIVATE key, decrypt with PUBLIC key
def cipher_d(m, d, n):
    i = int.from_bytes(m)
    return pow(i, d, n)    # Sign with private key

# Example:
ciph = cipher_d(b'test,message', 2753, 3127)
print("encrypted:     ", ciph)
# Output: encrypted:      2597

# Verify with public key
dciph = dcipher(2597, 65537, 3127)
print("decrypted:     ", dciph.to_bytes(12))
# Output: decrypted:      b'test,message'

💡 Key Points:

• Public key (n, e) encrypts messages → only private key (n, d) can decrypt
• Private key (n, d) signs messages → public key (n, e) verifies authenticity
• All operations use modular exponentiation: pow(base, exponent, modulus)
• λ(n) = lcm(p−1, q−1) is used instead of φ(n) for better security

Core RSA Functions (Reference)

The lab uses raw RSA without padding. Below are the core encryption/decryption operations from the Python implementation. Production systems use larger keys and padding schemes (e.g., OAEP) for security.

# Encryption: Convert message bytes to integer, then encrypt
def cipher(m_bytes, e, n):
    i = int.from_bytes(m_bytes)  # Message as integer
    return pow(i, e, n)          # C = M^e mod n

# Decryption: Decrypt ciphertext, return integer
def dcipher(c, d, n):
    return pow(c, d, n)          # M = C^d mod n

# Digital Signature: Sign with private key
def cipher_d(m_bytes, d, n):
    i = int.from_bytes(m_bytes)
    return pow(i, d, n)          # S = M^d mod n

# Helper: Modular multiplicative inverse
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        return None              # No inverse exists
    return x % m

# Helper: Extended Euclidean Algorithm
def egcd(a, b):
    x, y, u, v = 0, 1, 1, 0
    while a != 0:
        q, r = b // a, b % a
        m, n = x - u * q, y - v * q
        b, a, x, y, u, v = a, r, u, v, m, n
    return b, x, y

RSA Flow: Key generation selects primes p, q → n = p×q → λ(n) = lcm(p−1, q−1) → choose e (typically 65537) → compute d = e⁻¹ mod λ(n).
Encryption: C = M^e mod n  |  Decryption: M = C^d mod n

How to Run Locally

Requirements: Python 3.9+, modules: sympy, matplotlib. Install with:

pip install sympy matplotlib

Conceptual Recap

• Key Generation: pick primes p,q → n=pq → λ(n)=lcm(p-1,q-1) → choose e (65537) → d= e^-1 mod λ(n).
• Encrypt: C = M^e mod n.
• Decrypt: M = C^d mod n.
• Cracking (simplified): factor n ⇒ get p,q ⇒ derive d ⇒ decrypt.
• Security: relies on difficulty of factoring large n.

Limitations & Extensions

• Uses sympy.primefactors; real attacks use advanced algorithms (e.g., Quadratic Sieve, Number Field Sieve).
• No padding (e.g., OAEP); raw RSA is insecure for real messages.
• No side-channel considerations.
• Could extend Part 3 to log data to CSV and fit growth curves.