Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4572 + 2433 = 7005
 Foundations of Cryptography • CSCI 662-01 • Spring Semester 2018
Course Page

## CSCI 662—Foundations of Cryptography Chapter 1. Foundations of Cryptography Lecture Notes

Prof. Alan Kaminsky
Rochester Institute of Technology—Department of Computer Science

### The Four Goals of Practical Cryptography

• Confidentiality

• Authentication

• Integrity

• No replays

### Classical Substitution Ciphers

• Each letter of the plaintext is substituted with another letter to form the ciphertext

• Shift cipher
• Replace each letter with the letter n positions ahead in the alphabet (the end of the alphabet wraps around to the beginning)
• Example with n = 3:  Plaintext: abcdefghijklmnopqrstuvwxyz  friendsromanscountrymen Ciphertext: DEFGHIJKLMNOPQRSTUVWXYZABC  IULHQGVURPDQVFRXQWUBPHQ
• Roman emperor Julius Caesar used a shift cipher with n = 3 — the Caesar cipher
• Usenet newsgroups circa 1980 used a shift cipher with n = 13 to conceal potentially offensive jokes — the ROT13 cipher
• The geocaching.com web site uses the ROT13 cipher to conceal clues for finding geocaches

• Affine cipher
• Represent each letter as a number: A = 0, B = 1, . . . , Z = 25
• Encryption: C = aP + b (mod 26)
• P = number corresponding to plaintext letter
• C = number corresponding to ciphertext letter
• (a, b) = key
• (mod 26) means calculate the formula, divide by 26, keep the remainder in the range 0 .. 25
• Decryption: P = a−1⋅(Cb) (mod 26)
• a−1 is the multiplicative inverse of a (mod 26)
• That is, aa−1 = 1 (mod 26)
• Example: a = 3, a−1 = 9, because 3⋅9 = 27; remainder (mod 26) = 1
• Not every a necessarily has a multiplicative inverse; e.g., a = 2
• Example with (a, b) = (3, 5):  Plaintext letters: 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 Plaintext numbers: 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 Ciphertext numbers: 5  8 11 14 17 20 23  0  3  6  9 12 15 18 21 24  1  4  7 10 13 16 19 22 25  2 Ciphertext letters: F  I  L  O  R  U  X  A  D  G  J  M  P  S  V  Y  B  E  H  K  N  Q  T  W  Z  C
• Another example with (a, b) = (3, 5):  Plaintext letters: f  r  i  e  n  d  s  r  o  m  a  n  s  c  o  u  n  t  r  y  m  e  n Plaintext numbers: 5 17  8  4 13  3 18 17 14 12  0 13 18  2 14 20 13 19 17 24 12  4 13 Ciphertext numbers: 20  4  3 17 18 14  7  4 21 15  5 18  7 11 21 13 18 10  4 25 15 17 18 Ciphertext letters: U  E  D  R  S  O  H  E  V  P  F  S  H  L  V  N  S  K  E  Z  P  R  S

• Monoalphabetic cipher
• Replace each letter with another letter from a permuted alphabet, using the same permutation for every letter
• Newspaper cryptogram puzzles use a monoalphabetic cipher
• Example:

 Permuted alphabet: Message: Plaintext: abcdefghijklmnopqrstuvwxyz friendsromanscountrymen Ciphertext: THEQUICKBROWNFXJMPSVLAZYDG IPBUFQSPXNTFSEXLFVPDNUF

• Polyalphabetic cipher
• Replace each letter with another letter from a permuted alphabet, using a different permutation for every letter
• Example with two permuted alphabets
• 1st, 3rd, 5th, etc. plaintext letters use the first permuted alphabet
• 2nd, 4th, 6th, etc. plaintext letters use the second permuted alphabet

 Permuted alphabet 1: Permuted alphabet 2: Message: Plaintext: abcdefghijklmnopqrstuvwxyz abcdefghijklmnopqrstuvwxyz friendsromanscountrymen Ciphertext: THEQUICKBROWNFXJMPSVLAZYDG BOTHFICKLEDWARVSJNXMYPGQUZ INBFFHSNXATRSTXYFMPUNFF

• Classical substitution ciphers are too easy to break and are not used in serious cryptography any more

