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 le�er 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 le�er 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 le�er 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 le�er 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 le�er 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
http://pi.math.cornell.edu/~mec/2003-2004/cryptography/subs/frequencies.html
http://pi.math.cornell.edu/~mec/2003-2004/cryptography/subs/frequencies.html
Frequency Analysis
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 be�er 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 be�er 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 le�er: a, I
2 le�ers: 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 le�er 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 le�er 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 le�er 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 le�er 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