Classical Encryption

Techniques
 Crypto
 Cryptology  The art and science of
making and breaking “secret codes”
 Cryptography  making “secret codes”
 Cryptanalysis  breaking “secret codes”
 Crypto  all of the above (and more)
 How to Speak Crypto
 A cipher or cryptosystem is used to encrypt the
plaintext
 The result of encryption is ciphertext
 We decrypt ciphertext to recover plaintext
 A key is used to configure a cryptosystem
 A symmetric key cryptosystem uses the same
key to encrypt as to decrypt
 A public key cryptosystem uses a public key to
encrypt and a private key to decrypt
 Crypto
 Basic assumptions
 The system is completely known to the attacker
 Only the key is secret
 That is, crypto algorithms are not secret
 This is known as Kerckhoffs’ Principle
 Why do we make this assumption?
 Experience has shown that secret algorithms are
weak when exposed
 Secret algorithms never remain secret
 Better to find weaknesses beforehand
 Crypto as Black Box

key key

plaintext encrypt decrypt plaintext

ciphertext

A generic view of symmetric key crypto

 Symmetric Encryption
 or conventional / private-key / single-key
 sender and recipient share a common key
 all classical encryption algorithms are
private-key
 was only type prior to invention of public-
key in 1970’s
 and by far most widely used
 Some Basic Terminology
 plaintext - original message
 ciphertext - coded message
 cipher - algorithm for transforming plaintext to ciphertext
 key - info used in cipher known only to sender/receiver
 encipher (encrypt) - converting plaintext to ciphertext
 decipher (decrypt) - recovering ciphertext from plaintext
 cryptography - study of encryption principles/methods
 cryptanalysis (codebreaking) - study of principles/
methods of deciphering ciphertext without knowing key
 cryptology - field of both cryptography and cryptanalysis
Symmetric Cipher Model
 Cryptography
 characterize cryptographic system by:
 type of encryption operations used
• substitution / transposition / product
 number of keys used
• single-key or private / two-key or public
 way in which plaintext is processed
• block / stream
 Cryptanalysis
 objective to recover key not just message
 general approaches:
 cryptanalytic attack
 brute-force attack
 Cryptanalytic Attacks
 ciphertext only
 only know algorithm & ciphertext, is statistical,
know or can identify plaintext
 known plaintext
 know/suspect plaintext & ciphertext
 chosen plaintext
 select plaintext and obtain ciphertext
 chosen ciphertext
 select ciphertext and obtain plaintext
 chosen text
 select plaintext or ciphertext to en/decrypt
 More Definitions
 unconditional security
 no matter how much computer power or time
is available, the cipher cannot be broken
since the ciphertext provides insufficient
information to uniquely determine the
corresponding plaintext
 computational security
 given limited computing resources (eg time
needed for calculations is greater than age of
universe), the cipher cannot be broken
 Brute Force Search
 always possible to simply try every key
 most basic attack, proportional to key size
 assume either know / recognise plaintext

Key Size (bits) Number of Alternative Time required at 1 Time required at 106
Keys decryption/µs decryptions/µs
32 232 = 4.3  109 231 µs = 35.8 minutes 2.15 milliseconds
56 256 = 7.2  1016 255 µs = 1142 years 10.01 hours
128 2128 = 3.4  1038 2127 µs = 5.4  1024 years 5.4  1018 years

168 2168 = 3.7  1050 2167 µs = 5.9  1036 years 5.9  1030 years

26 characters 26! = 4  1026 2  1026 µs = 6.4  1012 years 6.4  106 years
(permutation)
 Classical Substitution
Ciphers
 where letters of plaintext are replaced by
other letters or by numbers or symbols
 or if plaintext is viewed as a sequence of
bits, then substitution involves replacing
plaintext bit patterns with ciphertext bit
patterns
 Caesar Cipher
 earliest known substitution cipher
 by Julius Caesar
 first attested use in military affairs
 replaces each letter by 3rd letter on
 example:
meet me after the toga party
PHHW PH DIWHU WKH WRJD SDUWB
 Caesar Cipher
 can define transformation as:
abcdefghijklmnopqrstuvwxyz
DEFGHIJKLMNOPQRSTUVWXYZABC

 mathematically give each letter a number

abcdefghij k l m n o p q r s t u v w x y z
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

 then have Caesar cipher as:

c = E(p) = (p + k) mod (26)
p = D(c) = (c – k) mod (26)
 Cryptanalysis of Caesar
Cipher
 only have 26 possible ciphers
 A maps to A,B,..Z
 could simply try each in turn
 a brute force search
 given ciphertext, just try all shifts of letters
 do need to recognize when have plaintext
 eg. break ciphertext "GCUA VQ DTGCM"
 Monoalphabetic Cipher
 rather than just shifting the alphabet
 could shuffle (jumble) the letters arbitrarily
 each plaintext letter maps to a different random
ciphertext letter
 hence key is 26 letters long

Plain: abcdefghijklmnopqrstuvwxyz
Cipher: DKVQFIBJWPESCXHTMYAUOLRGZN

Plaintext: ifwewishtoreplaceletters
Ciphertext: WIRFRWAJUHYFTSDVFSFUUFYA
 Monoalphabetic Cipher
Security
 now have a total of 26! = 4 x 1026 keys
 with so many keys, might think is secure
 but would be !!!WRONG!!!
 problem is language characteristics
 Language Redundancy and
Cryptanalysis
 human languages are redundant
 eg "th lrd s m shphrd shll nt wnt"
 letters are not equally commonly used
 in English E is by far the most common letter
 followed by T,R,N,I,O,A,S
 other letters like Z,J,K,Q,X are fairly rare
 have tables of single, double & triple letter
frequencies for various languages
English Letter Frequencies
 Use in Cryptanalysis
 key concept - monoalphabetic substitution
ciphers do not change relative letter frequencies
 discovered by Arabian scientists in 9th century
 calculate letter frequencies for ciphertext
 compare counts/plots against known values
 if caesar cipher look for common peaks/troughs
 peaks at: A-E-I triple, NO pair, RST triple
 troughs at: JK, X-Z
 for monoalphabetic must identify each letter
 tables of common double/triple letters help
 Example Cryptanalysis
 given ciphertext:
UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ
VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX
EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ
 count relative letter frequencies (see text)
 guess P & Z are e and t
 guess ZW is th and hence ZWP is the
 proceeding with trial and error finally get:
it was disclosed yesterday that several informal but
direct contacts have been made with political
representatives of the viet cong in moscow
 Playfair Cipher
 not even the large number of keys in a
monoalphabetic cipher provides security
 one approach to improving security was to
encrypt multiple letters
 the Playfair Cipher is an example
 invented by Charles Wheatstone in 1854,
but named after his friend Baron Playfair
 Playfair Key Matrix
 a 5X5 matrix of letters based on a keyword
 fill in letters of keyword (sans duplicates)
 fill rest of matrix with other letters
 eg. using the keyword MONARCHY

M O N A R
C H Y B D
E F G I/J K
L P Q S T
U V W X Z
 Encrypting and Decrypting
 plaintext is encrypted two letters at a time
1. if a pair is a repeated letter, insert filler like 'X’
2. if both letters fall in the same row, replace
each with letter to right (wrapping back to start
from end)
3. if both letters fall in the same column, replace
each with the letter below it (again wrapping to
top from bottom)
4. otherwise each letter is replaced by the letter
in the same row and in the column of the other
letter of the pair
 Security of Playfair Cipher
 security much improved over monoalphabetic
 since have 26 x 26 = 676 digrams
 would need a 676 entry frequency table to