• However, modern ciphers do use substitution as a building block

• And, modern ciphers do represent messages as (binary) numbers and perform calculations on them

### Classical Permutation Ciphers

• The order of the letters in the plaintext is permuted to form the ciphertext

• Transposition cipher
• Write the plaintext letters in rows of n columns
• Transpose the matrix to form the ciphertext
• Example with n = 7:
```thequickbrownfoxjumpsoverthelazydog

thequic
kbrownf
oxjumps
overthe
lazydog

TKOOL
HBXVA
ERJEZ
QOURY
UWMTD
INPHO
CFSEG

TKOOLHBXVAERJEZQOURYUWMTDINPHOCFSEG
```

• Permutation cipher
• Divide the plaintext into blocks of n letters
• Apply a permutation to each block to form the ciphertext
• Example with n = 7 and permutation = (4,1,3,7,6,2,5):
• 4th plaintext letter becomes 1st ciphertext letter
• 1st plaintext letter becomes 2nd ciphertext letter
• Etc.
```thequickbrownfoxjumpsoverthelazydog

thequic kbrownf oxjumps overthe lazydog

```

• Classical permutation ciphers are too easy to break and are not used in serious cryptography any more

• However, modern ciphers do use permutation as a building block

### Cryptographic Attacks

• Key
• Information used to parameterize a cryptographic algorithm
• Shift cipher: key = shift amount
• Affine cipher: key = (a, b)
• Monoalphabetic cipher: key = permutation of the alphabet
• Polyalphabetic cipher: key = list of permutations of the alphabet
• Transposition cipher: key = number of columns
• Permutation cipher: key = permutation of the plaintext block
• Modern cipher: key = n-bit binary number

• Key space
• Set of all possible keys for a cryptographic algorithm

• Key space size = number of possible keys
• Shift cipher: 26
• Affine cipher: 312 = (12 possible a values)×(26 possible b values)
• Monoalphabetic cipher: 26×25×24×...×3×2×1 = 26! = 4.03×1026 = 288.4
• Modern cipher: 2n

• Kerckhoffs' Principle
• Formulated by Dutch linguist and cryptographer Auguste Kerckhoffs in 1883
• The security of a cryptosystem must depend only on the key
• The attacker knows the algorithm but not the key
• Goal of a cryptographic attack: To find the key

• Kinds of attack
• Ciphertext-only
• Known plaintext
• Chosen plaintext
• Chosen plaintext and ciphertext

• Oracles
• An oracle is a "black box" that hides the key but lets an attacker compute the cipher
• Encryption oracle
• Attacker inputs plaintext
• Oracle encrypts plaintext with hidden key
• Oracle outputs ciphertext
• Decryption oracle
• Attacker inputs ciphertext
• Oracle decrypts ciphertext with hidden key
• Oracle outputs plaintext

• Methods of attack
• Generic attack
• Try every possible key
• A.k.a. brute force search
• Always succeeds
• But requires an amount of work proportional to the key space size
• Structural attack, analytical attack
• Exploit characteristics of the cipher algorithm design . . .
• To find the key with less work than brute force search
• Many structural attack techniques have been published
• A particular cipher might or might not be susceptible to a particular structural attack

• Cipher breaks
• A generic attack on a cipher with an n-bit key takes 2n operations
• If the fastest known attack takes 2n operations, the cipher is unbroken
• If there is an attack that takes less than 2n operations, but the attack still takes too long to finish, it is a theoretical break of the cipher
• If there is an attack that takes less than 2n operations, and the attack finishes quickly enough to be useful, it is a practical break of the cipher
• Example: In August 2011, an attack on the 128-bit-key Advanced Encryption Standard (AES) cipher that takes 2126.1 operations was published, so AES is now theoretically broken but not practically broken -- http://eprint.iacr.org/2011/449

• Security level
• A "security level of n bits" means "the attacker must do 2n operations to find the key"
• 56–64 bit security level = key safe for days or weeks
• 112–128 bit security level = key safe for decades
• 256–512 bit security level = key safe for decades even with quantum computers

 Foundations of Cryptography • CSCI 662-01 • Spring Semester 2018
Course Page
 Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4572 + 2433 = 7005