Linear cryptanalysis

In the open press linear method of cryptanalysis was first proposed by the Japanese mathematician Matsui. The method assumes that the cryptanalyst knows open and relevant encrypted texts.

Typically, encryption uses modulo-2 addition of text with a key and a scatter and mix operation. The task of the cryptanalyst is to find the best linear approximation (after all encryption cycles) of the expression
xi1 + .... + xir + yj1 + yjs = zk1 + .... + zk t (3.1)

Let pL be the probability that (3.1) holds, and it is necessary that pL - 1/2 and the quantity | pL-1/2 | should be the maximum.
If | pL-1/2 | large enough and the cryptanalyst knows a sufficient number of pairs of open and corresponding encrypted texts, then
sum modulo 2 bits of the key at the corresponding position in the right-hand side of (3.1) is equal to the most probable value of the sum modulo 2
corresponding bits of open and encrypted texts on the left. If pL> 1/2, then the sum of the key bits in the right-hand side of (3.1) is zero, if the sum of the bits in the left-hand side is zero more than half of the pairs of encrypted texts, and the sum of the key bits in the right-hand side of (3.1) is one, if the sum of the bits on the left side is one greater than half the texts. If pL <1/2, then vice versa: the sum of the key bits in the right-hand side of (3.1) is zero, if the sum of the bits in the left-hand side equals one more than half of the pairs of open and encrypted texts, and the sum of the key bits in the right-hand side (3.1 ) is equal to one, if the sum of bits in the left part is zero more than for half of the texts. To find each bit of the key itself, it is now necessary to solve a system of linear equations for known linear combinations of these bits, but this procedure is not difficult, since the complexity of solving a system of linear equations is described by a polynomial of no more than third degree of the key length.
The required for the disclosure of the key number of N pairs of open and encrypted texts (blocks) is estimated by the expression
N ё | pL-1/2 | -2

To reveal the DES cipher key with this method, 247 pairs of known open and encrypted texts are needed.