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

При использовании компьютеров удобно представлять информацию в виде последовательностей нулей и единиц. Это, в частности, обусловлено применяемыми техническими средствами: в компьютере используются элементы, которые могут находиться в одном из двух состояний. Одно из них обозначается «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 12+ a 0, где k — некоторе целое неотрицательное число, а каждое из чисел a k −1, ..., a 0— либо 0, либо 1.

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

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

Пусть мы подбрасываем «правильную» монету. В зависимости от того, как она падает, полагаем очередной член последовательности равным 0 (орел) или 1 (решка). Как показывает опыт, обычно нельзя угадать, как монета упадет в очередной раз. Однако, если подбрасывать монету достаточно долго, примерно в половине случаев выпадет орел, а в половине — решка. Говорят, что монета падает случайным образом, причем в каждом подбрасывании с одинаковой вероятностью ½ выпадает орел (0) или решка (1).

Однако бывают ситуации («кривая монета»), когда орел и решка выпадают с разной вероятностью — p и q соответственно ( p ≠ q ). Отметим, что p + q =1! В случайной двоичной последовательности, полученной на основе подбрасывания «кривой монеты», p можно считать частотой появления нуля, а q — частотой появления единицы.

Для тех кто изучал пределы, уточним: если обозначить через S 0( k ) число нулей, а через S 1( k ) — число единиц среди k первых членов нашей последовательности, то тогда предел отношения S 0( k )/ k равен p и предел отношения S 1( k )/ k равен q при k стремящемся к бесконечности.