Feistel cipher

A Feistel cipher is called a block encryption that is built up in the form of a Feistel network . This is a general structure with which block encryptions can be implemented. An IBM employee , Horst Feistel , is believed to be the inventor of this structure. In the 1970s he worked with others on the so-called " Lucifer " project , the aim of which was to develop efficient encryption technology. Lucifer and the DES algorithm derived from it represent a Feistel network.

Many modern symmetrical encryption methods are based on Feistel networks because they can easily be used to ensure the reversibility ( bijectivity ) of the encryption. This fulfills the necessary basic condition for block ciphers that there is no ambiguity when mapping cipher blocks to plain text blocks during decryption. Furthermore, the Feistel structure was analyzed by many cryptologists and found to be good.

Working method

Structure of a Feistel cipher

As the name "block cipher" suggests, the plain text is broken down into blocks, each of which is individually encrypted. The size of the blocks depends on the respective encryption method; it is often a multiple of 64 bits . A block is first divided into two (mostly equal) parts:, and processed in successive rounds. In each round one of these parts is linked to the output of a round function. The round function receives the other sub-block and a round key as input. The following formula is used within the -th round ( runs from 1 to ): ${\ displaystyle P = L_ {1} \ | R_ {1}}$ ${\ displaystyle n}$ ${\ displaystyle i}$ ${\ displaystyle i}$ ${\ displaystyle n}$

{\ displaystyle L_ {i + 1} \! \, = R_ {i}}

,

{\ displaystyle R_ {i + 1} \! \, = L_ {i} \ oplus F (R_ {i}, K_ {i})}

.

Thereby forming the so-called. Lap or transformation function and to have the round key. stands for an easily reversible link. The bitwise XOR is often used , which is identical to its inverse, ie is self-inverse . The ciphertext at the end of the rounds is the merge . ${\ displaystyle F}$ ${\ displaystyle K_ {1}}$ ${\ displaystyle K_ {n}}$ ${\ displaystyle \ oplus}$ ${\ displaystyle C = L_ {n + 1} \ | R_ {n + 1}}$

Feistel networks allow decryption without the need for the reverse function of . If you want to decipher a ciphertext, you carry out the steps of the above formula in reverse order, running from to 1: ${\ displaystyle F}$ ${\ displaystyle i}$ ${\ displaystyle n}$

{\ displaystyle R_ {i} \! \, = L_ {i + 1}}

,

{\ displaystyle L_ {i} \! \, = R_ {i + 1} \ ominus F (L_ {i + 1}, K_ {i})}

.

${\ displaystyle \ ominus}$ stands for the reverse of . For example , as an alternative to XOR , the addition can be modulo , with the length of a sub-block in bits, and the subtraction is then modulo . Both can easily be calculated on most digital computers, because the modulo division results automatically by cutting off any overflow bits. Example: XTEA . ${\ displaystyle \ oplus}$ ${\ displaystyle \ oplus}$ ${\ displaystyle 2 ^ {b}}$ ${\ displaystyle b}$ ${\ displaystyle \ ominus}$ ${\ displaystyle 2 ^ {b}}$

The link can also be more complex and z. B. also contain bit rotations . Examples: RC5 , RC6 .

variant

Some methods also link the round key directly to the sub-blocks, and the round function then (mostly) does not depend on the key: ${\ displaystyle F}$

{\ displaystyle L_ {i + 1} \! \, = R_ {i} \ circ K_ {i}}

,

{\ displaystyle R_ {i + 1} \! \, = L_ {i} \ oplus F (L_ {i + 1})}

.

${\ displaystyle \ oplus}$ and in turn stand for (not necessarily different) simply invertible links. Examples: RC5 , RC6 , Blowfish . ${\ displaystyle \ circ}$

Division into sub-blocks

A balanced Feistel network (BFN) exists when the two parts into which the data block is divided are of the same size. Otherwise, if the parts are of different sizes, it is called an unbalanced (unbalanced) Feistel network (UFN).

Applications

The following ciphers are further examples of Feistel networks:

literature

Horst Feistel: Cryptography and Computer Privacy . In: Scientific American . 228, No. 5, May 1973, pp. 15-23.

Web links

Sample program for calculation