●●●●● ●●●● ●●0 Caesar Cipher ●●● ●●●● o We can define the transformation as cde f ghijk l m nopgrstuvwxyz D E FGH工了 K LMNOPQRST BO mathematically give each letter a number a bcde f ghijklm 0123456789101112 o p a r st V W x y Z 13141516171819202122232425 o then we have Caesar cipher as C=E()=(p+k)mod(26) p=D(C)=(C-k mod(26) k is the key, which is in the range of 1 to 25. For Caesar cipher, k= 3 COMP4690. HKBU
COMP4690, HKBU 11 Caesar Cipher ⚫ We can define the transformation as: 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 D E F G H I J K L M N O P Q R S T U V W X Y Z A B C ⚫ mathematically give each letter a number a b c d e f g h i j k l m 0 1 2 3 4 5 6 7 8 9 10 11 12 n o p q r s t u v w x y Z 13 14 15 16 17 18 19 20 21 22 23 24 25 ⚫ then we have Caesar cipher as: C = E(p) = (p + k) mod (26) p = D(C) = (C – k) mod (26) k is the key, which is in the range of 1 to 25. For Caesar cipher, k = 3
Cryptanalysis of Caesar ●●●●● ●●●● ●●0 Cipher ●●● ●●●● o There are only 25 possible ciphers A maps to B,.., Z o Attacker could simply try each in turn ● a brute- force search o given ciphertext, just try all shifts of letters o do need to recognize when have plaintext E.g. break ciphertext GCUA VQ DTGCM e Caesar cipher is far from secure! COMP4690. HKBU
COMP4690, HKBU 12 Cryptanalysis of Caesar Cipher ⚫ There are only 25 possible ciphers ⚫ A maps to B,…,Z ⚫ Attacker could simply try each in turn ⚫ a brute-force search ⚫ given ciphertext, just try all shifts of letters ⚫ do need to recognize when have plaintext ⚫ E.g. break ciphertext "GCUA VQ DTGCM“ ⚫ Caesar cipher is far from secure!
●●●●● ●●●● ●●0 Monoalphabetic Cipher ●●● ●●●● e Rather than just shifting the alphabet, we could shuffle the letters arbitrarily each plaintext letter maps to a different random ciphertext letter o key is now 26 letters long, so there are 26!or greater than 4x1026 possible keys e Seems to be secure enough but Plain: abcdefghijklmnopqrstuvwxyz Key Cipher: DKVQFIBJWPESCXHTMYAUOLRGZN Plaintext: ifwewishtoreplaceletters Ciphertext: WIRFRWAJUHYFTSDVESFUUFYA COMP4690. HKBU
COMP4690, HKBU 13 Monoalphabetic Cipher ⚫ Rather than just shifting the alphabet, we could shuffle the letters arbitrarily ⚫ each plaintext letter maps to a different random ciphertext letter ⚫ key is now 26 letters long, so there are 26! or greater than 4x1026 possible keys. ⚫ Seems to be secure enough, but … Plain: abcdefghijklmnopqrstuvwxyz Cipher: DKVQFIBJWPESCXHTMYAUOLRGZN Plaintext: ifwewishtoreplaceletters Ciphertext: WIRFRWAJUHYFTSDVFSFUUFYA Key
Language redundancy and ●●●●● ●●●● ●●0 Cryptanalysis ●●● ●●●● o human languages are redundant o letters are not equally commonly used in English, E and T are the two most common letters then AO,I,N,S, H, R(5%) other letters are fairly rare, e.g., V,KJ, X, Q, 2 (<1%) have tables of single, double triple letter frequencies COMP4690. HKBU
COMP4690, HKBU 14 Language Redundancy and Cryptanalysis ⚫ human languages are redundant ⚫ letters are not equally commonly used ⚫ in English, E and T are the two most common letters ⚫ then {A,O,I,N,S,H,R} (>5%) ⚫ other letters are fairly rare, e.g., {V,K,J,X,Q,Z} (<1%) ⚫ have tables of single, double & triple letter frequencies
●●●●● ●●●● ●●0 English Letter Frequencies ●●● ●●●● s K L MN O
COMP4690, HKBU 15 English Letter Frequencies