Chapter 6 — Discrete structures

Chapter 6 — Discrete structures

Lesson map

Lesson 06 published. Map, example, EX016.

flowchart TD
  N0["Learning outcomes"]
  N1["6.1 Modular arithmetic and groups"]
  N2["6.2 The discrete logarithm"]
  N3["6.3 Diffie-Hellman by hand"]
  N4["Synthesis"]
  N0 --> N1 --> N2 --> N3 --> N4
  N4 --> EX["Worked example"]
  EX --> Q["Exercise EX016"]

Logical drawing

flowchart LR
  N0["Learning outcomes"]
  N1["6.1 Modular arithmetic and groups"]
  N2["6.2 The discrete logarithm"]
  N3["6.3 Diffie-Hellman by hand"]
  N4["Synthesis"]
  N0 --> N1 --> N2 --> N3 --> N4 --> Q["EX016"]

[Learning outcomes]
    |
    v
[6.1 Modular arithmetic and groups]
    |
    v
[6.2 The discrete logarithm]
    |
    v
[6.3 Diffie-Hellman by hand]
    |
    v
[Synthesis]
    |
    v
[Worked example] --> [Exercise EX016]

Learning outcomes

You will (1) use modular arithmetic and groups; (2) explain the discrete logarithm problem; (3) relate it to Diffie-Hellman key agreement.

6.1 Modular arithmetic and groups

Priya studies integers modulo a prime p. Multiplication modulo p, excluding zero, forms a group: it is closed, associative, has an identity and every element has an inverse. Some elements, called generators, produce every non-zero element when raised to successive powers. For p = 23 and generator 5, the powers of 5 modulo 23 cycle through all 22 non-zero values. These structures, covered in chapter 2 of the Handbook of Applied Cryptography, underlie many public-key systems and give precise meaning to operations that otherwise look like arbitrary arithmetic.

6.2 The discrete logarithm

Computing 5^x mod 23 is easy for any x, using fast exponentiation. Going backwards, finding x from the result, is the discrete logarithm problem. For tiny primes Priya can search all values, but for primes of thousands of bits no efficient classical algorithm is known. This asymmetry, easy forward and hard backward, is what public-key cryptography needs. Priya notes the word "known": security rests on the belief that the problem is hard, and Shor's algorithm would solve it on a large quantum computer, which motivates post-quantum standards such as FIPS 203.

6.3 Diffie-Hellman by hand

Priya works a toy Diffie-Hellman exchange: Alice picks secret a = 6 and sends 5^6 mod 23 = 8; Bob picks b = 15 and sends 5^15 mod 23 = 19. Alice computes 19^6 mod 23 = 2 and Bob computes 8^15 mod 23 = 2, a shared secret neither sent. An eavesdropper sees 8 and 19 but must solve a discrete logarithm. She emphasises that real systems use large groups or elliptic curves such as X25519 from RFC 7748, authenticate the exchange to stop active attackers, and run inside TLS 1.3 rather than as hand-written code. Priya repeats the calculation with a classmate to confirm both sides really reach the same value.

Worked example

Priya verifies that 5 generates the group modulo 23, computes a toy Diffie-Hellman shared secret of 2, and explains why real exchanges use X25519 inside TLS with authentication.

Synthetic case. Toy numbers only; RFC 7748 and FIPS 203 are real.

Errors and limits

Unauthenticated Diffie-Hellman is open to man-in-the-middle attacks. Toy groups are trivially breakable.

Exercises

• EX016 — Group properties. List the four group properties. Rubric: 3 = closure, associativity, identity, inverses;; 2 = three;; 1 = one;; 0 = none.
• EX017 — Toy shared secret. What shared secret did the toy exchange produce, and from which public values? Rubric: 3 = 2, from public values 8 and 19;; 2 = secret only;; 1 = wrong;; 0 = none.
• EX018 — Quantum threat. Why does Shor's algorithm matter here? Rubric: 3 = it would solve discrete logarithms on a large quantum computer, motivating FIPS 203;; 2 = quantum;; 1 = vague;; 0 = none.

Synthesis

Groups and the discrete logarithm problem explain key agreement; real systems use standard curves inside authenticated protocols.

Continue studying — chapter 06 of 40

← Chapter 05 (draft) · Course chapter index · Chapter 07 (draft) →