Part II Cryptanalysis University of Adelaide Working Session – SSE 2019 14 Cryptanalysis aka: try to break crypto Mathematical analysis Side-channel analysis Note: assume lowercase English alphabets for Message spaceM = {a, b, . . . , z} Ciphertext space C = {a, b, . . . , z} University of Adelaide Working Session – SSE 2019 15 Cryptanalysis aka: try to break crypto Mathematical analysis Side-channel analysis Note: assume lowercase English alphabets for Message spaceM = {a, b, . . . , z} Ciphertext space C = {a, b, . . . , z} University of Adelaide Working Session – SSE 2019 15 Caesar’s Cipher Encryption: rotate each leer by 3 places Decryption: rotate back each cipher by 3 places Mapping: 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 Example: “this is an example”→ “wklv lv dq hadpsoh” Problem: no key University of Adelaide Working Session – SSE 2019 16 Caesar’s Cipher Encryption: rotate each leer by 3 places Decryption: rotate back each cipher by 3 places Mapping: 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 Example: “this is an example”→ “wklv lv dq hadpsoh” Problem: no key University of Adelaide Working Session – SSE 2019 16 Caesar’s Cipher Encryption: rotate each leer by 3 places Decryption: rotate back each cipher by 3 places Mapping: 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 Example: “this is an example”→ “wklv lv dq hadpsoh” Problem: no key University of Adelaide Working Session – SSE 2019 16 Shi Cipher Key space K = {0, 1, . . . , 25} Example: k = 3→ Caesar’s cipher k = 10 : “this is an example”→ “drsc sc kx ohkwzvo” Problems: 1 small key space 2 same leer maps to same cipher University of Adelaide Working Session – SSE 2019 17 Shi Cipher Key space K = {0, 1, . . . , 25} Example: k = 3→ Caesar’s cipher k = 10 : “this is an example”→ “drsc sc kx ohkwzvo” Problems: 1 small key space 2 same leer maps to same cipher University of Adelaide Working Session – SSE 2019 17 Increasing Key Space shi alphabets→ permute alphabets Key = a permutation of 26 alphabets Key space |K| = 26! Example: 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 n v z y g q o u t s l f j e m h r b a d i c k p x w “this is an example”→ “duta ta ne gpnjhfg” 26! ≈ 288; is this secure? (Exercise 1) University of Adelaide Working Session – SSE 2019 18 Increasing Key Space shi alphabets→ permute alphabets Key = a permutation of 26 alphabets Key space |K| = 26! Example: 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 n v z y g q o u t s l f j e m h r b a d i c k p x w “this is an example”→ “duta ta ne gpnjhfg” 26! ≈ 288; is this secure? (Exercise 1) University of Adelaide Working Session – SSE 2019 18 Increasing Key Space shi alphabets→ permute alphabets Key = a permutation of 26 alphabets Key space |K| = 26! Example: 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 n v z y g q o u t s l f j e m h r b a d i c k p x w “this is an example”→ “duta ta ne gpnjhfg” 26! ≈ 288; is this secure? (Exercise 1) University of Adelaide Working Session – SSE 2019 18 Increasing Key Space shi alphabets→ permute alphabets Key = a permutation of 26 alphabets Key space |K| = 26! Example: 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 n v z y g q o u t s l f j e m h r b a d i c k p x w “this is an example”→ “duta ta ne gpnjhfg” 26! ≈ 288; is this secure? (Exercise 1) University of Adelaide Working Session – SSE 2019 18 Frequency Analysis http://pi.math.cornell.edu/~mec/2003-2004/cryptography/ subs/frequencies.html (sample from 40,000 words) University of Adelaide Working Session – SSE 2019 19 Frequency Analysis http://letterfrequency.org/ English Language e t a o i n s r h l d c u m f p g w y b v k x j q z Press Reporting e t a o n i s r h l d c m u f p g w y b v k j x q z Scientific Writings e t a i o n s r h l c d u m f p g y b w v k x q j z General Fiction e t a o h n i s r d l u w m c g f y p v k b j x z q University of Adelaide Working Session – SSE 2019 20 Let’s try ... Take previous example: “this is an example”→ “duta ta ne gpnjhfg” Frequency analysis: t=0.13, a=0.13, n=0.13, g=0.13, d=0.07, u=0.07, e=0.07, p=0.07, j=0.07, h=0.07, f=0.07 Use ‘English Language’ from http://letterfrequency.org/ t a n g d u e p j h f e t a o i n s r h l d c u m f p g w y b v k x j q z Decrypt “duta ta ne gpnjhfg”→ “inet et as orahldo” What went wrong? University of Adelaide Working Session – SSE 2019 21 Let’s try ... Take previous example: “this is an example”→ “duta ta ne gpnjhfg” Frequency analysis: t=0.13, a=0.13, n=0.13, g=0.13, d=0.07, u=0.07, e=0.07, p=0.07, j=0.07, h=0.07, f=0.07 Use ‘English Language’ from http://letterfrequency.org/ t a n g d u e p j h f e t a o i n s r h l d c u m f p g w y b v k x j q z Decrypt “duta ta ne gpnjhfg”→ “inet et as orahldo” What went wrong? University of Adelaide Working Session – SSE 2019 21 Let’s try ... Take previous example: “this is an example”→ “duta ta ne gpnjhfg” Frequency analysis: t=0.13, a=0.13, n=0.13, g=0.13, d=0.07, u=0.07, e=0.07, p=0.07, j=0.07, h=0.07, f=0.07 Use ‘English Language’ from http://letterfrequency.org/ t a n g d u e p j h f e t a o i n s r h l d c u m f p g w y b v k x j q z Decrypt “duta ta ne gpnjhfg”→ “inet et as orahldo” What went wrong? University of Adelaide Working Session – SSE 2019 21 Let’s try ... Take previous example: “this is an example”→ “duta ta ne gpnjhfg” Frequency analysis: t=0.13, a=0.13, n=0.13, g=0.13, d=0.07, u=0.07, e=0.07, p=0.07, j=0.07, h=0.07, f=0.07 Use ‘English Language’ from http://letterfrequency.org/ t a n g d u e p j h f e t a o i n s r h l d c u m f p g w y b v k x j q z Decrypt “duta ta ne gpnjhfg”→ “inet et as orahldo” What went wrong? University of Adelaide Working Session – SSE 2019 21 Let’s try ... Take previous example: “this is an example”→ “duta ta ne gpnjhfg” Frequency analysis: t=0.13, a=0.13, n=0.13, g=0.13, d=0.07, u=0.07, e=0.07, p=0.07, j=0.07, h=0.07, f=0.07 Use ‘English Language’ from http://letterfrequency.org/ t a n g d u e p j h f e t a o i n s r h l d c u m f p g w y b v k x j q z Decrypt “duta ta ne gpnjhfg”→ “inet et as orahldo” What went wrong? University of Adelaide Working Session – SSE 2019 21 Why didn’t it work? Distribution of alphabets should be close to average frequency Longer plaintext beer analysis 40,000 words VS 15 characters, not enough! What to do? University of Adelaide Working Session – SSE 2019 22 Why didn’t it work? Distribution of alphabets should be close to average frequency Longer plaintext beer analysis 40,000 words VS 15 characters, not enough! What to do? University of Adelaide Working Session – SSE 2019 22 Valid English Words For example: 1 leer: a, I 2 leers: an, am, is, in, on etc. th?→ the (with high probability) I ??→ I am (with high probability) University of Adelaide Working Session – SSE 2019 23 Vigenère Cipher Avoid mapping same leer to same cipher Poly-alphabetic shi cipher Example: key = ‘note’ message: thisisanexample key: notenotenotenot ciphertext: gvbwvgtrrltqczx Is this secure? (Exercise 2) University of Adelaide Working Session – SSE 2019 24 Vigenère Cipher Avoid mapping same leer to same cipher Poly-alphabetic shi cipher Example: key = ‘note’ message: thisisanexample key: notenotenotenot ciphertext: gvbwvgtrrltqczx Is this secure? (Exercise 2) University of Adelaide Working Session – SSE 2019 24 Vigenère Cipher Avoid mapping same leer to same cipher Poly-alphabetic shi cipher Example: key = ‘note’ message: thisisanexample key: notenotenotenot ciphertext: gvbwvgtrrltqczx Is this secure? (Exercise 2) University of Adelaide Working Session – SSE 2019 24 Vigenère Cipher Avoid mapping same leer to same cipher Poly-alphabetic shi cipher Example: key = ‘note’ message: thisisanexample key: notenotenotenot ciphertext: gvbwvgtrrltqczx Is this secure? (Exercise 2) University of Adelaide Working Session – SSE 2019 24 Textbook RSA N = pq Φ(n) = (p− 1)(q − 1) ed ≡ 1 (mod Φ(n)) Encryption: c ≡ me (mod Φ(n)) Decryption: m ≡ cd (mod Φ(n)) Seems good? (Exercise 3) University of Adelaide Working Session – SSE 2019 25 Textbook RSA N = pq Φ(n) = (p− 1)(q − 1) ed ≡ 1 (mod Φ(n)) Encryption: c ≡ me (mod Φ(n)) Decryption: m ≡ cd (mod Φ(n)) Seems good? (Exercise 3) University of Adelaide Working Session – SSE 2019 25 Textbook RSA N = pq Φ(n) = (p− 1)(q − 1) ed ≡ 1 (mod Φ(n)) Encryption: c ≡ me (mod Φ(n)) Decryption: m ≡ cd (mod Φ(n)) Seems good? (Exercise 3) University of Adelaide Working Session – SSE 2019 25 Textbook RSA N = pq Φ(n) = (p− 1)(q − 1) ed ≡ 1 (mod Φ(n)) Encryption: c ≡ me (mod Φ(n)) Decryption: m ≡ cd (mod Φ(n)) Seems good? (Exercise 3) University of Adelaide Working Session – SSE 2019 25