Lecture Notes on The Code Book by Simon Singh
... for the class
Codes, codemakers, codebreakers:
an introduction to cryptography.
[Stuff inside square brackets is not in Singh's text.]
extra stuff
sequential homophonic cipher
black chamber 48bce
black chamber 900
black chamber 1500
black chamber 1599
black chamber 1918
black chamber 1860
black chamber 1918
black chamber 1942
black chamber: one-time-pad evolution
context for reading this book
- science/history crypto course based on Singh's book
- def'ns
cryptography
history
science
- George Santayana 1905 those who cannot remember the past are condemned to repeat it
- how to read book? curiosity, scepticism, pencil, library
- pov? British
Introduction to The Code Book by Simon Singh
- dedication: Sawaran Kaur, Mehnga Singh
- epigraph: John Chadwick ... urge to discover secrets
knowledge is power Francis Bacon 1597
-
For thousands of years,
kings, queens and generals have relied on efficient communication
to govern their countries and command their armies ...
- obj. 1: chart
evolution
of codes
codemaker ... codebreaker ... codemaker ... codebreaker ...
- obj. 2: show subject more relevant today than ever before
cell phone computer networks email privacy v law/order
- code: secret comm'n, word ↔ word/symbol
cipher: secret comm'n, letter ↔ letter/symbol
plaintext: message
ciphertext: encrypted message
Cipher of Mary Queen of Scots
- 1586 Oct 15 Fotheringhay Castle Mary v Elizabeth I Queen of England
Evolution of Secret Writing
- Herodotus Histories
- Persia v Greece c 480 BC, Xerxes v Demaratus, waxed tablets
- Persia v Miletus c 499 BC, Histaiaeus, shaved head
- steganography covered/concealed writing
- cryptography hidden/scrambled writing
- ignoring spaces, more than 5*1034 rearrangements of
for example consider this short sentence
- easier: rearrangements of to be
beot ebot o... t...
beto ebto o... t...
boet eobt o... t...
bote eotb o... t...
bteo etbo o... t...
btoe etob o... t...
- rearrangements of to boot ?
t1
o1
b1
o2
o3
t2
6! / (2! * 3!)
- rearrangements of for example consider this short sentence ?
- 35 letters, distributed as:
a b c d e f g h i j k l m n o p q r s t u v w x y z
1 0 2 1 6 1 0 2 2 0 0 1 1 3 3 1 0 3 4 3 0 0 0 1 0 0
how many rearrangements of a 1-2-1-6-2-2-1-1-3-3-1-3-4-3-1 multiset?
35! /
(1! * 2! * 1! * 6! * 2! * 2! * 1! * 1! * 3! * 3! * 1! * 3! * 4! * 3! * 1! )
encryption/decryption
- encryption: plaintext,key => ciphertext f_k(p) = c
- decryption: ciphertext, key => plaintext f_k-1(c) = p
- security? ease of use?
transposition cipher
- ease of use => alg'm
- Spartan scytale c400 BC: Lysander v Pharnabazus
s e n d m o r e
\t \r \o \o \p \s \t \o
\s \o \u \t \h \e \r \n
\f \l \a \n \k \x \q \i
stsferolnouadotnmphkosexrtuqeoni
r i f n e i h r
\ /\ /\ /\ /\ /\ /\ /\
\a/ \l/ \e/ \c/ \c/ \p/ \e/ \
rifneihraleccpe
substitution cipher
- Vãtsyãyana Kama Sutra
400BC-4xxAD
art #45: mlecchita-vikalpā secret
writing (e.g. letter pair)
- Julius Caesar
De Bello Gallico V:XLVIII
a b c ...
α β γ ...
- Valerius Probus ... on Caesar's ciphers :(
- Suetonius
De Vita Caesarum: Divus Iulius LVI
Caesar cipher
abcdefghijklmnopqrstuvwxyz 3-shift Caesar cipher
DEFGHIJKLMNOPQRSTUVWXYZABC 3-VKLIW fDHVDU FLSKHU
- Caesar shift: ease of use? yes security?
no (only 25 versions/keys)
- Kerchoff 1883 cyptosystem security must not rely on alg'm secrecy
- substitution: security? yes
4 * 1026
versions/keys ease of use? alg'm?
- keyphrase substitution e.g. Mary, Queen of Scots
abcdefghijklmnopqrstuvwxyz how secure is this?
MARYQUENOFSCTVWXZBDGHIJKLP NWJ DQRHBQ OD GNOD?
Arab cryptanalysts: linguistics, statistics, religious devotion
- evol'n: ... substitution cipher ! (unbreakable?)
- 610 Muhammad
- 750 Abassid caliphate: conquest? no
- consolidation ... arts/sciences flourished in equal measure
- ↓ tax => ↑ commerce
stricter law => ↓ corruption, ↑ protection
- needed:
administration =>
communication =>
cryptography
- monoalphabetic substitution cipher
- every Muslim required to pursue ilm
in all forms
- acquire knowledge? translate ancient texts
- Egypt, Babylon, India, Persia, Syria, Armenia, Judea
- Baghdad: Bait al-Hikmah (library/translation centre)
- disperse knowledge? paper (China)
warraqin
- study Koran
- chronology => word frequency,
etymology, syntax, statistics, phonetics
- al-Kindi Manuscript on Deciphering Cryptographic Messages
- frequency analysis
- measure language letter frequency
- match with ciphertext letter frequency
cryptanalysing a ciphertext
- letter frequency => k-gram frequency
- letter doubles: (English) ss ee tt ff ll mm oo
- 2-letter words: (English) of to in it is ...
- 3-letter words: (English) the and
- tailor language frequency to message domain
- guess words/phrases
UANQ PILDNDC, PF HNC OANBS (T CNLB) SNS TQM THIVU PF
OLFJUICLTJAF OBTQQ. N QTNS UATU FIV TBB PVQU SI T UANLUF
YILS QUILF YNUAIVU VQNDC T JTLUNOVBTLBF OIPPID YLNUNDC
QFPHIB (N'P AIJNDC UATU FIV CLTQJ YATU N'P QTFNDC). QI
PF HNC OANBS TDS PF QPTBB OANBS (TBQI T CNLB) QUTLU
UANQ UTQM LNCAU TYTF.
English history
- source: Kings & Queens, the concise guide by Richard Cavendish
- 10000 BC hunter/gatherers
- 6500 BC ice melt => islands (defence)
- 4500 BC farming (fertile)
- 600 BC Celts iron age, chariots, European trade
- 55 BC -- 407 AD Romans uni-culture/religion(C)/lang(L),
roads, sewage/drainage, cities, gov't inst'ns, Romano/Brit elite
- Picts/Caledonians (north); Scotti (Ire.); Angles/Saxons (Germ.)
- 430-800 AD Saxon Eng.
- 800-1066 preconquest Eng: Vikings, Alfred etc. (Cnut the Dane 1016-1042)
- 1066-1154 Normans (inc. Henry I)
- 1154-1399 Angevins/Plantagenets
- 1399-1485 Lancaster/York
- 1485-1603 Tudors (Henry VII Henry VIII Edward VI Mary I Eliz I)
-
list of English monarchs
renaissance in the west
- monasteries, religion, bible ( atbash )
- 12xx Roger Bacon
Epistle on the Secret Works of Art and the Nullity of Magic
- a man is crazy who writes a secret in any other way than
one which will conceal it from the vulgar
- 13xx alchemists/scientists (Da Vinci, Chaucer)
- art/science/scholarship renaissance + politics => cryptography
- Giovani Soro Venice 1506
- Philibert Babou Francis I
- François Viète and Philip II of Spain
- nulls, mispelling (nonstandard), nomenclator
Babington plot
- historical background
- devolution of monarch power
(Henry I: Charter of Liberties;
John: Magna Carta; ... )
- tenuous reign of female monarchs
(White Ship/Matilda; Lady Jane Grey; Mary I; Elizabeth I)
- 1542 Henry VIII v Scots @ Solway Moss b Mary d James V
- 1543 Mary crowned
- Henry VIII: wooing Mary -?- Edward
- Scots: Mary -?- Francis, Dauphin of France
- Henry VIII: rough wooing
- 1548 Mary -> France
- 1559 Mary + Francis, King & Queen of France
- 1560 Mary widow
- 1561 Mary -> Scotland
- 1565 Mary + Henry Stewart, Earl of Darnley
- 1566 Darnley murders David Riccio
- 1567 boom ... d Darnley ... Mary + Bothwell ...
abdicates to infant son James VI ... imprisoned
- 1568 escape, battle Langside ... flee E (half-brother)? flee S
(Eliz) ?
- 1568 Mary imprisoned in England
- 1586 Jan 6
Gifford -> Mary: mail
- 1585 I have heard of the work you do ...
-
Walsingham
- cryptography: book by Cardano
- 1577: Philip II Spain plan to invade England thwarted by cryptan's
- cipher school London Thomas Phellipes
- 1586 July 17 Mary replies to
Babington
via Gifford
- Gifford -> Walsingham -> Phelippes + ps -> W -> G -> Babington
- gruesome end
Babington plot
- 1587 Feb 8 d Mary
le chiffre indéchiffrable
W H I T E W H I T E W H I T E W H I T E W H I
d i v e r t t r o o p s t o e a s t r i d g e
Z P D X V P A Z H S L Z B H I W Z B K M Z N M
abcdefghijklmnopqrstuvwxyz
bcdefghijklmnopqrstuvwxyza
cdefghijklmnopqrstuvwxyzab
defghijklmnopqrstuvwxyzabc
efghijklmnopqrstuvwxyzabcd
fghijklmnopqrstuvwxyzabcde
ghijklmnopqrstuvwxyzabcdef
hijklmnopqrstuvwxyzabcdefg
ijklmnopqrstuvwxyzabcdefgh
jklmnopqrstuvwxyzabcdefghi
klmnopqrstuvwxyzabcdefghij
lmnopqrstuvwxyzabcdefghijk
mnopqrstuvwxyzabcdefghijkl
nopqrstuvwxyzabcdefghijklm
opqrstuvwxyzabcdefghijklmn
pqrstuvwxyzabcdefghijklmno
qrstuvwxyzabcdefghijklmnop
rstuvwxyzabcdefghijklmnopq
stuvwxyzabcdefghijklmnopqr
tuvwxyzabcdefghijklmnopqrs
uvwxyzabcdefghijklmnopqrst
vwxyzabcdefghijklmnopqrstu
wxyzabcdefghijklmnopqrstuv
xyzabcdefghijklmnopqrstuvw
yzabcdefghijklmnopqrstuvwx
zabcdefghijklmnopqrstuvwxy
cj = ( pj + kj mod κ ) mod α
shunning Vigenére to Man in Iron Mask
- smooth exp. ciphertext letter distr'n
- homophonic subst'n cipher
a 09 12 33 47 53 67 78 92
b 48 81
c 13 41 62
d 01 03 45 79
e 14 16 24 44 46 55 57 64 74 82 87 98
f 10 31
... ...
x 28
y 21 52
z 02
Antoine/Bonaventure Rossignol
- 1626 decipher Huguenot msg
- Great Cipher of Louis XIV syllabic subst'n
- 1890 Victor Gendron => Étienne Bazeries
- 1698 Bastille, man in iron mask: General Vivien de Bulonde ?
black chambers
- 1700s industrialized cryptanalysis
- Vienna Geheime Kabinets Kanzlei
- cryptanalysis: black chambers => cryptographers:
polyalphabetic ciphers
- 1800s telegraph
- Vigenère: le chiffre indéchiffrable
Babbage v Vigenère
- b 1791, eccentric, ind. wealthy, marr. wout perm'n
- speedometer, cowcatcher, tree ring width, statistics, mortality tables
- fixed price stamps, street musicians
- I wish t Gd ths calc'ns h bn exec'td b steam!
- 1821 difference engine #1 25K parts £17470
- 183? difference engine #2
- 1854 Jn Hall Brock Thwaites J Soc Arts Letters new cipher
- Babbage: very old
- Thwaites: so break it!
- ?1854 Vigenère cryptanalysis
- find keyword length k (distance btwn repeated ctext fragments)
- for each k'th ctext subsequence, find shift (freq anal's)
- unpub Philosophy of Decyphering [20th century]
- 1863 Fr. W'm Kasiski Die Geheimschriften und die Dechiffrir-kunst
- nota bene
- computer program: index of coincidence
- running key cipher: Vig', w long keyword (e.g. use book)
agony columns to buried treasure
- telegraph => public interest in cryptography
- Vict'n England + romance? => agony columns
- Babbage / Charles Wheatstone / Lyon Playfair
- Dear Charlie, Write no more. Our cipher is discovered.
- unintended consequence of postal fees: pinprick cipher (Aeneas
the Tactician)
- 19th/20thC literature
- Jules Verne Journey t t Centre o t Earth, Mathias Sandorff
- Conan Doyle Adventure of t Dancing Men
- Edgar Allan Poe Gold Bug
- John Buchan 39 Steps (esp. Fast Fiction #5 comic)
Beale saga
- source Beale Papers 1885 (price 50 cents)
- Robert Morriss propr. Washington Hotel, Lynchburg Va
- 1820 Thomas J. Beale in town Jan--Mar
- 1822 Thomas J. Beale in town Jan--Mar, leaves locked box
- 1832 no letter arrives
- 1845 Morriss opens box, 3 mystery ciphers
- 1862 (age 84) Morriss confides in friend
- 1885 anonymous friend authors pamphlet, James B. Ward publ'r
- ciphers
- \#1: ?? [location]
- \#2: book cipher (US Decl'n Indep') [story]
- \#3: ?? [people]
- cryptanalysts
- Herbert O. Yardley [US Cipher Bureau]
- Col. W'm Friedman [US Signal Intell. Serv.]
- Carl Hammer [Sperry Univac]
- 1960s Beale Cipher and Treasure Association
- Louis Kruh [debunk: textual analysis]
mechanisation of secrecy
- end 18xx:
cryptanalysis :) cryptography :(
- Babbage, Kasiski
- telegraph traffic ↑
- Marconi 1894 radio 1896 Britain 1901 Cornwall-Nfld (!? ionosphere)
- GW (aka WWI)
- 4C BC Sun-Tzu Art of War
nothing ... as fav'bly/gen'ly rewarded/confidential as ... intelligence
- 1870: Napolean III => Prussia ... + Bavaria !! => Alsace/Lorraine
- crytpo: France ↑ Germany ↓
- Morse fist + radio triangulation => battalion location
- Kerchoffs La Cryptographie Militaire
- 1918: ADFGVX cipher rush munitions even by day if not seen
- Georges Painvin
- evolution of ADFGVX?
Polybius
- @wikipedia
- Polybius c203-120 BC historian
- Polybius grid (origin: telegraphy)
1 2 3 4 5
1 a b c d e
2 f g h i/j k
3 l m n o p
4 q r s t u
5 v w x y z
23 34 52 24 43 44 23 15 35 34 31 54 12
24 45 43 22 42 24 14 45 43 15 21 45 31
24 33 44 15 31 15 22 42 11 35 23 54 ?
1 2 3 4 5 6
1 a b c d e f
2 g h i j k l
3 m n o p q r
4 s t u v w x
5 y z 0 1 2 3
6 4 5 6 7 8 9
Playfair cipher (Appendix E)
- developed c 1854 Charles Wheatstone
- popularized Baron Lyon Playfair
- used 2nd Boer War, WWI, WWII
- encrypt
- break plaintext into digraphs
- ensure no double letter digraph by inserting x
- use keyword-scrambled Polybius grid
- same row? shift right
- same column? shift down
- diff't row/col? each: same row, other col
C H A R L
E S B D F
G I/J K M N
O P Q T U
V W X Y Z
plaintext: retreat left ??????????
re tr ea tl ef tx ?? ?? ?? ?? ??
ciphertext: CD YD BC UR SE QY BC DW UP PF GC
- decrypt ? some ambiguity
- cryptanalysis: digram frequency analysis
LP YN UG DZ UC PA DS OT MS AE SE CU DH NK BU UC ES TG YD
ADFGVX cipher (Appendix F)
. _
_ . .
. . _ .
_ _ .
. . . _
_ . . _
- Germany 1918
- encrypt
- phase 1
Polybius grid subst'n: p'text pairs => ADFGVX indices
- phase 2
columnar transposition (like scytale), keyword-permuted
A D F G V X
A 8 P 3 D 1 N
D L T 4 O A H
F 7 K B C 5 Z
G J U 6 W G M
V X S V I R 2
X 9 E Y 0 F Q
keyword: CUBE
c r a c k e d b y ? ? ? ? ? ? ? ? ? ? ? ? ? ?
FG VV DV FG FD XD AG FF XF ** ** ** ** ** ** ** ** ** ** ** ** ** **
C U B E => B C E U
F G V V VFXF*******FDFAX*******VGDF*******GVDGF*******
D V F G
F D X D
A G F F
X F * *
* * * *
* * * *
* * * *
* * * *
* * * *
* * * *
* *
ADFGVX cryptanalysis
v d g g f x x g g d d v d f g g d g g v d d f d x d d v v v d d f x a g a a a x
v d d d
d v d d
g d f f
g f d x
f g x a
x g d g
x d d a
g g v a
g g v a
d v v x
-
:) :) :) :)
grid and keyword known?
-
:) :) :)
grid and keysize known?
example below
-
:) :)
grid known?
-
:)
keyword known?
-
:)
keysize known?
grid: see Appendix F keysize: 4
VFXFGDGVDAVFDFAXXVXAVVAVGDFVGVDVXGGVDGFDVDDGFX
----------------------------------------------
perm? was 1234? e.g. keyword ARTY
12 chars 12 chars 11 chars 11 chars
VFXFGDGVDAVF DFAXXVXAVVAV GDFVGVDVXGG VDGFDVDDGFX
VDGVFFDD ... => s g b t ... :(
----------------------------------------------
perm? was 1243? e.g. keyword ARTS
12 chars 12 chars 11 chars 11 chars
VFXFGDGVDAVF DFAXXVXAVVAV GDFVGVDVXGG VDGFDVDDGFX
VDVGFFDD ... => s i b t ... :(
----------------------------------------------
perm? ...
:(
----------------------------------------------
perm? .... was 3142? e.g. keyword CUBE
11 chars 12 chars 11 chars 12 chars
VFXFGDGVDAV FDFAXXVXAVVA VGDFVGVDVXG GVDGFDVDDGFX
FGVVDVFG ... => c r a c ... :)
Zimmermann affair
- 1915 Lusitania
- 1917 Jan 16 telegram to ambassador/Washington
- Britain: room 40
- 1917 Feb 1 unrestr. naval warfare
- 1917 Feb 3 America stays neutral !?
- 1917 Feb 23 Br => Mexican telegram to Am ambassador
- 1917 Apr America to war
holy grail: 1-time pad
- running key cipher: cryptanalysis?
- Maj. Joseph Mauborgne, US Army, 1918
evolution of 1-time pad
D D D D D D D D D D D D
c a e s a r c i p h e r
F D H V D U F L S K H U
abcdefghijklmnopqrstuvwxyz
DEFGHIJKLMNOPQRSTUVWXYZABC
abcdefghijklmnopqrstuvwxyz
BLIZARDWNGHJKMOPQSTUVXYCEF
k e y p h r a s e s u b s t i t u t i o n c i p h e r
H A E P W S B T A T V L T U N U V U N O M I N P W A S
S E C R E T S E C R E T S E
v i g e n e r e c i p h e r
N M I V R X J I E Z T A W V
A N H I S T O R I C A L I N T R
r u n n i n g k e y c i p h e r
R H U V A G U B M A C T X U X I
Q T X P L K G G U R E M P D W X
o n e t i m e p a d c i p h e r
E G B I T W K V U U G U E K A O
equiprobable keys, equiprobable plaintexts
? ? ? ? ? ?
? ? ? ? ? ?
C T F Q Q R
C-H T-E F-L Q-P Q-M R-E C-G T-O F-A Q-W Q-A R-Y
h e l p m e g o a w a y
C T F Q Q R C T F Q Q R
reuse of 1-time pad: appendix G
cipher machines -- cipher discs to Enigma
- calculating machines
- abacus, slide rule, adding machine
- cipher disc
- 14xx Alberti 18xx US Civil War 19xx Code-o-graph
- rotor (rotating scrambler) cipher machine
- 1919 Alexander Koch Netherlands
- 19?? Arvid Damm Sweden
- 192? Edward Hebern US
Sphinx of the Wireless
- 1918 Arthur Scherbius, Richard Ritter Enigma
- Enigma plugboard/rotor-based running key cipher machine
- keyboard => rotor ... rotor => lampboard
- reflector (so e = e-1)
- 12-plug board (so more keys)
- ring
- number of keys?
- 263 * 3! * (26 choose 12) * (11 * 9 * 7 * 5 * 3)
- need? 1923 British WWI hist: Zimmermann affair
- 1925-45 German military 30,000 Enigma machines
cracking Enigma
- post-WWI cyptanalysis
- Br/Fr/Am :)
1926 ?? :( lean/hungry => fat/lazy
- Germany ← Poland → Russia => Biuro Szyfrów
- Maksymilian Ciezki + Monsieur Rex + Rudolph & Hans-Thilo Schmidt
- 1931 Schmidt ↔ Monsieur Rex: Enigma info (inc. scrambler wirings)
- daily key info
- plugboard pairings, eg. AL PR TD BW KF OY
- scrambler arrangement, eg. 231
- scrambler orientations, eg. QCW
- message protocol: new orientation for each message
e.g. PGH => message preface eQCW(PGHPGH) = KIVBJE
- Biuro Szyfrów:
crypto course at Poznán ... Marian Rejewski (+2?)
- exploit doubling of encrypted day orientation
L O K R G M A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
M V T X Z E P M R X
J K T M P E
D V Y P Z X
. . . . . .
F Q H P L W O G B M V R X U Y C Z I T N J E A S D K
- represent daily permutation as product of cycles
A -> F -> W -> A
B -> Q -> Z -> K -> V -> E -> L -> R -> I -> B
C -> H -> G -> O -> Y -> D -> P -> C
J -> M -> X -> S -> T -> N -> U -> J
- permutation cycle "fingerprint" 3,7,7,9 independent of plugboard pairings
- 26^3 * 3! = 105,456 scrambler orientations
- replicate Enigma, catalogue fingerprints of 105,456 orientations (1 year)
- plugboard pairings? start w no pairings ...
- exercise: complete the Rejewksi "fingerprints" for the data below
V E C J I B rotors 123, start DDN
E W O P F A
K D A L Y T 1-4:
L C V T E O A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
B A H Q D Z J
J Y S I B Y
T I Q W V P
Q X E Y R Q
P G Y F A V 2-5:
F Q P A L R A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
C R M U Q N I
D U R C J M
Z Z K N U L
Y O U M W K
X N B S S D 3-6:
I T J B T G A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
H J G E K H B
U K L V H J
W V F O O U
G P X D P C
R L N K M S
A S D R G I
S B Z G N X
O H T Z Z W
N F I H C F
M M W X X E
Poles pass baton ...
- German modifications => catalogue obsolete => automate: 6 bombes
- 17,576 settings, 2 hours to crack day key
- BS chief Maj. Gwido Langer had day-keys fr Rex fr Schmidt
- 1938-39
- 3+2=5 scramblers (5 choose 3) * 3! = 60 perm'ns :(
- 6+4=10 cables
- where's Schmidt?
- blitzkrieg speed of attack through speed of communication
- Langer => Br/Fr: Enigma starter kit !!!
geese that never cackled
- Room 40 => GCCS, Bletchley Park (exp. 2 million words/day)
- Alastair Denniston
- ling'sts, class'sts, puzz'sts + math'ns, sci'sts
- old Oxbridge boys/girls
- few hours to crack day key
- shortcuts
- first try cillies
- each scrambler changed from previous day (60 => abt half)
- 19xx mathematics
- 1900 David Hilbert's problems (2. compatibility of arithmetic axioms)
- 1931 Gödel undecidability
- 1936 Denes König: 1st graph theory book
Alan Turing
- b 1912 London (parents → India)
- 1926 Sherbourne by bicycle (met Chris Mercom, d 1930)
- 1931 King's College, Cambridge
- 1937 On Computable Numbers TM/UTM Entscheidungsproblem
- 1939 Bletchley Park
Rejewski and Enigma
- exploit initial 6-gram of each message: repeated 3-gram, encrypted with day key
- use e1(p) ↔ e4(p);
e2(p) ↔ e5(p);
e3(p) ↔ e6(p);
to categorize rotor slotting/setting
- factors out plugboard pairings
Turing and Enigma
- expected Germans to stop repeating 3-gram
- exploit probable ptext/ctext cribs see p175
- use ptext/ctext loops to categorize scrambler settings
- factors out plugboard pairings
- ptext/ctext crib alignment: e(x) ≠ x (??) see p177
Bletchley Park
- 6 Sep 1941 Churchill visit
- Turing wants more staff; BP Commander Travis: no
- 21 Oct 1941 Dear Prime Minister ...
- Churchill: make sure ... all they want ... extreme priority
- 1942 49 bombes, Gayhurst Manor
- Daily Telegraph crossword in under 12 minutes? (6 out of 25)
Turing's crib circuit method (assuming no ring)
- given crib plaintext and ciphertext, find a possible alignment
...wettervorhersage........
KVBVRBCPZFQFNTTQEQOGYIIOYNG
- construct the Turing graph for this alignment:
join two letters if there is some position in which one is enciphered as the other
G P A Z
| \| |
S--Q--O--E--R--F--V--W H--N
| /
|/
C--T--B
-
find a cycle in the Turing graph (also known as a Turing bombe menu)
here: only cycle is E->R->T->E at positions 5,15,14,5
- use the bombe: input 5-15-14-5 output below
rotors I-II-III start Z-U-B
cycle 5-15-14-5 H-W-N-H
....H........NW intxt
....W........HN outtxt
- next step ... ?
deduce plugboard settings
-
setup Enigma: I-II-III, Z-U-B, no plug-pairs to start
KVBVRBCPZFQFNTTQEQOGYIIOYNG ctxt
XFXTVNNHQZLWJYDSGGYMUHTGEYT ptxt (no plugboard pairs)
...wettervorhersage........ desired ptxt
-
no plug-pairs: cycle 5-15-14-5 H->W->N->H
all plug-pairs: cycle 5-15-14-5 E->R->T->E
so start with plug-pairs EH WR NT
apply these rules
- position j: ptext/ctext x:Y correct =>
no further pairing uses x or Y
- position j: ptext/ctext x:Y incorrect =>
further pairing uses x and/or Y
KVBVRBCPZFQFNTTQEQOGYIIOYNG ctxt
XFXNETTEQZLRHERSJGYMUENGHEN ptxt (pairs EH WR NT)
...wettervorhersage........ desired ptxt
++++ +++++ + <- ok psns, so BC EFGH PQRST ok
? <- F:Z, F ok, so must be pair VZ
KVBVRBCPZFQFNTTQEQOGYIIOYNG ctxt
XXXWETTERVLRHERSJGYMUENGHEN ptxt (pairs EH WR NT VZ)
++++++?+++++ + <- Q:L, Q ok, so pair LO
++++++ +++++?+ <- E:J, E ok, so pair AJ
KVBVRBCPZFQFNTTQEQOGYIIOYNG ctxt
XXXWETTERVORHERSAGEMUENCHEN ptext (pairs EH WR NT VZ LO AJ)
kidnapping codebooks
- networks: Afrika, Luftwaffe, Kriegsmarine
- Km: 8 scramblers, rot. refl'r, atypical msg form, diff't msg-key prot.
- U-boat wolfpack
- gardening: mine location crib
- pinching stealing codebooks, e.g. Operation Ruthless
- Gadenia/Gonzenhein report conclusion: natural disaster or spy
anonymous cryptanalysts
- ULTRA: German/Italian/Japanese deciphering
- Greece invasion Italy/Sicily/Normandy landings
- FW Winterbotham The Ultra Secret
- Rejewski, Denniston, Turing: no credit in lifetime
- Turing
- 1952 convicted of homosexuality
- hormone treatment, security clearance withdrawn
- 7 June 1954 cyanide apple
Ch 5: language barrier
- Germany: Enigma Japan: Purple
Britain: Type X US: SIGABA
- Purple: Midway/Yamamoto
- improper Enigma use: rpt msg key, cillies, plgbrd/scrmblr restr
- otw not have been broken? (later: Enigma broken)
- science: reasoning history/socialogy/psychology: human behaviour
- cipher machines: slow human language translators: fast
- WWI US (France): Choctaw
- WWII US (Pacific): Navajo code talkers
Navajo code talkers
- Philip Johnston → James Jones
- precision? 2 man whisper demo
- language? Navajo (28 Americans) Sioux Chippewa Pima-Papago
- large pop'n, literate, fluently bilingual
- language distinct fr Eur/Asia, not studied by roving German students
- cryptosystem
- word ↔ word 274 word military lexicon spell:
letter ↔ word
- submarine QZ ↔ iron fish quiver zinc ↔
besh-lo ca-yeilth besh-do-gliz
- US Naval Intel: guttural/nasal/tongue-twisting
- 7 Aug 1942: 1st use
- end 1942: rqst 83 add'l code talkers
- Na-Dené:
verb form = f(subj, obj = f(category), adverb,
personal/hearsay)
- enhancements
- lexicon: + 234 words
- homophones: (e t a o i n) + 2 (s h r d l u) + 1
- a ↔ ant, apple, axe ↔
wol-la-chee, be-la-sana, tse-nihl
- Iwo Jima: 800 Navajo msgs
decipher lost languages
- lost languages/scripts of Egypt
- ? 3000 BC
hieroglyphic script
from Greek sacred carving
- ? 3000 BC
hieratic script
from Greek priestly writing
- 600 BC
demotic script
from Greek popular
- some Egyptian history
- 313 BC
Alexander
(Macedonia) invades, becomes leader, ruling culture Macedonian/Greek
- 305 BC general
Ptolemeus
becomes leader, his line until ...
- 30 BC
Cleopatra
VII dies, Egypt now province of Rome
- ~100 AD Coptic language (late Egyptian)
- Greek alphabet + Egyptian language =>
Coptic script
24 Greek characters + 6 demotic characters (non-Greek sounds), Egyptian pronunciation
- demotic outlawed by Christian church (Constantine: 272-337)
- 10xx AD Arabic
(Egyptian/Coptic linguistic link mostly broken, but
e.g. survived in Coptic Christian church liturgy)
- 16xx: Egyptian obelisks erected in Rome
- hieroglyph = semagram (meaningful symbol) ?
- 1652 German Jesuit priest Athanasius Kircher Oedipus aegyptiacus
- 1798 Napolean historians/scientists/draughtsmen → Egypt
-
Rosetta stone → Cairo → Alexandria → London
- 3 scripts: heiroglyphic, demotic, classical Greek
-
heiroglyph typewriter
- Thomas Young 1773 - 1829
- Jean-Francois Champollion 1790-1832 (see
BBC bio)
- 1807
→ Collège de France, Paris
→ Egypt under the pharaohs
- Grk Lat Heb Eth San Zend Pahlevi Arab Syr Chal Pers Chin
- 1808 "Lenoir has published ... " (fainted)
- 1809 prof Grenoble (fainted)
- 1815 Grenoble Fac Arts closed
- 1822 following Young's ideas, more cartouches
- Ptolemaios ↔ P t o l m e s
- Cleopatra ↔ C l e o p a t r a
two diff't t glyphs
- ?????? ↔ a l ? s e ? t r ?
a l k s e n t r s
scrbs lkd t mt vwls
- 1822 Sept 14 pre-GrecoRoman cartouches
- still phonetic
- rebus ... in Coptic (late Egyptian) ! je tiens l'affaire
eureka
- 1828 → Egypt
- 1832 stroke
- Simon Singh's
decipherment of hieroglyphs
deciphering linear B
- after Egypt heiroglyphics cracked ...
- Bablyon cuneiform
- Turkey Kök-Turki
- India Brahmi
- linear B Greek background
- ≈ 1600-1100 BC Mycenaean age
- ≈ 1200 BC Trojan war
- ≈ 800 BC Homer Iliad, Odyssey
- ≈ 1100-750 BC Greek dark ages
- ≈ 750-480 BC archaic Greek period
- ≈ 500-323 BC classical Greek period (490 Marathon 323 death Alexander)
- 1872 Heinrich Schliemann Troy
- 1851-1941 Arthur Evans
- goal: find evidence of Mycenaean writing
- Athens antiquities → Crete seals Crete
- 1900 Knossos excavations: palace, fire-baked clay tablets
- 2000 - 1650 BC drawings/semagrams
- 1750 - 1450 BC linear A
- 1450 - 1375 BC linear B
- linear B script (see Lawrence Lo's webpage)
- ragged right margins → left to right
- 90 symbols → syllabic
- linear B language
- some Cypriot-like (Greek: 600-200 BC) characters
- few linear B words ended with Cypriot se symbol → not Greek
- tale of minotaur: King Minos receives Greek tributes
- Evans conviction: Minoan civilization spoke lost Cretan language
- ugly scientist: dispute conviction → no access to tablets
- 1939 Carl Bergen finds linear B tablets in Pylos (Greek mainland)
- 1906-1950 Alice Kober
Alice and Bob go public
- British WWII cryptanalysis machines
- bombes ↔ Enigma ciphers
- Colossus ↔ Lorenz SZ40 ciphers
- Colossus
- breaking Lorenz: John Tiltman, Bill Tutte (later Canadian)
- machine design: Max Newman
- machine construction: Tommy Flowers, delivered 8 Dec 1943
- machine destruction: British govt
- 1st working programmable computer ? Colossus or ENIAC ?
- computer evolution
- mechanical relay switch
- electronic valve
- 1947 transistor
- 1953 IBM computer
- 1957 Fortran
- 1959 integrated circuit
- age of computer ciphers
- Horst Feistel
- from Germany 1934
- WWII: house arrest
- NSA apparently has project cancelled (twice)
- at IBM TJ Watson, develops Lucifer encryption system
- 1973: US National Bureau of Standards adopts 56-bit key Lucifer as DES
- 256 ≈ 7.206 × 1016
- key distribution ? → public key cryptography
God rewards fools
- Whitfield Diffie, b 1944, MIT, ind. security expert: cypherpunk
- USDoD => Advanced Research Projects Agency => 1969 ARPAnet => internet
- key distribution ?
- 1974 IBM TJ Watson talk => drive to Stanford to find Martin Hellman b 1946
- joined by Ralph Merkle
- 1976 June National Computer Conference : DHM key exchange announced
birth of public-key cryptography
- 1975: Diffie proposes asymmetric key cipher
- symmetric/asymmetric cryptography
-
encrypt c = ek1( m )
decrypt m = dk2( c )
- symmetric:
easy to determine
dk2( )
from
ek1( )
(e.g. k2=k1)
- asymmetric:
difficult to determine
dk2( )
from
ek1( )
prime suspects
- 1977 April MIT Ron Rivest, Adi Shamir, Leonard Adelman
- 1977 August Martin Gardner
A new kind of cipher that would take millions of years to break
- patented
alternative history of public-key cryptography
- Bletchley Park => Gov't Comm'n HQ => Comm'n-Elec' Security Group (CESG)
- James Ellis unpredictable, innovative, not a teamworker, brilliant
- save costs on key distribution
- Bell telephone report: Alice adds noise, receives msg, subtracts noise
- 1969 non-secret encryption (PKC) possible, need one-way function
- 1973 Clifford Cocks (Cambridge U) => solves problem (RSA)
- 1975 Malcolm Williamson can't find flaw in Cocks's system (and solves key exchange problem, DHM)
- 1982 Diffie visits Ellis
- 1980s Thatcherism: government bad, private good GCHQ: go public ?
- 1984 Peter Wright publishes spycatcher GCHQ: heads down, hats on
- 1997 Nov Ellis dies
- 1997 Dec conference presentation by Cocks on RSA ... inc brief history of GCHQ
pkc work
binary numbers
Diffie-Hellman-Merkle key exchange
- exchange mutually-created random secret key over insecure channel
- see
wimp.com video
- over channel: Alice and Bob agree on prime p (say 97) and base g (say 5)
- Alice
- in secret:
chooses random number a in [2, p] (say 5)
- in secret: computes α = ga mod p
( here α = 55 mod 97 = 21 )
- over channel: sends α ( 21 ) to Bob
- Bob
- in secret:
chooses random number b in [2, p] (say 76),
- in secret: computes β = gb mod p
( here β = 576 mod 97 = 24 )
- over channel: sends β ( 24 ) to Alice
- secret key
- Alice uses βa mod p
( here 245 mod 97 = 88 )
- Bob uses αb mod p
( here 2176 mod 97 = 88 )
DHM correctness
-
αb =
(ga)b =
ga×b =
gb×a =
(gb)a =
βa
DHM efficiency
DHM security
how hard to "undo" exponentition, i.e. find e s.t. a**e %n = x ?
discrete logarithm problem
as far as we know: slow ... try each possible exponent
DHM example
p = 613144603035200518605071627722399281527
base = 347449578131074797459449734586666998031
alice_secret = 474140564715023867271727810192114419457
bob_secret = 556327197178837163583577967104054021837
alice_sends = pow(base, alice_secret, p)
bob_sends = pow(base, bob_secret, p)
alice_key = pow(bob_sends, alice_secret, p)
bob_key = pow(alice_sends, bob_secret, p)
Alice,Bob probable prime 613144603035200518605071627722399281527
Alice,Bob base 347449578131074797459449734586666998031
Alice sends Bob 344627486120828843474388906075377334410
Bob sends Alice 409706635860222822429885047531176332371
Alice creates key 450786317947341275948138905696766128062
Bob creates key 450786317947341275948138905696766128062
Alice and Bob find a large prime how?
- warmup
- Alice and Bob find primes probabilistically
Fermat's Little Theorem
- divides non-zero integer d divides integer n: there is
some integer k such that n=kd
- warmup: look for patterns
among aj mod n
- Fermat 1640
- a coprime to p prime =>
p divides ap
- a coprime to p prime =>
ap-1 = 1 (mod p)
probabilistic primality test
- simplest: use Fermat's little theorem as composite test
- pick random x in [2,n-1], and repeat the following many times:
- if gcd(x,n) not 1, then n not prime
- if x**(n-1) %n not 1, then n not prime
- problem: some composite (561 = 3*11*17) numbers never pass
the Fermat composite test
- better: use
Miller-Rabin
(python)
Euler's Totient Generalization
- Euler totient function φ(n)
number of integers a in [1 ... n-1] coprime to n
-
p prime => φ(p) = p-1
p has no common factors with any integer in [2 ... p-1]
- p, q different primes
=> φ(pq) =
(p-1)(q-1)
q-1 numbers in [1 ... pq-1] divisible by p
(every pth number)
p-1 numbers in [1 ... pq-1] divisible by q
(every qth number)
pq-1 - (q-1) - (p - 1) = (p - 1)(q - 1)
- Euler 1736
- a coprime to n =>
n divides aφ(n)+1
- a coprime to n =>
aφ(n) = 1 (mod n)
Euclid's Greatest Common Divisor
- ≈300BC Euclid for b ≥ a > 0
- gcd(a,0) = a
- gcd(b,a) = gcd(b-a,a)
- David Sumner's
Euclid's GCD algorithm
-
a ⋅ b = 1 (mod n)
<=>
b = a-1 (mod n)
- for a coprime to n use extended Euler gcd alg'm to find
a-1 (mod n)
Euclid gcd: compute gcd(a,b), a= 60534384 b= 35717371
gcd is last non-zero remainder
60534384 - 35717371 * 1 = 24817013
35717371 - 24817013 * 1 = 10900358
24817013 - 10900358 * 2 = 3016297
10900358 - 3016297 * 3 = 1851467
3016297 - 1851467 * 1 = 1164830
1851467 - 1164830 * 1 = 686637
1164830 - 686637 * 1 = 478193
686637 - 478193 * 1 = 208444
478193 - 208444 * 2 = 61305
208444 - 61305 * 3 = 24529
61305 - 24529 * 2 = 12247
24529 - 12247 * 2 = 35
12247 - 35 * 349 = 32
35 - 32 * 1 = 3
32 - 3 * 10 = 2
3 - 2 * 1 = 1
2 - 1 * 2 = 0
extension: express gcd as linear combination of a,b
1 = 3 * 1 + 2 * -1 ... substitute: 2 = 32 - 3 * 10
1 = 32 * -1 + 3 * 11 ... substitute: 3 = 35 - 32 * 1
1 = 35 * 11 + 32 * -12 ... substitute: 32 = 12247 - 35 * 349
1 = 12247 * -12 + 35 * 4199 ...
1 = 24529 * 4199 + 12247 * -8410 ...
1 = 61305 * -8410 + 24529 * 21019 ...
1 = 208444 * 21019 + 61305 * -71467 ...
1 = 478193 * -71467 + 208444 * 163953 ...
1 = 686637 * 163953 + 478193 * -235420 ...
1 = 1164830 * -235420 + 686637 * 399373 ...
1 = 1851467 * 399373 + 1164830 * -634793 ...
1 = 3016297 * -634793 + 1851467 * 1034166 ...
1 = 10900358 * 1034166 + 3016297 * -3737291 ...
1 = 24817013 * -3737291 + 10900358 * 8508748 ...
1 = 35717371 * 8508748 + 24817013 * -12246039 ...
1 = 60534384 * -12246039 + 35717371 * 20754787
RSA
- Alice
- picks secret primes p,q
11, 13
- sets public n = p ⋅ q
11 ⋅ 13 = 143
- computes secret φ(n) = (p-1)(q-1)
(11 - 1) ⋅ (13 - 1) = 120
- picks random e in [2 ... φ(n)-1] coprime to φ(n)
23 coprime to 120
120 = 23*5 + 5
23 = 5*4 + 3
5 = 3*1 + 2
3 = 2*1 + 1
2 = 1*2 + 0
- computes secret d = e-1 mod φ(n)
47 = 23-1 mod 120
1 = 3 - 2*1 2 = 5 - 3*1
= 3 - (5 - 3*1)*1
= 3*2 - 5*1 3 = 23 - 5*4
= (23 - 5*4)*2 - 5*1
= 23*2 - 5*9 5 = 120 - 23*5
= 23*2 - (120 - 23*5)*9
= 47*23 - 120*9
- publishes n, e
143, 23
- Bob, wanting to send secret m to Alice
84 ... ... ...
- computes β = me mod n
23 = 101112
8423 mod 143 =
( ( ( ( ( ( 1
) 2 ⋅ 84
) 2
) 2 ⋅ 84
) 2 ⋅ 84
) 2 ⋅ 84
) mod 143 = 24
1 * 1 * 84 = 84 mod 143
84 * 84 = 49 mod 143
49 * 49 * 84 = 54 mod 143
54 * 54 * 84 = 128 mod 143
128 * 128 * 84 = 24 mod 143
- sends β to Alice
24 ... ... ...
- Alice, receiving β from Bob
- computes m = βd mod n
47 = 1011112
2447 mod 143 =
( ( ( ( ( ( 1
) 2 ⋅ 24
) 2
) 2 ⋅ 24
) 2 ⋅ 24
) 2 ⋅ 24
) 2 ⋅ 24
) mod 143 = 84
1 * 1 * 24 = 24 mod 143
24 * 24 = 4 mod 143
4 * 4 * 24 = 98 mod 143
98 * 98 * 24 = 123 mod 143
123 * 123 * 24 = 19 mod 143
19 * 19 * 24 = 84 mod 143
- reads m
84 ... ... ...
- correctness
-
mod n:
βd
= (me)d
= me⋅d
= m
- why ?
- if m is coprime to n, by Euler's theorem
mod n: me⋅d
= mφ(n)⋅k +1
= (mφ(n))k m1
= 1 ⋅ m
= m
mod 143:
2447
= (8423)47
= 8423⋅47
= 84120⋅9 +1
= (84120)9 841
= 1 ⋅ 84
= 84
- if m is not coprime to n, but n is product of distinct primes,
by Euler's theorem and Chinese remainder theorem
- security
- Eve needs either
- to factor n (and then find e inverse, which is easy) or
factor 143 (and find 23 inverse)
- to solve β = ?e mod n
24 = ?23 mod 143
- so far, both problems seem hard
pretty good privacy
- history
| ≈ 2 000 000 BC | homo habilis handy man / stone age |
| ≈ 11 000 BC | last ice age ends |
| ≈ 8 000 BC | agriculture |
| ≈ 4 000 BC | bronze (copper+tin) age |
| ≈ 3 500 BC | writing |
| ≈ 1750 AD | industrial age |
| ≈ 1970 AD | information age |
- Society for Worldwide Interbank Financial Telecommunications (SWIFT) network
- encryption: government, military ... + commerce ... + crime
- Phil Zimmermann
- 1970s Florida Atlantic University
- 1977 RSA ... used by government, military, business ... costly
- previously ... large scale gov't privacy invasion ... prohibitive
- 1980s developed pgp
- 1991 asks friend to post pgp on internet
- 1993 US govt visits Phil
pgp features
- symmetric secret-key cryptosystem for message
- asymmetric public-key cryptosystem for secret key
- asymmetric public-key cryptosystem for signature
- automated
- pkc key generation
- session key
DH digital signature
- one-way function: given f( ),
determining f -1( ) infeasible
- reverse one-way function: given g-1( ),
determining g( ) infeasible
- e.g. RSA: g(m) = md mod n
g-1(y) = ye mod n
- to send signed message m to Bob, Alice ...
- uses her private g( ) and public g-1( )
- uses public hash function h( )
- computes j=h(m)
- computes c=g(j)
- sends Bob m, j, c
- to verify signature, Bob ...
- confirms j=h(m)
- confirms j=g-1(c)
- security ?
- determining g( ) from g-1( ) infeasible for Eve
- only Alice could have created signature
simple signature example (use RSA, ignore hashing)
- Alice's RSA public values are n=143, e = 7
- (so Alice's secret value d = e-inverse-mod-phi(n)= -17 = 103)
- Bob's RSA public values are n=323, e = 5
- (so Bob's secret value d = e-inverse-mod-phi(n)= -115 = 173)
- Bob wants to send Alice the signed, secret message m = 28
- Bob computes signed_m using his secret d
s = pow(m, d_B, n_B) = pow(28, 173, 323) = 24
- Bob sends m and signed_m to Alice the usual way
toA_m = pow(m, e_A, n_A) = pow(28, 7, 143) = 63
toA_s = pow(s, e_A, n_A) = pow(24, 7, 143) = 106
- Alice deciphers m and signed_m
m = pow(toA_m, d_A, n_A) = pow( 63, 103, 143) = 28
s = pow(toA_s, d_A, n_A) = pow(106, 103, 143) = 24
- Alice confirms that Bob signed m
pow(s, e_Bob, n_Bob) = pow(24, 5, 323) = 28
pgp protocol (roughly)
- before sending any messages
- Alice generates public key (nA,eA)
and secret key dA
- knows public hash function h( )
- to send message m to Bob, Alice ...
- knows Bob's public key (nB,eB)
- generates secret IDEA session key k
- c1 = IDEAk(m)
- c2 = keB mod n
- sends Bob c1 and c2
- if Alice wants to sign message
- j = h(m)
- c3 = jdA mod nA
- sends Bob j, c3
- to decrypt c1, c2 from Alice, Bob ...
- k = c2dB mod n
- m = IDEAk(c1)
- to verify Alice's signature, Bob ...
- j = h(m) ?
- j = c3eA mod nA ?
encryption for the masses ... or not
- 1993 - 1996 : FBI v Phil Zimmermann ... illegally exporting a weapon ?
- conclusion: safety with PGP (?)
a quantum leap into the future
- [1999] future ( present, but secret ? ) of cryptography ?
future of cryptanalysis
- lots of poorly encrypted traffic => lots of work
- tempest attack (record keystrokes)
- parasitic virus (e.g. attach private key sender to pgp)
- Trojan horse (e.g. looks like pgp)
- intentional backdoors?
- Crypto AG built backdoor into a product: truth or rumour ?
- cracking RSA
- faster factoring ?
- P = NP ?
- if yes, can we factor faster ?
- if no, can we factor faster ?
- without factoring ?
quantum mechanics
-
Anyone who can comptemplate quantum mechanics
without getting dizzy hasn't understood it.
Niels Bohr
- 1799 Thomas Young
- ripples of two ducks
- light through two slits
- The Undulatory Theory of Light
- light: particle or wave ?
- single photon through two slits ?
here
- single electron through two slits ?
here
- superposition
- light splits into two states simultaneously
- Schrödinger's cat
- many worlds (multiverse)
- light can be in one of two possible (interfering) universes
- 1984 David Deutsch: computer based on quantum mechanics
- essentially, use quantum mechanics to build massively parallel machine
- machine asks different question in each universe simultaneously
- find x : x2, x3 use digits 0, ..., 9
- classical computer: try x=0, x=1, ..., serially
- parallel computer: try x=0, x=1, ..., simultaneously
- quantum computer: based on particle spins (e.g. east/west)
- build quantum computer using qbits
- build how ?
- program how ?
- 1994 Peter Shor ATT/Bell: quantum factoring algorithm
- 1996 Lov Grover: quantum list search algorithm
quantum money
-
Scientific American articles
- Stephan Wiesner 1960s
- photon vibration has polarisation
- Heisenberg uncertainty principle: measuring changes state
- measure photon polarisation with filter
- simplifying assumption: polarisation states | - / \
- photon hits | filter ? *: absorbed
- | photon => | (probability 1)
- - photon => * (probability 1)
- / photon => * (probability 1/2) | (probability 1/2)
- \ photon => * (probability 1/2) | (probability 1/2)
- photon hits / filter ? similar ...
- photon hits \ filter ? similar ...
- photon hits - filter ? similar ...
- idea: embed photon traps in each bill
- bank records serial number and photon polarisation sequence
- bank checks validity of bill
- confirm each photon polarisation correct
- reset each photon
- forger tries to copy bill, by measuring each photon
- pick filter, e.g. |
- absorbed => guess polarisation (- prob 1/2, / prob 1/4, \ prob 1/4)
- not absorbed => guess polarisation (| prob 1/2, / prob 1/4, \ prob 1/4)
- probility that forger guesses polarisation correctly ?
at most 1/2
- prob. that forger guesses all k polarisations correctly ?
at most (1/2)k
quantum cryptrography
- Charles Bennett
- ugrad w Weisner @ Columbia
- TJ Watson research fellow
- Gilles Brassard
- rectilinear scheme
- send - (0) or | (1)
- receiver uses ( - or | or + ) filter ?
- interpret correctly w prob 1
- receiver uses ( / or \ or x ) filter ?
- interpret correctly w prob ½ and alters photon
- diagonal scheme
- send \ (0) or / (1)
- receiver uses ( - or | or + ) filter ?
- interpret correctly w prob ½ and alters photon
- receiver uses ( / or \ or x ) filter ?
- interpret correctly w prob 1
Bennett-Brassard qc protocol
- Alice
- selects random (+ or x) filter sequence
- selects random (0 or 1) message sequence
- sends resulting photon sequence
filter: + + x + x + + x + x x x + x
message: 1 1 0 0 1 1 0 1 0 1 0 1 1 1
photon: | | \ - / | - / - / \ / | /
- Bob
- selects random (+ or x) filter sequence
- interprets Alice's photon sequence
filter: + x x + x x + + + + x x x +
photon: | | \ - / | - / - / \ / | /
interpret: 1 ? 0 0 1 ? 0 ? 0 ? 0 1 ? ?
- after Bob receives message, Alice phones Bob
- Alice/Bob exchange filter sequences
- message on matching filters becomes key
Alice's filter: + + x + x + + x + x x x + x
Bob's filter: + x x + x x + + + + x x x +
matched: + x + x + + x x
key: 1 0 0 1 0 0 0 1
Bennett-Brassard qc security
- Eve
- guesses random filter sequence
- listens to Alice/Bob's phone conversation
- intercepts and measures Alice/Bob quantum transmission
- probably knows about ½ of Alice/Bob's key bits ... but ...
Eve's filter: x x + + + x x + + x + x + x
Alice/Bob matched: + x + x + + x x
key bits: 0 0 1
- ... Eve's measuring of A/B transmission altered about ½ photons
original photon: | | \ - / | - / - / \ / | /
Eve's filter: x x + + + x x + + x + x + x
altered photon: ? ? ? - ? ? ? ? - / ? / | /
e.g. : \ / | - - / / - - / | / | /
- ... changing Bob's reception ... so about ¼ his bits are wrong
altered photon: \ / | - - / / - - / | / | /
Alice-Bob matched: + x + x + + x x
key: ? ? 0 ? ? 0 ? ?
e.g.: 1 0 0 0 1 0 1 0
- ... so, over phone Alice and Bob
- agree on small random fraction of test bits
- compare values
- if enough are wrong, they suspect Eve
Alice-Bob matched: + x + x + + x x
test bits: . . .
Alice: 1 1 0
Bob: 1 0 1
quantum computers
so-called bible code
- 1997 The Bible Code by Michael Drosnin: equi-distant
letter sequences yield predictions !!!
-
scientific refutation
by Brendan McKay et al., including
McKay's findings in Moby Dick
- consider large book, say Moby Dick
- 951947 characters, letter counts
a b c d e f g h i j
77915 16875 22505 38217 117089 20833 20820 62895 65432 1082
k l m n o p q r s t
8058 42791 23274 65615 69325 17255 1556 52133 64231 87997
u v w x y z
26697 8597 22222 1030 16870 632
- main idea: consecutive letter pairs highly correlated
according to typical English letter-pair distribution, but
sufficiently separated letter pairs essentially
independently distributed
- warm-up probability question: birthday paradox
-
how many people before prob(at least 2 have same birthday) > 0.5 ?
-
how many people before
prob(all birthdays different) < 0.5 ?
prob(2 people, diff't b'days) = 1-1/365
prob(3 people, diff't b'days) = (1-1/365)*(1-2/365)
prob(4 people, diff't b'days) = (1-1/365)*(1-2/365)*(1-3/365)
...
prob(22 people, diff't b'days) = (1-1/365)* ... * (1-21/365) = 0.5243...
prob(23 people, diff't b'days) = (1-1/365)* ... * (1-21/365)*(1-22/365) = 0.4927...
- assuming k-separated pairs are independently distributed,
we can compute the probability of a given k-EDLS, say ilm
or koran
prob(some 3-character sequence "i**" is not "ilm") ?
two characters after i must be
either "(not l) *" A
or " l (not m)" B
prob(A) = (total - #l) / total
= 951 947 - 42 791 / 951 947
= 0.955...
prob(B) = ( #l / total) * ( (total - #m) / total)
= ( 42 791 / 951 947 ) * ( ( 951 947 - 23 274) / 951 947 )
= 0.043852...
prob(A) + prob(B) =
prob (each of the 65 432 sequences "i**" is not "ilm")
roughly = 0.99838...^65432
= 1.49e-46
= 0.000000000000000000000000000000000000000000000149
Prob(some 5-character k-EDLS is "koran") =
1- ( (951947-69325)/951947 +
(69325/951947)*(951947-52133)/951947 +
(69325/951947)*(52133/951947)*(951947-77915)/951947 +
(69325/951947)*(52133/951947)*(77915/951947)*(951947-65615)/951947) ^ 8058 =
1- ( 0.9999775 ) ^ 8058 =
1- 0.834179193 =
0.1658...
some linux crypto commands
substitute x with a, y with b, z with c:
tr [xyz] [abc] < infile
Caesar cipher
tr "a-zA-Z" "d-za-cD-ZA-C" < infile
remove all characters except "xyz":
tr -cd "xyz" < infile
character counts:
fold -w1 < infile | sort | uniq -c | sort -rn
print all 6-letter words ending in "ana":
egrep "^[a-z]{3}ana$" /usr/share/dict/words
troubleshooting
some 20C discrete math
- Enigma
- string matching
- permutation as product of cycles
- cycles in (bipartite) graphs
- Vigenère
- RSA
index of coincidence
- coincide: occupy same place in space/time [Web. 9th New Coll.]
- index of coincidence:
probability that 2 equiprobably-selected characters are equal
{ a,a,a,a,b,b,c,d,d,d,e,e,e,e,e} ?
I_c = (4*3 + 2*1 + 1*0 + 3*2 + 5*4) / (15*14)
= (12 + 2 + 0 + 6 + 20 ) / 210
= 0.19...
{ a,a,a,b,b,b,c,c,c,d,d,d,e,e,e } ?
I_c = (3*2 + 3*2 + 3*2 + 3*2 + 3*2) / (15*14)
= ( 6 + 6 + 6 + 6 + 6 ) / 210
= 0.14...
I_c = ( f_1*(f_1 - 1) + f_2*(f_2 - 1) + ... + f_c*(f_c - 1) / n*(n-1)
if n is large, (f_j - 1) / (n - 1) ≈ f_j / n = p_j, and so
I_c ≈ p_1^2 + p_2^2 + ... + p_c^2
index of mutal coincidence
- index of mutual coincidence:
given two multisets,
probability that a character equiprobably selected from
one multiset equals a character equiprobably selected from
the other multiset
{ a a a a b b c d d d e e e e e } and
{ a a a a a b b b b c c d e e e } ?
I_mc = (4*5 + 2*4 + 1*2 + 3*1 + 5*3) / (15*15) =
= 48/225 = 0.21...
{ a a a a b b c d d d e e e e e } and
{ a a a a b b c d d d e e e e e } ?
I_mc = (4*4 + 2*2 + 1*1 + 3*3 + 5*5) / (15*15) =
= 55/225 = 0.24...
Friedman IC and IMC method to crack Vigenère cipher
- find most likely keylength
- for each possible keylength k, split text into
k substrings
- start at position 1 and take each k'th character
- start at position 2 and take each k'th character
- . . .
- start at position k and take each k'th character
- for each substring, compute its IC
- take average IC of the k substrings
- pick the k with largest average IC
- for each substring, find most likely shift
- for each of 26 possible shifts, compute
the index of mutal coincidence of
typical English text with the shifted string
- pick shift that gives the largest IMC
fake example: consider 5 character alphabet
with typical frequencies below,
and ciphertext substring frequencies (a bbb ccccc dddd ee).
which shift gives best IMC?
a b c d e
.27 .13 .07 .20 .33
shift 0 a->a (a bbb ccccc dddd ee)
((1*.27) + (3*.13) + (5*.07) + (4*.2) + (2*.33))/15 = .165
shift 1 a->b (aa b ccc ddddd eeee)
((2*.27) + (1*.13) + (3*.07) + (5*.2) + (4*.33))/15 = .213
shift 2 a->c (aaaa bb c ddd eeeee)
((4*.27) + (2*.13) + (1*.07) + (3*.2) + (5*.33))/15 = .244
shift 3 a->d (aaaaa bbbb cc d eee)
((5*.27) + (4*.13) + (2*.07) + (1*.2) + (3*.33))/15 = .213
shift 4 a->e (aaa bbbbb cccc dd e)
((3*.27) + (5*.13) + (4*.07) + (2*.2) + (1*.33))/15 = .165
IC and Vigenère cryptanalysis
- Kasiski test to find keyword length: gcd of k-gram offsets
- William Friedman test 1922: compute average IC of k-substrings
- IC( English plaintext ) ?
a b c ... z
.081 .019 .028 .001
.0066 + .0004 + .0008 + ... + .0000 = .065...
- IC of Caesar-shifted English plaintext ? .065...
- IC of equiprobably-selected English letters ? 1/26 = .038...
SAABTFWFTBJVAKLGCZSRVVAHCMBEHNQIFIAWNA
FGZMIOFUIZPRKCZUSGZFCQSGFVRFWFSFGNFVRV
WQGAGBIWYDAAIAVIEHUWLASFLWPOLQWGQNFAUB
TXWDHUWEUZYTMFVNLEMGJSTFYRDTK
keysize 1 ?
substring S A A B T ...
I_c = .050
keysize 2 ?
substring S A T W T ...
substring A B F F B ...
avg I_c = .053
keysize 3 ?
substring S B W B A ...
substring A T F J K ...
substring A F T V L ...
avg I_c = .054
keysize 4 ?
substring S T B K Z ...
substring A F J L S ...
substring A W V G R ...
substring B F A C V ...
avg I_c = .046
keysize 5 ?
substring S F J G V ...
substring A W V C V ...
substring A F A Z A ...
substring B T K S H ...
substring T B L R C ...
avg I_c = .070
keysize 6 ?
substring S W A S C ...
substring A F K R M ...
substring A T L V B ...
substring B B G V E ...
substring T J C A H ...
substring F V Z H N ...
avg I_c = .043
counting plugboard pairings
- how many ways to connect 1 plug ?
26 choose 2
= (26*25) / 2
= 325
- how many ways to connect 2 plugs ?
(26 choose 2) * (24 choose 2) / 2!
= (26*25*24*23) / (2 * 2 * 2!)
= 44 850
- how many ways to connect 3 plugs ?
(26 choose 2) * (24 choose 2) * (22 choose 2) / 3!
= (26*25*24*23*22*21) / (2*2*2 * 3!)
= 3 453 450
- how many ways to connect 6 plugs ?
? ? ? ? ? ? ? ?
= ? ? ? ? ? ? ? ?
= 100 391 791 500
cycle decompositions (for Rejewksi signatures)
how many cycle decompositions of a 26-permutation ?
how many ways to sum to 26 ?
how many partitions of n=26 ?
n p(n)
1 1 1
2 2 2 1+1
3 3 3 2+1 1+1+1
4 5 4 3+1 2+2 2+1+1 1+1+1+1
5 7 5 4+1 3+2 3+1+1 2+2+1 2+1+1+1 1+1+1+1+1
6 11 6 5+1 4+2 4+1+1 3+3 3+2+1 3+1+1+1 2+2+2 2+2+1+1 2+1+1+1+1 1+1+1+1+1+1
...
26 2436
prime factorization
- integer factorization seems hard (200 digit prime took ≈ 500 CPU-years)
- verifying that a number has a given factorization easy (multiply)
- class NP: yes/no questions for which yes-answers can be verified in polytime
- is_composite is in NP
- class P: yes/no questions for which answer can be found in polytime
- answering is this number prime ? easy
(2002 Agrawal Kayal Saxena algorithm)
- AKS => is_prime is in P
- AKS => is_composite is in P
- Clay Mathematics Institute $1,000,000 Millenium Problem:
P = NP ?
- find a polytime algorithm to solve these kinds of problems, and win $1,000,000
recognizing the running key cipher
- ptext short ? RKC hard to break
- ptext long ? ptext/running key single letter freq's typical?
then can compute expected ctext slf ...
- prob(ctxt char = j) =
sum, over all ptext chars k,
prob(ptxt char = k) * prob(rkey char = j-k (mod alphabetsize))
#!/usr/bin/env python
# show single letter frequencies of running key cipher,
# assuming both key and ptext independently uniformly sampled from
# typical English letter single letter frequencies
import string
L = [ # English letter frequencies
8.167, 1.492, 2.782, 4.253, 12.702, 2.228, 2.015, 6.094, 6.966, 0.153,
0.772, 4.025, 2.406, 6.749, 7.507, 1.929, 0.095, 5.987, 6.327, 9.056,
2.758, 0.978, 2.360, 0.150, 1.974, 0.074 ]
def printAlphabet():
alphabet = string.ascii_lowercase
for letter in alphabet:
print ' '+letter,
print ''
def showAsPerCentRatios(A):
for j in range(len(A)):
print "%2d" % int(round (100.0*A[j]/(1.0*sum(A)))),
print ''
def runningCipherFreqs(L):
M = [] # running cipher frequencies
n = len(L)
# compute M
for j in range(n):
s = 0.0
for k in range(n):
s += 1.0*L[k]*L[(j-k)%n] # ptxt k + key (j-k) = ctxt j
M.append(s/sum(L))
return M
printAlphabet()
showAsPerCentRatios(L)
showAsPerCentRatios(runningCipherFreqs(L))
---------------
python < run_ciph_freq.py
a b c d e f g h i j k l m n o p q r s t u v w x y z
8 1 3 4 13 2 2 6 7 0 1 4 2 7 8 2 0 6 6 9 3 1 2 0 2 0
5 3 3 3 5 4 4 5 5 3 4 5 4 3 3 4 3 4 4 4 3 5 5 4 3 4
sequential homophonic cipher
s*iqq4epdwvjg3oh2#*3z,5e'9icmsw3qtg0r*s/t9%+mes%bvpwhxlat*&1ke'
wi3g.h26uvu4'-zk*s9+qei5rwxjh3,)ba't.*%clq)u0e(4#m,doksg&k1/2uib(
6w5paxu3.5r9sz-t*hc0jenomx2l4s1#zgk93wcm-'3jid,8ubh0uyo'6g&59(*d2a/&
r.+4kzi,t1p%beh(cla3m0q-k6gdkj#.kw2r4/&*'xzo1$uyl9(p,dm5bi3aec
&u+%gnwh(9d+*'xi.e#36w/%4&0-h(ju2r3*po+m'e
zlgd9&%wi5m(*n,#qdghvu+e/1'b9c3-i&m(0djk%g2z+a.%&4c6wh0r,(b*
de'xwi59&*)ou2zlpa.sm+4(%1hvgcd)#,ex06w2'-yj9izbf3a.5&*8ue/c4p
okwsm+,g09(dby*#e2axk/1szr.swmh%*'5)qe&3wp34+qy,#3bycg)%a3/.4$
-j!9ivm0(t*q2lpouv6etg+x,#hbd&1k/a.5(w'xd%9s4*ken-pmz,#b&j/cok
0raswp(l6.i2r4n,vbz*cg1heds9vl0)a&uyy-(.5md&3w'2j#*z+4e(c
xtw/kgd6io0p,b&1k*hqsev'92u5aw#.z-)4(,biha*/cr.t4d0,p'bf2#asmzq
tl./4kjpcsou%0#g,&2eix(wh5t6b/a*p.d1s4s9&,#e)+bk/wsa)um%xg'v(
z.i*hc45xup9'vduss,#)q0rbkuvm2gna&k/-s3lep+.(zji5udcwhxk4n,#s*q
)bkou'59ixa.5064)/m&2%qye+s,zc1)u02rbtl-%ag(+whxt9z6cr.
4f3,y0mj'ok2lgdtb&zapiy19hc*'5e%mi.-k6w#xtrg04),*3ljh26b
(ae3owdz9&31n./45tmcr*x,'(bui5apv#-t0ljk26.dt4,zsq/c+b&osu3r
ypg!ax)q0l.61#293u%zu/m(cd-k4hv+e'50r,&lpu)6b#ajk2.iwzc*gh(0r4
l,9v62okkmkzba'1/ct.i0qk4,2ehxk-psdw'*%sj&zgsybiac#e)+.3oyy934
)u/0r,hm'v2lbwgpt9z6mc(k#*v/ei3a
1117 characters 49 different (each datum is count)
224 2202727271932203017292427172829302220 2273030282732 327272818342027 8182418203121301831221528
! # $ % & ' ( ) * + , - . / 0 1 2 3 4 5 6 8 9 a b c d e f g h i j k l m n o p q r s t u v w x y z
! . . . . . . . . . . . . . . . . . . . . . . 1 1 . . . . . . . . . . . . . . . . . . . . . . . . .
# . . . . . . . 1 3 . 1 1 2 . . . 1 2 . . . . . 2 1 . . 3 . 1 1 . . . . 1 . . . 1 . 1 . . . . 1 . 1
$ . . . . . . . . . . . 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 . . . . .
% . . . . 1 . . . 1 1 . . . . 1 1 . . 1 . . . 1 2 2 1 . . . 2 . . . . . 1 . . . 1 . 1 . . . 1 1 . 1
& . . . 1 . . . . 3 . 1 . . . 1 3 2 3 1 1 . . . . . . . . . . . . 1 2 1 1 . 1 . . 1 . . 2 . . . . 2
' . . . . . . 1 . 1 . . 2 . . . 1 1 1 . 4 1 . 2 . 2 . . 1 . . . . . . . . . 1 . . . . 1 . 3 1 4 . .
( . . . 1 . . . . 2 1 1 . 1 . 2 . . . 1 . 1 . 1 1 2 3 1 . . . . . 1 1 1 . . . 1 . . . 1 . . 2 . . 2
) . 1 . 1 . . . . . 2 1 . . 1 . . . . 1 . 1 . . 1 2 . . . . . . . . . . . . 1 . 3 . . . 4 . . . . .
* . 1 . 2 1 4 . 1 . . . . . 1 . . . 2 . . . 1 . . . 1 2 . . 1 3 1 . 1 . . 1 . 2 2 . 2 . . 1 . 1 . 1
+ . . . 1 . . . . 1 . 1 . 2 . . . . . 3 . . . . 1 2 . . 2 . . . . . . . 2 . . . 2 . 1 . . . 1 1 . .
, . 7 . . 2 1 1 1 1 . . . . . . . 1 . . 1 . 1 1 . 2 . 2 1 . 1 1 . . . . . . . 1 . . . 1 . 1 . . 1 2
- . . . 1 . 1 1 1 . . . . . . . . . . . . . . . . . . . . . . 1 1 1 3 . . . . 2 . . 1 2 . . . . 1 1
. . . . 1 . . 1 . 1 1 . 1 . 2 . . . 1 2 5 1 . . . . . 2 1 . . 1 4 . 1 . . . . . . . 2 1 . . . . . 1
/ . . . 1 2 . . . . . . 1 1 . 1 2 1 . 2 . . . . 2 . 5 . 1 . . . . . 1 . 2 . . . . . . 1 . . 1 . . .
0 . 1 . . . . 1 1 . . 1 1 . . . . 1 . 1 . 2 . 1 . . . 1 1 . . . . 1 . 2 1 . . 1 2 7 . . 1 . . . . .
1 . 2 1 . . 1 . 1 . . . . . 2 . . . . . . . . 1 . . . . . . . 2 . . 3 . . 1 . 1 . . 2 . . . . . . .
2 . 2 . 1 . 1 . . . . . . 1 . . . . . . . 3 . 1 2 . . . 2 . 1 . . 1 . 4 . . 1 . . 4 . . 2 . . . . 2
3 . . . . . . . . 1 . 2 1 1 1 . 1 . . 2 . 1 . . 3 1 . . . . 1 . . 1 . 2 1 . 3 . 1 1 . . 1 . 3 . . 1
4 . 1 1 . 1 1 2 3 1 1 2 . . 1 . . . . . 2 . . . . . 1 1 2 1 . 1 . . 2 1 . 2 . 1 . . 2 . . . . . . .
5 . . . . 1 . 1 1 . . . . . . 2 . . . . . . . 3 2 1 . . 2 . . . . . . . 2 . . 1 . 2 . 2 1 . . 1 . .
6 . . . . . . . . . . . . 2 . . 1 1 . 1 . . . . . 3 1 . 1 . 2 . 1 . . . 1 . . . . . . . 1 . 5 . . .
8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 . . . . .
9 . . . 1 4 1 3 . . 1 . . . . . . 1 3 . . . . . . . 1 1 . . . 1 4 . . . . . . . . . 2 . . 2 . . . 2
a . . . . 2 2 . 1 2 . . . 5 1 . . . 2 . . . . . . . 1 . 2 . 1 . . 1 . . . . . 2 . . 2 1 . . 1 3 . .
b . 1 . . 4 . 2 . 1 . . . . 1 . . . . . . . . 1 2 . . 1 1 2 . 1 3 . 3 . . . . . . . . 1 1 1 1 . 2 1
c . 1 . . 1 . 1 . 2 1 . . . . 1 1 . 1 2 . 1 . . . . . 2 . . 2 . . . . 2 2 . 1 . . 3 1 1 . . 1 1 . .
d . . . 1 2 . . 1 . 1 1 1 . . 1 1 1 . . . 1 . 1 . 1 1 . 1 . 1 . . 1 1 . 1 . 1 . . . 1 2 1 . 2 . . 1
e . 1 . 1 1 4 2 2 . 1 . . . 2 . . 1 1 . . . . . . . 1 1 . . . 2 3 . . . . 2 . 2 . . 1 1 . 1 . 1 . 1
f . . . . . . . . . . . . . . . . 1 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
g 1 . . . 2 1 1 1 . 1 1 . 1 . 3 1 1 1 . . . . . . . 1 4 . . . 2 . . 1 . . 2 . 1 . . 1 . . . . . . .
h . . . 1 . . 4 . . . . . . . 2 . 3 1 . 1 . . . 1 1 3 . 1 . . . . . . . 1 . . . 1 . . . . 3 . 4 . .
i . . . . 1 . . . 1 . 1 . 2 . 1 . 1 3 . 5 . . . 1 1 1 1 . . . 1 . . . . . . 1 . 1 . . . . 1 1 2 1 1
j 1 2 . . 1 1 . . . . . . . 1 . . . . . . . . 1 . . . . 1 . 1 2 2 . 3 . . . . 1 . . . . 1 . . . . .
k . 1 . 1 . . . . 2 . . 1 . 4 1 1 3 . 3 . 2 . 1 . . . . 2 . 1 . . 2 1 . 1 . 1 . . . 1 . 1 . 2 . . 2
l . . . . . . . . . . 1 1 2 . 1 . . . 1 . 1 . 1 2 1 . . 1 . 2 . . 2 . . . . . 3 1 . . . . . . . . .
m . . . 1 1 2 3 . . 2 1 1 . . 2 . 1 . . 1 . . . . . 2 1 1 . . 1 1 1 1 . . . . . . . 1 . . . . 1 . 2
n . . . . . . . . . . 3 1 1 . . . . . . . . . . 1 . . . . . . . . . . . . . 1 . . . . . . . 1 . . .
o . . . . . 1 . . . 1 . . . . 1 1 . . . . . . . . . . . . . . 1 . . 5 . 1 . . . . . 1 . 4 . 1 . 1 .
p . . . 1 . 1 1 . . 1 2 . 1 . . . . 1 . . . . 1 2 . 1 1 . . 1 . 1 . . . 1 . 3 . . . 1 1 1 1 1 . . .
q . . . . . . . 2 . . . 1 . 1 2 . 1 . 1 . . . . . . . 1 2 . . . . . 1 . . . . . 1 . 1 2 . . . . 2 .
r . . . . . . . . 2 . 3 . 4 . . . . 1 3 . . . 1 1 2 . . . . 1 . . . . . . . . . . . . . . . 1 . 1 .
s . . . 1 . . . . 2 . 2 . . 1 . 1 . 1 2 . . . 3 1 . . 1 1 . 1 . . 1 . . 3 . 1 . 1 . 1 . 1 . 3 . 1 2
t . . . . . . . . 3 . . . 2 . 1 1 . . 2 . 1 . 3 . 1 . . . . 2 . . . . 2 1 . . . . 1 . . . . 1 . . .
u . . . 2 . 1 . 1 . 2 . . . 2 2 . 2 2 1 1 . . . . 1 . 1 1 . . . 2 . . . 1 . . 1 . . 1 . . 3 . . 3 .
v . 1 . . . 1 1 . . 1 . . . 1 . . 1 . . . 2 . . . 1 . 1 . . 1 . . 1 . 1 2 . . 1 . . . . 2 . . . . .
w . 2 . . . 3 . . . . . . . 2 . . 2 1 . 1 . . . . . 1 1 . . 1 6 3 . . . 1 . . 2 . . 2 . . 1 . 1 . 1
x . . . . . . 1 1 . . 2 . . . 1 . 1 . . . . . . 1 . . 1 . . 1 . 1 1 3 1 . . . . . . . 3 2 . 1 . . 1
y . . . . . . . . 1 . 1 1 . . 1 1 . . . . . . 1 . 1 1 . 1 . . . . 1 . 1 . . 1 1 . . . . . . . . 2 .
z . . . . . . . . 1 2 2 2 1 . . . . . . . 2 . 1 1 2 2 . . . 2 . 1 1 1 2 . . 1 . 1 1 1 . 1 . . . . .
digram frequency: Pride and Prejudice (non-alphabetic characters removed)
536406 characters (each datum is ratio*10000; eg. 'a' ratio 777/10000, 'aa' ratio 1/10000)
777 169 251 416 1293 224 187 635 705 16 60 403 275 703 746 153 12 602 617 870 279 107 229 16 237 17
a b c d e f g h i j k l m n o p q r s t u v w x y z
a 1 30 24 47 0 12 18 2 30 0 11 55 29 149 1 17 0 79 96 107 10 28 9 0 23 0
b 5 0 . 0 78 . . 0 8 3 . 19 0 . 12 . . 6 3 2 21 0 . . 12 .
c 26 0 6 0 46 0 . 42 10 . 8 6 0 0 58 0 2 6 0 24 7 . 0 . 10 .
d 47 19 5 8 55 8 5 26 55 2 1 7 14 17 29 4 0 8 24 42 6 3 15 . 12 .
e 99 17 51 114 46 28 13 36 49 2 4 71 47 125 30 25 4 221 99 92 3 30 44 14 30 .
f 23 2 3 2 23 12 1 14 21 0 0 4 6 1 44 2 0 17 6 25 7 0 4 . 4 .
g 22 4 1 1 26 2 1 35 15 0 0 11 4 3 15 1 0 13 7 14 3 0 4 . 2 .
h 130 3 2 2 278 2 1 9 89 1 0 2 6 1 53 2 0 4 7 27 6 0 6 . 3 .
i 20 7 31 28 28 14 16 6 0 0 6 33 34 188 40 3 0 28 95 92 0 16 4 1 0 14
j 6 . . . 4 . . . 0 . . . . . 3 . . . . . 3 . . . . .
k 3 0 0 0 20 1 0 5 11 0 0 1 0 9 2 0 0 0 3 2 0 0 2 . 1 .
l 32 4 3 32 68 14 1 4 62 0 5 59 4 3 28 2 0 1 7 13 6 2 5 . 47 .
m 43 6 1 1 60 2 1 4 32 0 0 1 7 2 26 14 0 21 11 9 14 0 4 . 16 .
n 33 6 35 107 81 9 91 15 28 2 7 11 8 16 74 3 2 2 39 96 5 6 12 1 14 0
o 10 17 9 15 6 77 5 14 11 1 8 24 52 116 28 14 0 75 30 62 117 10 39 0 4 0
p 19 0 0 0 32 0 0 2 8 0 . 17 0 0 19 13 . 25 4 7 3 0 1 . 2 .
q . . . . . . . . . . . . . . . . . . . 0 12 . . . . .
r 46 12 22 26 142 13 6 16 48 1 3 13 18 14 45 7 0 15 52 47 7 5 15 . 27 .
s 54 15 15 7 78 11 5 66 56 1 2 8 13 11 50 20 1 5 53 90 30 3 19 . 4 .
t 54 13 9 7 87 7 2 279 84 1 2 20 14 6 114 6 1 19 27 54 17 1 25 . 19 1
u 12 5 21 6 8 1 16 2 8 0 1 33 7 27 1 9 0 49 33 36 0 0 3 0 0 0
v 7 . . . 80 . . . 16 . . . . . 4 . . 0 . . 0 . . . 0 .
w 53 1 1 1 34 1 0 46 49 0 0 2 2 10 20 0 0 2 3 3 0 0 2 . 0 .
x 1 0 3 . 1 0 . 0 1 . . . 0 . 0 5 0 . . 3 0 . 0 . 0 .
y 20 8 9 11 11 7 3 11 14 1 1 5 9 4 51 5 0 5 21 22 2 1 15 . 2 .
z 12 . . . 1 . . . 0 . . 0 . . . . . . . . . . 1 . 2 2
black chamber 1860
FOR NEXT TIME: make column width divisible by keylength
KRWAOIBCZMBPKSMVMWFEJMNMFIVMXKOTZIDIZPSZOVDLQKYVPIJU
CBREALOVDILGYNDHWEYUKNTMRQXDLPOUYNSTSAKSAKYVSCKUSTOG
WZWIXYKCXQFEJASBIOXPOQNEDJOZQSSGCAREAAVQCAVMVOSOUWXL
YWANOWPFDWBMXTAVOJESAVOACMSVPZKNUMCKYDWTQQYCGVNWKCUW
BLSNYBYVYTWAGZSTLMXQXTZMWIBGAVCWPATWYSLYSNBQONVWPTOO
FIBLYDSDSVMISADPOAJBSADWGZUMNOFBRMWAKBOZZIWKOBREKKRW
YLKISLSNSADIDEEMXBWOFLKGDHWLSAMONMBGLYSPOQNEDJOZQUFQ
FMBSABITSBJIBGWAFCCKBIHBOFZEJBKXZESZCBYCGVPQBMOPKBRA
KTYVQBWMXAESHMMBODABSAKLKWKVKNKEOZDHSBRICBWMXQXPDISV
FIWEPWBCWVDCBIWADPOMGVKTSSSQCSXOOVKAVAYQYKYNVISVSTST
SIXDWTQQYCGVNWGAKNSZCTFIWMNAKBRMVICMXMCSAVDPOPSQXBSN
YJIQDADQKVGRABOZQIGZQQYVSAKZSIFERWKLKWNIDEVBRMGOJSKB
LELEOMXAFLDPOUFQFMBSABIAKIV
black chamber 48 bce
HKR LRGMH MBXXMA FODXXM DHKYSAMDH HCBVM.
MQIHOMFMAHV EMEOMRALHFD HAMDP FRVVBPSHABV.
What does the message say? Who sent it? When?
Hint: the Latin alphabet of that time had no J,U,W,Y,Z,
and V would today be treated as U. So here is how
the Caesar 3-shift cipher would be implemented.
ABCDEFGHIKLMNOPQRSTVX
DEFGHIKLMNOPQRSTVXABC
- to get Latin plaintext, undo Caesar cipher, either by hand
or computer:
linuxmachine$ tr "D-IK-TVXA-C" "A-IK-TVX" < ciphertext
- to get modern-alphabet Latin, replace V with U
- to get English, use google translate
- to get date, search caesar bio
black chamber 900
ghrjdtip gszjwc chahyc yzi zy kwfzdtisx ghrdhrp eji zy vhp ghrdhrp
black chamber 1500
fg Y egf'n rmfn ng rkynj mfgnxjk nkmqjc oggb, Y rmfn ng rkynj m
nxkyccjk, mfe ya Y xmqj ng Y'cc ayfe mfgnxjk hpocylxjk
fgyegfnrmfnngrkynjmfgnxjknkmqjcoggbyrmfnngrkynjm
nxkyccjkmfeyayxmqjngyccayfemfgnxjkhpocylxjk
fgyzegfznrmfznngrzkynjzmfgznxjzknkzmqjczoggzbyrzmfnzngrkzynjm
znxkzyccjzkmfzeyayzxmqjzngyzccayzfemzfgnzxjkhzpocyzlxjk
' , Yy a b c e
f g h j k l m
n o p q r x
2 2 10 2 1 6 3
8 9 1 8 8 1 8
12 2 1 2 4 5
keyphrase substn cipher. what does the message say? who sent it? when?
black chamber 1599: trivial homophonic cipher
hjnrydjcidzdxhqtifhysskvlefxnochyldrevhewouldbesucceedjdby
maryavdthjnyfnzcjssaryjlizqbjthbythystimjhzwasquitj
dyzzyvzryanxiousavdqphysycqlwrzckixwasagreqtrjlijfwhenhjdyed
black chamber 1918
_ _ _ _ _ ._. ... .
_._. _ _ _ _.. . ...
_ .. ._.. ._.. .._
... . _.. _ _ _ _
_.. ._ _._ _ .._ _..
..._ .._. _.._ .._. _ _.
_.. _ _. ..._ _.. ._
..._ .._. _.. .._. ._
_.._ _.._ ..._ _.._ ._
..._ ..._ ._ ..._ _ _.
_.. .._. ..._ _ _. ..._
_.. ..._ _.._ _ _. _ _.
..._ _.. _ _. .._. _..
..._ _.. _..
_ _. .._. _.._
black chamber 1942
- Enigma crib loop search
- alignment ?
- loop(s) ?
- scrambler settings ?
u n i v e r s i t a t
F U U X U S A J T S I E N C V R T M P T N A R
black chamber: evolution of one-time-pad
xli izspyxmsr sj xli sri-xmqi-teh
Ycpgvcvcmc lkdpi pfi Rcnc-gjpkc em pfi 4pf aimpjkv co.
Ep emawjoig c oigaketpedm dh c gjxgpepjpedm aetfik.
.d-mryli-mk6iy8odbva+%7iv7mbv#o7-yrimh#-h.ola%
b18.1y7-8y7hik7'm6og7o1-9aymro1-by71-7k1hi'+a7iyl/-
+bi98a96+ry-logo6j8rik7l1i6/ysb-kmymrsh1-khsshi
k7'mloy6/-+ry-loyh-m6sh1ykhsshi+ai98b9r+l-y6oaiv1hhi
dydmeiccyhmyutwmgqmwgpxphvfcewgowprvgcwtq
jalprfcmivgenmrfgcwcpgpeugnjftmmprqlepogw
yzvfjgykvfkdkwcudifmvsitqqmwgpxphvfcelqkq
alqlkngknjpvuytpwwqeptvgdwivmnpxvctaekphc
issgygayplpaqkd
bdpoajhniyzqmurouuciknlztko
data for 3rd cipher
data for 4th cipher
196 characters 27 different (each datum is count)
2 3 16 3 8 6 7 2 13 1 8 11 7 16
2 7 3 10 12 5 7 2 15 8 10 8 4
# % ' + - . / 1 6 7 8 9 a b d g h i j k l m o r s v y
# . . . . 1 . . . . . . . . . . . . . . . . . 1 . . . .
% . . . . . . . . . 1 . . . 1 . . . . . . . . . . . . .
' . . . 1 . . . . . . . . . . . . . . . . . 2 . . . . .
+ . 1 . . . . . . . . . . 2 1 . . . . . . 1 . . 2 . . .
- . . . 2 . . . . . 1 1 1 . 1 . . 1 . . 2 2 3 . . . . 2
. . . . . . . . 1 . . . . . . 1 . . . . . . . 1 . . . .
/ . . . . 2 . . . . . . . . . . . . . . . . . . . . . 1
1 . . . . 4 . . . . . 1 . . . . . 2 1 . . . . . . . . 2
6 . . . 1 . . 2 . . . . . . . . . . 1 1 . . . 2 . 1 . .
7 . . 2 . 2 . . 1 . . . . . . . . 1 2 . 1 1 1 1 . . . .
8 . . . . . 1 . . . . . . 1 1 . . . . . . . . 1 1 . . 1
9 . . . . . . . . 1 . 2 . 1 . . . . . . . . . . 1 . . .
a . 1 . 1 . . . . . 1 . 1 . . . . . 2 . . . . . . . . 1
b . . . . 1 . . 1 . . . 1 . . . . . 1 . . . . . . . 2 1
d . . . . 1 . . . . . . . . 1 . . . . . . . . . . . . .
g . . . . . . . . . 1 . . . . . . . . . . . . 1 . . . .
h 1 . . . 1 1 . 2 . . . . . . . . 1 5 . . . . . . 2 . .
i . . 1 1 1 . . . 1 . . 2 . . . . . . . 3 . 1 . . . 2 2
j . . . . . . . . . . 1 . . . . . . . . . . . . . . . .
k . . . . . . . 1 1 3 . . . . . . 2 . . . . 1 . . . . .
l . . . . 1 . 1 1 . . . . 1 . . . . 1 . . . . 3 . . . .
m . . . . . . . . 2 . . . . 1 . . 1 . . 1 1 . . 3 . . 1
o . . . . . . . 2 1 1 . . 1 . 1 2 . . . . 1 . . . . . 2
r . . . 1 . . . . . . . . . . . . . 2 . . . . 1 . 1 . 3
s . . . . . . . . . . . . . 1 . . 4 . . . . . . . 2 . .
v 1 . . . . . . 1 . 1 . . 1 . . . . . . . . . . . . . .
y . . . . 2 . . . 2 3 1 . . . . . 1 . . 1 2 2 . 1 1 . .
length 4 substring frequencies
a b c d e f g h i j k l m n o p q r s t u v w x y z
0 0 3 1 4 3 4 1 2 2 2 2 3 2 0 2 3 0 0 1 1 1 3 1 4 0 45 0.0385
0 0 2 1 1 2 3 1 3 1 3 1 1 1 0 8 3 1 1 4 2 2 3 0 1 0 45 0.0524
3 0 2 3 2 2 5 2 0 1 2 1 3 0 0 3 2 2 1 1 0 5 2 2 1 0 45 0.0405
2 0 4 1 1 1 3 0 1 0 1 2 4 2 2 4 2 1 1 1 1 3 4 0 2 1 44 0.0372
0.0422
length 5 substring frequencies
a b c d e f g h i j k l m n o p q r s t u v w x y z
2 0 1 1 0 2 4 0 1 0 2 0 2 0 0 0 4 2 1 2 2 8 2 0 0 0 36 0.0741
0 0 3 0 0 5 5 0 0 2 1 2 3 1 1 4 3 0 1 0 0 0 1 0 4 0 36 0.0664
1 0 5 2 3 0 4 1 0 1 3 0 1 2 0 1 3 0 0 2 2 1 1 2 1 0 36 0.0463
2 0 2 3 2 0 0 0 0 1 0 2 4 2 0 10 0 0 1 1 0 0 2 0 3 1 36 0.0973
0 0 0 0 3 1 2 3 5 0 2 2 1 0 1 2 0 2 0 2 0 2 6 1 0 0 35 0.0621
0.0693
length 6 substring frequencies
a b c d e f g h i j k l m n o p q r s t u v w x y z
1 0 4 1 0 0 3 3 0 1 0 1 5 0 0 3 1 0 0 1 1 4 0 0 1 0 30 0.069
1 0 3 0 0 2 1 0 1 0 2 1 1 1 2 3 0 1 1 2 1 3 3 0 1 0 30 0.0356
2 0 0 2 0 3 5 0 2 2 1 0 0 2 0 1 2 1 0 0 0 2 4 0 1 0 30 0.0578
1 0 2 2 1 1 4 1 1 0 1 0 2 0 0 5 2 1 1 2 1 0 1 0 1 0 30 0.0467
0 0 1 1 6 2 1 0 0 0 3 2 1 0 0 1 2 1 1 1 0 0 1 3 3 0 30 0.0601
0 0 1 0 1 0 1 0 2 1 1 2 2 2 0 4 3 0 0 1 1 2 3 0 1 1 29 0.0405
0.0516
gcw 21
qmwgpxphvfce 90
