— мысленно стать в положение противника и пытаться с его позиций атаковать шифр, т.е. разрабатывать различные алгоритмы вскрытия шифра; при этом необходимо в максимальной мере обеспечить моделирование сил, средств и возможностей противника;
— наилучший из разработанных алгоритмов использовать для практической оценки стойкости шифра.
Здесь полезно для иллюстрации упомянуть о двух простейших методах вскрытия шифра: случайного угадывания ключа (он срабатывает с маленькой вероятностью, зато имеет маленькую сложность) и перебора всех подряд ключей вплоть до нахождения истинного (он срабатывает всегда, зато имеет очень большую сложность).
2.7. Всегда ли нужна атака на ключ
Нет, для некоторых шифров можно сразу, даже не зная ключа, восстанавливать открытый текст по шифрованному.
Эту мысль удобнее всего проиллюстрировать на примере шифра замены, для которого уже давно разработаны методы вскрытия.
Напомним, что шифр замены математически описывается с помощью некоторой подстановки g (см. этюд 2.4). Такой шифр преобразует открытый текст в шифрованный по следующему правилу: каждая буква x заменяется на букву g(x). Вскрытие шифра основано на двух следующих закономерностях:
1) в осмысленных текстах любого естественного языка различные буквы встречаются с разной частотой, а действие подстановки g «переносит» эту закономерность на шифрованный текст;
2) любой естественный язык обладает так называемой избыточностью, что позволяет с большой вероятностью «угадывать» смысл сообщения, даже если часть букв в сообщении неизвестна.
Приведем для примера относительные частоты букв алфавита русского языка.
NБукваОтносит. частота 1а0,062 2б0,014 3в0,038 4г0,013 5д0,025 6е, ё0,072 7ж0,007 830,016 9и0,062 10й0,010 11к0,028 12л0,035 13м0,026 14н0,053 15о0,090 16п0,023 17р0,040 18с0,045 19т0,053 20у0,021 21ф0,002 22x0,009 23ц0,004 24ч0,012 25ш0,006 26щ0,003 27ы0,016 28ъ, ь0,014 29э0,003 30ю0,006 31я0,018 32пробел0,175Подобные таблицы используются для вскрытия шифра простой замены следующим образом. Составляем таблицу частот встречаемости букв в шифртексте. Считаем, что при замене наиболее частые буквы переходят в наиболее частые. Последовательно перебирая различные варианты, пытаемся либо прийти к противоречию с законами русского языка, либо получить читаемые куски сообщения. Далее по возможности продляем читаемые куски либо по смыслу, либо по законам русского языка.
Подробный разбор даже одного примера может занять слишком много места. Любознательным читателям рекомендуем проделать это самостоятельно для какого-нибудь своего шифра замены. Можно также прочитать подробное описание трех примеров:
— в рассказе Э. По «Золотой жук»;
— в рассказе А. Конан-Дойля «Пляшущие человечки»;
— в книге М.Н. Аршинова и Л.Е. Садовского «Коды и математика».
2.8. Криптография, комбинаторные алгоритмы и вычислительная техника
Зададимся теперь вопросом: от прогресса в каких областях науки зависят оценки практической стойкости шифров? Внимательный читатель сам из предыдущего изложения ответит на этот вопрос: в первую очередь это — теория сложности алгоритмов и вычислений, а также сложность реализации алгоритмов на вычислительной технике. В последние годы эти области бурно развиваются, в них получены интересные результаты, которые, в частности, влияют на оценки практической стойкости шифров. Многие полезные результаты носят характер «ухищрений» для ускорения алгоритмов и поэтому быстро входят в массовую практику программистов. Особенно это относится к области комбинаторных алгоритмов, выросшей из хорошо известных типичных задач быстрого поиска и сортировки данных. Систематическое подробное изложение этих вопросов содержится в популярном трехтомнике Д. Кнута «Искусство программирования для ЭВМ».
Отметим, что к области комбинаторных алгоритмов относятся также алгоритмы для хорошо известных игр-головоломок типа «кубика Рубика».
Алгоритмы вскрытия шифров, как правило, используют большое количество различных приемов сокращения перебора ключей (или других элементов шифра), а также поиска, сравнения и отбраковки данных. Поэтому в оценки стойкости шифров входят различные оценки из теории комбинаторных алгоритмов.
Подумайте сами:
1. Докажите, что наименьший элемент среди чисел {x1, ..., xn} нельзя найти меньше, чем за n−1 сравнение.
2. Предложите алгоритм расположения чисел {x1, ..., xn} в порядке возрастания, использующий меньше, чем n(n−1)/2 сравнений (т.е. более эффективный, чем тривиальный алгоритм последовательного сравнения каждого числа с каждым).