4003-482-01/4005-705-01 Cryptography
Chapter 1. Introduction to Cryptography
Lecture Notes

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 = a⋅P + 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⁻¹⋅(C − b) (mod 26)
    • a⁻¹ is the multiplicative inverse of a (mod 26)
    • That is, a⋅a⁻¹ = 1 (mod 26)
    • Example: a = 3, a⁻¹ = 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
  • Example:

    Plaintext:	abcdefghijklmnopqrstuvwxyz  friendsromanscountrymen
    Ciphertext:	THEQUICKBROWNFXJMPSVLAZYDG  IPBUFQSPXNTFSEXLFVPDNUF

  • Newspaper cryptogram puzzles use a monoalphabetic cipher

• Polyalphabetic cipher
  • Replace each letter with another letter from a permuted alphabet, using a different permutation for every letter

• 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
    
    QTECIHU OKRFNBW UOJSPXM ROEEHVT YLZGOAD
    
    QTECIHUOKRFNBWUOJSPXMROEEHVTYLZGOAD
    

• 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
  • 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

• 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

• Methods of attack
  • Generic attack -- try every possible key, a.k.a. brute force search
  • Structural attack, analytical attack -- depending on the characteristics of the cipher and/or the possible plaintexts, find the key without trying every possible key

• Cipher breaks
  • A generic attack on a cipher with an n-bit key takes 2ⁿ operations
  • If the fastest known attack takes 2ⁿ operations, the cipher is unbroken
  • If there is an attack that takes less than 2ⁿ 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 2ⁿ 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 Advanced Encryption Standard (AES) cipher that takes 2^126.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 2ⁿ 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

Cryptography • 4003-482-01/4005-705-01 • Spring Quarter 2013

Course Page

Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706

Home Page

Copyright © 2012 Alan Kaminsky. All rights reserved. Last updated 26-Nov-2012. Please send comments to ark­@­cs.rit.edu.