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

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

В теоретической криптографии принято работать с универсальным алфавитом, состоящим из всех двоичных слов некоторой длины. Двоичное слово длины 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 −1}2 ^{k −1}+...+ a ₁2+ a ₀, где k – некоторе целое неотрицательное число, а каждое из чисел a _{k −1},..., a ₀ – либо 0, либо 1.