程序代写代做代考 algorithm 17crypto_L06

17crypto_L06

Feistal Ciphers and DES

Crpto & SecDev 2017 © Ron Poet:
Lecture 5

1

Feistel Ciphers

� A family of single key, block substitution ciphers.

� Feistel was in charge of the IBM Lucifer project (1973),
and provided the theoretical underpinning for many of the
first block ciphers.

Crpto & SecDev 2017 © Ron Poet:
Lecture 5

2

first block ciphers.

�His work was based on Shannon (1945)

� He proposed 64-bit or 128-bit block sizes.

Feistel Cipher Keys

� The key is the mapping between input and output blocks.

� If all possible mappings are possible then the keys would
be 1021 bits long for a block size of 64.

�Stirling’s approximation of 64!.

Crpto & SecDev 2017 © Ron Poet:
Lecture 5

3

�Stirling’s approximation of 64!.

� There are thus a lot of possible keys.

� The actual size of the key space was reduced, with a key
length of 128 bits.

Product Ciphers

� Feistel used a product cipher.
�Several small transformations are applied one after the

other.
� He alternated substitutions and permutations.

Crpto & SecDev 2017 © Ron Poet:
Lecture 5

4

� He alternated substitutions and permutations.
� The resulting large transformation is likely to be much

harder to break than each of the individual transformations.
� Each substitution used a sub-key, which is generated from

the main or master key.

Feistel Structure

� The initial data block is split into two halves, the left (L)
and right (R) halves.

�So that actual operations involve just one half of each
data block, and so fewer bits.

Crpto & SecDev 2017 © Ron Poet:
Lecture 5

5

data block, and so fewer bits.

�This speeds up data processing. Blocks can be larger
than the computer word length, which was 32 bits in
that era.

� There are a number of rounds, each making a substitution
followed by swapping the two halves.

Feistal Rounds

Initial Permutation

for i = 1 to n (number of rounds)

{

Li = Li-1 ⊕ F(Ri-1, Ki)i i-1 i-1 i
Ri = Ri-1
Swap (Li, Ri)

}

Reverse the Initial Permutation

� F is any function, there are several different Feistel algorithms. Ki is
a sub key, ⊕ is exclusive or.

Crpto & SecDev 2017 © Ron Poet:
Lecture 5

6

Decryption

� Decryption follows the same steps, but with the sub keys
used in the reverse order.

� Thus the same algorithm and key is used for encryption
and decryption.

Crpto & SecDev 2017 © Ron Poet:
Lecture 5

7

� To prove this works, all we need do is show that two
applications of each substitution step, with the same key,
cancel each other.

� Clearly two permutation steps, swapping left and right
halves, cancel each other.

Proof: Two Substitutions Cancel

� Let us represent the substitution process as

(L0, R0) � (L1, R1)

� Then a further application can be written as

(L , R ) � (L , R )

Crpto & SecDev 2017 © Ron Poet:
Lecture 5

8

(L1, R1) � (L2, R2)

� All we need do is show that L2=L0 and R2=R0

Proof (2)

� Applying the Feistel function gives

L1 = L0 ⊕ F(R0, K); R1 = R0
L2 = L1 ⊕ F(R1, K); R2 = R1

� Clearly R = R .

Crpto & SecDev 2017 © Ron Poet:
Lecture 5

9

� Clearly R2 = R0.

� L2 = L1 ⊕ F(R1, K)
= L0 ⊕ F(R0, K) ⊕ F(R0, K)
= L0 ⊕ 0, since a ⊕ a = 0
= L0, since a ⊕ 0 = a

Criteria for the Design of F

� No output bit is close to a linear function of a subset of the
input bits.

� If they were it would be vulnerable to a chosen plain text
attack (linear cryptanalysis).

Crpto & SecDev 2017 © Ron Poet:
Lecture 5

10

�Choose several plain text messages whose bits form a
linear combination.

�Solve the linear equations.
� There is no bias towards some bit positions.
� If two different inputs (key or data) differ by 1 bit, the

output must differ by at least two bits.
�Confusion and diffusion.

DES

� DES stands for Data Encryption Standard.
� It is now an older algorithm but still widely used.
� It is a Feistel block cipher, working with 64 bit data blocks

and 56 bit keys.

Crpto & SecDev 2017 © Ron Poet:
Lecture 5

11

and 56 bit keys.

S-DES

� We can understand how it works by studying a toy system
S-DES developed by Edward Schaefer of the University of
Santa Clara.

� S-DES encrypts 8 bit blocks of data using a 10 bit key.� S-DES encrypts 8 bit blocks of data using a 10 bit key.

� Sample data
Data = 01101011

Key = 1011000110

� There are two substitution rounds, each with its own sub-
key.

� Left and right halves are swapped between them.
Crpto & SecDev 2017 © Ron Poet:

Lecture 5
12

The Initial Permutation

� The initial permutation operates on the 8-bit data blocks.

� If the data bits are numbered 0..7 then the initial
permutation is 15203746.

� Data is now 00111110

Crpto & SecDev 2017 © Ron Poet:
Lecture 5

13

� Data is now 00111110

� The inverse permutation applied at the end of the process
is 30246175.

Sub Key Generation

� Two 8 bit sub keys are generated from the 10 bit master key.
1. The bits of the original key are permuted as 2416390875

