Линейный метод
В открытой печати линейной метод криптоанализа впервые был предложен японским математиком Мацуи. Метод предполагает, что криптоаналитик
знает открытые и соответствующие зашифрованные тексты.
Обычно при шифровании используется сложение по модулю 2 текста с ключом и операции рассеивания и перемешивания. Задача
криптоаналитика - найти наилучшую линейную аппроксимацию (после всех циклов шифрования ) выражения
xi1+ .... + xir + yj1 + yjs=zk1 + .... + zk t (3.1)
Пусть pL - вероятность того, что (3.1) выполняется, при этом необходимо, чтобы pL - 1/2 и величина | pL-1/2 | должна быть максимальна.
Если | pL-1/2 | достаточно велика и криптоаналитику известно достаточное число пар открытых и соответствующих зашифрованных текстов, то
сумма по модулю 2 бит ключа на соответствующей позиции в правой части (3.1) равна наиболее вероятному значению суммы по модулю 2
соответствующих бит открытых и зашифрованных текстов в левой части. Если pL > 1/2, то сумма бит ключа в правой части (3.1) равна нулю,
если сумма бит в левой части равна нулю больше, чем для половины пар зашифрованных текстов, и сумма бит ключа в правой части (3.1) равна
единице, если сумма бит в левой части равна единице больше, чем для половины текстов . Если pL< 1/2 , то наоборот : сумма бит ключа в
правой части (3.1) равна нулю , если сумма бит в левой части равна единице больше , чем для половины пар открытых и зашифрованных текстов,
и сумма бит ключа в правой части (3.1) равна единице, если сумма бит в левой части равна нулю больше, чем для половины текстов. Для
нахождени каждого бита собственно ключа теперь нужно решить систему линейных уравнений для известных линейных комбинаций этих бит, но эта
процедура не представляет сложности, так как сложность решения системы линейных уравнений описываетс полиномом не более третьей степени от длины ключа.
Требуемое для раскрытия ключа количество N пар открытых и зашифрованных текстов (блоков) оценивается выражением
N ё | pL-1/2 | -2 .
Для раскрытия ключа шифра DES этим методом необходимо 247 пар известных открытых и зашифрованных текстов.
Дргие Методы
Метод Полларда
Метод встречи посередине
Дифференциальный метод
|
