Сергей Дориченко - 25 этюдов о шифрах

Нет, для некоторых шифров можно сразу, даже не зная ключа, восстанавливать открытый текст по шифрованному.

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

Напомним, что шифр замены математически описывается с помощью некоторой подстановки g (см. этюд 2.4). Такой шифр преобразует открытый текст в шифрованный по следующему правилу: каждая буква x заменяется на букву g ( x ). Вскрытие шифра основано на двух следующих закономерностях:

1) в осмысленных текстах любого естественного языка различные буквы встречаются с разной частотой, а действие подстановки g «переносит» эту закономерность на шифрованный текст;

2) любой естественный язык обладает так называемой избыточностью , что позволяет с большой вероятностью «угадывать» смысл сообщения, даже если часть букв в сообщении неизвестна.

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

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

Подробный разбор даже одного примера может занять слишком много места. Любознательным читателям рекомендуем проделать это самостоятельно для какого-нибудь своего шифра замены. Можно также прочитать подробное описание трех примеров:

— в рассказе Э. По «Золотой жук»;

— в рассказе А. Конан-Дойля «Пляшущие человечки»;

— в книге М.Н. Аршинова и Л.Е. Садовского «Коды и математика».

Зададимся теперь вопросом: от прогресса в каких областях науки зависят оценки практической стойкости шифров? Внимательный читатель сам из предыдущего изложения ответит на этот вопрос: в первую очередь это — теория сложности алгоритмов и вычислений, а также сложность реализации алгоритмов на вычислительной технике. В последние годы эти области бурно развиваются, в них получены интересные результаты, которые, в частности, влияют на оценки практической стойкости шифров. Многие полезные результаты носят характер «ухищрений» для ускорения алгоритмов и поэтому быстро входят в массовую практику программистов. Особенно это относится к области комбинаторных алгоритмов , выросшей из хорошо известных типичных задач быстрого поиска и сортировки данных . Систематическое подробное изложение этих вопросов содержится в популярном трехтомнике Д. Кнута «Искусство программирования для ЭВМ».

Отметим, что к области комбинаторных алгоритмов относятся также алгоритмы для хорошо известных игр-головоломок типа «кубика Рубика».

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