analyse (verses 26 for a monoalphabetic)
 and correspondingly more ciphertext
 was widely used for many years
 eg. by US & British military in WW1
 it can be broken, given a few hundred letters
 since still has much of plaintext structure
 Polyalphabetic Ciphers
 polyalphabetic substitution ciphers
 improve security using multiple cipher alphabets
 make cryptanalysis harder with more alphabets
to guess and flatter frequency distribution
 use a key to select which alphabet is used for
each letter of the message
 use each alphabet in turn
 repeat from start after end of key is reached
 Vigenère Cipher
 simplest polyalphabetic substitution cipher
 effectively multiple caesar ciphers
 key is multiple letters long K = k1 k2 ... kd
 ith letter specifies ith alphabet to use
 use each alphabet in turn
 repeat from start after d letters in message
 decryption simply works in reverse
 Example of Vigenère Cipher
 write the plaintext out
 write the keyword repeated above it
 use each key letter as a caesar cipher key
 encrypt the corresponding plaintext letter
 eg using keyword deceptive
key: deceptivedeceptivedeceptive
plaintext: wearediscoveredsaveyourself
ciphertext:ZICVTWQNGRZGVTWAVZHCQYGLMGJ
 Aids
 simple aids can assist with en/decryption
 a Saint-Cyr Slide is a simple manual aid
 a slide with repeated alphabet
 line up plaintext 'A' with key letter, eg 'C'
 then read off any mapping for key letter
 can bend round into a cipher disk
 or expand into a Vigenère Tableau
 Security of Vigenère Ciphers
 have multiple ciphertext letters for each
plaintext letter
 hence letter frequencies are obscured
 but not totally lost
 start with letter frequencies
 see if look monoalphabetic or not
 if not, then need to determine number of
alphabets, since then can attach each
 Kasiski Method
 method developed by Babbage / Kasiski
 repetitions in ciphertext give clues to period
 so find same plaintext an exact period apart
 which results in the same ciphertext
 of course, could also be random fluke
 eg repeated “VTW” in previous example
 suggests size of 3 or 9
 then attack each monoalphabetic cipher
individually using same techniques as before
 Autokey Cipher
 ideally want a key as long as the message
 Vigenère proposed the autokey cipher
 with keyword is prefixed to message as key
 knowing keyword can recover the first few letters
 use these in turn on the rest of the message
 but still have frequency characteristics to attack
 eg. given key deceptive
key: deceptivewearediscoveredsav
plaintext: wearediscoveredsaveyourself
ciphertext:ZICVTWQNGKZEIIGASXSTSLVVWLA
 One-Time Pad
 if a truly random key as long as the message is
used, the cipher will be secure
 called a One-Time pad
 is unbreakable since ciphertext bears no
statistical relationship to the plaintext
 since for any plaintext & any ciphertext there
exists a key mapping one to other
 can only use the key once though
 problems in generation & safe distribution of key
 Transposition Ciphers
 now consider classical transposition or
permutation ciphers
 these hide the message by rearranging
the letter order
 without altering the actual letters used
 can recognise these since have the same
frequency distribution as the original text
 Rail Fence cipher
 write message letters out diagonally over a
number of rows
 then read off cipher row by row
 eg. write message out as:
m e m a t r h t g p r y
e t e f e t e o a a t
 giving ciphertext
MEMATRHTGPRYETEFETEOAAT
 Row Transposition Ciphers
 a more complex transposition
 write letters of message out in rows over a
specified number of columns
 then reorder the columns according to
some key before reading off the rows
Key: 3421567
Plaintext: a t t a c k p
ostpone
duntilt
woamxyz
Ciphertext: TTNAAPTMTSUOAODWCOIXKNLYPETZ
 Product Ciphers
 ciphers using substitutions or transpositions are
not secure because of language characteristics
 hence consider using several ciphers in
succession to make harder, but:
 two substitutions make a more complex substitution
 two transpositions make more complex transposition
 but a substitution followed by a transposition makes a
new much harder cipher
 this is bridge from classical to modern ciphers
