Методы криптоанализа классических шифров




Линейный метод криптоанализа - часть 2


Для раскрытия ключа шифра DES этим методом необходимо

247 пар известных открытых и зашифрованных текстов.

  2.2.

Инструменты криптоанализа .

 Для анализа шифров могут

использоваться различные математические инструменты. Однако существуют

общие принципы решения сложных вычислительных задач .

Обычно задачу вычисления ключа можно переформулировать

как задачу поиска внутри большого конечного множества М элемента m, обладающего

нужными свойствами. Один из подходов к решению этой задачи получил название

“разделяй и властвуй”. Суть его заключается в том, что исходная сложна

задача поиска разделяется на две подзадачи. Для этого множество элементов

разбивается на пересекающиеся или слабо пересекающиеся перечислимые подмножества,

распознаваемые по отношению к свойствам, которыми обладает данный элемент.

На первом этапе ищется подмножество, в котором находится требуемый элемент

(решается первая подзадача), затем ищется требуемый элемент внутри найденного

подмножества(решается вторая подзадача). Такого рода разбиение может применятьс

многократно. Примером такого подхода является известный способ угадывани

произвольного слова из многотомной энциклопедии, если отгадывающий может

задать 20 вопросов и получать на них ответы “да” или “нет”.

Подход “разделяй и властвуй” может быть использован

и при проведении анализа шифров. Естественно, его применение должно быть

индивидуальным для каждого криптоалгоритма. Например, если множество М

допускает разбиение на подмножества, распознаваемые в части свойства А,

и существует сжимающее отображение, действующее на этих подмножествах и

сохраняющее данное свойство А, то метод Полларда может быть применен не

к элементам множества М, а к подмножествам, содержащим данный элемент.

Другой эффективный метод решения вычислительных

задач заключается в том, что множество М упорядочивается в порядке убывани

вероятности того, что данный элемент обладает нужным свойством. Далее происходит

опробование элементов М (перебор), начиная с наиболее вероятных. Это техника




Содержание  Назад  Вперед