Jeremiah 25:26 — “The king of Sheshach shall drink after them”
ששךššk → בבלbbl
Ancient Cryptography
Caesar Wheel
Last 500 years
Vigenère Cipher
KEY
1
3
2
4
1
3
2
4
1
3
2
4
PLAINTEXT
A
T
T
A
C
K
A
T
D
A
W
N
CIPHERTEXT
B
W
V
E
D
N
C
X
E
D
Y
R
“impossible of translation” — Scientific American, 1917
Example of a substitution cipher (replacing characters)
First World War
A
D
F
G
V
X
A
c
o
8
x
f
4
D
m
k
3
a
z
9
F
n
w
1
0
j
d
G
5
s
i
y
h
u
V
p
l
v
b
6
r
X
e
q
7
t
2
g
3
4
2
1
D
G
X
G
X
G
D
G
A
A
D
D
D
G
X
G
F
X
D
G
F
D
F
A
Plaintext: attackatdawn
Intermediate Step: DGXGXGDGAADDDGXGFXDGFDFA
Ciphertext: GGDGGAXDDXDFDXADFFGGAGXD
Includes an example of a transposition cipher (reordering characters)
Second World War
Wartime Enigma Machine
at left: public domain; at right: Bundesarchiv, Bild 101I-769-0229-10A / Borchert, Erich (Eric) / CC-BY-SA 3.0, CC BY-SA 3.0 DE https://creativecommons.org/licenses/by-sa/3.0/de/deed.en, via Wikimedia Commons
Second World War
TedColes, public domain, via Wikimedia Commons
Second World War
Luftwaffe Enigma key sheet no. 649, public domain, via Wikimedia Commons
Symmetric Key Cryptography
All the systems discussed so far are symmetric key cryptosystems. Such a system consists of:
A secret key, i.e. a piece of information that allows for easy encryption and decryption, secretly shared between sender and receiver.
An encryption method, that uses the secret key to transform the plaintext (the original message, typically in a natural language such as english) into the ciphertext (the encrypted message that looks like gobbledygook to the untrained eye).
A decryption method, that uses the secret key to transform the ciphertext into the plaintext.
Problems: key distribution
Security of a cryptosystem
The keyspace is the set of all possible secret keys.
A cryptanalyst tries to break a cryptosystem.
The first, most naïve method is exhaustive search: trying all possible keys.
key
plaintext
0
WFYDAKZLWPL
1
XGZEBLAMXQM
2
YHAFCMBNYRN
3
ZIBGDNCOZSO
4
AJCHEODPATP
5
BKDIFPEQBUQ
6
CLEJGQFRCVR
7
DMFKHRGSDWS
8
ENGLISHTEXT
9
FOHMJTIUFYU
10
GPINKUJVGZV
11
HQJOLVKWHAW
12
IRKPMWLXIBX
key
plaintext
13
JSLQNXMYJCY
14
KTMROYNZKDZ
15
LUNSPZOALEA
16
MVOTQAPBMFB
17
NWPURBQCNGC
18
OXQVSCRDOHD
19
PYRWTDSEPIE
20
QZSXUETFQJF
21
RATYVFUGRKG
22
SBUZWGVHSLH
23
TCVAXHWITMI
24
UDWBYIXJUNJ
25
VEXCZJYKVOK
What’s better than exhaustive search?
The number of possible keys: \(26!\)\(> 400,\!000,\!000,\!000,\!000,\!000,\!000,\!000,\!000,\!000 = 4 \times 10^{26}\).
An eavesdropper Eve can see \(g^a\) and \(g^b\) and must compute \(g^{ab}\).
Hard Cryptographic Problems
A hard cryptographic problem is:
a mathematical problem (e.g. factoring)
which is believed to be computationally intensive to solve,
and upon which we can build a public-key cryptographic protocol such as encryption,
whose security is guaranteed by the infeasibility of solving the problem for inputs of a large size.
The idea for public-key encryption is that
encryption is easy (i.e. fast) using no secret info
decryption is easy for the intended recipient (who has extra secret info)
decryption is infeasible (i.e. too slow) for anyone else (who does not have the extra info)
For example, to decrypt a message meant for someone else, it may require factoring a number so big, that it is expected to take longer than the length of time before the sun dies.
Warning
We don’t actually know they are hard!
Hard Cryptographic Problems
The Computational Diffie-Hellman Problem:
Given \(g^a, g^b \pmod p\), compute \(g^{ab}\).
Generic algorithms take around \(\sqrt{p}\) time.
Human record: \(p\) of \(795\) bits using 3100 core-years
Standard internet security: \(2048\) bits
Logjam attack: \(512\) bits attacked in the wild
(Why did Logjam work? Big swaths of the internet were using the same prime!)
RSA: Rivest-Shamir-Adleman
The Factoring Problem:
Given an integer \(n=pq\) for \(p\) and \(q\) prime, find \(p\) and \(q\).
Human record: \(n \sim 2^{829}\).
Standard internet security: \(n \sim 2^{2048}\).
How big is \(2^{2048}\)?
How big is \(2^{2048}\)?
Estimate each quantity as a power of two (and put them in order!)
The number of atoms in the universe.
The number of cells in a human body.
The number of insects per human on earth.
The number of seconds until the sun dies.
How big is \(2^{2048}\)?
The number of insects per human on earth: \(2^{28} \sim 200\) million.
The number of cells in a human body: \(2^{45} \sim 37.2\) trillion.
The number of seconds until the sun dies: \(2^{57} \sim 7.5\) billion years.
The number of atoms in the universe: \(2^{266} \sim 10^{80} \sim 100\) quadrillion vigintillion.
More modern cryptography: Elliptic Curve Cryptography
Do your computations with a crazy group called an
elliptic curve.
The Quantum Age
When will we have quantum computers?
The unit of measure is decades.
What can they do?
They can factor and solve discrete logarithm too quickly: break all of current cryptography.
What are we doing about it?
NIST has standardized new protocols (ML-KEM, ML-DSA, SLH-DSA in 2024; FN-DSA and HQC on the way) based on new hard problems that are believed to be quantum-safe.
We will study quantum cryptography, quantum algorithms and post-quantum cryptography.
Bonus: Whirlwind tour of coding theory
Image: the editors of encyclopedia britannica, CC BY-SA 4.0 https://creativecommons.org/licenses/by-sa/4.0, via Wikimedia Commons
Coding Theory
What is coding theory for? (What problem are we solving?)
Real-life channels (radio, cell phone, copper wires) are noisy.
We want to send messages in such a way that errors won’t prevent understanding.
Usually we model a channel as something that randomly flips bits of our binary message (errors).
Nothing to do with secrecy.
Coding Theory
What is coding theory?
We change our message (encoding) so that it is error resistant.
We send codewords instead of plaintext symbols.
Example: ‘Victor’ instead of ‘V’ (radio) or ‘000’ instead of ‘0’ (a repeat code)
The receiver must decode
Coding Theory
What makes a good code?
Strong error correction: the number of errors a codeword can absorb and still be guessed correctly (e.g. ‘010’ is probably ‘0’ not ‘1’)
Strong efficiency: not too much space inflation (codewords are longer than the symbols they represent)
What math goes into it?
Finite fields, linear algebra
Your semester ahead
About me: a number theorist and cryptographer (cryptanalyst mostly) studying post-quantum cryptography, elliptic-curve cryptography etc.
