暗号化の分析

今回はキーを見つかる方法を考えたいです。特に線形の方法の数式に関して書きます。　　One way of breaking a block cipher is via linear cryptanalysis. This involves utilizing an approximation to a nonlinear cipher function which is a linear relationship between the ciphertext and plaintext. Then, given a known plaintext, it is trivial to solve for the key. One aspect of this method I am not too familiar with is the use of Walsh transforms to determine the best approximation.
One of the most famous applications of linear cryptanalysis was a recovery of the DES key by Matsui in less than the time required for a brute force search (2^64?).
An example of a nonlinear function presented by Mirza's paper is F(A,B,C) = ABC XOR BC XOR C. The nonlinearity would be due to the bitwise ANDs between A, B,C in ABC, and between B and C in BC, it seems. Examples of linear approximations are A XOR C and A XOR B XOR C XOR 1. Note that neither of these equations can be graphed as lines (they oscillate between 0 and 1) if we consider ABC to be a single variable written in binary. However, fixing two of the three values, the output is linear in the third (it is constrained to 0 and 1, and the output will be 0 in one case and one in the other). In the most superficial sense, linear refers to the degree of each variable. AB XOR C would be degree two (quadratic), and would be equivalent to something like f = xy + z in the decimal domain. In short, expressions for a cipher where all variables (L, R, K) are not multiplied by any other variables can be described as linear.