Editing Linear cryptanalysis (section)

===Constructing linear equations===
For the purposes of linear cryptanalysis, a linear equation expresses the equality of two expressions which consist of binary variables combined with the exclusive-or (XOR) operation. For example, the following equation, from a hypothetical cipher, states the XOR sum of the first and third plaintext bits (as in a block cipher's block) and the first ciphertext bit is equal to the second bit of the key:

:<math>
  P_1 \oplus P_3 \oplus C_1 = K_2.
</math>

In an ideal cipher, any linear equation relating plaintext, ciphertext and key bits would hold with probability 1/2. Since the equations dealt with in linear cryptanalysis will vary in probability, they are more accurately referred to as linear ''approximations''.

The procedure for constructing approximations is different for each cipher. In the most basic type of block cipher, a [[substitution–permutation network]], analysis is concentrated primarily on the [[S-box]]es, the only nonlinear part of the cipher (i.e. the operation of an S-box cannot be encoded in a linear equation). For small enough S-boxes, it is possible to enumerate every possible linear equation relating the S-box's input and output bits, calculate their biases and choose the best ones. Linear approximations for S-boxes then must be combined with the cipher's other actions, such as permutation and key mixing, to arrive at linear approximations for the entire cipher. The [[piling-up lemma]] is a useful tool for this combination step. There are also techniques for iteratively improving linear approximations (Matsui 1994).