RSA — PKCS#1 v1.5 Padding: The Bleichenbacher Oracle

# io.thecodeforge: RSA Mathematical Foundations
# These are the building blocks — understand these before touching RSA code.

import random
from math import gcd

# ─────────────────────────────────────────────────────────────
# 1. MILLER-RABIN PRIMALITY TEST
# Probabilistic test: if it says 'composite', it's definitely composite.
# If it says 'probably prime', the error probability is < 4^(-k).
# With k=20 rounds, error probability < 10^(-12). Good enough.
# ─────────────────────────────────────────────────────────────

def is_prime_miller_rabin(n, k=20):
    if n < 2: return False
    if n == 2 or n == 3: return True
    if n % 2 == 0: return False

    # Write n-1 = 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  # definitely composite

    return True  # probably prime (error < 4^(-k))

# ─────────────────────────────────────────────────────────────
# 2. EULER'S TOTIENT FUNCTION
# φ(n) = count of integers from 1 to n that are coprime to n.
# For prime p: φ(p) = p-1
# For n = p*q (two primes): φ(n) = (p-1)(q-1)
# ─────────────────────────────────────────────────────────────

def euler_totient_two_primes(p, q):
    """Compute φ(n) when n = p * q and p, q are prime."""
    return (p - 1) * (q - 1)

def euler_totient_naive(n):
    """Compute φ(n) by brute force — for educational purposes only."""
    count = 0
    for i in range(1, n):
        if gcd(i, n) == 1:
            count += 1
    return count

# Verify: φ(61*53) = φ(3233) = 60*52 = 3120
assert euler_totient_two_primes(61, 53) == 3120
assert euler_totient_naive(3233) == 3120

# ─────────────────────────────────────────────────────────────
# 3. EXTENDED EUCLIDEAN ALGORITHM
# Finds gcd(a,b) AND the coefficients x,y such that ax + by = gcd(a,b).
# Used to compute d = e^(-1) mod φ(n) — the modular inverse.
# ─────────────────────────────────────────────────────────────

def extended_gcd(a, b):
    """Returns (gcd, x, y) such that a*x + b*y = gcd(a, b)."""
    if b == 0:
        return a, 1, 0
    g, x, y = extended_gcd(b, a % b)
    return g, y, x - (a // b) * y

def mod_inverse(e, phi):
    """Compute d = e^(-1) mod phi using extended Euclidean algorithm."""
    g, d, _ = extended_gcd(e, phi)
    if g != 1:
        raise ValueError(f"Modular inverse does not exist: gcd({e}, {phi}) = {g}")
    return d % phi

# Verify: 17^(-1) mod 3120 = 2753
assert mod_inverse(17, 3120) == 2753
# Verify: 17 * 2753 mod 3120 = 1 (the inverse property)
assert (17 * 2753) % 3120 == 1

# ─────────────────────────────────────────────────────────────
# 4. MODULAR EXPONENTIATION
# Python's pow(b, e, m) uses square-and-multiply: O(log e) multiplications.
# This is why RSA is fast despite enormous exponents.
# ─────────────────────────────────────────────────────────────

# Demo: 2^1000 mod 13 — computed instantly
result = pow(2, 1000, 13)
print(f'2^1000 mod 13 = {result}')  # 3

# Without modular exponentiation, 2^1000 is a 302-digit number.
# With pow(b, e, m), it's computed in ~10 multiplications.

print('\n=== All mathematical foundations verified ===')
print(f'Miller-Rabin: 3233 is prime? {is_prime_miller_rabin(3233)} (False — it is 61*53)')
print(f'Miller-Rabin: 61 is prime? {is_prime_miller_rabin(61)} (True)')
print(f'φ(3233) = {euler_totient_two_primes(61, 53)}')
print(f'17^(-1) mod 3120 = {mod_inverse(17, 3120)}')
print(f'65^2753 mod 3233 = {pow(65, 2753, 3233)} (decryption of ciphertext 2790)')

# io.thecodeforge: RSA Key Generation
# Generates RSA key pair from first principles.
# For production use: from cryptography.hazmat.primitives.asymmetric import rsa

import random
from math import gcd

def is_prime_miller_rabin(n, k=20):
    if n < 2: return False
    if n == 2 or n == 3: return True
    if n % 2 == 0: return False
    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=512):
    """Generate a random prime of the specified bit length."""
    while True:
        # Ensure the number has exactly 'bits' bits (set MSB and LSB)
        p = random.getrandbits(bits)
        p |= (1 << bits - 1) | 1  # set MSB (correct bit length) and LSB (odd)
        if is_prime_miller_rabin(p):
            return p

