Public-Key Cryptography: RSA & Elliptic Curves

Public-key cryptography lets strangers communicate securely. Learn RSA key generation, encryption, decryption and signatures from Euler's theorem; Diffie–Hellman key exchange; elliptic-curve group law, scalar multiplication and ECDH; key sizes and security levels; and why hashing, padding and quantum threats matter — with toy RSA and ECC in Python.

Before the 1970s, secure communication needed a pre-shared secret key. Public-key cryptography splits the key in two: a public key anyone can use to encrypt or verify, and a private key only the owner holds to decrypt or sign.

RSA relies on the difficulty of factoring n = pq; elliptic-curve cryptography (ECC) relies on the difficulty of the discrete logarithm on a curve. ECC gives the same security with far smaller keys, which is why phones, IoT devices and TLS 1.3 favour it.

An analogy

A public key is like an open padlock you hand out freely: anyone can snap it shut on a box, but only you have the key that opens it.

Two keys, two jobs

Public-key systems provide:

Why RSA works

ed ≡ 1 (mod φ) means ed = 1 + kφ. Then c^d = m^(ed) = m·(m^φ)^k ≡ m (mod n) by Euler's theorem. Knowing φ requires knowing p and q — i.e. factoring n. Nobody can do that for 2048-bit n with classical computers.

Elliptic-curve group law

Points on the curve, plus a 'point at infinity', form a group: draw a line through P and Q, find the third intersection, reflect it. Repeated addition kG is fast by double-and-add; recovering k from kG (ECDLP) is hard. A 256-bit curve ≈ 3072-bit RSA security (128-bit level).

Real-world pitfalls and the future

Textbook RSA is deterministic and malleable — padding (OAEP, PSS) is mandatory. Nonce reuse in ECDSA leaks the private key (the PlayStation 3 break). Side channels (timing, power) need constant-time code. Shor's algorithm would break RSA and ECC on a large quantum computer, so NIST has standardised post-quantum algorithms (ML-KEM, ML-DSA) based on lattice problems.

Formulas

Worked example: RSA key pair

Given: p = 61, q = 53, e = 17

Find: n, φ, d.

Answer: Public (3233, 17); private d = 2753

Worked example: Encrypt and decrypt

Given: m = 65

Find: c and check.

Answer: c = 2790 → m = 65 ✓

Worked example: Diffie–Hellman

Given: p = 23, g = 5, a = 6, b = 15

Find: Shared key.

Answer: K = 2

Toy RSA: keys, encryption and a signature

from math import gcd

# Toy RSA -- real keys use primes of ~1024+ bits each
p, q = 61, 53
n, phi = p * q, (p - 1) * (q - 1)
e = 17
assert gcd(e, phi) == 1
d = pow(e, -1, phi)                 # modular inverse (Python 3.8+)
print(f"n = {n}, phi = {phi}, e = {e}, d = {d}")

m = 65                              # message encoded as an integer < n
c = pow(m, e, n)                    # encrypt: c = m^e mod n
m2 = pow(c, d, n)                   # decrypt: m = c^d mod n
print(f"cipher = {c}, decrypted = {m2}")

s = pow(m, d, n)                    # sign with the private key
print(f"signature = {s}, verify -> {pow(s, e, n)}")
# n = 3233, phi = 3120, e = 17, d = 2753
# cipher = 2790, decrypted = 65
# signature = 588, verify -> 65

Educational only: real RSA uses 2048+-bit n, random padding (OAEP/PSS) and signs a hash, never raw messages. Use a vetted library (e.g. Python 'cryptography').

Toy elliptic curve and ECDH key agreement

# Toy elliptic curve y^2 = x^3 + 2x + 2 over GF(17), generator G = (5, 1)
p, a = 17, 2
O = None                                   # point at infinity

def add(P, Q):
    if P is O: return Q
    if Q is O: return P
    (x1, y1), (x2, y2) = P, Q
    if x1 == x2 and (y1 + y2) % p == 0:
        return O
    if P == Q:
        lam = (3 * x1 * x1 + a) * pow(2 * y1, -1, p) % p
    else:
        lam = (y2 - y1) * pow(x2 - x1, -1, p) % p
    x3 = (lam * lam - x1 - x2) % p
    return x3, (lam * (x1 - x3) - y1) % p

def mul(k, P):                             # double-and-add
    R = O
    while k:
        if k & 1: R = add(R, P)
        P, k = add(P, P), k >> 1
    return R

G = (5, 1)
print("2G =", mul(2, G), " 3G =", mul(3, G))
order = next(k for k in range(1, 100) if mul(k, G) is O)
print("order of G =", order)
da, db = 3, 7                              # private keys
A, B = mul(da, G), mul(db, G)              # public keys
print("Alice pub", A, " Bob pub", B)
print("shared secrets:", mul(da, B), mul(db, A))
# 2G = (6, 3)  3G = (10, 6)
# order of G = 19
# Alice pub (10, 6)  Bob pub (0, 6)
# shared secrets: (6, 3) (6, 3)

Both parties reach the same point 21G = 2G (since 21 mod 19 = 2) without ever sending their private keys. Real curves (P-256, Curve25519) use ~256-bit primes, making the discrete log infeasible.

Common mistakes

Applications

Key takeaways

Going further