Data Encryption Standard (DES)
 most widely used block cipher in world
 encrypts 64-bit data using 56-bit key
 has widespread use
 has been considerable controversy over
its security
 DES History
 IBM developed Lucifer cipher
 by team led by Feistel in late 60’s
 used 64-bit data blocks with 128-bit key
 then redeveloped as a commercial cipher
with input from NSA and others
 in 1973 NBS issued request for proposals
for a national cipher standard
 IBM submitted their revised Lucifer which
was eventually accepted as the DES
 DES Design Controversy
 although DES standard is public
 was considerable controversy over design
 in choice of 56-bit key (vs Lucifer 128-bit)
 and because design criteria were classified
 subsequent events and public analysis
show in fact design was appropriate
 use of DES has flourished
 especially in financial applications
 still standardised for legacy application use
DES Encryption Overview
 Initial Permutation IP
 first step of the data computation
 IP reorders the input data bits
 even bits to LH half, odd bits to RH half
 quite regular in structure (easy in h/w)
 example:

IP(675a6967 5e5a6b5a) = (ffb2194d

004df6fb)
 DES Round Structure
 uses two 32-bit L & R halves
 as for any Feistel cipher can describe as:
Li = Ri–1
Ri = Li–1  F(Ri–1, Ki)
 F takes 32-bit R half and 48-bit subkey:
 expands R to 48-bits using perm E
 adds to subkey using XOR
 passes through 8 S-boxes to get 32-bit result
 finally permutes using 32-bit perm P
DES Round Structure
 Substitution Boxes S
 have eight S-boxes which map 6 to 4 bits
 each S-box is actually 4 little 4 bit boxes
 outer bits 1 & 6 (row bits) select one row of 4
 inner bits 2-5 (col bits) are substituted
 result is 8 lots of 4 bits, or 32 bits
 row selection depends on both data & key
 feature known as autoclaving (autokeying)
 example:
 S(18 09 12 3d 11 17 38 39) = 5fd25e03
 DES Key Schedule
 forms subkeys used in each round
 initial permutation of the key (PC1) which
selects 56-bits in two 28-bit halves
 16 stages consisting of:
• rotating each half separately either 1 or 2 places
depending on the key rotation schedule K
• selecting 24-bits from each half & permuting them
by PC2 for use in round function F
 note practical use issues in h/w vs s/w
 DES Decryption
 decrypt must unwind steps of data computation
 with Feistel design, do encryption steps again
using subkeys in reverse order (SK16 … SK1)
 IP undoes final FP step of encryption
 1st round with SK16 undoes 16th encrypt round
 ….
 16th round with SK1 undoes 1st encrypt round
 then final FP undoes initial encryption IP
 thus recovering original data value
 Avalanche Effect
 key desirable property of encryption alg
 where a change of one input or key bit
results in changing approx half output bits
 making attempts to “home-in” by guessing
keys impossible
 DES exhibits strong avalanche
 Strength of DES – Key Size
 56-bit keys have 256 = 7.2 x 1016 values
 brute force search looks hard
 recent advances have shown is possible
 in 1997 on Internet in a few months
 in 1998 on dedicated h/w (EFF) in a few days
 in 1999 above combined in 22hrs!
 still must be able to recognize plaintext
 must now consider alternatives to DES
 Strength of DES – Analytic
Attacks
 now have several analytic attacks on DES
 these utilise some deep structure of the cipher
 by gathering information about encryptions
 can eventually recover some/all of the sub-key bits
 if necessary then exhaustively search for the rest
 generally these are statistical attacks
 include
 differential cryptanalysis
 linear cryptanalysis
 related key attacks
 Strength of DES – Timing
Attacks
 attacks actual implementation of cipher
 use knowledge of consequences of
implementation to derive information about
some/all subkey bits
 specifically use fact that calculations can
