Читать книгу Security Engineering - Ross Anderson - Страница 164

Attacks on real block ciphers are usually harder to spot than in this example, but they use the same ideas. It might turn out that the S-box had the property that bit one of the input was equal to bit two plus bit four of the output; more commonly, there will be linear approximations to an S-box which hold with a certain probability. Linear cryptanalysis [897, 1246] proceeds by collecting a number of relations such as “bit 2 plus bit 5 of the input to the first S-box is equal to bit 1 plus bit 8 of the output, with probability 13/16”, then searching for ways to glue them together into an algebraic relation between input bits, output bits and key bits that holds with a probability different from one half. If we can find a linear relationship that holds over the whole cipher with probability , then according to the sampling theorem in probability theory we can expect to start recovering keybits once we have about known texts. If the value of for the best linear relationship is greater than the total possible number of known texts (namely where the inputs and outputs are bits wide), then we consider the cipher to be secure against linear cryptanalysis.