### 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.]

• 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

• #### 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


• railfence cipher
r    i    f    n    e    i    h    r
\   /\   /\   /\   /\   /\   /\   /\
\a/  \l/  \e/  \c/  \c/  \p/  \e/  \

rifneihraleccpe


#### substitution cipher

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?)
• 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.)
• 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

• our story so far ...
• codemakers: mono'subst'n cipher
• codebreakers: frequency analysis
• Battista Alberti, b 1404 Florence   2-alph'c subst'n
• Johannes Trithemius, b 1462 Germ.
• Giovanni Porta, b 1535 Italy
• Blaise de Vigenère, b 1523 France
• 39 => scholar
• 1586 Traicté des Chiffres
• polyaphabetic keyword shift subst'n cipher
• not used for 2 centuries
• misnamed cipher?
key-letter a b c ...  z
shift      0 1 2 ... 25

ciphertext:     fk( pj ) = ( pj + kj mod m) mod 26
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

#### 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 * *
* * * *
* * * *
* * * *
* * * *
* * * *
* * * *
* *


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

• running key cipher:     cryptanalysis?
• Maj. Joseph Mauborgne, US Army, 1918

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


#### 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
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 zincbesh-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, axewol-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
• 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
• polymath Grk Lat Fr Ital Heb Chald Syr Sam Arab Pers Turk Eth
• Cambridge medicine, eye
 -----------
| cartouche |
-----------

• 1814 summer: foreign name would have to be phonetic     Ptolemy ?     Berenika ?
• rest of text ? ( respect for Kircher ? )
• Ptolemy → Copernicus → Brahe → Kepler ( respect for Brahe ? )
• 1819 Encyclopedia Brittanica
• 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
• 1939 Carl Bergen finds linear B tablets in Pylos (Greek mainland)
• 1906-1950 Alice Kober
• varying syllable triplets → inflective language, eg. Akkadian
   sadani       sa da ni

• from Fig. 8 in Kober's paper
case
1     25 26 37 57        70 52 41 57
2     "  "  "  36        "  "  "  36
3     "  "  05           "  "  12

• Kober's conjectures
• each word: common 5-ltr stem
• each case: common end (case 1,2: 3 ltrs; case 3: 1 ltr)
• common (3-ltr) end ...37-57, ...41-57 → common vowel 37,41
• common (1-ltr) end ...05, ...12 → common vowel 05,12
• common (5-ltr) stem 25-26... → common consonant 37,05
• common (5-ltr) stem 70-52... → common consonant 41,12
• 1922-1956 Michael Ventris
• extended Kober's ideas
• some symbols prob. single vowels; recognize by high initial frequency
• grouped many symbols with common initial consonant
• Ventris's grid
• frequently repeated words: town names ?
• town with initial vowel ? Amnisos ? → 08-73-30-12 = a-mi-ni-so = Aminsos ?
• next: 70-52-12 = ?o-?o-so = ko-no-so = Knossos ?
• next: 69-53-12 = ??-?i-so = tu-li-so = Tulissos ?
• next: more words ... Greek !!!
• expert in archaic Greek, Greek philology (language evolution)
• 1953 Chadwick/Ventris   Evidence for Greek Dialect in the Mycenaean Archives
• prob. ≈ 1450 BC Mycenaeans conquered Minoans
• h2g2's decipherment of linear B

#### 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 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
• 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

• computers use binary numbers
• like decimal, a positional number system
• decimal-binary conversion

 217 = 2 × 108 + 1 108 = 2 × 54 + 0 54 = 2 × 27 + 0 27 = 2 × 13 + 1 13 = 2 × 6 + 1 6 = 2 × 3 + 0 3 = 2 × 1 + 1 1 = 2 × 0 + 1

110110012
= 1 × 27 + 1 × 26 + 0 × 25 + 1 × 24 + 1 × 23 + 0 × 22 + 0 × 21 + 1 × 20
= 1 × 128 + 1 × 64 + 0 × 32 + 1 × 16 + 1 × 8 + 0 × 4 + 0 × 2 + 1 × 1
= 21710

• characters as binary numbers: e.g. ASCII code

#### 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

• exponentiation     be = ?
• logarithm (exponent)     x = b?
• discrete exponentiation     (be) mod n = ?
• discrete logarithm     x = (b?) mod n
• modular arithmetic, a.k.a. clock arithmetic
for * ∈ { × , + , - } :
( a * b ) mod n = ( (a mod n) * (b mod n) ) mod n
• how to compute a**423 ?
usual method            fast method    hint: 423 = 0b 110100111

x = 1    <- a**0        x = 1          <- a**0
x = x*a  <- a**1    1   x = x*x*a      <- a**1
x = x*a  <- a**2    1   x = x*x*a      <- a**3
x = x*a  <- a**3    0   x = x*x        <- a**6
x = x*a  <- a**4    1   x = x*x*a      <- a**13
x = x*a  <- a**5    0   x = x*x        <- a**26
x = x*a  <- a**6    0   x = x*x        <- a**52
x = x*a  <- a**7    1   x = x*x*a      <- a**105
x = x*a  <- a**8    1   x = x*x*a      <- a**211
x = x*a  <- a**9    1   x = x*x*a      <- a**423
x = x*a  <- a**10
x = x*a  <- a**11
x = x*a  <- a**12
...
...
...
x = x*a  <- a**423

• steps to compute a**(10**1000) = digits in binary rep'n of 10**1000 = 3322
• (discrete) exponentiation? fast ...
• number of operations proportional to number of bits in exponent

#### 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

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 ?
• number theory ...

#### 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
• cs, U de Montréal
• 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


#### 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":
• 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