take varying times depending on the value
of the inputs to it
 particularly problematic on smartcards
 Double-DES?
 could use 2 DES encrypts on each block
 C = EK2(EK1(P))
 issue of reduction to 1-DES; “is DES a group?”
 Campbell, Wiener in 1992: NO!
 “meet-in-the-middle” attack
 works whenever use a cipher twice
 since X = EK1(P) = DK2(C)
 attack by encrypting P with all keys and store
 then decrypt C with keys and match X value
 Basic round of the attack takes 2 * 256
encryptions/decryptions; we may have to repeat it a few
times.
 Show on board
 Triple-DES with Two-Keys
 hence must use 3 encryptions
 would seem to need 3 distinct keys
 but can use 2 keys with E-D-E sequence
 C = EK1(DK2(EK1(P)))
 because encrypt & decrypt equivalent in
security
 if K1=K2 then can work with single DES
 standardized in ANSI X9.17 & ISO8732
 no current known practical attacks
 Triple-DES with Three-Keys
 although are no practical attacks on two-
key, Triple-DES has some drawbacks
 can use Triple-DES with Three-Keys to
avoid even these
 C = EK3(DK2(EK1(P)))
 has been adopted by some Internet
applications, eg PGP, S/MIME
 Public Key
Cryptography
and the
RSA Algorithm
Cryptography and Network
Security
by William Stallings
Lecture slides by Lawrie Brown
Edited by Dick Steflik
 Private-Key Cryptography
 traditional private/secret/single key
cryptography uses one key
 Key is shared by both sender and receiver
 if the key is disclosed communications are
compromised
 also known as symmetric, both parties are
equal
 hence does not protect sender from receiver forging a
message & claiming is sent by sender
 Public-Key Cryptography
 probably most significant advance in the 3000
year history of cryptography
 uses two keys – a public key and a private key
 asymmetric since parties are not equal
 uses clever application of number theory
concepts to function
 complements rather than replaces private key
cryptography
 Public-Key Cryptography
 public-key/two-key/asymmetric cryptography
involves the use of two keys:
 a public-key, which may be known by anybody, and
can be used to encrypt messages, and verify
signatures
 a private-key, known only to the recipient, used to
decrypt messages, and sign (create) signatures
 is asymmetric because
 those who encrypt messages or verify signatures
cannot decrypt messages or create signatures
Public-Key Cryptography
 Why Public-Key
Cryptography?
 developed to address two key issues:
 key distribution – how to have secure
communications in general without having to
trust a KDC with your key
 digital signatures – how to verify a message
comes intact from the claimed sender
 public invention due to Whitfield Diffie &
Martin Hellman at Stanford U. in 1976
 known earlier in classified community
 Public-Key Characteristics
 Public-Key algorithms rely on two keys
with the characteristics that it is:
 computationally infeasible to find decryption
key knowing only algorithm & encryption key
 computationally easy to en/decrypt messages
when the relevant (en/decrypt) key is known
 either of the two related keys can be used for
encryption, with the other used for decryption
(in some schemes)
Public-Key Cryptosystems
 Public-Key Applications
 can classify uses into 3 categories:
 encryption/decryption (provide secrecy)
 digital signatures (provide authentication)
 key exchange (of session keys)
 some algorithms are suitable for all uses,
others are specific to one
 Security of Public Key
Schemes
 like private key schemes brute force exhaustive
search attack is always theoretically possible
 but keys used are too large (>512bits)
 security relies on a large enough difference in
difficulty between easy (en/decrypt) and hard
(cryptanalyse) problems
 more generally the hard problem is known, its
just made too hard to do in practise
 requires the use of very large numbers
 hence is slow compared to private key schemes
 RSA
 by Rivest, Shamir & Adleman of MIT in 1977
 best known & widely used public-key scheme
 based on exponentiation in a finite (Galois) field
