Chapter 1 — Calculus I

Lesson map

Lesson 01 published. Map, example, EX001.

flowchart TD
  N0["Learning outcomes"]
  N1["1.1 The case and why growth matters"]
  N2["1.2 Logarithms tame huge numbers"]
  N3["Lab — Exhaustive-search time"]
  N4["1.3 Reading the estimate"]
  N5["Synthesis"]
  N0 --> N1 --> N2 --> N3 --> N4 --> N5
  N5 --> EX["Worked example"]
  EX --> Q["Exercise EX001"]

Logical drawing

flowchart LR
  N0["Learning outcomes"]
  N1["1.1 The case and why growth matters"]
  N2["1.2 Logarithms tame huge numbers"]
  N3["Lab — Exhaustive-search time"]
  N4["1.3 Reading the estimate"]
  N5["Synthesis"]
  N0 --> N1 --> N2 --> N3 --> N4 --> N5 --> Q["EX001"]

[Learning outcomes]
    |
    v
[1.1 The case and why growth matters]
    |
    v
[1.2 Logarithms tame huge numbers]
    |
    v
[Lab — Exhaustive-search time]
    |
    v
[1.3 Reading the estimate]
    |
    v
[Synthesis]
    |
    v
[Worked example] --> [Exercise EX001]

Learning outcomes

You will (1) read growth rates as the language of cryptographic strength; (2) use logarithms to compare enormous quantities; (3) estimate exhaustive-search time for key lengths.

1.1 The case and why growth matters

Aiyana Torres is a first-year engineering student at the fictional Halden Institute of Engineering. Over five years she will help the fictional Ridgeway Water Utility design how its 50,000 smart water meters authenticate readings and accept firmware updates, mentored by utility engineer Marcus Webb. Every meter, key and figure in this book is synthetic. Calculus begins with rates of change, and cryptography depends on one rate above all: how fast the work to guess a key grows as the key gets longer. Linear growth adds a fixed amount per step; exponential growth multiplies. Key search is exponential, and that difference is why a few extra bits protect so much.

1.2 Logarithms tame huge numbers

A 128-bit key has 2^128 possible values, about 3.4 × 10^38, a number too large to picture. Logarithms turn multiplication into addition: log10(2^128) = 128 × log10(2), roughly 38.5. Aiyana learns to compare security levels by comparing exponents, not raw numbers. The derivative of 2^x is ln(2) × 2^x, so the growth rate is itself proportional to the current size, the signature of exponential behaviour. When engineers say a key length offers "128-bit security", they mean an attacker needs work on the order of 2^128 operations, and Katz and Lindell use the same convention when they define concrete security.

Lab — Exhaustive-search time

"""Exhaustive-search time for key lengths at a hypothetical 10^12 guesses per second (synthetic rate)."""
import math
RATE = 10**12
YEAR = 365.25 * 24 * 3600

def main():
    for bits in (40, 56, 80, 128):
        years = 2 ** (bits - 1) / RATE / YEAR  # expected half the space
        print(f"{bits:>3}-bit key: log10(years) = {math.log10(years):6.2f}")
    print(f"each extra bit multiplies work by {2 ** 1}; 10 extra bits by {2 ** 10}")

if __name__ == "__main__":
    main()

Run with python3 lab_keyspace.py. Verified output:

 40-bit key: log10(years) =  -7.76
 56-bit key: log10(years) =  -2.94
 80-bit key: log10(years) =   4.28
128-bit key: log10(years) =  18.73
each extra bit multiplies work by 2; 10 extra bits by 1024

1.3 Reading the estimate

At a hypothetical trillion guesses per second, a 40-bit key falls in a fraction of a second (log10 of years about -7.8) and a 56-bit key, the length of the retired DES cipher, in about a day (log10 about -2.9). An 80-bit key needs around nineteen thousand years, and a 128-bit key about 10^18.7 years, far longer than the age of the universe. Each extra bit doubles the work and ten extra bits multiply it by 1,024. Aiyana notes that the rate is invented and that real attackers improve, which is why standards such as AES in FIPS 197 start at 128 bits rather than at the edge of feasibility.

Worked example

Aiyana tabulates search times for 40, 56, 80 and 128 bits, compares them by their base-10 logarithms, and recommends that Ridgeway never accept meter keys below 128 bits.

Synthetic case. Ridgeway, its meters and the guess rate are invented; FIPS 197 is the real AES standard.

Errors and limits

Exhaustive search is only one attack; a long key does not help if it is stored badly or generated from a weak random source. Logarithmic estimates are orders of magnitude, not schedules.

Exercises

• EX001 — Exponential versus linear. Why is key search described as exponential rather than linear in key length?
  Show marking criteria

  Rubric: 3 = each extra bit doubles the number of keys, so work multiplies;; 2 = "grows fast";; 1 = linear answer;; 0 = none.
• EX002 — Key-search logs. Using the lab, give the base-10 log of expected years for 56-bit and 128-bit keys.
  Show marking criteria

  Rubric: 3 = about -2.94 and 18.73;; 2 = one right;; 1 = wrong sign;; 0 = none.
• EX003 — Why start at 128. Why does Aiyana recommend at least 128-bit keys for meters?
  Show marking criteria

  Rubric: 3 = 2^127 expected work is infeasible with margin; matches FIPS 197 minimum;; 2 = "safer";; 1 = 56 bits enough;; 0 = none.

Synthesis

Calculus gives engineers the vocabulary of growth; exponential key spaces, compared through logarithms, explain why modern keys start at 128 bits.

Continue studying — chapter 01 of 50

← Course home · Course chapter index · Chapter 02 (draft) →