Double transposition cipher decryption example

Classic Symmetric Cryptography Dr. Y. Chu CIS3360: Security in Computing 0R02 Spring 2018

1

Information

Reading: Chapter 20.1 in textbook

Reference:

Cryptography and Network Security: Principles and Practice, Sixth Edition, William Stallings, Pearson – Prentice Hall, 2014

Other online tutorials

2

Symmetric Encryption

Also referred to as:

Conventional encryption

Secret-key or single-key encryption

The sender and recipient share a common key

All classical encryption algorithms are symmetric

Only alternative before public-key encryption in 1970’s

Still most widely used alternative

Requirements

Strong encryption algorithm

A secret key known only to sender / receiver

Must have a secure means for distributing the key

Security by obscure approach (hoping the algorithm is unknown to the attacker) is unreliable

we should assume the attacker knows the encryption algorithm

Security depends on the secrecy of the key, not the algorithm

Has five ingredients:

Plaintext

Encryption algorithm

Secret key

Ciphertext

Decryption algorithm

3

More Terminology

plaintext - original message

ciphertext – the encrypted message

cipher – the encryption algorithm for transforming plaintext to ciphertext

key(s) - info used by cipher algorithm, should be known only to sender/receiver

encipher (encrypt) - converting plaintext to ciphertext

decipher (decrypt) - recovering plaintext from ciphertext

cryptography - study of encryption principles/methods

cryptanalysis (codebreaking) - study of principles/ methods of deciphering ciphertext without knowing the key

cryptosystem – a set of keys, algorithms, and specific language that form a system for encrypting and decrypting text

Mathematical notation

Encryption and decryption are functions in the mathematical sense

Encrypting plaintext message M using encryption algorithm E with key k:

C = E(k, M)

Decrypting ciphertext C using decryption algorithm D with key k:

M=D(k, C)

4

Computationally Secure Encryption

Encryption is computationally secure if:

Cost of breaking cipher exceeds value of information

Time required to break cipher exceeds the useful lifetime of the information

Usually very difficult to estimate the amount of effort required to break

Can estimate time/cost of a brute-force attack

5

Cryptanalysis

6

Table 20.1

deliberately pick patterns to reveal the

structure of the key

Substitution Ciphers

A substitution cipher is a class of cipher algorithms where:

Letters of plaintext are replaced by other letters or by numbers or symbols

If the plaintext is viewed as a sequence of bits, then substitution involves replacing plaintext bit patterns with ciphertext bit patterns

Assuming English language and letter only substitutions (no numbers or other character)

Then, 26 choices for substitution for “a”

25 choices for substitution for “b” since we can’t use what we chose for “a”

24 choices for “c”, etc.

26! Choices overall: ≈ 4.03 x 1026 = 403,000,000,000,000,000,000,000,000

7

Caesar Cipher

Simplest and earliest known use of a substitution cipher

Used by Julius Caesar

Involves replacing each letter of the alphabet with the letter standing three places further down the alphabet

Shift cipher

Alphabet is wrapped around so that the letter following Z is A

Example

plain: meet me after the toga party

cipher: PHHW PH DIWHU WKH WRJD SDUWB

8

The earliest known, and the simplest, use of a substitution cipher was by Julius

Caesar. The Caesar cipher involves replacing each letter of the alphabet with the

letter standing three places further down the alphabet.

Note that the alphabet is wrapped around, so that the letter following Z is A.

Caesar Cipher Algorithm

Can define transformation as:

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

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

Mathematically give each letter a number

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

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

User modular arithmetic, algorithm can be expressed as:

Encryption: C = E(3, M) = (M + 3) mod (26)

Decryption: M = D(3, C) = (C – 3) mod (26)

A shift may be of any amount, so that the general Caesar algorithm is:

Encryption: C = E(k , M ) = (M + k ) mod 26

Decryption: M = D(k , C ) = (C - k ) mod 26

9

Cryptanalysis of Caesar Cipher

Brute-force cryptanalysis of Caesar cipher

The third line

10

