Feistel Cipher

Loading...

From the course by University of Colorado System

Symmetric Cryptography

30 ratings

University of Colorado System

Symmetric Cryptography

30 ratings

Course 2 of 4 in the Specialization Applied Cryptography

Welcome to Symmetric Cryptography! Symmetric cryptography relies on shared secret key to ensure message confidentiality, so that the unauthorized attackers cannot retrieve the message. The course describes substitution and transposition techniques, which were the bases for classical cryptography when the message is encoded in natural language such as English. Then, we build on product ciphers (using both substitution and transposition/permutation) to describe modern block ciphers and review the widely used cipher algorithms in DES, 3-DES, and AES. Lastly, we enable the use of block ciphers to support variable data length by introducing different modes of block cipher operations in ECB, CBC, CFB, OFB, and CTR modes. This course is cross-listed and is a part of the two specializations, the Applied Cryptography specialization and the Introduction to Applied Cryptography specialization.

From the lesson

Block Cipher and DES

This module is about modern ciphers based on product ciphers. We will first define block cipher and contrast it with stream cipher. We will then describe the ideal block cipher, which maximizes the number of transformations, and Feistel Cipher, which is a practical structure framework approximating the ideal block cipher. As a widely used cipher example based on the Feistel Cipher structure; we will study Data Encryption Standard (DES).

Feistel Cipher6:36

Meet the Instructors

Sang-Yoon Chang
Assistant Professor
Computer Science

As discussed previously, ideal block cipher, the use of ideal block cipher

is limited in practice because the key length is too large.

Let's discuss about block cipher designs that enables secured

communications with smaller key lengths.

One researcher who worked on designing practical block cipher is Horst Feistel.

Horst Feistel was a German born researcher who worked in IBM.

He is famous for

leading the IBM team whose design became the Data Encryption Standard or DES.

But let's first review Feistel cipher.

Feistel cipher structure framework for symmetric block ciphers, and

it is used for many block ciphers including DES.

Feistel was motivated to design a practical block cipher

because he knew that ideal block cipher would be limited in practice.

Feistel wanted an approximation of ideal block cipher built out of components that

are easily realizable.

Feistel proposed that the ideal block cipher can be approximated by utilizing

the concept of a product cipher, which executes two or

more simple ciphers in sequence.

So that the final product is cryptographically stronger than any of

the component ciphers.

In particular, Feistel proposed the use of a cipher that alternates substitutions and

permutations, this structure is called Feistel cipher or Feistel network.

Feistel cipher uses a finite number of bits for the key length of k bits,

which is significantly smaller than the key length of an ideal block cipher,

which is n x 2 to the nth power bits given the block length of n.

Also, because the key is k bits, their 2 to the kth power possible keys,

which is smaller than the 2 to the nth power,

factorial possible transformations or keys for the ideal block cipher.

The figure illustrates the Feistel Cipher where the encryption process is shown

on the left and the decryption on the right.

The cipher progresses downward.

Feistel cipher partitions input block into two halves, the left half and

the right half, which are processed through multiple rounds.

Each round performs a substitution with the left half of the data,

which is based on the function F of the right half of the data and the subkey.

Then permutation follows, swapping the two halves.

Let's look at the diagram.

From the top of the diagram, the plain text block is divided into two halves,

L0 and R0, which are the inputs to round 0.

The two halves of the data iterates through n rounds to generate

the cipher text block.

For each round i, the inputs of round i are Li and Ri, derived

from the previous round and a subkey Ki, which is derived from the key K.

The key K is not directly used in the rounds, and

the subkeys Ki are different from K and from each other.

The substitution and

the permutation transformations come from the processing within the rounds.

The function F is called a round function and is designed for substitution.

The output of the round function F is with the left half of the data in each round.

At the end of each round, Feistel cipher swaps the left half and the right half for

permutation.

For each round i, we can mathematically express the operation as following,

and this is iterative operation.

The left half of the round output is nearly the right half

of the previous round output, so Li is equal to Ri- 1.

For the right half of the round output, Ri,

it is actually a result of the between the left

half of the previous round and the F function output.

The F function inputs are the right half of the previous round and the subkey Ki.

Therefore, Ri = Li- 1,

with F of Ri- 1 in Ki Let's

compare that decryption process of the Feistel cipher to the encryption process.

We see that the structure is identical and

that the processes are the same, except for the parameter values.

Essentially, the same hardware or software is used for both encryption and

decryption, with just a slight change in how the keys are used.

For decryption, the ciphertext is the input and

the subkeys Ki are used in the reverse order.

That is use Kn the first round, Kn- 1 in the second round,

and so on until K1 is used in the last round for decryption.

This is a nice feature because it means that there's no need to implement two

different algorithms, one for encryption and one for decryption.

That is, one implementation can be used for both encryption and

decryption but with changes in the subkey inputs and the data inputs.

Feistel cipher is a structure that many symmetric block ciphers use.

There's some design parameters for

Feistel cipher that can vary according to the block cipher design.

These design parameters are the block size, how many bits the block can process,

which accounts for both the L sub i and the R sub i bits.

Key size is another parameter, and key size is the length of the key.

The number of rounds is another parameter.

The subkey generation algorithm, as well as the round function design.

In the rest of the module, we will see the most prominent block

cipher based on Feistel cipher, data encryption standard or DES,

which has been developed by IBM, including Horst Feistel himself.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play