Block Cipher takes a fixed number of bits as

an input and outputs the same number of bits.

Suppose that number of bits is n. Because they are n bits long,

there are two to the nth power possible block options for both plaintext and ciphertext.

Not all functions can be used for block ciphers.

To be used as a block cipher,

the function needs to be reversible,

so that given any x,

the decryption of the encryption of X results in the same X.

Also, given the key K,

the computation of the encryption and the decryption functions

are deterministic and they should be easy to compute.

For example, it takes a short time to compute them.

Let's construct an ideal block cipher by considering

an n bit general substitution where for any plaintext bits,

a bit can get mapped to any ciphertext bit.

For example, a plaintext bit of zero can get mapped to either bit one or bit zero.

Because a block cipher function needs to be reversible,

each unique plaintext block needs to be mapped to a unique ciphertext block.

Given such constraint, the ideal block cipher allows

the maximum number of possible encryption mappings from plaintext to ciphertext block.

And this maximizes the information entropy of the ciphertext block.

As we will see in the rest of the lesson,

the maximum number of possible transformations for

the block cipher is two to the nth power factorial.

Let's consider an example using n=4,

to explain ideal block cipher.

Because the block is four-bits long n is equal to four,

there are two to the fourth power or 16 possible plaintext options from 0000 to 0001,

0010 all the way to 1111.

These plaintext blocks are listed in the left column.

The figure next to me also shows the mapping implementation of

a block cipher by connecting the plaintext and the ciphertext with arrows.

For example, the plaintext block zero or 0000

gets mapped to the ciphertext block 15 or 1111.

Plaintext Block one or 0001 gets mapped to the ciphertext block seven or 01111.

Plaintext block two to ciphertext block nine and so on.

Note that I'm converting from boolean to decimals when talking about the blocks here.

The decryption from cipher text block to plain text block merely reverses the encryption,

so that the mapping is from right to left.

The arrows are in the reverse direction from before and are from right to left.

Let's go back to the encryption,

given two to the fourth power or 16 possible block options,

let's show that there are 16 factorial mappings.

16 factorial is equal to 16 times 15 times 14 times 13 times dot dot dot times one.

For the plaintext block zero,

there are 16 possible block options for the ciphertext mapping.

In this example, corresponding to the red arrow,

the block cipher maps the first plaintext block zero or

0000 to the cipher text block 15 or 1111.

To ensure one to one mapping and reversible operations for decryption,

the second plaintexts block or block one,

because we started with block zero.

Block one, the plaintext block one can get mapped to any ciphertext block

except for the ciphertext corresponding to that data of the plaintext block zero.

In this case, because the plaintext block zero got mapped to the ciphertext block 15,

the second plaintext block of one can get mapped

to any ciphertext block except for block 15.

And because of that, it has 16-1 which is

equal to 15 possible options for the ciphertext to which it can get mapped.

In this block cipher,

the plaintext block one gets mapped to the ciphertext block seven.

Similarly, the plain text block two can now choose any ciphertext except for

ciphertext block 15 and 7 because

these two ciphertext blocks are already taken by the previous two plaintext blocks.

Therefore it has 16-2 or 14 possible ciphertext blocks that it can get mapped to.

Moving on, the plaintext block three will have 16-3 or 13 ciphertext block options.

We can continue the logic throughout the blocks until

the last block which is the plaintext block 15.

To generalize this logic for the i plaintext block,

it will have 16-i blocks to choose from.

The number of possible mappings is equal to

the number of block choices that plaintext block zero has,

multiplied by a number of block choices for the plaintext block one,

multiply by that of the plaintext block two and so on.

Therefore, for n=4, there are

16 factorial mappings between a four-bit plaintext and a four-bit ciphertext.

To generalize this over any block length of n,

there are two to the nth power factorial possible mappings

between the plaintext and ciphertext.

This mapping or the transformation itself is the key for such block cipher.

And therefore, the number of key options is two to the nth power factorial.

So each block cipher can be implemented by having a table listing the mapping or

the key so that each row corresponds to the plaintext ciphertext mapping.

Such implementation requires the key to specify the right-hand side of the table,

which takes 16 times four-bits,

so a total of 64 bits.

Generalizing the key length over any block length of n,

the key length needs to be n times two to the nth bits.

This number can grow quite big as it increases.

For example, when n is equal to 64 bits,

the key length and bits is 64 times two to the 64th power,

which is equal to two to the 70th power.

Which is approximately equal to 10 to the 21st power number of bits.