If it is known that a given ciphertext is a Caesar cipher, then a brute-force

cryptanalysis is easily performed: simply try all the 25 possible keys. Figure 2.3

shows the results of applying this strategy to the example ciphertext. In this case, the

plaintext leaps out as occupying the third line.

Three important characteristics of this problem enabled us to use a brute-force

cryptanalysis:

1. The encryption and decryption algorithms are known.

2. There are only 25 keys to try.

3. The language of the plaintext is known and easily recognizable.

Keyword Cipher

Example: use keyword “PROGRAM” to encrypt a message

Steps:

Lay out keyword and ignore duplicate letters (e.g., the second ‘R’ in program)

Finish out the mapping with the letters of the alphabet that were not used, using the standard ordering of the letters

Plaintext and ciphertext alphabets are shown below:

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

P R O G A M B C D E F H I J K L N Q S T U V W X Y Z

Plaintext: p a r t y

Ciphertext: LPQTY

Number of possible ciphers is 26! / (26 – n)! where n = keyword length

For n = 6 (as above), this number is (26)(25)(24)(23)(22)(21) = 165,765,600

11

Monoalphabetic Cipher

Instead of just shifting the alphabet we could shuffle the letters arbitrarily

Each plaintext letter maps to a different random ciphertext letter

This is essentially a keyword cipher with a key that is 26 letters long

Example

Plain: a b c d e f g h i j k l m n o p q r s t uv w x yz

Cipher: D K V Q F I B J W PES C X HT M YAUOL RG ZN

Plaintext: i f w e w i s h t o r e p l a c e l e t t e r s

Ciphertext: W I R F R W AJ UHY F T SDV FS FUUFY A

Number of possible ciphers is 26! ≅ 4.03 x 1026

Susceptible to letter frequency analysis

12

Letter Frequency Analysis

13

Relative frequencies of letters in the English language

Easy to break monoalphabetic cipher because they reflect the frequency data of the original alphabet

One to one mapping

Polyalphabetic Ciphers

Polyalphabetic substitution cipher

Does not use a one-to-one (1:1) correspondence between plaintext letter and its corresponding ciphertext letter

Uses multiple substitution alphabets and switches among them systematically

The same plaintext letter will generally be encrypted differently each time it appears (one-to-many function)

Similarly, the same ciphertext character will generally represent multiple plaintext characters

The Vigenère Cipher is the best-known example

The famous Enigma Cipher from World War II is a well-known more complex example

14

Vigenère Cipher

Best known and one of the simplest polyalphabetic substitution ciphers

This scheme uses multiple shift ciphers (in the form of the Vigenere table)

Vigenere table is a table with all possible shifts

26 Caesar ciphers with shifts of 0 through 25

key is multiple letters long K = k1 k2 ... kd, d = key length

each letter of key specifies a different row of Vigenere table

Substitution

Use the rows (alphabets) specified by the key letters sequentially

