INFO2222 · Computing 2 Usability and Security
Public-Key Cryptography
Week 7 introduces asymmetric cryptography and why it solves the key-distribution problem: public-key encryption, digital signatures, and Diffie-Hellman key exchange, all resting on the hardness of problems like the discrete logarithm. Small modular-arithmetic items (a DH shared key, a discrete-log search) and the pk/sk role distinctions are common 2-mark and 4-mark exam questions.
What this chapter covers
- 01Why public-key crypto: the key-distribution problem — symmetric schemes need a shared secret per pair, hard to distribute
- 02Public-key encryption (PKE): encrypt with the public key pk, decrypt with the private key sk; anyone can encrypt, only sk holder reads
- 03Digital signatures: sign with sk, verify with pk — providing authenticity and integrity (the mirror of PKE)
- 04Diffie-Hellman key exchange: public g and prime p; each side derives K = g^(ab) mod p without transmitting the secret
- 05The Discrete Logarithm Problem: g^x mod p is easy forward, believed hard to reverse — the basis of DH security
- 06Key agreement (DH, both contribute) vs key transport (PKE, one party picks and encrypts the key); RSA and ECDH
- 07Forward secrecy via ephemeral keys; the man-in-the-middle attack on key exchange and fixes (certificates, pinning)
- 08Authenticated encryption compositions (Encrypt-then-MAC preferred) and end-to-end vs hop-by-hop encryption
Recover a discrete log by forward search
- +1(a) Recovering x from A = g^x mod p is the Discrete Logarithm Problem. Modular exponentiation has no inverse you can compute directly — there is no modular 'division back' and an ordinary calculator log ignores the mod p wrap-around — so no closed-form shortcut applies.
- +1(b) Brute-force forward, computing 3^x mod 17 for x = 1, 2, 3, ...: 3^1 = 3, 3^2 = 9, 3^3 = 27 ≡ 10, 3^4 = 3^3·3 = 30 ≡ 13, 3^5 = 13·3 = 39 ≡ 5. Match at x = 5.
- +1So the secret exponent is x = 5 (since 3^5 = 243 = 14·17 + 5 ≡ 5 mod 17). The only method was to test exponents until g^x matched A — forward computation is easy, reversing it is not.
- +1(c) It fails on real Diffie-Hellman because a genuine prime p is enormous (hundreds to thousands of bits): forward search would take infeasibly many trials. The gap between easy-forward and hard-backward is precisely what keeps the shared key secret.
Key terms
- Public-key encryption (PKE)
- Asymmetric encryption with a public key pk (publishable, used to encrypt) and a private key sk (secret, used to decrypt): C = Enc(pk, M), M = Dec(sk, C). Anyone can encrypt to the sk holder, enabling secure communication without pre-sharing a secret. RSA is the classic example.
- Digital signature
- The mirror of PKE for authenticity and integrity: sign with the private key, T = Sign(sk, M), and anyone verifies with the public key, Verify(pk, M, T). Only the sk holder can produce a valid signature; encryption alone gives confidentiality but not authenticity.
- Diffie-Hellman key exchange
- A protocol where two parties agree a shared secret over a public channel. With public g and prime p, Alice sends A = g^a mod p and Bob sends B = g^b mod p; each computes K = g^(ab) mod p by raising the received value to its own secret. The secret exponents are never sent.
- Discrete Logarithm Problem (DLP)
- Given g, p and y = g^x mod p, recovering x is believed computationally hard for large p, even though computing y from x is fast. DH and related schemes rest their security on this asymmetry.
- Forward secrecy
- The property that stealing a long-term private key later does not expose past sessions, because each session used a unique ephemeral (short-lived, then deleted) key. DH supports it naturally; TLS 1.3 only permits forward-secret key exchange (ephemeral ECDHE).
- Man-in-the-middle (MITM) on key exchange
- An attacker intercepts a public-key request, substitutes their own key, and relays traffic while reading or modifying it. Fixes verify the public key: digital certificates from trusted CAs (TLS), key pinning / web-of-trust (PGP), or decentralised verification.
Public-Key Cryptography FAQ
Why do we need public-key cryptography at all?
Symmetric encryption and MACs require both parties to already share the same secret key, fully protected — but distributing that key, and managing a distinct key for every conversation pair, is a hard problem. Public-key cryptography solves it: you can publish an encryption (public) key so anyone can send you confidential messages, or use Diffie-Hellman so two parties derive a shared secret over an open channel without ever transmitting it.
How does Diffie-Hellman keep the key secret if the exchange is public?
Each party keeps a private exponent and only sends g raised to it (A = g^a mod p, B = g^b mod p). Each then raises the value it received to its own secret, so both reach g^(ab) mod p. An eavesdropper sees g, p, A and B but would have to recover a from A = g^a mod p — the Discrete Logarithm Problem — which is believed infeasible for a large prime. The shared key is computed by both sides but sent by neither.
What is the difference between key agreement and key transport?
In key agreement (Diffie-Hellman) both parties contribute to the secret and it is never sent over the wire; it is jointly derived. In key transport (public-key encryption) one party chooses a key, encrypts it under the other's public key, and sends it — only one side decides the key. DH also gives forward secrecy when ephemeral keys are used, which is why modern TLS prefers it.
Can AI help me with public-key cryptography in INFO2222?
Yes, as a study aid. Sia can walk you through a Diffie-Hellman shared-key calculation or a discrete-log forward search step by step, contrast the pk/sk roles in encryption versus signatures, and explain forward secrecy and MITM defences. Use it to rehearse the modular-arithmetic drills and the concepts for the security quizzes and exam; it does not do graded assessment for you, and the University of Sydney academic-integrity policy applies.
Exam move
Practise the two small numeric skills first: a full Diffie-Hellman computation (send g^a and g^b, each raises the received value to its own secret to reach g^(ab) mod p) and a discrete-log forward search (tabulate powers until a match). Use exponentiation by squaring so you are fast under time pressure, and rehearse rejecting the shortcut distractors (no calculator log, no modular division). Then lock the role distinctions as one-liners: encrypt with pk / decrypt with sk; sign with sk / verify with pk; DH is key agreement while PKE is key transport. Understand why each exists — public-key crypto answers the key-distribution problem — and know forward secrecy and the MITM fix by certificates. Because these ideas set up the TLS chapter, learning them well pays off twice. Confirm the exam scope on Canvas.
Working through Public-Key Cryptography in INFO2222? Sia is AskSia’s AI Computer Science tutor — ask any INFO2222 Public-Key Cryptography question and get a clear, step-by-step explanation grounded in how INFO2222 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