over integers modulo a prime
 nb. exponentiation takes O((log n)3) operations (easy)
 uses large integers (eg. 1024 bits)
 security due to cost of factoring large numbers
 nb. factorization takes O(e log n log log n) operations (hard)
 RSA Key Setup
 each user generates a public/private key pair by:
 selecting two large primes at random - p, q
 computing their system modulus N=p.q
 note ø(N)=(p-1)(q-1)
 selecting at random the encryption key e
• where 1<e<ø(N), gcd(e,ø(N))=1
 solve following equation to find decryption key d
 e.d=1 mod ø(N) and 0≤d≤N
 publish their public encryption key: KU={e,N}
 keep secret private decryption key: KR={d,p,q}
 RSA Use
 to encrypt a message M the sender:
 obtains public key of recipient KU={e,N}
 computes: C=Me mod N, where 0≤M<N
 to decrypt the ciphertext C the owner:
 uses their private key KR={d,p,q}
 computes: M=Cd mod N
 note that the message M must be smaller
than the modulus N (block if needed)
 Why RSA Works
 because of Euler's Theorem:
 aø(n)mod N = 1
 where gcd(a,N)=1
 in RSA have:
 N=p.q
 ø(N)=(p-1)(q-1)
 carefully chosen e & d to be inverses mod ø(N)
 hence e.d=1+k.ø(N) for some k
 hence :
Cd = (Me)d = M1+k.ø(N) = M1.(Mø(N))q = M1.(1)q =
M1 = M mod N
 RSA Example
1. Select primes: p=17 & q=11
2. Compute n = pq =17×11=187
3. Compute ø(n)=(p–1)(q-1)=16×10=160
4. Select e : gcd(e,160)=1; choose e=7
5. Determine d: de=1 mod 160 and d < 160
Value is d=23 since 23×7=161= 10×160+1
6. Publish public key KU={7,187}
7. Keep secret private key KR={23,17,11}
 RSA Example cont
 sample RSA encryption/decryption is:
 given message M = 88 (nb. 88<187)
 encryption:
C = 887 mod 187 = 11
 decryption:
M = 1123 mod 187 = 88
 Exponentiation
 can use the Square and Multiply Algorithm
 a fast, efficient algorithm for exponentiation
 concept is based on repeatedly squaring base
 and multiplying in the ones that are needed to
compute the result
 look at binary representation of exponent
 only takes O(log2 n) multiples for number n
 eg. 75 = 74.71 = 3.7 = 10 mod 11
 eg. 3129 = 3128.31 = 5.3 = 4 mod 11
Exponentiation
 RSA Key Generation
 users of RSA must:
 determine two primes at random - p, q
 select either e or d and compute the other
 primes p,q must not be easily derived from
modulus N=p.q
 means must be sufficiently large
 typically guess and use probabilistic test
 exponents e, d are inverses, so use Inverse
algorithm to compute the other
 RSA Security
 three approaches to attacking RSA:
 brute force key search (infeasible given size
of numbers)
 mathematical attacks (based on difficulty of
computing ø(N), by factoring modulus N)
 timing attacks (on running of decryption)
 Factoring Problem
 mathematical approach takes 3 forms:
 factor N=p.q, hence find ø(N) and then d
 determine ø(N) directly and find d
 find d directly
 currently believe all equivalent to factoring
 have seen slow improvements over the years
• as of Aug-99 best is 130 decimal digits (512) bit with GNFS
 biggest improvement comes from improved algorithm
• cf “Quadratic Sieve” to “Generalized Number Field Sieve”
 barring dramatic breakthrough 1024+ bit RSA secure
• ensure p, q of similar size and matching other constraints
 Timing Attacks
 developed in mid-1990’s
 exploit timing variations in operations
 eg. multiplying by small vs large number
 or IF's varying which instructions executed
 infer operand size based on time taken
 RSA exploits time taken in exponentiation
 countermeasures
 use constant exponentiation time
 add random delays
 blind values used in calculations
 Summary
 have considered:
 principles of public-key cryptography
 RSA algorithm, implementation, security