Линейный метод криптоанализа
В открытой печати линейной метод криптоанализа
впервые был предложен японским математиком Мацуи. Метод предполагает, что
криптоаналитик знает открытые и соответствующие зашифрованные тексты.
Обычно при шифровании используется сложение по
модулю 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 пар известных открытых и зашифрованных текстов.
2.2.
Инструменты криптоанализа .
Для анализа шифров могут
использоваться различные математические инструменты. Однако существуют
общие принципы решения сложных вычислительных задач .
Обычно задачу вычисления ключа можно переформулировать
как задачу поиска внутри большого конечного множества М элемента m, обладающего
нужными свойствами. Один из подходов к решению этой задачи получил название
“разделяй и властвуй”. Суть его заключается в том, что исходная сложна
задача поиска разделяется на две подзадачи. Для этого множество элементов
разбивается на пересекающиеся или слабо пересекающиеся перечислимые подмножества,
распознаваемые по отношению к свойствам, которыми обладает данный элемент.
На первом этапе ищется подмножество, в котором находится требуемый элемент
(решается первая подзадача), затем ищется требуемый элемент внутри найденного
подмножества(решается вторая подзадача). Такого рода разбиение может применятьс
многократно. Примером такого подхода является известный способ угадывани
произвольного слова из многотомной энциклопедии, если отгадывающий может
задать 20 вопросов и получать на них ответы “да” или “нет”.
Подход “разделяй и властвуй” может быть использован
и при проведении анализа шифров. Естественно, его применение должно быть
индивидуальным для каждого криптоалгоритма. Например, если множество М
допускает разбиение на подмножества, распознаваемые в части свойства А,
и существует сжимающее отображение, действующее на этих подмножествах и
сохраняющее данное свойство А, то метод Полларда может быть применен не
к элементам множества М, а к подмножествам, содержащим данный элемент.
Другой эффективный метод решения вычислительных
задач заключается в том, что множество М упорядочивается в порядке убывани
вероятности того, что данный элемент обладает нужным свойством. Далее происходит
опробование элементов М (перебор), начиная с наиболее вероятных. Это техника
использована в дифференциальном методе анализа. Если вероятности распределены
существенно неравномерно, то получается большой выигрыш по сложности. В
частности, если вероятности образуют геометрическую прогрессию, то сложность
нахождения нужного элемента оказывается линейной от размера задачи (логарифма
мощности исходного множества).
Общепринятым инструментом является также линеаризаци
задачи. Это часто обусловлено тем, что аффинные аппроксимации преобразований
образуют полугруппу относительно композиции и имеют простые описания. Однако
такую полугруппу образуют не только аффинные преобразования, но и другие
объекты, например симметрические полиномы, решетки, некоторые классы форм
(однородных полиномов, все слагаемые которых имеют одинаковую степень ).
Под композицией полиномов понимается подстановка полинома в качестве переменной
в другой полином.
Андельман и Ридс для анализа шифров предложили
использовать переход от исходного дискретного шифратора к “непрерывному”
шифратору, который совпадает с исходным на вершинах n-мерного единичного
куба, и далее искать непрерывный ключ с использованием техники поиска экстремумов
непрерывных отображений. Заметим, что здесь кроется определенная сложность
. Это вызвано тем, что все элементы кольца полиномов Жегалкина или кольца
булевых функций с операциями И, ИЛИ, НЕ является идемпотентными. Пусть
переменные принимают значения из некоторого непрерывного подмножества А
вещественных чисел. Для численных значений вещественных аналогов булевых
формул необходимо обеспечить x2=x, для любого рационального
числа r. Таким образом, все вещественные числа А оказываются равными, то
есть элементы А являются элементами факторгруппы R/Q. Нетрудно видеть,
что ни в одной вычислительной модели с конечной разрядностью числа из А
непредставимы, поэтому такой метод не работает ( по крайней мере, для вещественных
и, следовательно, для комплексных чисел ).
Каждый новый метод криптоанализа приводит к пересмотру
безопасности шифров, к которым он применим. Если целью криптоаналитика
является раскрытие возможно большего числа шифров ( независимо от того,
хочет ли он этим нанести ущерб обществу, предупредить его о возможной опасности
или просто получить известность), то для него наилучшей стратегией являетс
разработка универсальных методов анализа. Но эта задача является также
и наиболее сложной.
Алгоритмы (стандарты) шифрования периодически
меняются (что видно на примере шифров LUCIFER, DES, FEAL, клиппер-чипов),
а секретная информация часто имеет свойство стареть, то есть не представляет
большого интереса для нарушителя спустя какое-то время после ее передачи
по каналам связи в зашифрованном виде. Поэтому зависимость эффекта от нахождени
способа раскрытия ключей данного шифра во времени имеет максимум: в начале
срока своего действия криптоалгоритм не имеет широкого распространения,
а в конце срока он перестает быть популярным, а основной объем зашифрованной
информации не представляет интереса.