FIT1093 Chap.6 Diffie-Hellman, ElGamal and RSA Encryption
Diffie-Hellman, ElGamal and RSA Encryption
Week 5 turns the number theory of Week 4 into working algorithms. Diffie-Hellman key exchange, published in 1976, lets two parties agree on a shared secret using only public messages. With a public prime p and base g, Alice sends g to the power a and Bob sends g to the power b, and each raises the other's value to their own secret exponent, so both obtain g to the power ab modulo p.
The lecture notes the protocol is used across the web, VPNs, Bluetooth, 5G and the internet of things.
An eavesdropper would need to solve the discrete logarithm or Diffie-Hellman problem, but an active attacker who swaps the public values can sit in the middle and share a separate key with each victim.
ElGamal, from 1985, converts the exchange into public-key encryption: the receiver publishes a long-term public value, and for every message the sender creates a fresh ephemeral key pair, derives a shared key and encrypts the message with it.
RSA, from 1977, takes a different route based on factoring. Key generation chooses primes p and q, sets n = pq and phi(n) = (p − 1)(q − 1), picks a public exponent e coprime to phi(n) and computes the private exponent d as the inverse of e modulo phi(n).
Encryption raises the message to e modulo n, decryption raises the ciphertext to d, and Euler's theorem guarantees the round trip.
The chapter closes with practical lessons. A public key is only useful if it really belongs to its owner, which is why certificates signed by a trusted authority are needed.
Public-key operations are slower than symmetric ones but avoid key distribution, so real systems use hybrid encryption, also called a digital envelope. And textbook RSA on a small set of possible messages can be broken by encrypting every candidate, which randomisation prevents.
What this chapter covers
- 01
Diffie-Hellman key exchange and why both sides agree
- 02
The discrete logarithm and Diffie-Hellman problems
- 03
The man-in-the-middle attack on public values
- 04
ElGamal encryption with an ephemeral key
- 05
RSA key generation, encryption and decryption
- 06
RSA security and the integer factorisation problem
- 07
Certificates, hybrid encryption and small message spaces
Worked example · free
Build an RSA key from 11 and 7 and encrypt the message 5
- 2n = 11 × 7 = 77 and phi(n) = 10 × 6 = 60. The exponent 7 shares no factor with 60, so it is a valid choice.
- 2Find d with 7d ≡ 1 mod 60: 7 × 43 = 301 = 5 × 60 + 1, so d = 43.
- 2Encrypt: 5 squared is 25, 5 to the 4th is 625 ≡ 9, so 5 to the 7th ≡ 9 × 25 × 5 = 1125 ≡ 47 mod 77.
Key terms
- Diffie-Hellman Key Exchange
- A protocol in which two parties derive the same secret key from exchanged public values and their own secret exponents.
- Man-in-the-Middle Attack
- An active attack in which the adversary intercepts and replaces public keys so that each victim unknowingly shares a key with the attacker.
- Ephemeral Key
- A one-time key pair generated for a single message or session and then discarded.
- Digital Certificate
- A statement signed by a trusted certification authority that binds a name to a public key.
- Hybrid Encryption
- A combination in which public-key encryption transports a symmetric key and the symmetric cipher encrypts the bulk data.
Diffie-Hellman, ElGamal and RSA Encryption FAQ
Why do Alice and Bob get the same Diffie-Hellman key?
Alice raises Bob's value g to the b to her exponent a, and Bob raises g to the a to his exponent b. Both results equal g to the power ab modulo p, because exponents multiply in either order.
Does a larger prime stop the man-in-the-middle attack?
No. The attacker never solves a discrete logarithm; they simply replace each public value with their own. Only authenticating the public values, for example with certificates or signatures, stops the attack.
How is ElGamal different from Diffie-Hellman?
In key exchange both parties publish values first. In ElGamal only the receiver publishes, and the sender generates a fresh ephemeral key pair for every message, sends its public half with the ciphertext, and encrypts with the derived shared key.
What does an attacker need to compute the RSA private key?
The private exponent is the inverse of e modulo (p − 1)(q − 1), which requires the primes p and q. Recovering them from n is the integer factorisation problem, infeasible for large well chosen primes.
Why do real systems combine RSA with AES?
Public-key encryption is slow but solves key distribution, while symmetric encryption is fast but needs a shared key. Hybrid encryption uses the public-key step only to send a short symmetric key and then encrypts the data with it.
Assessment move
Work one complete Diffie-Hellman exchange, one ElGamal encryption and decryption, and one RSA key generation with encryption and decryption every few days until each takes only a few minutes by hand. Choose small primes yourself and check every answer by computing it a second way, from the other party's side for Diffie-Hellman or by decrypting for RSA.
For each algorithm, write which hard problem protects it and what an eavesdropper sees. Then rehearse the attack questions in words: the man-in-the-middle substitution, the hard-coded prime that hands an attacker half of the factorisation, and the small message space that lets an attacker encrypt every candidate. Being able to explain why each attack works earns as many marks as the arithmetic.
Working through Diffie-Hellman, ElGamal and RSA Encryption in FIT1093? Sia is AskSia’s AI Cybersecurity tutor — ask any FIT1093 Diffie-Hellman, ElGamal and RSA Encryption question and get a clear, step-by-step explanation grounded in how FIT1093 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
