# jemdoc: addcss{rbh.css}, addcss{jacob.css}
= ch2: le chiffre indechiffrable
~~~
{}{raw}
vig
shun
Ross
chamber
BV
crack
BK
ioc
imc
Friedman
agony
Beale
Polybius
Playfair
~~~
~~~
{}{raw}
evolution of Vigenere
~~~
~~~
- [https://en.wikipedia.org/wiki/Leon_Battista_Alberti Alberti]
-- 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+
- [https://en.wikipedia.org/wiki/Johannes_Trithemius Trithemius]
- [https://en.wikipedia.org/wiki/Giambattista_della_Porta della Porta]
- [https://en.wikipedia.org/wiki/Giovan_Battista_Bellaso Bellaso]
- [https://en.wikipedia.org/wiki/Blaise_de_Vigen%C3%A8re Vigenere]
-- {{39 => scholar}}
-- 1586 Traicté des Chiffres
-- polyaphabetic keyword shift subst'n cipher
-- not used for 2 centuries
~~~
~~~
{modular arithmetic}
- [https://en.wikipedia.org/wiki/Modular_arithmetic 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
~~~
~~~
{Vigenere cipher}{}
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
~~~
~~~
{Vigenere encryption function}
{{cj = fk( pj ) = ( pj + kj mod m) mod 26}}
in general, ~ {{cj = ( pj + kj mod κ ) mod α}}
~~~
~~~
{number of keys}
- 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}}
~~~
~~~
{}{raw}
shunning Vigenere
~~~
~~~
- goal: to smooth the expected distribution of ciphertext letter frequencies
- one way: homophonic substitution cipher
- e.g. use 100 characters for ciphertext
~~~
~~~
{simple homophonic cipher}{}
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
~~~
~~~
{text eg.: 100-ctxt-character homophonic cipher}{}
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
~~~
~~~
{}{raw}
pere et fils Rossignol
~~~
~~~
{}
- 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, [https://en.wikipedia.org/wiki/Man_in_the_Iron_Mask man in iron mask] ~ [https://www.mycomicshop.com/search?TID=395571 comic] ~ General de Bulonde?
~~~
~~~
{}{raw}
black chambers
~~~
~~~
- 1700s industrialized cryptanalysis
- Vienna /Geheime Kabinets Kanzlei/
- cryptographers: polyalphabetic vs cryptanalysis: black chambers
- 1800s telegraph, morse code
- Vigenère vs le chiffre indéchiffrable
~~~
~~~
{}{raw}
Babbage v Vigenere
~~~
~~~
{}
- 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)
~~~
~~~
{}{raw}
crack this
~~~
~~~
{}{}
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
~~~
~~~
{cracking vigenere}
- 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
~~~
~~~
{}{raw}
Babbage/Kasiski
~~~
~~~
{BK keylength}{}
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 .
~~~
~~~
{BK shifts}{}
- 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 ? ? ? ? ?
~~~
~~~
{}{raw}
index of coincidence
~~~
~~~
{}{}
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
~~~
~~~
{English letter frequency (as probability)}{}
.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
https://en.wikipedia.org/wiki/Letter_frequency accessed 2017-01-01
~~~
~~~
{ioc English text}{}
ioc is sum of squares of above probabilities
0.066
~~~
~~~
{ioc random English letters}{}
* 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
~~~
~~~
{}{raw}
index of mutual coincidence
~~~
~~~
{}{}
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...
~~~
~~~
{}{raw}
Friedman
~~~
~~~
{keylength}{}
* 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
...
~~~
~~~
{shifts via imc: small example}{}
* 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
~~~
~~~
{shifts via imc: above ctxt}{}
* 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'
~~~
~~~
{}{raw}
agony columns to buried treasure
~~~
~~~
- by 1830s social change ~ [https://en.wikipedia.org/wiki/Electrical_telegraph\#History telegraph] ~ [https://www.theguardian.com/environment/bike-blog/2015/jun/09/feminism-escape-widneing-gene-pools-secret-history-of-19th-century-cyclists bicycle]
-- [https://en.wikipedia.org/wiki/Morse_code Morse code]
-- {{=>}} 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
-- [https://en.wikipedia.org/wiki/Polybius Polybius] credits [https://en.wikipedia.org/wiki/Aeneas_Tacticus Aeneas Tacticus]
~~~
~~~
{decipher this}{}
. ._ ... .. ._.. _.__
.. _. _ . ._. _._. . .__. _ . _..
~~~
~~~
{crack this}{}
. .
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.
~~~
~~~
{crypto lit}
- 1840 Poe [http://www.scientificamerican.com/article/a-cipher-from-poe-solved/ secret writing]
- 1843 Poe [https://en.wikipedia.org/wiki/The_Gold-Bug The Gold Bug]
- 1864 Verne Journey tt Centre ot Earth
-- [https://en.wikipedia.org/wiki/Journey_to_the_Center_of_the_Earth\#/media/File:Jules_verne_cryptogramme.png rune cipher]
- 1885 Verne: Mathias Sandorf
-- turning grille cipher (Cardano)
-- [https://en.wikipedia.org/wiki/Grille_(cryptography)\#/media/File:ChessBoardCipher.png simpler checkerboard cipher]
- 1903 Doyle [https://en.wikipedia.org/wiki/The_Adventure_of_the_Dancing_Men Adventure of the Dancing Men]
-- steganography, substitution
- 1915 [https://en.wikipedia.org/wiki/John_Buchan Buchan]: 39 Steps
-- [http://www.cleavebooks.co.uk/grol/buchan/39step03.htm substitution: numerals]
~~~
~~~
{make a turning grille cipher}{}
- 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
~~~
~~~
{}{raw}
Beale saga
~~~
~~~
{book cipher}
- book cipher
- key: a book
- replace 1st letter of each word with word number
- becomes a homophonic cipher
~~~
~~~
{example}{}
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 ?
~~~
~~~
{}{raw}
Polybius
~~~
~~~
{}
- [https://en.wikipedia.org/wiki/Polybius\#Cryptography grid used for 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
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
~~~
~~~
{}{raw}
Playfair cipher (appendix E)
~~~
~~~
- 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
~~~
~~~
{Playfair example}{}
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
~~~
~~~
{cracking Playfair}
- use digram frequency analysis
- 1932 Dorothy L Sayers [https://en.wikipedia.org/wiki/Have_His_Carcase have his carcase]
LP YN UG DZ UC PA DS OT MS AE SE CU DH NK BU UC ES TG YD
~~~
~~~
{answers}{}
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
~~~