Лемма о накоплении

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Найти источники:  "Лемма о накоплении"  -  новости  · газеты  · книги  · ученый  · JSTOR ( февраль 2009 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

В криптоанализе , то укладка вверх леммы являются принципом , используемым в линейном криптоанализе построить линейное приближение к действию блочных шифров . Он был введен Мицуру Мацуи (1993) как аналитический инструмент для линейного криптоанализа.

Теория [ править ]

Лемма о наборе данных позволяет криптоаналитику определить вероятность того, что равенство:

${\ Displaystyle X_ {1} \ oplus X_ {2} \ oplus \ cdots \ oplus X_ {n} = 0}$

выполняется, где X - двоичные переменные (то есть биты: либо 0, либо 1).

Пусть P (A) обозначает «вероятность того, что A истинно». Если он равен единице , A обязательно произойдет, а если он равен нулю, A не может произойти. Прежде всего, рассмотрим лемму о накоплении двух двоичных переменных, где и .${\ Displaystyle P (X_ {1} = 0) = p_ {1}}$${\ Displaystyle P (X_ {2} = 0) = p_ {2}}$

Теперь мы рассматриваем:

${\ Displaystyle P (X_ {1} \ oplus X_ {2} = 0)}$

Благодаря свойствам операции xor это эквивалентно

${\ Displaystyle P (X_ {1} = X_ {2})}$

X ₁ = X ₂ = 0 и X ₁ = X ₂ = 1 являются взаимоисключающими событиями , поэтому мы можем сказать

${\ Displaystyle P (X_ {1} = X_ {2}) = P (X_ {1} = X_ {2} = 0) + P (X_ {1} = X_ {2} = 1) = P (X_ { 1} = 0, X_ {2} = 0) + P (X_ {1} = 1, X_ {2} = 1)}$

Теперь мы должны сделать основное предположение леммы о накоплении: двоичные переменные, с которыми мы имеем дело, независимы ; то есть состояние одного не влияет на состояние остальных. Таким образом, мы можем расширить функцию вероятности следующим образом:

${\ Displaystyle P (X_ {1} \ oplus X_ {2} = 0)}$	${\ Displaystyle = P (X_ {1} = 0) P (X_ {2} = 0) + P (X_ {1} = 1) P (X_ {2} = 1)}$
	${\ displaystyle = p_ {1} p_ {2} + (1-p_ {1}) (1-p_ {2})}$
	${\ displaystyle = p_ {1} p_ {2} + (1-p_ {1} -p_ {2} + p_ {1} p_ {2})}$
	${\ displaystyle = 2p_ {1} p_ {2} -p_ {1} -p_ {2} +1}$

Теперь мы выражаем вероятности p ₁ и p ₂ как ½ + ε ₁ и ½ + ε ₂ , где ε - это смещения вероятности - величина, на которую вероятность отклоняется от 1/2.

${\ Displaystyle P (X_ {1} \ oplus X_ {2} = 0)}$	${\displaystyle =2(1/2+\epsilon _{1})(1/2+\epsilon _{2})-(1/2+\epsilon _{1})-(1/2+\epsilon _{2})+1}$
	${\displaystyle =1/2+\epsilon _{1}+\epsilon _{2}+2\epsilon _{1}\epsilon _{2}-1/2-\epsilon _{1}-1/2-\epsilon _{2}+1}$
	${\displaystyle =1/2+2\epsilon _{1}\epsilon _{2}}$

Таким образом, смещение вероятности ε _1,2 для суммы XOR, указанной выше, равно 2ε ₁ ε ₂ .

Эта формула может быть расширена на большее количество X следующим образом:

${\displaystyle P(X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n}=0)=1/2+2^{n-1}\prod _{i=1}^{n}\epsilon _{i}}$

Обратите внимание, что если любое из ε равно нулю; то есть, если одна из двоичных переменных несмещена, вся функция вероятности будет несмещенной - равной ½.

Связанное с этим несколько иное определение смещения - фактически минус два раза предыдущее значение. Преимущество в том, что теперь с${\displaystyle \epsilon _{i}=P(X_{i}=1)-P(X_{i}=0),}$

${\displaystyle \varepsilon _{total}=P(X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n}=1)-P(X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n}=0)}$

у нас есть

${\displaystyle \varepsilon _{total}=(-1)^{n+1}\prod _{i=1}^{n}\varepsilon _{i},}$

добавление случайных величин означает умножение их (2-е определение) смещений.

Практика [ править ]

На практике X являются приближениями к S-блокам (компонентам подстановки) блочных шифров. Обычно значения X являются входами для S-блока, а значения Y - соответствующими выходами. Просто взглянув на S-блоки, криптоаналитик может определить вероятностные смещения. Уловка состоит в том, чтобы найти комбинации входных и выходных значений с вероятностью ноль или один. Чем ближе приближение к нулю или единице, тем полезнее приближение в линейном криптоанализе.

Однако на практике двоичные переменные не являются независимыми, как предполагается при выводе леммы о накоплении. Это соображение необходимо иметь в виду при применении леммы; это не формула автоматического криптоанализа.

Ссылки [ править ]

• Мацуи, Мицуру (1994). «Метод линейного криптоанализа для шифра DES». Достижения в криптологии - EUROCRYPT '93 . Springer. С. 386–397. DOI : 10.1007 / 3-540-48285-7_33 .