25 этюдов о шифрах

N	Буква	Относит. частота
1	а	0,062
2	б	0,014
3	в	0,038
4	г	0,013
5	д	0,025
6	е, ё	0,072
7	ж	0,007
8	3	0,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
22	x	0,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. Докажите, что наименьший элемент среди чисел {x₁, ..., x_n} нельзя найти меньше, чем за n−1 сравнение.

2. Предложите алгоритм расположения чисел {x₁, ..., x_n} в порядке возрастания, использующий меньше, чем n(n

−1)/2 сравнений (т.е. более эффективный, чем тривиальный алгоритм последовательного сравнения каждого числа с каждым).

3. На полке в беспорядке стоят n томов собрания сочинений. Хозяин, увидев два тома, стоящие в неправильном порядке, меняет их местами. Докажите, что не позднее, чем через n² таких перестановок, тома будут расставлены по порядку.

4. На сортировочной станции имеется несколько поездов. Разрешается либо расцепить поезд, состоящий из нескольких вагонов, на два поезда, либо удалить поезд, если в нём всего один вагон. Докажите, что, выполняя эти действия в произвольном порядке, мы рано или поздно удалим все вагоны.

5. Задумано и введено в компьютер n натуральных чисел a₁, ..., a_n. За один шаг разрешается ввести в компьютер любые n других натуральных чисел b₁, ..., b_n. После этого компьютер вычисляет сумму a₁b₁+ ...+ a_nb_n и выводит результат на экран. Ясно, что этот результат содержит некоторую информацию о задуманных числах. За какое минимальное число шагов всегда можно угадать задуманные числа?

Глава 3

Новые направления

В 1983 году в книжке «Коды и математика» М.Н. Аршинова и Л.Е. Садовского (библиотечка «Квант») было написано: «Приемов тайнописи — великое множество, и, скорее всего, это та область, где уже нет нужды придумывать что-нибудь существенно новое». Однако это было очередное большое заблуждение относительно криптографии. Еще в 1976 году была опубликована работа молодых американских математиков У. Диффи и М.Э. Хеллмэна «Новые направления в криптографии», которая не только существенно изменила криптографию, но и привела к появлению и бурному развитию новых направлений в математике. В настоящей главе мы опишем основные понятия «новой криптографии».

3.1. Односторонняя функция

Односторонней называется функция F:X→Y, обладающая двумя свойствами: