Unit-2-Symmetric Key Techniques (Part-1)
Unit-2-Symmetric Key Techniques (Part-1)
Unit-2-Symmetric Key Techniques (Part-1)
2
Classical encryption techniques
• As opposed to modern cryptography
• Goals:
– to introduce basic concepts & terminology of
encryption
3
Basic terminology
• Plaintext: original message to be
encrypted
• Ciphertext: the encrypted message
• Enciphering or encryption: the process of
converting plaintext into ciphertext
• Encryption algorithm: performs encryption
– Two inputs: a plaintext and a secret key
4
Ciphers
• Symmetric cipher: same key used for
encryption and decryption
– Block cipher: encrypts a block of plaintext at a
time (typically 64 or 128 bits)
– Stream cipher: encrypts data one bit or one byte
at a time
5
Symmetric Encryption
• or conventional / secret-key / single-key
• sender and recipient share a common key
• all classical encryption algorithms are
symmetric
• The only type of ciphers prior to the
invention of asymmetric-key ciphers in
1970’s
• by far most widely used
6
Classical Ciphers
• Plaintext is viewed as a sequence of
elements (e.g., bits or characters)
• Substitution cipher: replacing each element of
the plaintext with another element.
• Transposition (or permutation) cipher:
rearranging the order of the elements of the
plaintext.
• Product cipher: using multiple stages of
substitutions and transpositions
7
Caesar Cipher
• Earliest known substitution cipher
• Invented by Julius Caesar
• Each letter is replaced by the letter three
positions further down the alphabet.
• Plain: 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
Cipher: 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: ohio state RKLR VWDWH
8
Caesar Cipher
• Mathematically, map letters to numbers:
a, b, c, ..., x, y, z
p = DK(c) = (c – k) mod 26
• Can be generalized with any alphabet.
9
Cryptanalysis of Caesar Cipher
• Key space: {0, 1, ..., 25}
• Vulnerable to brute-force attacks.
• E.g., break ciphertext "UNOU YZGZK“
10
Monoalphabetic Substitution Cipher
11
Monoalphabetic Cipher Security
• Now we have a total of 26! = 4 x 1026 keys.
• With so many keys, it is secure against
brute-force attacks.
• But not secure against some cryptanalytic
attacks.
• Problem is language characteristics.
12
Language Statistics and Cryptanalysis
13
English Letter Frequencies
14
Statistics for double & triple letters
• In decreasing order of frequency
• Double letters:
th he an in er re es on, …
• Triple letters:
the and ent ion tio for nde, …
15
Letter frequencies in ciphertext
P 13.33 H 5.83 F 3.33 B 1.67 C 0.00
Z 11.67 D 5.00 W 3.33 G 1.67 K 0.00
S 8.33 E 5.00 Q 2.50 Y 1.67 L 0.00
U 8.33 V 4.17 T 2.50 I 0.83 N 0.00
O 7.50 X 4.17 A 1.67 J 0.83 R 0.00
M 6.67
16
What type of attack?
• Ciphertext-only attack
• Known-plaintext attack
• Chosen-plaintext attack
• Chosen-ciphertext attack
17
Playfair Cipher
• Not even the large number of keys in a
monoalphabetic cipher provides security.
•
18
Playfair Key Matrix
• Use a 5 x 5 matrix.
• Fill in letters of the key (w/o duplicates).
• Fill the rest of matrix with other letters.
• E.g., key = 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
19
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 the letter to its right (circularly).
3. If both letters fall in the same column, replace
each with the the letter below it (circularly).
4. Otherwise, each letter is replaced by the letter
in the same row but in the column of the other
letter of the pair.
20
Security of Playfair Cipher
• Equivalent to a monoalphabetic cipher with an
alphabet of 26 x 26 = 676 characters.
• Security is much improved over the simple
monoalphabetic cipher.
• Was widely used for many decades
– eg. by US & British military in WW1 and early WW2
• Once thought to be unbreakable.
• Actually, it can be broken, because it still leaves
some structure of plaintext intact.
21
Polyalphabetic Substitution Ciphers
• A sequence of monoalphabetic ciphers (M1, M2,
M3, ..., Mk) is used in turn to encrypt letters.
• A key determines which sequence of ciphers to
use.
• Each plaintext letter has multiple corresponding
ciphertext letters.
• This makes cryptanalysis harder since the letter
frequency distribution will be flatter.
22
Vigenère Cipher
• Simplest polyalphabetic substitution cipher
• Consider the set of all Caesar ciphers:
{ Ca, Cb, Cc, ..., Cz }
• Key: e.g. security
• Encrypt each letter using Cs, Ce, Cc, Cu, Cr,
Ci, Ct, Cy in turn.
• Repeat from start after Cy.
• Decryption simply works in reverse.
23
Example of Vigenère Cipher
• Keyword: deceptive
key: deceptivedeceptivedeceptive
plaintext: wearediscoveredsaveyourself
ciphertext: ZICVTWQNGRZGVTWAVZHCQYGLMGJ
24
Security of Vigenère Ciphers
• There are multiple (how many?) ciphertext letters
corresponding to each plaintext letter.
• So, letter frequencies are obscured but not totally lost.
• To break Vigenere cipher:
1. Try to guess the key length. How?
2. If key length is N, the cipher consists of N Caesar
ciphers. Plaintext letters at positions k, N+k, 2N+k,
3N+k, etc., are encoded by the same cipher.
3. Attack each individual cipher as before.
25
Rotor Cipher Machines
• Before modern ciphers, rotor machines were most common
complex ciphers in use.
• Widely used in WW2.
• Used a series of rotating cylinders.
• Implemented a polyalphabetic substitution cipher of period K.
• With 3 cylinders, K = 263 =17,576.
• With 5 cylinders, K = 265 =12 x 106.
• What is a key?
– If the adversary has a machine
– If the adversary doesn’t have a machine
26
27
German secret setting sheets
Date
Which rotors to use (there were 10 rotors)
Ring setting
Plugboard setting
28
The Rotors
29
Enigma Rotor Machine
30
Enigma Rotor Machine
31
Transposition Ciphers
• Also called permutation ciphers.
• Shuffle the plaintext, without altering the
actual letters used.
• Example: Row Transposition Ciphers
32
Row Transposition Ciphers
• Plaintext is written row by row in a rectangle.
• Ciphertext: write out the columns in an order
specified by a key.
a t t a c k p
Key: 3 4 2 1 5 6 7
o s t p o n e
d u n t i l t
Plaintext:
wo a mx y z
Ciphertext: TTNAAPTMTSUOAODWCOIXKNLYPETZ
33
Product Ciphers
• Uses a sequence of substitutions and
transpositions
– Harder to break than just substitutions or
transpositions
• This is a bridge from classical to modern ciphers.
34
Unconditional & Computational
Security
• A cipher is unconditionally secure if it is
secure no matter how much resources
(time, space) the attacker has.
• A cipher is computationally secure if the
best algorithm for breaking it will require
so much resources (e.g., 1000 years) that
practically the cryptosystem is secure.
• All the ciphers we have examined are not
unconditionally secure.
35
An unconditionally Secure Cipher
Plaintext = m1m2m3m4
Ciphertext = c1c2c3c4
where ci mi ki
36
Symmetric encryption
Classical Encryption Techniques
• Symmetric encryption
• Secret key encryption
• Shared key encryption
Symmetric Encryption
• or conventional / secret-key / single-key
• sender and recipient share a common key
• was the only type of cryptography, prior to
invention of public-key in 1970’s
Basic Terminology
• plaintext - the original message
• ciphertext - the 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) - the study of principles/
methods of deciphering ciphertext without knowing key
• cryptology - the field of both cryptography and
cryptanalysis
Symmetric Cipher Model
Requirements
• Two requirements for secure use of
symmetric encryption:
– a strong encryption algorithm
Y = EK(X)
X = DK(Y)
• assume encryption algorithm is known
• implies a secure channel to distribute key
Cryptography
• can be characterized by:
– type of encryption operations used
• substitution / transposition / product
47
Types of Ciphers
• Substitution ciphers
• Permutation (or transposition) ciphers
• Product ciphers
Classical Substitution Ciphers
plaintext: wearediscoveredsaveyourself
ciphertext:ZICVTWQNGRZGVTWAVZHCQYGLMGJ
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 the ‘number
of alphabets’ in the key string (aka. the
period of the key), 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
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
• have problem of 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
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
OR
• C = KP mod 26
• where C and P are column vectors of length
3, representing the plaintext and ciphertext,
and K is a 3 x 3 matrix, representing the
encryption key. Operations are performed
mod 26.
• For example, consider the plaintext
"paymoremoney" and use the encryption
key