1 Historical Ciphers ECE 646 - Lecture 6 Why (not) to study historical ciphers? AGAINST FOR Not similar to modern ciphers Long abandoned Basic components became a part of modern ciphers Under special circumstances modern ciphers reduce to historical ciphers Influence on world events The only ciphers you can break! Secret Writing Steganography (hidden messages) Cryptography (encrypted messages) Substitution Transformations Transposition Ciphers (change the order of letters) Codes Substitution Ciphers (replace words) (replace letters)2 Selected world events affected by cryptology 1586 - trial of Mary Queen of Scots - substitution cipher 1917 - Zimmermann telegram, America enters World War I 1939-1945 Battle of England, Battle of Atlantic, D-day - ENIGMA machine cipher 1944 – world’s first computer, Colossus - German Lorenz machine cipher 1950s – operation Venona – breaking ciphers of soviet spies stealing secrets of the U.S. atomic bomb – one-time pad Ciphers used predominantly in the given period(1) Electromechanical machine ciphers (Complex polyalphabetic substitution ciphers) 1919 Vigenère cipher (Simple polyalphabetic substitution ciphers) Cryptography Cryptanalysis 1586 Invention of the Vigenère Cipher Monoalphabetic substitution cipher Homophonic ciphers Invention of rotor machines XVIII c. Black chambers 1863 Kasiski’s method 1918 Index of coincidence William Friedman Shift ciphers 100 B.C. IX c. Frequency analysis al-Kindi, Baghdad 1926 Vernam cipher (one-time pad) Ciphers used predominantly in the given period(2) Cryptography Cryptanalysis DES 1977 2001 AES Triple DES 1932 1977 2001 Rejewski, Poland Reconstructing ENIGMA 1939 1949 Shennon’s theory of secret systems Polish cryptological bombs, and perforated sheets Publication of DES 1945 British cryptological bombs, Bletchley Park, UK Breaking Japanese “Purple” cipher 1990 DES crackers one-time pad Stream Ciphers S-P networks3 Substitution Ciphers (1) 1. Monalphabetic (simple) substitution cipher M = m1 m2 m3 m4 . . . . mN C = f(m1) f(m2) f(m3) f(m4) . . . . f(mN) Generally f is a random permutation, e.g., f = 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 s l t a v m c e r u b q p d f k h w y g x z j n i o Key = f Number of keys = 26! ≈ 4 ⋅ 1026 Monalphabetic substitution ciphers Simplifications (1) A. Caesar Cipher ci = f(mi) = mi + 3 mod 26 No key B. Shift Cipher ci = f(mi) = mi + k mod 26 Key = k Number of keys = 26 mi = f-1(ci) = ci - 3 mod 26 mi = f-1(ci) = ci - k mod 26 Coding characters into numbers A ⇔ 0 B ⇔ 1 C ⇔ 2 D ⇔ 3 E ⇔ 4 F ⇔ 5 G ⇔ 6 H ⇔ 7 I ⇔ 8 J ⇔ 9 K ⇔ 10 L ⇔ 11 M ⇔ 12 N ⇔ 13 O ⇔ 14 P ⇔ 15 Q ⇔ 16 R ⇔ 17 S ⇔ 18 T ⇔ 19 U ⇔ 20 V ⇔ 21 W ⇔ 22 X ⇔ 23 Y ⇔ 24 Z ⇔ 254 Caesar Cipher: Example Plaintext: Ciphertext: I C A M E I S A W I C O N Q U E R E D 8 2 0 12 4 8 18 0 22 8 2 14 13 16 20 4 17 4 3 11 5 3 15 7 11 21 3 25 11 5 17 16 19 23 7 20 7 6 L F D P H L V D Z L F R Q T X H U H G Monalphabetic substitution ciphers Simplifications (2) C. Affine Cipher ci = f(mi) = k1 ⋅ mi + k2 mod 26 Key = (k1, k2) Number of keys = 12⋅26 = 312 gcd (k1, 26) = 1 mi = f-1(ci) = k1-1 ⋅ (ci - k2) mod 26 Most frequent single letters Average frequency in a long English text: E — 13% T, N, R, I, O, A, S — 6%-9% D, H, L — 3.5%-4.5% C, F, P, U, M, Y, G, W, V — 1.5%-3% B, X, K, Q, J, Z — < 1% = 0.038 = 3.8% Average frequency in a random string of letters: 1 265 Digrams: TH, HE, IN, ER, RE, AN, ON, EN, AT Trigrams: THE, ING, AND, HER, ERE, ENT, THA, NTH, WAS, ETH, FOR, DTH Most frequent digrams, and trigrams 0 2 4 6 8 10 12 14 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 Relative frequency of letters in a long English text by Stallings 7.25 1.25 3.5 4.25 12.75 3 2 3.5 7.75 0.25 0.5 3.75 2.75 7.75 7.5 2.75 0.5 8.5 6 9.25 3 1.5 1.5 0.5 2.25 0.25 0 2 4 6 8 10 12 14 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 2 4 6 8 10 12 14 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 Character frequency in a long English plaintext Character frequency in the corresponding ciphertext for a shift cipher6 0 2 4 6 8 10 12 14 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 Character frequency in a long English plaintext Character frequency in the corresponding ciphertext for a general monoalphabetic substitution cipher 0 2 4 6 8 10 12 14 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 2 4 6 8 10 12 14 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 2 4 6 8 10 12 14 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 2 4 6 8 10 12 14 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 2 4 6 8 10 12 14 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 Long English text T Ciphertext of the long English text T Short English message M Ciphertext of the short English message M Frequency analysis attack: relevant frequencies Ciphertext: FMXVE DKAPH FERBN DKRXR SREFM ORUDS DKDVS HVUFE DKAPR KDLYE VLRHH RH 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 R - 8 D - 7 E, H, K - 5 Frequency analysis attack (1) Step 1: Establishing the relative frequency of letters in the ciphertext7 f(E) = R …
View Full Document
Unlocking...