Chapter 19 — RSA

Worked example (run it)

cd ~/sec-lab/scratch

# --- the toy version, by hand ---
python3 - <<'PY'
def inv(a, m):
    g, x = m, 0
    x0, a0 = 1, a
    while a0:
        q = g // a0
        g, a0 = a0, g - q*a0
        x, x0 = x0, x - q*x0
    return x % m

p, q = 61, 53
n = p*q
phi = (p-1)*(q-1)
e = 17
d = inv(e, phi)
print(f"n={n}  phi={phi}  e={e}  d={d}")

m = 65
c = pow(m, e, n);  print(f"encrypt {m} -> {c}")
print(f"decrypt {c} -> {pow(c, d, n)}")
s = pow(m, d, n);  print(f"sign {m} -> {s}")
print(f"verify {s} -> {pow(s, e, n)}")

# malleability of TEXTBOOK RSA -- why padding exists
c2 = pow(2, e, n)
print(f"\n(c * enc(2)) mod n decrypts to {pow(c*c2, d, n)}  == 65*2 = 130")
print("attacker doubled the plaintext without decrypting. OAEP prevents this.")
PY

# --- real RSA with OpenSSL ---
openssl genpkey -algorithm RSA -pkeyopt rsa_keygen_bits:2048 -out rsa.pem
openssl pkey -in rsa.pem -pubout -out rsa.pub

# inspect it
openssl pkey -in rsa.pem -text -noout | head -20

# encrypt a SMALL secret with OAEP (this is real OpenSSL 3.x syntax)
echo -n "this is a 32-byte AES key ......." > aeskey.bin
openssl pkeyutl -encrypt -pubin -inkey rsa.pub -in aeskey.bin -out aeskey.enc \
        -pkeyopt rsa_padding_mode:oaep -pkeyopt rsa_oaep_md:sha256
openssl pkeyutl -decrypt -inkey rsa.pem -in aeskey.enc \
        -pkeyopt rsa_padding_mode:oaep -pkeyopt rsa_oaep_md:sha256

# sign a document with PSS
echo "transfer 100 to alice" > doc.txt
openssl dgst -sha256 -sign rsa.pem -sigopt rsa_padding_mode:pss -out doc.sig doc.txt
openssl dgst -sha256 -verify rsa.pub -sigopt rsa_padding_mode:pss \
        -signature doc.sig doc.txt        # -> "Verified OK"

# tamper and re-verify
echo "transfer 100 to mallory" > doc.txt
openssl dgst -sha256 -verify rsa.pub -sigopt rsa_padding_mode:pss \
        -signature doc.sig doc.txt        # -> "Verification Failure"

macOS note: the pkeyutl -encrypt line needs OpenSSL 3.x; the LibreSSL build fails on the key format. The Python equivalent below always works.

.venv/bin/python - <<'PY'
from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives import hashes

key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
pub = key.public_key()

# encrypt a 32-byte key with OAEP
secret = b"x" * 32
ct = pub.encrypt(secret, padding.OAEP(
        mgf=padding.MGF1(hashes.SHA256()), algorithm=hashes.SHA256(), label=None))
print("ciphertext bytes:", len(ct))                 # 256 for RSA-2048
print("decrypts back:", key.decrypt(ct, padding.OAEP(
        mgf=padding.MGF1(hashes.SHA256()), algorithm=hashes.SHA256(),
        label=None)) == secret)

# how big can the message be?
for size in (32, 190, 191, 245):
    try:
        pub.encrypt(b"x"*size, padding.OAEP(
            mgf=padding.MGF1(hashes.SHA256()),
            algorithm=hashes.SHA256(), label=None))
        print(f"  {size} bytes: OK")
    except ValueError:
        print(f"  {size} bytes: TOO BIG for RSA-2048 + OAEP-SHA256")
PY