01100 01110

2. The left 5 bits and the right 5 bits are both rotated left 1 bit.

Crpto & SecDev 2017 © Ron Poet:
Lecture 5

14

11000 11100

3. The first 8 bit sub key is formed from the following bits: 52637498
K1 = 1010 1000

4. The left and right 5 bits from step 2 are both rotated left 2 bits
00011 10011

5. The second 8 bit sub key is formed from the same bits as step 3.
K2 = 1001 1111

The Function F has 5 steps

1. Expansion of 4 data bits (right half of block) to 8 bits as 30121230
01111101

2. These 8 bits are xored with the 8 bits of the key.
10101000 (key)

Crpto & SecDev 2017 © Ron Poet:
Lecture 5

15

11010101

3. The resulting 8 bits (numbered 01234567) are treated as 4 separate 2
bit numbers called row1, col1, row2, col2. Row and column indices

row1 = bits-03, col1 = bits-12, row2 = bits-47, col2 = bits-56.
(11, 10) : (01, 10)

In decimal, row1 = 3, col1 = 2, row2 = 1, col2 = 2.

The S-Boxes

4. (row1,col1) and (row2,col2) form the row and column indices of two
4×4 tables called S-boxes.

�Each S-box produces 2 bits of output.

�An S-box is a matrix, indexed by the row and column.

Crpto & SecDev 2017 © Ron Poet:
Lecture 5

16

�See next slide for details of the S-boxes.
�S1(3, 2) = 00, S2(1, 2) = 01

�So output = 0001

5. The resulting 4 bit number, the output from the 2 s-boxes undergoes
another permutation 1320, producing the output from F.

0100

Details of the S-Boxes

� Here are the two S-boxes, containing 2 bit numbers

� The output two bits are written as an integer in the
following 2 tables.

Crpto & SecDev 2017 © Ron Poet:
Lecture 5

17

S1 S2

1 0 3 2 0 1 2 3

3 2 1 0 2 0 1 3

0 2 1 3 3 0 1 2

3 1 0 2 2 1 0 3

Relationship with DES

� DES has the same structure as S-DES, but with more steps.

� There are 16 FK steps, each with a 48 bit sub key generated from the
56 bit actual key.

� The function F operates on 32 bit halves of the data.

Crpto & SecDev 2017 © Ron Poet:
Lecture 5

18

�The data is expanded to 48 bits and xored with the sub key.

�These 48 bits are split into 8 chunks, each 6 bits long.

�Each 6 bit chunk is treated as row (2 bits) and column (4 bits)

�They each index an S-box.

� Internally it has 8 S-Boxes, each 4 x 16.

�Each S-Box produces a 4 bit number.

Results from Applying 16 steps in DES

� The following table lists the number of bits that have
changed after each round of DES with
�two very similar plain text blocks (diffusion).
�two very similar keys (confusion).

Crpto & SecDev 2017 © Ron Poet:
Lecture 5

19

�two very similar keys (confusion).
� Clearly diffusion and confusion is quite effective.
� Permutations on their own do not effect confusion or

diffusion.
�A 1 bit change in the origin only changes one bit in the

destination.

16 steps: Number of Different Bits

Round Confusion Diffusion
1 6 2
2 21 14
3 35 28
4 39 32

Crpto & SecDev 2017 © Ron Poet:
Lecture 5

20

4 39 32
10 44 38
11 32 31
12 30 33
13 30 28
14 29 34
15 29 34
16 34 35

Design of the S-Boxes

� The design principles were published in 1992, answering questions
that NSA had introduced a trap door.

� The design made DES resistant to differential cryptanalysis, which
NSA had known about but kept secret.

� Other Feistel ciphers were vulnerable to differential analysis.� Other Feistel ciphers were vulnerable to differential analysis.

� Differential Cryptanalysis uses two very similar chosen plaintext
messages to uncover details of the encryption algorithm.

� Linear cryptanalysis is a similar attack that relies on two similar known
plaintext messages. DES is also resistant to it.

Crpto & SecDev 2017 © Ron Poet:
Lecture 5

21

Double DES

� Double DES uses two different keys to encrypt twice.
�C = EK2(EK1(P))

� It is vulnerable to a known plaintext (assume P and C are
known) meet in the middle attack.

Crpto & SecDev 2017 © Ron Poet:
Lecture 5

22

known) meet in the middle attack.
� Construct a lookup table of all intermediate results

X = EK1(P) for all possible keys K1.
� Decrypt C for all possible keys K2: Y = DK2(C).
� The key we want is when X = Y.
� Look up each value of Y in the table of X’s.
� This takes about twice the effort needed to break the

standard single key DES.

Three Key Triple DES

� Three Key Triple DES
�C = EK3 ( DK2(EK1(P)))
�No known weaknesses.
�Decryption with the second key is used so that if the

Crpto & SecDev 2017 © Ron Poet:
Lecture 5

23

�Decryption with the second key is used so that if the
same key is used three times then this is equivalent to
single DES.

� There are 3 options:
�K1, K2, K3 are all different – 168 bit key
�K1 = K3, K2 different – 112 bit key avoiding meet in the middle.
�K1 = K2 = K3 – 56 bit key, equivalent to single DES.