Введение
Принцип, используемый в линейном криптоанализе
В криптоанализе лемма накопления — это принцип, используемый в линейном криптоанализе для построения линейных аппроксимаций действия блочных шифров. Она была введена Мицуру Мацуи (1993) как аналитический инструмент для линейного криптоанализа. Лемма утверждает, что смещение (отклонение ожидаемого значения от 1/2) линейной булевой функции (XOR-выражения) независимых бинарных случайных переменных связано с произведением входных смещений:
In cryptanalysis, the piling up lemma is a principle used in linear cryptanalysis to construct linear approximations to the action of block ciphers. It was introduced by Mitsuru Matsui (1993) as an analytical tool for linear cryptanalysis. The lemma states that the bias (deviation of the expected value from 1/2) of a linear Boolean function (XOR clause) of independent binary random variables is related to the product of the input biases:
или
где — смещение (в сторону нуля), а — дисбаланс.
Обратно, если лемма не выполняется, то входные переменные не являются независимыми.
Conversely, if the lemma does not hold, then the input variables are not independent.
Интерпретация
Лемма подразумевает, что операция XOR над независимыми двоичными переменными всегда уменьшает смещение (или, по крайней мере, не увеличивает его); более того, выходной сигнал не смещен, если и только если хотя бы одна входная переменная не смещена. Обратите внимание, что для двух переменных величина является мерой корреляции между и , равной ; ее можно интерпретировать как корреляцию между и .
Практика
На практике, Xs являются приближениями к S-блокам (компонентам подстановки) блочных шифров. Обычно значения X являются входными данными для S-блока, а значения Y – соответствующими выходными данными. Просто изучив S-блоки, криптоаналитик может определить вероятностные смещения. Суть заключается в поиске комбинаций входных и выходных значений, имеющих вероятности, равные нулю или единице. Чем ближе приближение к нулю или единице, тем более полезно это приближение в линейном криптоанализе. Однако на практике двоичные переменные не являются независимыми, как это предполагается при выводе леммы накопления. Этот момент необходимо учитывать при применении леммы; это не автоматическая формула криптоанализа.