scene: Fotheringhay Castle, October 15, 1586
players: QE MQS Walsingham
offstage: Phelippes conspirators
Herodotus Histories
Persia v Greece c-480 Xerxes Demaratus waxed tablets
Persia v Miletus c-499 Histaiaeus shaved head
steganography covered/concealed writing
cryptography hidden/scrambled writing
encryption: a function f maps (plaintext, key) to ciphertext
decryption: f-inverse maps (ciphertext,key) to original plaintext
security ? ease of use ?
two operations commonly used in early ciphers: transposition, substitution
Spartan scytale c-400 Lysander v Pharnabazus
more recent railfence cipher
plaintext
sendmoretroopstosouthernflank
key (circumference of scytale)
4
how to pick the width ?
usually, round up (characters / key), then
pad any unused locations with garbage letters
here, round up ( 29 / 4 ) = 8,
pad final 3 unused locations with garbage x q i
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
ciphertext
stsferolnouadotnmphkosexrtrqeoni
plaintext railfencecipher key (depth of rail peaks) 2 r i f n e i h r \ /\ /\ /\ /\ /\ /\ /\ \a/ \l/ \e/ \c/ \c/ \p/ \e/ \ ciphertext rifneihraleccpe
warning: for depth more than 2, there are two encryption methods
- down and up
- down only
plaintext
railfencecipher
----------------------------------------
key: 3, down and up
r f e h
a l e c c p e
i n i r
rfehalceepeinir
----------------------------------------
key: 3, down only
r l n c h
a / f / c / i / e
i e e p r
rlnchafcieieepr
how many arrangements of toboot ?
b:1 t:2 o:3
6!/(2! * 3!) = 720/(2*6) = 60
for example consider this short sentence
35 letters, distributed as a-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
number of arrangements of 1-2-1-6-2-2-1-1-3-3-1-3-4-3-1 multiset is 35! / (1! * 2! * 1! * 6! * 2! * 2! * 1! * 1! * 3! * 3! * 1! * 3! * 4! * 3! * 1! ) = 5.7e31
transliteration e.g. Roman <--> Greek
related evolution of alphabets
Caesar shift
(except for transliteration) these are variants of monoalphabetic substitition cipher (masc)
plaintext this cipher is old key a b c d e f g j l n o p t v h m x u w i k r s q y z ciphertext zbgn mgybul gn qrx
transliteration
a b c ... => α β γ ...
Valerius Probus On Caesar's Ciphers :(
shift
plaintext beware the ides of march key (shift) 3 ciphertext ehzduh wkh lghv ri pdufk
create file plain.txt encrypt (above kama sutra subs'n cipher) tr abcdefgjlnoptvhmxuwikrsqyz vhmxuwikrsqyzabcdefgjlnopt < plain.txt > c.txt decrypt tr abcdefgjlnoptvhmxuwikrsqyz vhmxuwikrsqyzabcdefgjlnopt < c.txt other examples * caesar-3 tr a-z d-za-c ... decrypt: tr d-za-c a-z ... * atbash tr a-z zyxwvutsrqponmlkjihgfedcba ... * rot13 tr a-z n-za-m ...
26 ! (26 factorial) how big is this ? ask python ... (or ask google) $ python >>> from math import factorial >>> factorial(26) 403291461126605635584000000L >>> 1.0 * factorial(26) 4.0329146112660565e+26
write each key in alphabetic order
above example: av bh cm dx eu fw gi jk lr ns oq py tz
how many such keys?
first character? 1 choice: a
next: 25 choices
next: 1 choice: 1st in alphabetic order after 3 previous characters removed
next: 23 choices
next: 1 choice
next: 21 choices
...
total number of keys = 25 * 23 * 21 * 19 * 17 * 15 * 13 * 11 * 9 * 7 * 5 * 3 * 1 = 7.9e12
today's computers perform more than 1e8 operations/second, so brute force search of kama sutra cipher is feasible, especially with parallel threads
so kama sutra has too few keys to be secure
750 Abassid caliphate: conquest?
no!
consolidation ... arts/sciences flourished in equal measure
administration, communication => crypto
monoalphabetic substitution cipher
each Muslim required to pursue ilm (knowledge) in all forms
Baghdad: Bait al-Hikmah (library/translation centre), languages: Egypt, Babylon, India, Persia, Syria, Armenia, Judea
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
what al-Kindi did not mention, but surely knew
combine frequency analysis with knowledge of texts (corpus, word lists, dictionary)
frequency analysis: Al Kindi's rule + dictionary
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/context
guess words/phrases
tools
linux command: tr
210 python code: freqs.py
pcq vmjypd lbyk lyso kbxbjxwxv bxv zcjpo eypd kbxbjyuxj lbjoo kcpk cp lbo lbcmkxpv xpv iyjkl pydbl qbop kbo bxv opvov lbo lxro ci sx xjmi kbo jcko xpv eykkov lbo djcmpv zoicjo bys kxuypd djoxl eypd icj x lbcmkxpv xpv cpo pydblk y bxno zoop joacmplypd lc ucm lbo ixzrok ci fxkl xdok xpv lbo rodopvk ci xpayopl eypdk sxu y sxeo kc zcrv xk lc ajxno x ixncj ci ucmj sxgoklu ofyrcdmo lxrok ijcs lbo lbcmkxpv xpv cpo pydblk English e t a o i n s h r d l c u m w f g y p b v k j x q z ciphertext o x p c k b l y j v d i m s r u e z a n f q g w h t 38 34 31 27 26 25 25 19 18 18 14 11 10 7 6 6 5 5 3 3 2 2 1 1 0 0 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 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 b 0 0 3 0 0 0 0 0 0 3 0 3 0 0 9 0 0 0 0 0 0 0 0 5 2 0 c 0 0 0 1 0 0 0 0 4 4 1 0 7 0 0 4 1 1 1 0 0 0 0 0 0 0 d 0 3 0 0 0 0 0 0 0 2 1 0 1 0 2 0 0 0 0 0 0 0 0 0 0 0 e 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 4 0 f 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 g 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 h 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 i 0 0 2 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1 0 j 0 0 3 0 0 0 0 0 0 0 1 0 1 0 4 1 0 0 0 0 0 0 0 2 2 0 k 0 4 2 0 0 0 0 0 0 0 1 3 0 0 2 0 0 0 1 0 0 0 0 4 0 0 l 0 11 2 0 0 0 0 0 0 0 2 0 0 0 0 0 1 0 0 0 1 0 0 2 2 0 m 0 0 0 0 0 0 0 0 1 2 3 0 0 0 1 2 0 0 0 0 0 0 0 0 0 0 n 0 0 1 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 o 1 0 0 1 0 1 0 0 1 0 4 0 0 0 2 5 0 0 0 0 0 2 0 1 0 0 p 1 0 1 6 0 0 0 0 0 0 1 2 0 0 3 0 0 0 0 0 0 11 0 0 3 0 q 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 r 0 0 1 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 1 0 0 0 0 s 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 4 0 0 t 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 u 0 0 2 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 v 0 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 w 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 x 0 2 0 1 1 0 1 0 0 2 2 1 0 3 0 9 0 2 0 0 2 3 1 0 0 1 y 0 0 0 3 0 0 0 0 0 1 2 0 0 0 1 6 0 1 2 0 1 0 0 0 0 0 z 0 0 2 0 0 0 0 0 0 0 0 0 0 0 2 0 0 1 0 0 0 0 0 0 0 0
from above
1=o before 9 letters after 16 vowel ? a, e, ... ?
2=x before 14 letters after 10 vowel ? a, e, ... ?
3=p before 8 letters after 6 consonant ? t, n, ... ?
abcdefghijklmnopqrstuvwxyz
tr 'a-z' '..............13.......2..' < ch1.ctxt
3.. ....3. .... ...1 ..2..2.2. .2. ...31 ..3.
..2....2. ...11 ..3. .3 ..1 .....23. 23. ..... 3....
..13 ..1 .2. 13.1. ..1 .2.1 .. .2 2... ..1 ...1 23.
....1. ..1 ....3. .1...1 ... .2..3. ..12. ..3. ... 2
.....23. 23. .31 3..... . .2.1 .113 .1...3..3. .. ...
..1 .2..1. .. .2.. 2.1. 23. ..1 .1.13.. .. 23..13. ..3..
.2. . .2.1 .. .... 2. .. ..2.1 2 .2... .. .... .2.1...
1......1 .2.1. .... ..1 .....23. 23. .31 3.....
which fits better: 1a 2e or 1e 2a ?
...11 .113 suggests 1 likely e
try 1=e 2=a
example: look at pairs involving e
which letter most frequently precedes e?
above: ctxt b (ptxt h?) most often precedes ctext o (ptxt e?)
try ctxt abcdefghijklmnopqrstuvwxyz
ptxt .h............e3.......a..
3.. ....3. .h.. ...e .hah.a.a. ha. ...3e ..3.
.hah...a. .h.ee ..3. .3 .he .h...a3. a3. ..... 3..h.
.he3 .he ha. e3.e. .he .a.e .. .a a... .he ...e a3.
....e. .he ....3. .e...e h.. .a..3. ..ea. ..3. ... a
.h...a3. a3. .3e 3..h.. . ha.e .ee3 .e...3..3. .. ...
.he .a..e. .. .a.. a.e. a3. .he .e.e3.. .. a3..e3. ..3..
.a. . .a.e .. .... a. .. ..a.e a .a... .. .... .a.e...
e......e .a.e. .... .he .h...a3. a3. .3e 3..h..
3-letter words:
.he = the => lbo = the => ctxt-l = ptxt-t
a3. = and => xpv = and => ctxt-p = ptxt-n ctxt-v = ptxt-d
n.. d...n. th.. t..e .hah.a.ad had ...ne ..n.
.hah...a. th.ee ..n. .n the th...and and ....t n..ht
.hen .he had ended the ta.e .. .a a... .he ...e and
....ed the ....nd .e...e h.. .a..n. ..eat ..n. ... a
th...and and .ne n..ht. . ha.e .een .e...nt.n. t. ...
the .a..e. .. .a.t a.e. and the .e.end. .. an..ent ..n..
.a. . .a.e .. ...d a. t. ..a.e a .a... .. .... .a.e.t.
e......e ta.e. .... the th...and and .ne n..ht.
3-letter words:
.ne = one => cpo = one => ctxt-c = ptxt-o
no. d...n. th.. t..e .hah.a.ad had .o.ne ..n.
.hah...a. th.ee .on. on the tho..and and ....t n..ht
.hen .he had ended the ta.e o. .a a... .he .o.e and
....ed the ..o.nd .e.o.e h.. .a..n. ..eat ..n. .o. a
tho..and and one n..ht. . ha.e .een .e.o.nt.n. to .o.
the .a..e. o. .a.t a.e. and the .e.end. o. an..ent ..n..
.a. . .a.e .o .o.d a. to ..a.e a .a.o. o. .o.. .a.e.t.
e...o..e ta.e. ..o. the tho..and and one n..ht.
exercise: finish this off (solution in Singh)
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.
uko vqbo uj cyrejwoq roeqour yr coolma ygbqtygoc yg kvntg gtuvqo; owog uko motru evqyjvr nygc yr qjvroc ha uko lqjnyro jd rktqygb igjxmocbo xyukkomc dqjn jukoqr. sjkg ektcxyei a b c d e g h i j k l m 2 4 8 2 5 10 1 2 10 10 2 4 n o q r s t u v w x y 4 20 11 11 1 6 9 6 2 3 12
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
monarch power devolving, female reign tenuous
Henry I -1135 charter of liberties
John 1215 Magna Carta
Lady Jane Grey -1554 reign 6 weeks
Mary I 1554-1558 reign 5 years
Elizabeth I -1603 reign 44 years video et taceo
our story
1558 Elizabeth I
1559 religious settlement (leads to Church of England)
1570 Pope declares her illegitimate
1586 war with Spain coming
preparing to invade France, Henry VIII moves to eliminate Scottish threat to north
1542 Henry VIII v Scots @ Solway Moss b Mary d James V
1543 Mary crowned (infant)
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
Walsingham crypto savvy
Cardano text
1577 van Marnix thwarts Philip II Spain plan to invade England
Gifford double ? triple ? agent
1585 to W I have heard of the work you do
arranges to deliver letters from Paris to Mary (via W)
1586 meets Babington with letter from Mary (via W)
cipher school London Phelippes
1586 July 17 Mary replies to Babington via Gifford
G -> W -> P + ps -> W -> G -> Babington
gruesome end Babington plot
1587 February 8 Mary Queen of Scots executed