duo-alphabetic substitution cipher
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
f z b v k i x a y m e p l s d h j o r g n q c u t w cipher1
g o x b f w t h q i l a p z j d e s v y c r k u h n cipher2
plaintext d u o a l p h a b e t i c
ciphertext v c d g p d a g z f g q b
39 => scholar
1586 Traicté des Chiffres
polyaphabetic keyword shift subst'n cipher
not used for 2 centuries
wiki aka clock arithemetic
9 hours ago it was 4 oclock: what time is it now ?
(9 + 7) (mod 12) = 16 (mod 12) = 4
a (mod n) is remainder of integer division a / n
a (mod n) will be an integer in range 0 1 … n-1
key-letter a b c ... z
shift 0 1 2 ... 25
W H I T E W H I T E W H I T E W H I T E W H I key
d i v e r t t r o o p s t o e a s t r i d g e ptxt
Z P D X V P A Z H S L Z B H I W Z B K M Z N M ctxt
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 = fk( pj ) = ( pj + kj mod m) mod 26
in general, cj = ( pj + kj mod κ ) mod α
Alberti
26! x 26! = 1.6e53
Vigenere, keyphrase length t
26t
t = 10: 2610 = 1.4e14
t = 20: 2620 = 2.0e28
t = 30: 2630 = 2.8e42
goal: to smooth the expected distribution of ciphertext letter frequencies
one way: homophonic substitution cipher
e.g. use 100 characters for ciphertext
encryption
e: homophones {e_;}
a: homophones {a,}
t: homophones {t?}
everything else: itself
ptxt
forcenturiesthesimplemonoalphabeticsubstitu
tioncipherhadbeensufficienttoensuresecrecy
ctxt
forc_n?uries?hesimpl_monoalph,beticsubsti?u
?ionciph;rh,dbeensuffici_ntto_nsur;s;cr_cy
ctxt frequencies
i s c n _ e o r u ? h t ; b f p , m l a d y
8 7 6 6 5 5 5 5 5 4 4 4 3 3 3 3 2 2 2 1 1 1 85 chars
a 9 12 33 47 53 67 78 92 b 48 81 c 13 41 62 d 1 3 45 79 e 14 16 24 44 46 55 57 64 74 82 87 98 f 10 31 g 6 25 h 23 39 50 56 65 68 i 32 70 73 83 88 93 j 15 k 04 l 26 37 51 84 m 22 27 n 18 58 59 66 71 91 o 0 5 7 54 72 90 99 p 38 95 q 94 r 29 35 40 42 77 80 s 11 19 36 76 86 96 t 17 20 30 43 49 69 75 85 97 u 8 61 63 v 34 w 60 89 x 28 y 21 52 z 02
1626 decipher Huguenot message
devise great cipher Louis XIV
after death of fils R, cipher fell into disuse
historians: how to read this ciphertext ?
1890 Gendron --> Bazeries
587 symbols
homophonic ?
digraphs ?
124-22-125-46-345 … 124-22-125-46-345 … 124-22-125-46-345 …
crib: 124-22-125-46-345 = les enemis = les-en-ne-mi-s ?
syllabic substn !
his majesty desires that you arrest General Bulonde and cause him to be conducted to the fortress of Pignerole, where he will be locked in a cell under guard at night, and permitted to walk the battlements during the day with a mask
1698 Bastille, man in iron mask comic General de Bulonde?
1700s industrialized cryptanalysis
Vienna Geheime Kabinets Kanzlei
cryptographers: polyalphabetic vs cryptanalysis: black chambers
1800s telegraph, morse code
Vigenère vs le chiffre indéchiffrable
speedometer, cowcatcher, tree ring, stats, mortality
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 (repeated ctext fragment offsets)
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
1922 Friedman: ioc, imc
running key cipher: Vig', w long keyword (e.g. use book)
rywutjivvisjeknpamrrrcuguwzrepxqjfvcugnsjxtbujsk lqdmajieftqwfspghvidfyyptqtswgydjyyevapjbysnlmkkfvv vnymvipntnxyqkulnxumtlkyjuxqmqsirhkmnnhlpvfiijwiea wwfemowwxxzfksqydzrkaqkdfyuwmfpksjputkrqcjpnsvjqy xjjcmpniutkevvpjbzpnwztsfypjmnyzqrvaxnspgpndtltglt fufxcawbnklkajjkfvgoqxjpiuombncpflkqfiikacxjciuz jjhryulqybzpnuwyxcmeliuneicwxqjzqrhzyyyiuhujuimpjquqv stzptbklgzirjdeeoqsjkscuirjimehvtwksqumtkfytjwqtemuaa fsucqbenqcsdzmwavxjhbymvajvtjjwjqybtkymutqsizwvvnnsu wqtmsjnerwtnhrxkvvtkklgwznstmrsmxtdiplezxvjqybmjzruazzrvrv a b c d e f g h i j k l m 14 11 13 9 16 18 9 9 23 38 26 14 24 n o p q r s t u v w x y z 25 4 22 28 19 23 27 28 27 22 18 26 19 max freq 38/512 = .074
Babbage/Kasiski
find keylength with repeated kgram offsets
for each substring, find shift by hand
Friedman 1922
find keylength with index of coincidence
for each substring, find shift by index of mutual coincidence
gcd of repeated kgram offsets cug 14 xqj 294 spg 175 dfy 105 pjb 126 kfv 168 vvn 350 ymv 322 umt 269 <-- false positive qsi 315 fii 143 <-- false positive ksq 222 <-- false positive utk 22 <-- false positive jqy 238 zqr 98 qyb 131 194 <-- false positives klg 119 irj 14 wqt 60 <-- false positive vjqy 301 bzpn 91 jqyb 63 false positive example key ? ? i f f ? ? ? ? ? f f r ? ptxt . . m o t . . . . . p o t . ctxt . . u t k . . . . . u t k .
- keylength known, now find shifts by hand (eyeball)
eg. shift until 9 most freq chars align with typical English
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
* * * * * * * * *
- substring 0: maybe 'c' ?
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 6 1 5 2 7 0 0 3 7 0 0 4 1 5 8 5 0 4 8 7 0 0 1 0
* * * * * *
- substring 1: maybe 'h' ?
8 2 0 1 0 1 0 5 0 4 0 7 2 2 3 5 0 0 2 3 6 7 6 0 5 4
* * * * * * * *
3 3 1 1 2 0 2 0 6 2 2 1 9 4 0 4 9 0 0 5 3 3 6 3 0 4
* * * * *
1 2 0 1 0 3 0 0 2 9 2 0 2 10 0 0 5 2 5 7 5 0 3 5 7 2
* * * * * * * *
1 4 0 3 0 3 0 3 2 15 6 0 2 4 0 1 2 2 7 6 2 0 2 5 3 0
* * * * *
0 0 5 2 4 8 0 0 4 2 8 2 0 1 0 1 0 5 3 1 4 7 2 0 5 9
* * * * * * *
1 0 1 0 5 1 0 1 9 3 1 4 9 0 0 6 4 5 6 1 0 3 3 5 5 0
* * * * * * * *
keyword ?: c h ? ? ? ? ?
given basket of characters, probability that
two 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
source https://en.wikipedia.org/wiki/Letter_frequency accessed 2017-01-01 .082 .015 .028 .043 .127 .022 .020 .061 .070 .002 .008 .040 .024 .067 .075 .019 .001 .060 .063 .091 .028 .010 .024 .002 .020 .001
ioc is sum of squares of above probabilities 0.065124
* by random, we mean uniform random, i.e. equiprobable
* so fraction of each character will be close to 1/26
* so close to (but a bit larger than, since
sum of squares of numbers that add up to a fixed
total is minimized when all numbers are same)
(1/26)^2 + (1/26)^2 + ... + (1/26)^2
= 26(1/26)^2 ≈ .038
given two baskets of characters, probability that
element equiprobably-selected from one basket equals
element equiprobably-selected from other basket
{ 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...
* recall above ctxt: rywutjivvisjek...
* for each possible keylength
find ioc of each substring (English .065)
1 .042
2 .041 .043
3 .044 .041 .042
4 .045 .043 .040 .048
5 .045 .040 .043 .041 .042
6 .042 .040 .043 .056 .036 .042
7 .066 .057 .056 .066 .074 .063 .061 <--
8 .048 .043 .034 .047 .042 .042 .047 .049
9 .043 .050 .038 .046 .043 .036 .049 .047 .043
...
* assume language with 5 char alphabet, typical freq:
a b c d e
.27 .13 .07 .20 .33
* assume ctext substring with this distribution:
(a bbb ccccc dddd ee)
* which shift gives best IMC ?
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
shift 2 is best
* for each substring, find shift maximizing imc
substring 0
shift 0 .033
shift 1 .037
shift 2 .066 <-- 'c'
shift 3 .040
shift 4 .029
shift 5 .027
shift 6 .047
shift 7 .030
shift 8 .032
shift 9 .039
shift 10 .036
shift 11 .034
shift 12 .042
shift 13 .051
shift 14 .032
shift 15 .035
shift 16 .043
shift 17 .050
shift 18 .030
shift 19 .027
shift 20 .029
shift 21 .033
shift 22 .034
shift 23 .035
shift 24 .046
shift 25 .037
repeat for other substrings
<-- 'c h i f f r e'
by 1830s social change telegraph bicycle
=> public interest in cryptography
Victorian England + romance? => agony columns
Babbage Wheatstone Playfair
dear charlie write no more our cipher is discovered
postal fees => pinprick cipher
Polybius credits Aeneas Tacticus
. ._ ... .. ._.. _.__ .. _. _ . ._. _._. . .__. _ . _..
. .
Transliteration is the conversion
. . .
of a text from one script to another.
.
It is concerned not with the sounds
. .
of the original but only the accurate
mapping of the characters.
1840 Poe secret writing
1843 Poe The Gold Bug
1864 Verne Journey tt Centre ot Earth
1885 Verne: Mathias Sandorf
turning grille cipher (Cardano)
1903 Doyle Adventure of the Dancing Men
steganography, substitution
1915 Buchan: 39 Steps
- pick a grille size, say 6x6 - there will be 6x6 / 4 = 9 holes in the grid - pick a pattern for the 9 holes - 1st hole, and its 3 rotations + 1 + + + + + + + + + * + + + + + + + + + + + + * + + + + + + + + + * + - repeat for remaining holes, e.g. + 1 + 2 3 + + + + + + + + 4 + 5 6 + 7 + + + + + + 8 + + + + + + + + + 9 - choose the order of rotations e.g. clockwise - write plaintext across the rows + W + A L + + + + + + + + S + I N + G + + + + + + H + + + + + + + + + A + + M + + + + H + A + S + + + + + + + + + C + R + + + A + C K + + + + + E + + + + + + + + + D + + + + + + M + A R + Y + + + + + + + + S C + I + + + + + + R W + A + + + R + N + + + + + + + + + B + A + B + + + + B + + E W M A L R W H A A D S R S N I N M G A R C Y R B H A A B C K S C B I A ciphertext: read the columns EWRG BKW HSAHS MANRACA AICA BL DNY BIRSM RCAZQ
book cipher
key: a book
replace 1st letter of each word with word number
becomes a homophonic cipher
key: The vast sun was past its zenith, hot like an xray. Giant pandas raced back and forth. A mangy cat jumped on the kid, until then quietly eying the dozing newt. He yelped. 0 1 2 3 4 5 6 The vast sun was past its zenith, 7 8 9 10 11 12 hot like an xray. Giant pandas 13 14 15 16 17 18 19 raced back and forth. A mangy cat 20 21 22 23 24 25 26 jumped on the kid, until then quietly 27 28 29 30 31 32 eying the dozing newt. He yelped. ciphertext: 31 21 18 21 4 31 21 30 5 19 plaintext ?
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 ciphertext: 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 plaintext: ? 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
1854 Charles Wheatstone, popularized by 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
#/media/File:ChessBoardCipher.png){kind=link}
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
decrypt: BC DW UP PF GC
ea sy to us ev
use digram frequency analysis
1932 Dorothy L Sayers have his carcase
LP YN UG DZ UC PA DS OT MS AE SE CU DH NK BU UC ES TG YD
h o m o p h o n i c h o w i s t h e p o l y b i u s g r i d u s e f u l i n t e l e g r a p h y