Public-Key Cryptography - RSA, Diffie-Hellman, ElGamal and ECC

Symmetric ciphers have a problem that no amount of cleverness inside the cipher can solve: both parties must already share a secret key.

How do two strangers, a customer and an online shop, agree on one over a network that anyone can listen to? Public-key (asymmetric) cryptography solved this in the 1970s.

Each party has a public key, which may be published, and a private key, which is never shared, linked by a mathematical one-way relationship from Unit 2: easy to compute in one direction and infeasible to reverse.

This unit works through RSA, Diffie–Hellman, ElGamal and elliptic-curve cryptography with small numbers you can verify by hand, every one of which was executed and cross-checked.

4.1 The public-key idea

With n users, symmetric keys need n(n − 1)/2 pairs: 1,000 users need 499,500 shared keys. Public-key schemes need only n key pairs. The roles: a public key encrypts (or verifies signatures) and a private key decrypts (or signs).

Two uses follow: encryption (anyone encrypts with Alice's public key; only Alice decrypts) and digital signatures (Alice signs with her private key; anyone verifies with her public key, Unit 5).

Public-key operations are slow (thousands of times slower than AES), so in practice they are used to establish or transport a symmetric session key, and AES encrypts the data: a hybrid scheme.

The security rests on hard problems: integer factorisation (RSA), the discrete logarithm (Diffie–Hellman, ElGamal, DSA) and the elliptic-curve discrete logarithm (ECDH, ECDSA).

4.2 RSA

Key generation (Rivest, Shamir, Adleman, 1977):

1. Choose two large distinct primes p and q (1024 bits each for a 2048-bit key).
2. Compute n = pq and φ(n) = (p − 1)(q − 1).
3. Choose a public exponent e with 1 < e < φ(n) and gcd(e, φ(n)) = 1 (commonly 65537).
4. Compute the private exponent d = e⁻¹ mod φ(n) (extended Euclid).

The public key is (e, n); the private key is d (with p and q kept secret).

Encryption: c = mᵉ mod n, for 0 ≤ m < n. Decryption: m = cᵈ mod n. Why it works: ed ≡ 1 (mod φ(n)), so ed = 1 + kφ(n) and, by Euler's theorem (Unit 2), mᵉᵈ = m · (m^φ(n))ᵏ ≡ m (mod n) (the case where m shares a factor with n also works, by the Chinese Remainder Theorem).

Security depends on the difficulty of factoring n: anyone who can factor n computes φ(n) and then d.

CRT speed-up. The owner knows p and q, so decryption is done modulo each prime separately: m₁ = c^(d mod (p−1)) mod p, m₂ = c^(d mod (q−1)) mod q, and h = q⁻¹(m₁ − m₂) mod p gives m = m₂ + h·q.

This is about four times faster and is how real RSA libraries decrypt. Signing with RSA is the same operation as decryption applied to a digest: s = hᵈ mod n; verification computes sᵉ mod n and compares it with h.

The classic textbook example, p = 61, q = 53, e = 17, message m = 65:

p, q, e = 61, 53, 17
n, phi = p * q, (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = 65
c = pow(m, e, n)
print("n =", n, " phi =", phi, " d =", d)
print("c =", c, " decrypted =", pow(c, d, n))
dp, dq, qinv = d % (p - 1), d % (q - 1), pow(q, -1, p)
m1, m2 = pow(c, dp, p), pow(c, dq, q)
h = qinv * (m1 - m2) % p
print("CRT decrypt =", m2 + h * q, " (dp, dq, qinv) =", (dp, dq, qinv))
s = pow(m, d, n)
print("signature =", s, " verifies:", pow(s, e, n) == m)

p2, q2, e2 = 17, 11, 7
n2, d2 = p2 * q2, pow(e2, -1, (p2 - 1) * (q2 - 1))
print("second key: n =", n2, " d =", d2, " 88 ->", pow(88, e2, n2), "->", pow(pow(88, e2, n2), d2, n2))

n = 3233  phi = 3120  d = 2753
c = 2790  decrypted = 65
CRT decrypt = 65  (dp, dq, qinv) = (53, 49, 38)
signature = 588  verifies: True
second key: n = 187  d = 23  88 -> 11 -> 88

By hand: n = 3233, φ = 60 × 52 = 3120, e = 17, d = 2753 (since 17 × 2753 = 46801 = 15 × 3120 + 1). Then 65¹⁷ mod 3233 = 2790, and 2790²⁷⁵³ mod 3233 = 65.

The second key (n = 187, e = 7, d = 23) is the small example used in many textbooks: 88 encrypts to 11 and decrypts back.

4.3 Diffie–Hellman key exchange

Diffie–Hellman (1976) lets two parties create a shared secret over a public channel. They agree publicly on a prime p and a primitive root g (Unit 2). Alice picks a secret a and sends A = gᵃ mod p; Bob picks b and sends B = gᵇ mod p.

Alice computes Bᵃ mod p, Bob computes Aᵇ mod p, and both equal gᵃᵇ mod p.

An eavesdropper sees p, g, A, B but would need the discrete log to find a or b. ElGamal encryption turns this into a cipher: with private x and public y = gˣ mod p, to encrypt m choose a random k and send (c₁, c₂) = (gᵏ mod p, m·yᵏ mod p); to decrypt compute s = c₁ˣ mod p and m = c₂·s⁻¹ mod p.

The ciphertext is twice as long as the message and must use a fresh k each time.

p, g = 23, 5
a, b = 6, 15
A, B = pow(g, a, p), pow(g, b, p)
print("A =", A, " B =", B, " shared:", pow(B, a, p), pow(A, b, p))
x = 6
y = pow(g, x, p)
m, k = 10, 3
c1, c2 = pow(g, k, p), m * pow(y, k, p) % p
s = pow(c1, x, p)
print("ElGamal: y =", y, " c1 =", c1, " c2 =", c2, " decrypted =", c2 * pow(s, -1, p) % p)

A = 8  B = 19  shared: 2 2
ElGamal: y = 8  c1 = 10  c2 = 14  decrypted = 10

Plain Diffie–Hellman provides no authentication: in a man-in-the-middle attack Mallory intercepts A and B, replaces them with her own values, and holds one shared key with Alice and another with Bob, relaying and reading everything.

The defence is to authenticate the exchanged values, with digital signatures and certificates (Unit 5), as TLS does.

Modern protocols use ephemeral DH (a fresh key per session), giving forward secrecy: stealing a server's long-term key later cannot decrypt recorded old sessions. Real groups use 2048-bit or larger primes, or elliptic curves.

4.4 Elliptic-curve cryptography

An elliptic curve over a prime field is the set of points (x, y) satisfying y² = x³ + ax + b (mod p) together with a special point at infinity O (the identity).

Points can be added with a geometric rule that is computed algebraically: for P = (x₁, y₁) and Q = (x₂, y₂), the slope is m = \dfrac{y₂ - y₁}{x₂ - x₁} for P ≠ Q and m = \dfrac{3x₁^{2} + a}{2y₁} for doubling P = Q (division means multiplying by the modular inverse); then x₃ = m² − x₁ − x₂ and y₃ = m(x₁ − x₃) − y₁, all mod p; P + (−P) = O, where −P = (x, −y).

Scalar multiplication kP = P + P + … + P (k times) is computed fast by double-and-add; but recovering k from P and kP is the elliptic-curve discrete logarithm problem, which has no sub-exponential algorithm, so a 256-bit curve key gives security comparable to a 3072-bit RSA key, with smaller keys and faster operations.

The textbook curve y² = x³ + 2x + 2 over p = 17 with base point G = (5, 1):

p, a, b = 17, 2, 2
G = (5, 1)

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

def mul(k, P):
    R = None
    while k:
        if k & 1:
            R = add(R, P)
        P = add(P, P)
        k >>= 1
    return R

pts, P = [], G
while P is not None:
    pts.append(P)
    P = add(P, G)
print("multiples:", pts)
print("order of G =", len(pts) + 1)
alice, bob = 3, 7
A, B = mul(alice, G), mul(bob, G)
print("ECDH: A =", A, " B =", B, " shared:", mul(alice, B), mul(bob, A))

multiples: [(5, 1), (6, 3), (10, 6), (3, 1), (9, 16), (16, 13), (0, 6), (13, 7), (7, 6), (7, 11), (13, 10), (0, 11), (16, 4), (9, 1), (3, 16), (10, 11), (6, 14), (5, 16)]
order of G = 19
ECDH: A = (10, 6)  B = (0, 6)  shared: (6, 3) (6, 3)

G has order 19 (19G = O), so there are 19 distinct multiples; 2G = (6, 3). In the elliptic-curve Diffie–Hellman, Alice (secret 3) sends 3G = (10, 6), Bob (secret 7) sends 7G = (0, 6), and both compute 21G = 2G = (6, 3).

Real curves (P-256, Curve25519) use primes of 256 bits; ECDSA and EdDSA (Ed25519) are the matching signature schemes.

RSA is simple and universal but its keys are large and key generation slow; elliptic curves give small keys and signatures and dominate on mobile and in TLS 1.3.

Quantum computers running Shor's algorithm would break RSA, DH and ECC; NIST has standardised post-quantum algorithms (ML-KEM/Kyber for key exchange, ML-DSA/Dilithium for signatures), and "harvest now, decrypt later" is the reason migration is already under way, while symmetric ciphers need only larger keys (AES-256).

4.6 Seeing public-key cryptography: pioneers, keys and curves

Public-key cryptography solves the oldest problem of secret writing: how can two people who have never met agree on a key over an open line?

The plate shows the two researchers who first published the answer and a worked key exchange with small numbers.

The figures show the two-key idea, the RSA steps with the textbook numbers, an elliptic-curve addition drawn on real axes and the key sizes that give equal strength.

(a) Diffie and Hellman

(b) Diffie-Hellman with p = 23, g = 5

4.6.1 Eight applications of public-key cryptography

1. HTTPS and online banking. When a browser opens a bank or ConnectIPS site, the server proves its identity with a certificate and the two sides agree a session key with public-key methods (RSA or elliptic-curve Diffie-Hellman). The bulk data are then encrypted with fast AES. The padlock beside the address is the visible result.
2. Digital signatures. A signer uses a private key to sign a document, and anybody can verify it with the public key. This proves who signed and that the content was not changed. Nepal's Electronic Transactions Act gives legal standing to digital signatures issued by licensed certifying authorities.
3. Key exchange for private chats. Messaging apps use Diffie-Hellman variants so that two phones agree on a fresh key without sending it. Even if the server is hacked later, old conversations stay safe when the keys were temporary. This is called forward secrecy.
4. Secure email and files. PGP and S/MIME let a sender encrypt an email with the receiver's public key and sign it with their own private key. A hospital can send a patient report so that only the doctor named can open it. No shared password has to be agreed first.
5. Software updates. Phone and computer vendors sign each update with a private key, and the device checks the signature with a built-in public key before installing it. This stops an attacker from sending a fake update with malware. The same idea protects app stores.
6. Server login with SSH keys. System administrators log in to servers by proving that they hold a private key instead of typing a password. The server stores only the public key, so a stolen server file does not allow log-in. Cloud teams in Kathmandu use this daily.
7. Cryptocurrency and blockchain. A wallet address is derived from a public key, and a transaction is authorised by a signature made with the matching private key (elliptic-curve signatures). Anyone can verify the payment, and nobody can spend without the private key. Losing the key means losing the funds.
8. Smart cards and national ID. Chips in bank cards, passports and national ID cards store a private key that never leaves the chip. The chip signs a challenge from a reader to prove that the card is genuine. ECC is favoured here because its small keys fit small chips.

(a) A letterbox: anyone posts, only the owner opens

(b) Toy RSA and the cost of factoring n

Chapter summary

• Public-key cryptography removes the shared-secret problem: n users need n key pairs instead of n(n − 1)/2, and it is used to exchange symmetric keys (hybrid encryption).
• RSA: n = pq, d = e⁻¹ mod φ(n), c = mᵉ mod n, m = cᵈ mod n; the example n = 3233, d = 2753 encrypts 65 to 2790; real RSA needs OAEP/PSS padding and ≥ 2048-bit keys.
• Diffie–Hellman agrees gᵃᵇ mod p and needs authentication against man-in-the-middle; ElGamal encrypts with a fresh k.
• Elliptic curves give the same security with far smaller keys; the example curve has a point of order 19.

Practice

1. How many symmetric keys do 50 users need for pairwise secure communication, and how many key pairs for public-key?
2. Generate an RSA key with p = 11, q = 13, e = 7: give n, φ, d.
3. Encrypt m = 9 with the key from question 2.
4. Why does RSA decryption recover m? State the theorem used.
5. Alice and Bob use p = 13, g = 2, a = 5, b = 4. Compute A, B and the shared key.
6. How does a man-in-the-middle break unauthenticated Diffie–Hellman?
7. ElGamal with p = 11, g = 2, x = 3: compute y; then encrypt m = 7 with k = 4.
8. On y² = x³ + 2x + 2 (mod 17) double P = (5, 1).
9. Why is textbook RSA unsafe and what fixes it?
10. Why do elliptic curves allow shorter keys?

Answers and worked solutions

1. 50 × 49 / 2 = 1,225 symmetric keys; 50 key pairs.

2. n = 143, φ = 10 × 12 = 120, d = 7⁻¹ mod 120: 7 × 103 = 721 = 6 × 120 + 1, so d = 103.

3. 9⁷ mod 143: 9² = 81; 9⁴ = 6561 mod 143 = 6561 − 45 × 143 (6435) = 126; 9⁷ = 9⁴ · 9² · 9 = 126 · 81 · 9 mod 143. 126 · 81 = 10206 mod 143 = 10206 − 71 × 143 (10153) = 53; 53 · 9 = 477 mod 143 = 477 − 429 = 48. (Decrypting: 48¹⁰³ mod 143 = 9.)

4. ed ≡ 1 (mod φ(n)); by Euler's theorem m^φ(n) ≡ 1 (mod n), so mᵉᵈ ≡ m.

5. A = 2⁵ mod 13 = 32 mod 13 = 6; B = 2⁴ mod 13 = 3; shared = B⁵ mod 13 = 3⁵ = 243 mod 13 = 9 (check: A⁴ = 6⁴ = 1296 mod 13 = 9).

6. Mallory replaces A and B with her own public values and negotiates separate keys with each side, then decrypts and re-encrypts all traffic; neither side can tell without authentication.

7. y = 2³ mod 11 = 8. c₁ = 2⁴ mod 11 = 5; c₂ = 7 · 8⁴ mod 11; 8² = 64 ≡ 9, 8⁴ ≡ 81 ≡ 4; c₂ = 28 mod 11 = 6. Ciphertext (5, 6).

8. m = \dfrac{3\cdot 25 + 2}{2\cdot 1} = 77/2 mod 17 = 9 · 2⁻¹ = 9 · 9 = 81 mod 17 = 13 (since 77 mod 17 = 9 and 2⁻¹ = 9). x₃ = 13² − 10 = 159 mod 17 = 6; y₃ = 13(5 − 6) − 1 = −14 mod 17 = 3. 2G = (6, 3).

9. It is deterministic and malleable, and has attacks for small messages and small e; OAEP/PSS randomised padding fixes it.

10. The best known attacks on the elliptic-curve discrete logarithm are fully exponential, whereas factoring and the ordinary discrete log have sub-exponential algorithms, so smaller keys reach the same security.

Model answers: medium (5 marks) and long (10 marks) questions

Q1 (5 marks). With p = 3 and q = 11, generate RSA keys with e = 7 and encrypt and decrypt the message m = 4.

Introduction. RSA is a public-key system whose security depends on the difficulty of factoring the product of two large primes (section 4.2, Figure 4.2).

1. Modulus. n = p x q = 3 x 11 = 33.
2. Totient. phi(n) = (3 - 1)(11 - 1) = 20.
3. Public exponent. e = 7 is valid because gcd(7, 20) = 1.
4. Private exponent. d is the inverse of 7 modulo 20. Since 7 x 3 = 21 = 1 (mod 20), d = 3.
5. Encryption. c = m to the power e mod n = 4 to the power 7 mod 33 = 16384 mod 33 = 16, because 33 x 496 = 16368.
6. Decryption. m = c to the power d mod n = 16 to the power 3 mod 33 = 4096 mod 33 = 4, because 33 x 124 = 4092. The message is recovered.

Item	Value
Public key (n, e)	(33, 7)
Private key d	3
Ciphertext of 4	16

These numbers are far too small to be secure; real keys use primes of 1024 bits or more.

Q2 (5 marks). Explain Diffie-Hellman key exchange with an example. Why is it vulnerable to a man-in-the-middle attack?

Introduction. Diffie-Hellman (1976) lets two parties agree on a shared secret over a public channel (section 4.3, Plate 4.1).

1. Public values. A prime p = 23 and a generator g = 5 are agreed openly.
2. Private choices. Alice picks a = 6, Bob picks b = 15, and each keeps their number secret.
3. Exchange. Alice sends A = 5 to the power 6 mod 23 = 8. Bob sends B = 5 to the power 15 mod 23 = 19.
4. Shared key. Alice computes B to the power a = 19 to the power 6 mod 23 = 2. Bob computes A to the power b = 8 to the power 15 mod 23 = 2. Both obtain K = 2.
5. Security. An eavesdropper sees p, g, A and B but must solve the discrete logarithm problem to find a or b, which is infeasible for large p.
6. Weakness. The exchange does not check who is at the other end. Mallory can run one exchange with Alice and another with Bob, and read and forward all messages. The defence is to authenticate the exchanged values, using digital signatures and certificates, as TLS does.

Q3 (5 marks). Explain elliptic-curve cryptography and point addition with an example.

Introduction. ECC uses the group of points on a curve y squared = x cubed + ax + b over a finite field. It gives the same security as RSA with much smaller keys (section 4.4, Figure 4.3).

1. Curve and group. Points (x, y) on the curve, plus a point at infinity O, form a group under a chord-and-tangent addition rule.
2. Addition formulas. For P not equal to Q the slope is \dfrac{y_2 - y_1}{x_2 - x_1}; for doubling it is (3 x1 squared + a)/(2 y1). Then x3 = slope squared - x1 - x2 and y3 = slope (x1 - x3) - y1, all modulo p.
3. Example. On y squared = x cubed + 2x + 2 mod 17 with G = (5, 1): slope = (3 x 25 + 2)/2 = 77/2 = 9 x 9 = 81 = 13 (mod 17). Then x3 = 169 - 10 = 159 = 6, y3 = 13(5 - 6) - 1 = -14 = 3. So 2G = (6, 3). Continuing gives 3G = (10, 6) and 19G = O, so G has order 19.
4. Hard problem. Given G and kG, finding k (the elliptic-curve discrete logarithm) has no sub-exponential algorithm, so a 256-bit curve matches 3072-bit RSA.
5. Use. ECDH key exchange and ECDSA signatures in TLS, Bitcoin and smart cards.

Q4 (10 marks). Describe the RSA algorithm: key generation, encryption and decryption, with a worked example, the reason that it works, the attacks on it and a comparison with Diffie-Hellman and ECC.

Introduction. RSA (Rivest, Shamir and Adleman, 1977) is the most widely taught public-key system.

It provides encryption and signatures, and its security rests on the factoring problem: multiplying two primes is easy, recovering them from the product is hard (section 4.2, Figure 4.2).

1. Key generation. Choose two large random primes p and q (Miller-Rabin tested). Compute n = pq and phi(n) = (p - 1)(q - 1). Choose e with gcd(e, phi) = 1 (commonly 65537). Compute d with ed = 1 (mod phi) by the extended Euclidean algorithm. Publish (n, e); keep d.
2. Encryption and decryption. c = m to the power e mod n, then m = c to the power d mod n.
3. Worked example. p = 61, q = 53 give n = 3233 and phi = 3120. With e = 17 the private exponent is d = 2753. For m = 65: c = 65 to the power 17 mod 3233 = 2790, and 2790 to the power 2753 mod 3233 = 65.
4. Why it works. ed = 1 + k phi(n), so (m to the power e) to the power d = m times (m to the power phi) to the power k, which is m (mod n) by Euler's theorem (the case gcd(m, n) not 1 follows by the Chinese remainder theorem).
5. Attacks. Factoring n (use at least 2048 bits); small exponent and no padding (use OAEP padding); timing and side-channel attacks (use blinding and constant-time code); reusing primes across keys (a gcd test of two public keys reveals them).
6. Practical use. RSA encrypts only short data, so it protects an AES session key; it also signs hashes.
7. Speed. Decryption with the Chinese remainder theorem is about four times faster than a direct power.

Point	RSA	Diffie-Hellman	ECC
Purpose	Encryption, signature	Key agreement	Key agreement, signature
Hard problem	Factoring	Discrete logarithm	Elliptic-curve discrete log
Key for 128-bit security	3072 bits	3072 bits	256 bits
Speed	Slow private operation	Moderate	Fast
Typical use	Certificates, signatures	TLS key exchange	Phones, smart cards, TLS

Conclusion. RSA made secure communication between strangers practical. It is now mostly used for signatures and key transport, with elliptic curves taking over where small keys and speed matter, and every system must add padding and authentication to be safe.