Repeat from start after d letters in message (here, we reuse keyword, unlike the keyword cipher

Decryption simply performs same operations in reverse

15

Vigenère Table

16

Shift 0

Shift 1

Shift 25

.

.

.

Vigenère Cipher Example

Example: using the keyword “deceptive”

Write out the plaintext: wearediscoveredsaveyourselves

Write the keyword above it, repeated as needed, trimming off any excess

key: deceptivedeceptivedeceptivede

plaintext: wearediscoveredsaveyourselves

Use each key letter as index to row of Vigenere table

Look up the corresponding letter for the plaintext letter

Repeat the process for each plaintext letter

key: deceptivedeceptivedeceptivede

plaintext: wearediscoveredsaveyourselves

ciphertext: ZICVTWQNGRZGVTWAVZHCQYGLMGZHW

Notice the one to many mapping

Plaintext “e” maps to {I,T,G,H,M}

Ciphertext “G” represents {c,e,r,l}

17

Vigenère Cipher: Modular Arithmetic

Applied modular arithmetic to Vigenere Cipher

key: deceptivedeceptivedeceptivede

plaintext: wearediscoveredsaveyourselves

ciphertext: ZICVTWQNGRZGVTWAVZHCQYGLMGZHW

Columns in red show that modulo reduction was used to get the values

18

Vernam Cipher

The ultimate defense against such a cryptanalysis is to choose a keyword that is as long as the plaintext and has no statistical relationship to it

Vernam cipher works on binary data (bits) rather than letters.

Use a very long but repeating keyword

19

One-Time Pad

Improvement to Vernam cipher

Use a random key that is as long as the message so that the key need not be repeated

Key is used to encrypt and decrypt a single message and then is discarded

Each new message requires a new key of the same length as the new message

Scheme is unbreakable

Produces random output that bears no statistical relationship to the plaintext

Because the ciphertext contains no information whatsoever about the plaintext, there is simply no way to break the code

20

Binary One-Time Pad

Bit operation using exclusive-or (XOR)

The symmetry property of XOR:

C = M ⊕ P and M = C ⊕ P

where P is the pad (the key)

Example:

Let M be the word “IF”, whose ASCII code is: 1001001 1000110

Let pad P (the key) be the random bit pattern: 1010110 0110001

Encryption:

Plaintext 1 0 0 1 0 0 1 1 0 0 0 1 1 0

Key 1 0 1 0 1 1 0 0 1 1 0 0 0 1

Ciphertext 0 0 1 1 1 1 1 1 1 1 0 1 1 1

Decryption:

Ciphertext 0 0 1 1 1 1 1 1 1 1 0 1 1 1

Key 1 0 1 0 1 1 0 0 1 1 0 0 0 1

Plaintext 1 0 0 1 0 0 1 1 0 0 0 1 1 0

21

Same key

Plaintext recovered

Challenges of One-Time Pad

There is the practical problem of making large quantities of random keys

Any heavily used system might require millions of random characters on a regular basis

Key distribution problem

For every message to be sent, a key of equal length is needed by both sender and receiver

22

Pseudo-Random Number Generators

Recall random numbers have many applications

But computers can’t generate truly random numbers.

Computers generate pseudo-random numbers that can pass statistical tests

Uniformity and independence

A pseudo-random number generator (PRNG) is a computer algorithm for generating pseudo-random numbers

The algorithm takes a fixed value, called the seed, as an input and produces a sequence of output bits using a deterministic algorithm

The output bit stream is determined solely by the input value or values, so an adversary who knows the algorithm and the seed can reproduce the entire bit stream

An adversary who does not know the seed is unable to determine the pseudorandom string

23

Linear Congruential Generator

Linear congruential generator (LCG) is one of the PRNGs

An algorithm first proposed by Lehmer that is parameterized with four numbers:

m the modulus m > 0

a the multiplier 0 < a< m

c the increment 0≤ c < m

x0 the starting value, or seed 0 ≤ x0 < m

The sequence of random numbers {xn} is obtained via the following iterative equation:

Xn+1 = (a · xn + c) mod m

If m , a , c , and x0 are integers, then this technique will produce a sequence of integers with each integer in the range 0 ≤ xn < m

The selection of values for a , c , and m is critical in developing a good random number generator

Example:

Let m = 1823, a = 17, b = 248 and x0 = 362

Then x1 = ( 17 x362 + 248 ) mod 1823

= ( 6154 + 248 ) mod 1823

= 6402 mod 1823= 933

We repeat this calculation using the value of x1 instead of x0, obtaining x2 =1525

Similarly, x3 = 651, x4 = 377, x5 = 1188…

24

Playfair Cipher

Recall monoalphabetic ciphers are susceptible to letter frequency analysis

Another polyalphabetic approach to improving security was to encrypt multiple letters as a single unit

Playfair Cipher

Best-known multiple-letter encryption cipher

Invented by British scientist Sir Charles Wheatstone in 1854, but named after Lord Playfair who promoted it

Encrypts pairs of letters (digrams), instead of single letters

Based on the use of a 5 x 5 matrix of letters constructed using a keyword

Reasonably fast and more secure than simple substitution

there are 676 bigrams (2-letter combinations), versus 26 letters

25

Playfair Key Matrix

Fill in letters of keyword (minus duplicates) from left to right and from top to bottom, then fill in the remainder of the matrix with the remaining letters in alphabetic order

Using the keyword MONARCHY:

To get 25 entries, we combine I/J but some people just drop Q

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
26

In this case, the keyword is monarchy . The matrix is constructed by filling

in the letters of the keyword (minus duplicates) from left to right and from top to

bottom, and then filling in the remainder of the matrix with the remaining letters in

alphabetic order. The letters I and J count as one letter. Plaintext is encrypted two

letters at a time, according to the following rules:

1. Repeating plaintext letters that are in the same pair are separated with a filler

letter, such as x, so that balloon would be treated as ba lx lo on.

2. Two plaintext letters that fall in the same row of the matrix are each replaced

by the letter to the right, with the first element of the row circularly following

the last. For example, ar is encrypted as RM.

3. Two plaintext letters that fall in the same column are each replaced by the

letter beneath, with the top element of the column circularly following the last.

For example, mu is encrypted as CM.

4. Otherwise, each plaintext letter in a pair is replaced by the letter that lies in

its own row and the column occupied by the other plaintext letter. Thus, hs

becomes BP and ea becomes IM (or JM, as the encipherer wishes).

The Playfair cipher is a great advance over simple monoalphabetic ciphers.

For one thing, whereas there are only 26 letters, there are 26 * 26 = 676 digrams, so

that identification of individual digrams is more difficult. Furthermore, the relative

frequencies of individual letters exhibit a much greater range than that of digrams,

making frequency analysis much more difficult. For these reasons, the Playfair

cipher was for a long time considered unbreakable. It was used as the standard field

system by the British Army in World War I and still enjoyed considerable use by the

U.S. Army and other Allied forces during World War II.

Despite this level of confidence in its security, the Playfair cipher is relatively

easy to break, because it still leaves much of the structure of the plaintext language

intact. A few hundred letters of ciphertext are generally sufficient.

Playfair Encrypting and Decrypting

Encryption: Each 2-letter plaintext combination forms the opposite diagonal corners of a rectangle in the Playfair matrix.

The corresponding cipher letters are found in the other two corners of that rectangle

The first ciphertext letter is the one in the same row as the first plaintext letter

Decryption: performed in the same manner, except using the ciphertext as input

Example: plaintext “wh” is encrypted as “vy”

27

Playfair Rules

If one plaintext character left over, pad with a ‘Z’ , except if the singleton is a ‘Z’ then replace it with an ‘X’

If a bigram consists of two of the same letter, insert an 'X’ after the first letter to make a bigram, and then move the second letter to be the first letter of the next bigram

If both letters fall in the same row, replace each with the letter to its right (wrapping back to start from end)

If both letters fall in the same column, replace each with the letter below it (wrapping from bottom to top)

Otherwise each letter is replaced by the letter in the same row and in the column of the other letter of the pair (opposite diagonal corners of rectangle)

The first cipher letter is the corner that is in the same row as the first plaintext letter of the bigram; the second cipher letter is the opposite diagonal corner from the first cipher letter (also: when choosing a ciphertext letter from the “I/J” matrix element, always choose “I”).

28

Playfair Example

Wireless: E( wi re le sx sz ) =XG MK UL XA TX

note double “s” and singleton

Monday: E( mo nd ay ) = ON RY NB

note “m” and “o” are in same row

Deem: E( de em ) = CK LC

no double-”e”; also, “e” and “m” in same column

For the Playfair cipher, the “key” is the keyword and all six rules

29

Frequency of Letter Occurance

Revealing the effectiveness of the Playfair and other ciphers

30

Hill Cipher

Developed by the mathematician Lester Hill in 1929

Strength is that it hides single-letter frequencies

Features

Uses linear algebra (matrix multiplication)

Letters are encoded as numbers modulo 26

Blocks of letters are interpreted as vectors

Key is a random matrix of same dimension as vectors

Strong against a ciphertext-only attack but easily broken with a known plaintext attack

31

Vector and Matrix

A vector is an ordered set of numbers

Example: [ 3, 27, 16 ]

Can be represented horizontally or vertically

The dot product of two vectors (same length) is simply the sum of the products of each component

Example: [ 1, 5, 4 ] · [ 4, 2, 6 ] = (1)(4) + (5)(2) + (4)(6) = 4 + 10 + 24 = 38

A matrix is a rectangular arrangement of numerical values

a vector is a special case of matrix with at least one of whose dimensions is 1

we can consider each row or column as a vector

We enclose matrices with square brackets

Examples:

,

32

Enclose matrices with square brackets

Matrix Arithmetic for Hill Cipher

To multiply a matrix by a vector, the matrix must be have as many columns as the vector has rows.

Example

=

The Hill cipher uses a square matrix as its key – “key matrix”

Requirement for the key matrix: must have a matrix inverse

33

Matrix Inverse

The inverse of a square matrix A, is a matrix such that

=I, where I is the identity matrix

Inverse of a matrix by Gauss-Jordan elimination

Example:

34

Matrix Inverse

Not invertible matrix

During Gauss-Jordan elimination, a zero row shows up on the left side

Example:

35

Hill Cipher Encryption

The key matrix must have a matrix inverse so we can decrypt what we encrypt

The key matrix , for any vector

To encrypt

To decrypt

Padding

Use the letter “x” to pad the last block if needed

Modular arithmetic

Matrix arithmetic modulo 26

36

Hill Cipher Example

M=“next”= [13, 4, 23, 19]

Since the matrix is 3x3, this time we split the message into blocks of length 3 and encrypt each block separately.

Since the second block is just the letter “t” we must pad it to make a full block; so,let’s just use “x” as the pad character.

This gives us 2 blocks: “nex” and “txx”

For example, the first block (“nex”) is encrypted as follows (using mod 26 arithmetic)

37

Transposition Ciphers

Ciphertext is a permutation (i.e. rearrangement or shuffling) of the plaintext letter.

Simplest transposition cipher is Rail Fence cipher

Plaintext is written down as a sequence of diagonals and then read off as a sequence of rows

38

Rail Fence of Depth 2

Write plaintext message in 2 rows, alternating letters from one row to the next

Encryption performed by reading across each row

Example: meet me after the toga party

m e m a t r h t g p r y

e t e f e t e o a a t

cipher: MEMATRHTGPRYETEFETEOAAT

39

2 rails

Rail Fence of Depth 3

Use 3 rows and weave back and forth from row 1 to row 2 to row 3, then back to row 2, then 1, and repeat

Example: meet me after the toga party

m m t h g r

e t e f e t e o a a t

e a r t p y

cipher: MMTHGRETEFETEOAATEARTPY

40

3 rails

Columnar Transposition Cipher

Also called “Row Transposition Cipher”

More complex transposition

Write the message in a rectangle, row by row, and read the message off, column by column, but permute the order of the columns

The order of the columns then becomes the key to the algorithm

Key length is same as row length

Pad with the letter ‘x’ (random characters in general, but we will use ‘x’), as needed to complete the last row

41

Columnar Transposition Cipher

Example: “Attack postponed until two am”

Key: 4 3 1 2 5 6 7

Plaintext: a t t a c k p

o s t p o n e

d u n t i l t

w o a m x x x

Ciphertext: TTNAAPTMTSUOAODWCOIXKNLXPETX

42

Summary

What is Symmetric Encryption

Requirements

Terminology

Computationally Secure Encryption

Concept of Substitution Ciphers

Caesar Cipher

Keyword Cipher

Monoalphabetic Cipher

Polyalphabetic Ciphers

Vigenère Cipher

Vernam Cipher and One-Time Pad

Pseudo-Random Number Generators

Linear Congruential Generator

Playfair Cipher

Hill Cipher

Transposition Ciphers

Rail Fence Cipher

Columnar Transposition Cipher