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