Transcript (m,c).

Introduction
CS 303 Algorithmic Number Theory and
Cryptography
Jeremy R. Johnson
1
KHOOR
2
HELLO
3
Introduction to Classical Cryptography
• Objective: Introduction to Cryptography and Cryptanalysis
–
–
–
–
Shift Cipher
Substitution Cipher
Attacks and adversaries
Frequency analysis
4
Classical Cryptography
• Basic problem: Secure communication over an
insecure channel
• Solution: private key encryption
– m  E(k,m) = c  D(k,c) = m
• Shannon provided a rigorous theory of perfect secrecy
based on information theory
– Adversary has unlimited computational resources, but
key must be as long as message
5
Communication Scenario
Decryption key
Encryption key
ciphertext
Alice
Encrypt
Decrypt
Bob
plainrtext
Eve
6
Shift Cipher
hello
all hail ceasar
If he had anything confidential to say, he wrote it in cipher, that is, by so
changing the order of the letters of the alphabet, that not a word could be made
out. If anyone wishes to decipher these, and get at their meaning, he must
substitute the fourth letter of the alphabet, namely D, for A, and so with the
others.
— Suetonius, Life of Julius Caesar 56
7
Shift Cipher
KHOOR
DOO KDLO FHDVDU
a bc defgh i j k l mnopq r st uvwx y z
DEFGHIJKLMNOPQRSTUVWXYZABC
Key = 3
m  E(k,m) = c = m+k mod 26
c  D(k,c) = c-k mod 26
8
Possible Attacks
Kerchoff’s Principle
1. Ciphertext only
2. Known plaintext
3. Chosen plaintext
4. Chosen ciphertext
9
Cryptanalysis of Shift Ciphers
Number of keys = size of alphabet
1. Ciphertext only
1.
2.
Brute force
Look for most frequently occurring symbol
2. Known plaintext
1.
m + k = c (mod 26)
3. Chosen plaintext
1.
1 + k = c (mod 26)
4. Chosen ciphertext
1.
m + k = 1 (mod 26)
10
Frequency Analysis
en.wikipedia.org/wiki/Frequency_analysis_(cryptanalysis)
scottbryce.com/cryptograms
11
War and Peace
• 3,223,402 Characters
• http://www.gutenberg.org/ebooks/2600
12
freq.pl
infile = file(filename,'r')
freq = {}
count = 0
for c in string.ascii_lowercase:
freq[c] = 0
for line in infile:
for c in line.lower():
if c.isalpha():
freq[c] = freq[c] + 1
count = count + 1
keys = freq.keys()
keys.sort()
for c in keys:
print "freq[" + c + "] = ",float(freq[c])/count
13
Substitution Cipher
NYVVZ
JVV NJSV RYJDJC
a bc de f gh i j k lmnop q r s tuvwxy z
JERMYOHNSTUVWXZABCDFGIKLPQ
Key – bijection from {0..25}  {0..25}: i  (i)
m  E(k,m) = c = (m)
c  D(k,c) = -1(c)
14
Cryptanalysis of Substitution Ciphers
Number of keys = n! where n is the size of the alphabet
1. Ciphertext only
1.
2.
Brute force (too expensive)
Frequency analysis
2. Known plaintext
1.
m  (i) = c, for known (m,c). Partial permutation
3. Chosen plaintext
1.
m  (i) = c, m = 0..n-1
4. Chosen ciphertext
1.
-1(c)  m, c = 0..n-1
15
One Time Pad
• Pad = b1  bn  {0,1}* chosen randomly
• m = m1  mn
– E(Pad,m) = c = m  Pad
– D(Pad,c) = c  Pad = (m  Pad)  Pad = m
• m,c PrPad[E(Pad,m) = c] = 1/2n
– No information gained from seeing c
– However, E(Pad,m)  E(Pad,m’) = m  m’
16