def extended_gcd(a, b):
    if b == 0: return a, 1, 0
    g, x, y = extended_gcd(b, a % b)
    return g, y, x - (a // b) * y

def mod_inverse(e, phi):
    g, d, _ = extended_gcd(e, phi)
    if g != 1:
        raise ValueError(f"Modular inverse does not exist: gcd({e}, {phi}) = {g}")
    return d % phi

def rsa_keygen(bits=1024):
    """
    Generate RSA key pair.
    
    Args:
        bits: Total key size in bits. Each prime is bits/2 bits.
              1024-bit total = two 512-bit primes (educational only).
              2048-bit total = two 1024-bit primes (production minimum).
              4096-bit total = two 2048-bit primes (conservative).
    
    Returns:
        (public_key, private_key) where each is a tuple (n, exponent).
    """
    print(f'Generating {bits}-bit RSA key pair...')
    print(f'Each prime will be {bits // 2} bits.')

    # Step 1: Generate two distinct large primes
    p = generate_prime(bits // 2)
    q = generate_prime(bits // 2)
    while q == p:  # ensure p ≠ q
        q = generate_prime(bits // 2)

    print(f'Prime p: {len(bin(p))-2} bits')
    print(f'Prime q: {len(bin(q))-2} bits')

    # Step 2: Compute modulus n = p * q
    n = p * q
    print(f'Modulus n: {len(bin(n))-2} bits')

    # Step 3: Compute Euler's totient φ(n) = (p-1)(q-1)
    phi = (p - 1) * (q - 1)

    # Step 4: Choose public exponent e
    # 65537 = 2^16 + 1 = 0x10001 (binary: 10000000000000001)
    # - Prime (so gcd(e, φ(n)) = 1 for almost all φ(n))
    # - Binary weight 2 (only two 1-bits → fast exponentiation: 16 squarings + 1 multiply)
    # - Large enough to avoid small-exponent attacks (e=3 is vulnerable)
    # - Small enough that encryption is fast
    e = 65537

    # Verify gcd(e, φ(n)) = 1 (required for modular inverse to exist)
    if gcd(e, phi) != 1:
        # Extremely rare — regenerate primes
        return rsa_keygen(bits)

    # Step 5: Compute private exponent d = e^(-1) mod φ(n)
    d = mod_inverse(e, phi)

    # Step 6: Return key pair
    public_key = (n, e)
    private_key = (n, d)

    print(f'Public key:  (n={len(str(n))} digits, e={e})')
    print(f'Private key: (n=..., d={len(str(d))} digits)')

    return public_key, private_key

# ─────────────────────────────────────────────────────────────
# DEMO: Generate a small key pair (educational — NOT secure)
# ─────────────────────────────────────────────────────────────

# Small primes for demonstration (DO NOT USE IN PRODUCTION)
p, q = 61, 53
n = p * q          # 3233
phi = (p - 1) * (q - 1)  # 3120
e = 65537 % phi    # 65537 mod 3120 ≠ 1 but gcd(e,phi) must be 1. Use e=17 instead.
e = 17
assert gcd(e, phi) == 1, 'e must be coprime to φ(n)'
d = mod_inverse(e, phi)

print('\n=== Textbook RSA Example (p=61, q=53) ===')
print(f'n = {n}, φ(n) = {phi}')
print(f'Public key:  (n={n}, e={e})')
print(f'Private key: (n={n}, d={d})')
print(f'Verify: e * d mod φ(n) = {(e * d) % phi} (should be 1)')

# io.thecodeforge: RSA Encryption and Decryption
# Textbook implementation for understanding. Production code uses OAEP padding.

from math import gcd

def extended_gcd(a, b):
    if b == 0: return a, 1, 0
    g, x, y = extended_gcd(b, a % b)
    return g, y, x - (a // b) * y

def mod_inverse(e, phi):
    g, d, _ = extended_gcd(e, phi)
    if g != 1: raise ValueError('Modular inverse does not exist')
    return d % phi

def rsa_encrypt(message_int, public_key):
    """Encrypt an integer: c = m^e mod n"""
    n, e = public_key
    if message_int >= n:
        raise ValueError(f'Message ({message_int}) must be smaller than n ({n})')
    return pow(message_int, e, n)

def rsa_decrypt(ciphertext, private_key):
    """Decrypt an integer: m = c^d mod n"""
    n, d = private_key
    return pow(ciphertext, d, n)

# ─────────────────────────────────────────────────────────────
# TEXTBOOK EXAMPLE: p=61, q=53
# ─────────────────────────────────────────────────────────────

p, q = 61, 53
n = p * q          # 3233
phi = (p - 1) * (q - 1)  # 3120
e = 17
d = mod_inverse(e, phi)  # 2753

public_key = (n, e)
private_key = (n, d)

# Encrypt the number 65 (ASCII 'A')
msg = 65
ciphertext = rsa_encrypt(msg, public_key)
plaintext = rsa_decrypt(ciphertext, private_key)

print('=== RSA Encryption/Decryption ===')
print(f'Message:    {msg}')
print(f'Encrypted:  {ciphertext}')
print(f'Decrypted:  {plaintext}')
print(f'Match:      {msg == plaintext}')
print()

# ─────────────────────────────────────────────────────────────
# STRING ENCRYPTION: Convert text to integers, encrypt each chunk
# In production, you'd use OAEP padding + hybrid encryption (RSA+AES)
# ─────────────────────────────────────────────────────────────

def text_to_int(text):
    """Convert string to integer via UTF-8 bytes."""
    return int.from_bytes(text.encode('utf-8'), 'big')

def int_to_text(number, length):
    """Convert integer back to string."""
    return number.to_bytes(length, 'big').decode('utf-8').strip('\x00')

message = 'Hi'
msg_int = text_to_int(message)
print(f'String "{message}" as integer: {msg_int}')
print(f'Integer smaller than n ({n})? {msg_int < n}')

# For this tiny n, only very short messages fit.
# In production with 2048-bit n, you can encrypt up to 256 bytes.
if msg_int < n:
    ct = rsa_encrypt(msg_int, public_key)
    pt_int = rsa_decrypt(ct, private_key)
    pt = int_to_text(pt_int, len(message.encode('utf-8')))
    print(f'Encrypted: {ct}')
    print(f'Decrypted: "{pt}"')
    print(f'Match: {message == pt}')
else:
    print(f'Message too large for this tiny key. Use larger primes.')

# ─────────────────────────────────────────────────────────────
# DETERMINISM PROBLEM: Same message always gives same ciphertext
# This is why textbook RSA is insecure — see padding section.
# ─────────────────────────────────────────────────────────────

print('\n=== Determinism Problem ===')
ct1 = rsa_encrypt(65, public_key)
ct2 = rsa_encrypt(65, public_key)
print(f'Encrypting 65 twice: {ct1} and {ct2}')
print(f'Same ciphertext? {ct1 == ct2} — YES, textbook RSA is deterministic')
print('This is why production RSA uses OAEP padding (adds randomness).')

# io.thecodeforge: Why e=65537 — Performance and Security

from math import gcd

def extended_gcd(a, b):
    if b == 0: return a, 1, 0
    g, x, y = extended_gcd(b, a % b)
    return g, y, x - (a // b) * y

def mod_inverse(e, phi):
    g, d, _ = extended_gcd(e, phi)
    if g != 1: raise ValueError('No inverse')
    return d % phi

# ─────────────────────────────────────────────────────────────
# BINARY REPRESENTATION: Why 65537 is fast
# ─────────────────────────────────────────────────────────────

exponents = {
    'e=3':      3,
    'e=17':     17,
    'e=65537':  65537,
    'e=random': 123456789012345678901234567890,
}

print('=== Binary Weight (set bits) ===')
for name, val in exponents.items():
    binary = bin(val)
    set_bits = binary.count('1')
    print(f'{name:12s}: {binary[:50]}... ({set_bits} set bits)')

print()
print('=== Exponentiation Cost ===')
print('pow(m, e, n) cost is roughly: (bit_length - 1) squarings + (set_bits - 1) multiplications')
for name, val in exponents.items():
    bits = val.bit_length()
    squarings = bits - 1
    multiplications = bin(val).count('1') - 1
    total = squarings + multiplications
    print(f'{name:12s}: {squarings:>6} squarings + {multiplications:>4} multiplications = {total:>6} ops')

print()
print('=== Security Comparison ===')
print('e=3:     VULNERABLE — Hastad broadcast attack, Coppersmith attack')
print('e=17:    Acceptable for small demos, but not standard')
print('e=65537: STANDARD — fast, secure, universally compatible')

# ─────────────────────────────────────────────────────────────
# HASTAD'S BROADCAST ATTACK (e=3 vulnerability)
# If the same message is encrypted with e=3 to 3 different recipients,
# the attacker can recover the message via the Chinese Remainder Theorem.
# ─────────────────────────────────────────────────────────────

print('\n=== Hastad Attack Demo (e=3) ===')

# Three recipients with different moduli, all using e=3
e_attack = 3
p1, q1 = 61, 53; n1 = p1 * q1; phi1 = (p1-1)*(q1-1)
p2, q2 = 67, 59; n2 = p2 * q2; phi2 = (p2-1)*(q2-1)
p3, q3 = 71, 61; n3 = p3 * q3; phi3 = (p3-1)*(q3-1)

msg = 42  # secret message

# Encrypt same message to all three recipients
c1 = pow(msg, e_attack, n1)
c2 = pow(msg, e_attack, n2)
c3 = pow(msg, e_attack, n3)

print(f'c1 = {c1} (mod {n1})')
print(f'c2 = {c2} (mod {n2})')
print(f'c3 = {c3} (mod {n3})')

# Attacker recovers msg using CRT + cube root
# CRT: find x such that x ≡ c1 (mod n1), x ≡ c2 (mod n2), x ≡ c3 (mod n3)
# Then msg = round(x^(1/3))
from sympy import integer_nthroot

N = n1 * n2 * n3
# CRT coefficients (simplified for demo)
x = (c1 * (N//n1) * pow(N//n1, -1, n1) +
     c2 * (N//n2) * pow(N//n2, -1, n2) +
     c3 * (N//n3) * pow(N//n3, -1, n3)) % N

recovered, is_exact = integer_nthroot(x, 3)
print(f'Attacker recovers: {recovered} (exact: {is_exact})')
print(f'Original message:  {msg}')
print(f'Match: {recovered == msg}')
print('This attack works because m^3 < n1*n2*n3, so CRT gives the exact cube.')

# io.thecodeforge: RSA Digital Signatures
# Textbook implementation for understanding. Production code uses PSS padding.

import hashlib

def extended_gcd(a, b):
    if b == 0: return a, 1, 0
    g, x, y = extended_gcd(b, a % b)
    return g, y, x - (a // b) * y

def mod_inverse(e, phi):
    g, d, _ = extended_gcd(e, phi)
    if g != 1: raise ValueError('No inverse')
    return d % phi

def hash_message(message):
    """Hash message to a fixed-size integer. SHA-256 produces 256 bits."""
    digest = hashlib.sha256(message.encode('utf-8')).digest()
    return int.from_bytes(digest, 'big')

def rsa_sign(message, private_key):
    """Sign a message: signature = hash(message)^d mod n"""
    n, d = private_key
    h = hash_message(message)
    # In production: apply PSS padding to h before exponentiation
    return pow(h, d, n)

def rsa_verify(message, signature, public_key):
    """Verify a signature: check hash(message) == signature^e mod n"""
    n, e = public_key
    h = hash_message(message)
    # In production: verify PSS padding after exponentiation
    recovered_hash = pow(signature, e, n)
    return h == recovered_hash

# ─────────────────────────────────────────────────────────────
# DEMO: Sign and verify
# ─────────────────────────────────────────────────────────────

p, q = 61, 53
n = p * q
phi = (p - 1) * (q - 1)
e = 17
d = mod_inverse(e, phi)

public_key = (n, e)
private_key = (n, d)

message = 'Transfer £500 to account 1234-5678'
signature = rsa_sign(message, private_key)

print('=== RSA Digital Signatures ===')
print(f'Message:   "{message}"')
print(f'Signature: {signature}')
print()

# Verify with public key
is_valid = rsa_verify(message, signature, public_key)
print(f'Verification (original message): {is_valid}')  # True

# Tamper with the message
tampered = 'Transfer £5000 to account 1234-5678'  # changed amount
is_valid_tampered = rsa_verify(tampered, signature, public_key)
print(f'Verification (tampered message): {is_valid_tampered}')  # False

# Try to forge a signature (without the private key)
print('\n=== Forgery Attempt ===')
forged_sig = 12345  # random guess
is_valid_forged = rsa_verify(message, forged_sig, public_key)
print(f'Verification (forged signature): {is_valid_forged}')  # False

print()
print('=== Key Insight ===')
print('Signing:  hash^d mod n  (private key — only owner can do this)')
print('Verify:   sig^e mod n   (public key — anyone can do this)')
print('This is the REVERSE of encryption (encrypt with public, decrypt with private).')

# io.thecodeforge: RSA with Production Padding (OAEP + PSS)
# Uses Python's cryptography library — the correct way to do RSA.

from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives import hashes, serialization
from cryptography.hazmat.primitives.asymmetric.utils import Prehashed
from cryptography.hazmat.backends import default_backend

# ─────────────────────────────────────────────────────────────
# KEY GENERATION (production)
# ─────────────────────────────────────────────────────────────

private_key = rsa.generate_private_key(
    public_exponent=65537,
    key_size=2048,  # minimum for production
    backend=default_backend()
)
public_key = private_key.public_key()

print('=== RSA Key Generated (2048-bit, e=65537) ===')
print(f'Key size: {private_key.key_size} bits')
print()

# ─────────────────────────────────────────────────────────────
# ENCRYPTION WITH OAEP PADDING
# OAEP adds randomness: same plaintext → different ciphertext every time.
# ─────────────────────────────────────────────────────────────

message = b'Transfer 500 GBP to account 1234-5678'

# Encrypt with OAEP + SHA-256
ciphertext1 = public_key.encrypt(
    message,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None
    )
)

# Encrypt the same message again — different ciphertext (randomness)
ciphertext2 = public_key.encrypt(
    message,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None
    )
)

print('=== OAEP Encryption ===')
print(f'Plaintext:  {message}')
print(f'Ciphertext1 (hex): {ciphertext1[:32].hex()}...')
print(f'Ciphertext2 (hex): {ciphertext2[:32].hex()}...')
print(f'Same ciphertext? {ciphertext1 == ciphertext2}')  # False — OAEP is probabilistic
print()

# Decrypt
plaintext = private_key.decrypt(
    ciphertext1,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None
    )
)
print(f'Decrypted: {plaintext}')
print(f'Match: {plaintext == message}')  # True
print()

# ─────────────────────────────────────────────────────────────
# DIGITAL SIGNATURES WITH PSS PADDING
# PSS adds randomness: same message → different signature every time.
# ─────────────────────────────────────────────────────────────

sign_message = b'Transfer 500 GBP to account 1234-5678'

# Sign with PSS + SHA-256
signature1 = private_key.sign(
    sign_message,
    padding.PSS(
        mgf=padding.MGF1(hashes.SHA256()),
        salt_length=padding.PSS.MAX_LENGTH
    ),
    hashes.SHA256()
)

signature2 = private_key.sign(
    sign_message,
    padding.PSS(
        mgf=padding.MGF1(hashes.SHA256()),
        salt_length=padding.PSS.MAX_LENGTH
    ),
    hashes.SHA256()
)

print('=== PSS Signatures ===')
print(f'Signature1 (hex): {signature1[:32].hex()}...')
print(f'Signature2 (hex): {signature2[:32].hex()}...')
print(f'Same signature? {signature1 == signature2}')  # False — PSS is probabilistic
print()

# Verify
try:
    public_key.verify(
        signature1,
        sign_message,
        padding.PSS(
            mgf=padding.MGF1(hashes.SHA256()),
            salt_length=padding.PSS.MAX_LENGTH
        ),
        hashes.SHA256()
    )
    print('Signature verification: VALID')
except Exception as e:
    print(f'Signature verification: INVALID ({e})')

# Verify with tampered message
try:
    public_key.verify(
        signature1,
        b'Transfer 5000 GBP to account 1234-5678',  # tampered
        padding.PSS(
            mgf=padding.MGF1(hashes.SHA256()),
            salt_length=padding.PSS.MAX_LENGTH
        ),
        hashes.SHA256()
    )
    print('Tampered verification: VALID (should not happen)')
except Exception:
    print('Tampered verification: INVALID (correctly rejected)')

# io.thecodeforge: RSA + AES Hybrid Encryption
# This is how production systems use RSA for large data.

from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
from cryptography.hazmat.primitives import hashes, padding as sym_padding
from cryptography.hazmat.backends import default_backend
import os

# ─────────────────────────────────────────────────────────────
# Step 1: Generate RSA key pair
# ─────────────────────────────────────────────────────────────

private_key = rsa.generate_private_key(
    public_exponent=65537,
    key_size=2048,
    backend=default_backend()
)
public_key = private_key.public_key()

# ─────────────────────────────────────────────────────────────
# Step 2: Generate random AES-256 key and IV
# ─────────────────────────────────────────────────────────────

aes_key = os.urandom(32)  # 256-bit random key
iv = os.urandom(16)       # 128-bit random IV for AES-CBC

print(f'AES key: {aes_key.hex()[:32]}... (256 bits, random)')
print(f'IV:      {iv.hex()[:32]}... (128 bits, random)')
print()

# ─────────────────────────────────────────────────────────────
# Step 3: Encrypt the AES key with RSA (only 32 bytes — fast)
# ─────────────────────────────────────────────────────────────

encrypted_aes_key = public_key.encrypt(
    aes_key,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None
    )
)

print(f'Encrypted AES key: {len(encrypted_aes_key)} bytes (RSA ciphertext)')
print()

# ─────────────────────────────────────────────────────────────
# Step 4: Encrypt the actual data with AES
# ─────────────────────────────────────────────────────────────

plaintext = b'This is a large document that would be too slow to encrypt with RSA directly. ' * 100
print(f'Plaintext size: {len(plaintext)} bytes')

# AES-CBC requires padding to block size (128 bits = 16 bytes)
padder = sym_padding.PKCS7(128).padder()
padded_plaintext = padder.update(plaintext) + padder.finalize()

cipher = Cipher(algorithms.AES(aes_key), modes.CBC(iv), backend=default_backend())
encryptor = cipher.encryptor()
ciphertext = encryptor.update(padded_plaintext) + encryptor.finalize()

print(f'Ciphertext size: {len(ciphertext)} bytes')
print()

# ─────────────────────────────────────────────────────────────
# Step 5: Receiver decrypts AES key with RSA private key
# ─────────────────────────────────────────────────────────────

decrypted_aes_key = private_key.decrypt(
    encrypted_aes_key,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None
    )
)

print(f'Decrypted AES key matches original: {decrypted_aes_key == aes_key}')

# ─────────────────────────────────────────────────────────────
# Step 6: Receiver decrypts data with recovered AES key
# ─────────────────────────────────────────────────────────────

decipher = Cipher(algorithms.AES(decrypted_aes_key), modes.CBC(iv), backend=default_backend())
decryptor = decipher.decryptor()
decrypted_padded = decryptor.update(ciphertext) + decryptor.finalize()

unpadder = sym_padding.PKCS7(128).unpadder()
decrypted = unpadder.update(decrypted_padded) + unpadder.finalize()

print(f'Decrypted size: {len(decrypted)} bytes')
print(f'Plaintext matches: {decrypted == plaintext}')
print()
print('=== Summary ===')
print(f'RSA encrypted: {len(aes_key)} bytes (the AES key)')
print(f'AES encrypted: {len(plaintext)} bytes (the actual data)')
print('RSA handles key exchange. AES handles bulk encryption. Both are needed.')

# io.thecodeforge: RSA CRT Optimization
# Demonstrates the Chinese Remainder Theorem speedup for decryption.

import time
from math import gcd

def extended_gcd(a, b):
    if b == 0: return a, 1, 0
    g, x, y = extended_gcd(b, a % b)
    return g, y, x - (a // b) * y

def mod_inverse(e, phi):
    g, d, _ = extended_gcd(e, phi)
    if g != 1: raise ValueError('No inverse')
    return d % phi

# ─────────────────────────────────────────────────────────────
# SETUP: Generate key pair with known p, q (for CRT demo)
# ─────────────────────────────────────────────────────────────

# Using larger primes for meaningful timing comparison
from sympy import nextprime
import random

bits = 512  # per prime — 1024-bit total key
p = nextprime(random.getrandbits(bits))
q = nextprime(random.getrandbits(bits))
while q == p:
    q = nextprime(random.getrandbits(bits))

n = p * q
phi = (p - 1) * (q - 1)
e = 65537
d = mod_inverse(e, phi)

# Precompute CRT components (stored with private key in production)
dp = d % (p - 1)  # d mod (p-1)
dq = d % (q - 1)  # d mod (q-1)
qinv = mod_inverse(q, p)  # q^(-1) mod p

msg = 42
ciphertext = pow(msg, e, n)

print(f'Key size: {n.bit_length()} bits')
print(f'd size: {d.bit_length()} bits')
print(f'dp size: {dp.bit_length()} bits (half of d)')
print(f'dq size: {dq.bit_length()} bits (half of d)')
print()

# ─────────────────────────────────────────────────────────────
# STANDARD DECRYPTION: m = c^d mod n
# ─────────────────────────────────────────────────────────────

iterations = 100
start = time.perf_counter()
for _ in range(iterations):
    m_standard = pow(ciphertext, d, n)
standard_time = (time.perf_counter() - start) / iterations

print(f'Standard decryption: {standard_time*1000:.3f} ms per operation')
print(f'Result: {m_standard}')

# ─────────────────────────────────────────────────────────────
# CRT DECRYPTION: split into two half-size operations
# ─────────────────────────────────────────────────────────────

start = time.perf_counter()
for _ in range(iterations):
    # Step 1: Compute mod p and mod q separately (half-size exponents)
    m1 = pow(ciphertext, dp, p)
    m2 = pow(ciphertext, dq, q)

    # Step 2: Combine using CRT
    # m = m1 + p * ((m2 - m1) * qinv mod p)
    h = (qinv * (m1 - m2)) % p
    m_crt = m2 + h * q

crt_time = (time.perf_counter() - start) / iterations

print(f'CRT decryption: {crt_time*1000:.3f} ms per operation')
print(f'Result: {m_crt}')
print()
print(f'Speedup: {standard_time / crt_time:.1f}x faster')
print('Production RSA libraries use CRT automatically — you get this speedup for free.')

package io.thecodeforge.crypto;

import javax.crypto.Cipher;
import java.nio.charset.StandardCharsets;
import java.security.*;
import java.security.spec.PKCS8EncodedKeySpec;
import java.security.spec.X509EncodedKeySpec;
import java.util.Base64;

/**
 * Production-grade RSA in Java.
 * 
 * - Uses OAEP padding (not PKCS#1 v1.5)
 * - Uses 2048-bit keys (minimum)
 * - Uses SHA256withRSA for signatures
 * - Keys are stored in PKCS#12 KeyStore in real deployments
 */
public class RsaProductionExample {

    public static void main(String[] args) throws Exception {
        // ─────────────────────────────────────────────────────
        // KEY GENERATION (2048-bit, e=65537)
        // ─────────────────────────────────────────────────────
        KeyPairGenerator keyGen = KeyPairGenerator.getInstance("RSA");
        keyGen.initialize(2048);
        KeyPair keyPair = keyGen.generateKeyPair();
        PublicKey publicKey = keyPair.getPublic();
        PrivateKey privateKey = keyPair.getPrivate();

        System.out.println("=== RSA Key Pair Generated ===");
        System.out.println("Algorithm: " + publicKey.getAlgorithm());
        System.out.println("Format: " + publicKey.getFormat());
        System.out.println("Public key (Base64): " + Base64.getEncoder().encodeToString(publicKey.getEncoded()).substring(0, 60) + "...");
        System.out.println("Private key (Base64): " + Base64.getEncoder().encodeToString(privateKey.getEncoded()).substring(0, 60) + "...");
        System.out.println();

        // ─────────────────────────────────────────────────────
        // ENCRYPTION WITH OAEP
        // ─────────────────────────────────────────────────────
        String message = "Transfer 500 GBP to account 1234-5678";
        byte[] messageBytes = message.getBytes(StandardCharsets.UTF_8);

        Cipher encryptCipher = Cipher.getInstance("RSA/ECB/OAEPWithSHA-256AndMGF1Padding");
        encryptCipher.init(Cipher.ENCRYPT_MODE, publicKey);
        byte[] ciphertext = encryptCipher.doFinal(messageBytes);

        System.out.println("=== OAEP Encryption ===");
        System.out.println("Plaintext: " + message);
        System.out.println("Ciphertext (Base64): " + Base64.getEncoder().encodeToString(ciphertext).substring(0, 60) + "...");
        System.out.println("Ciphertext length: " + ciphertext.length + " bytes (always 256 for 2048-bit RSA)");
        System.out.println();

        // Decrypt with private key
        Cipher decryptCipher = Cipher.getInstance("RSA/ECB/OAEPWithSHA-256AndMGF1Padding");
        decryptCipher.init(Cipher.DECRYPT_MODE, privateKey);
        byte[] decryptedBytes = decryptCipher.doFinal(ciphertext);
        String decrypted = new String(decryptedBytes, StandardCharsets.UTF_8);

        System.out.println("Decrypted: " + decrypted);
        System.out.println("Match: " + message.equals(decrypted));
        System.out.println();

        // ─────────────────────────────────────────────────────
        // DIGITAL SIGNATURES WITH SHA256withRSA
        // ─────────────────────────────────────────────────────

        // Sign with private key
        Signature signer = Signature.getInstance("SHA256withRSA");
        signer.initSign(privateKey);
        signer.update(messageBytes);
        byte[] signature = signer.sign();

        System.out.println("=== RSA Digital Signature ===");
        System.out.println("Signature (Base64): " + Base64.getEncoder().encodeToString(signature).substring(0, 60) + "...");
        System.out.println("Signature length: " + signature.length + " bytes");
        System.out.println();

        // Verify with public key
        Signature verifier = Signature.getInstance("SHA256withRSA");
        verifier.initVerify(publicKey);
        verifier.update(messageBytes);
        boolean valid = verifier.verify(signature);

        System.out.println("Verification (original): " + valid);  // true

        // Verify with tampered message
        verifier.initVerify(publicKey);
        verifier.update("Transfer 5000 GBP to account 1234-5678".getBytes(StandardCharsets.UTF_8));
        boolean tamperedValid = verifier.verify(signature);
        System.out.println("Verification (tampered): " + tamperedValid);  // false
    }
}