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

Работы Диффи и Хеллмэна (70-е годы) послужили толчком для бурного развития новых направлений математики: теории односторонних функций, доказательств с нулевым разглашением. Сейчас прогресс именно в этих направлениях определяет практические возможности криптографии.

Глава 2

Математические основы криптографии

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

2.1. Приведение любой информации к двоичному виду

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

В теоретической криптографии принято работать с универсальным алфавитом, состоящим из всех двоичных слов некоторой длины. Двоичное слово длины n — это набор из n

нулей и единиц. Соответствующий алфавит состоит из 2ⁿ символов. Выбор такого алфавита объясняется многими соображениями.

При использовании компьютеров удобно представлять информацию в виде последовательностей нулей и единиц. Это, в частности, обусловлено применяемыми техническими средствами: в компьютере используются элементы, которые могут находиться в одном из двух состояний. Одно из них обозначается «0», а другое — «1».

С другой стороны, слова в любом алфавите можно легко перевести в двоичные слова. Пусть мы имеем дело с текстами на русском языке и пусть буквы «е» и «ё», а также «и» и «й» не различаются, а пробел между словами считается отдельной буквой (обозначение: _). Тогда наш алфавит состоит из тридцати двух символов. Рассмотрим теперь телеграфный код — старое техническое применение двоичной системы счисления. Он состоит тоже из 32 символов — двоичных слов длины 5. (Подробно о двоичной и других системах счисления можно прочитать в брошюре С.В. Фомина «Системы счисления» из серии «Популярные лекции по математике».) Сопоставим каждой букве двоичное слово длины 5 следующим образом:

_ → 00000, A → 00001, Б → 00010, B → 00011, Г → 00100, Д

→ 00101, ... , Ю → 11110, Я → 11111.

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

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

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

Таким образом, двоичные слова и двоичные последовательности — типовые объекты в криптографических исследованиях.

Подумайте сами:

1. Докажите, что каждое натуральное число n единственным образом представляется в виде n

=2^k+a_k−12^k−1+...+a₁2+a₀, где k

— некоторе целое неотрицательное число, а каждое из чисел a_k−1, ..., a₀ — либо 0, либо 1.

2.2. Случайность и закономерность в двоичных последовательностях

Понятие последовательности известно еще со школьных лет. Однако последовательности, которые там изучались, были детерминированными — они однозначно восстанавливались по их нескольким элементам. Так, арифметическая и геометрическая прогрессии восстанавливаются по любым двум своим подряд идущим членам. Значения многочлена в целых точках также образуют детерминированную последовательность: она определяется любыми n+1 своими членами, где n — степень данного многочлена (докажите это!).

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