← Back to the reading view
Slides · 14 slides
The math underneath: modular arithmetic & one-way functions
The same module told visually, ready to present. Speaker notes carry the full explanation.
Foundations
The math underneath
Modular arithmetic and one-way functions: easy one way, effectively impossible the other
The math underneath: modular arithmetic & one-way functions · Classical Crypto Today1 / 14
The core idea
One-way functions
The math underneath: modular arithmetic & one-way functions · Classical Crypto Today2 / 14
Clock arithmetic
Arithmetic that wraps around
The math underneath: modular arithmetic & one-way functions · Classical Crypto Today3 / 14
Division, mod n
Inverses: multiply instead of divide
The math underneath: modular arithmetic & one-way functions · Classical Crypto Today4 / 14
c. 300 BCE
Euclid's algorithm: gcd without factoring
The math underneath: modular arithmetic & one-way functions · Classical Crypto Today5 / 14
The extended version
Run Euclid backwards to find the inverse
The math underneath: modular arithmetic & one-way functions · Classical Crypto Today6 / 14
Fast exponentiation
Square-and-multiply: 5¹³ mod 19
The math underneath: modular arithmetic & one-way functions · Classical Crypto Today7 / 14
The identity RSA runs on
Fermat and Euler
The math underneath: modular arithmetic & one-way functions · Classical Crypto Today8 / 14
Square roots, mod p
Quadratic residues: which numbers have square roots?
The math underneath: modular arithmetic & one-way functions · Classical Crypto Today9 / 14
Chinese Remainder Theorem
Two remainders pin down one number
The math underneath: modular arithmetic & one-way functions · Classical Crypto Today10 / 14
Abstraction
Groups: one algorithm, many settings
The math underneath: modular arithmetic & one-way functions · Classical Crypto Today11 / 14
Public and private keys
Trapdoors: a shortcut for the key-holder
The math underneath: modular arithmetic & one-way functions · Classical Crypto Today12 / 14
Three hard problems
Three one-way functions, one idea
The math underneath: modular arithmetic & one-way functions · Classical Crypto Today13 / 14
What 'hard' means
Computationally hard, not impossible
The math underneath: modular arithmetic & one-way functions · Classical Crypto Today14 / 14
1 / 14
Keys: ← → move, F full screen, G all slides, N notes