Сергей Дориченко - 25 этюдов о шифрах
1.8. Почему нужно много разных шифрмашин
Потому что не существует единого, подходящего для всех случаев способа шифрования информации. Выбор криптографической системы зависит от особенностей информации, ее ценности и возможностей владельцев по защите своей информации.
Прежде всего подчеркнем большое разнообразие видов защищаемой информации: документальная, телефонная, телевизионная, компьютерная и т.д. Каждый вид информации имеет свои специфические особенности, и эти особенности сильно влияют на выбор методов шифрования информации. Большое значение имеют объемы и требуемая скорость передачи шифрованной информации. Выбор вида шифра, его параметров и его стойкости существенно зависит от характера защищаемых секретов или тайны. Некоторые тайны (например, государственные, военные и др.) должны сохраняться десятилетиями, а некоторые (например, биржевые) — уже через несколько часов можно разгласить. Необходимо учитывать также и возможности того противника, от которого защищается данная информация. Одно дело — противостоять одиночке или даже банде уголовников, а другое дело мощной государственной структуре.
Из-за такого разнообразия требований приходится разрабатывать различные шифры, которые реализуются в сотнях типов шифрующих машин и устройств. Вместе с тем в наиболее развитых в криптографическом отношении странах существуют стандартные шифры: например, DES — в США и СКЗД — в России.
1.9. Зависимость криптографии от уровня технологий
Результаты криптографии реализуются в виде шифрующих устройств, встроенных в современные сети связи. Поэтому криптографы ограничены в выборе средств тем уровнем техники и технологии, который достигнут на данный момент. Такая зависимость отражается и на выборе используемого в криптографии математического аппарата.
Условно можно выделить три принципиально разные этапа в развитии математического аппарата криптографии.
До 40-х годов XX века были только электромеханические шифрмашины, поэтому и спектр математических преобразовании был ограничен: применялись в основном методы комбинаторного анализа и теории вероятностей.
После появления электронной техники, а тем более компьютеров, сильно изменился и математический аппарат криптографии. Получили развитие прикладные идеи и методы теории информации, алгебры, теории конечных автоматов.
Работы Диффи и Хеллмэна (70-е годы) послужили толчком для бурного развития новых направлений математики: теории односторонних функций, доказательств с нулевым разглашением. Сейчас прогресс именно в этих направлениях определяет практические возможности криптографии.
Глава 2
Математические основы криптографии
Большое влияние на развитие криптографии оказали появившиеся в середине нашего века работы американского математика Клода Шеннона. В этих работах были заложены основы теории информации, а также был разработан математический аппарат для исследований во многих областях науки, связанных с информацией. В данной главе мы кратко ознакомим вас с основополагающими математическими понятиями и идеями, без знания которых успешная работа в области криптографии невозможна.
2.1. Приведение любой информации к двоичному виду
Для того, чтобы доказывать математические теоремы, нужно четко определить объекты, с которыми мы имеем дело. При шифровании текста необходимо, в первую очередь, знать, какие символы могут в нем встречаться, или, проще говоря, знать алфавит. Но алфавитов существует великое множество. Передаваемая информация может состоять и просто из наборов цифр, скажем, номера счетов в банке и деланные по ним выплаты. Поэтому естественно работать с некоторым обобщенным алфавитом — тогда одну и ту же теорему не нужно будет отдельно доказывать, например, для текстов на русском и на английском языке.
В теоретической криптографии принято работать с универсальным алфавитом, состоящим из всех двоичных слов некоторой длины. Двоичное слово длины n — это набор из n нулей и единиц. Соответствующий алфавит состоит из 2n символов. Выбор такого алфавита объясняется многими соображениями.
При использовании компьютеров удобно представлять информацию в виде последовательностей нулей и единиц. Это, в частности, обусловлено применяемыми техническими средствами: в компьютере используются элементы, которые могут находиться в одном из двух состояний. Одно из них обозначается «0», а другое — «1».
С другой стороны, слова в любом алфавите можно легко перевести в двоичные слова. Пусть мы имеем дело с текстами на русском языке и пусть буквы «е» и «ё», а также «и» и «й» не различаются, а пробел между словами считается отдельной буквой (обозначение: _). Тогда наш алфавит состоит из тридцати двух символов. Рассмотрим теперь телеграфный код — старое техническое применение двоичной системы счисления. Он состоит тоже из 32 символов — двоичных слов длины 5. (Подробно о двоичной и других системах счисления можно прочитать в брошюре С.В. Фомина «Системы счисления» из серии «Популярные лекции по математике».) Сопоставим каждой букве двоичное слово длины 5 следующим образом:
_ → 00000, A → 00001, Б → 00010, B → 00011, Г → 00100, Д → 00101, ... , Ю → 11110, Я → 11111.
Заменив в тексте каждую букву на соответствующее двоичное слово, получим двоичный вид нашей информации — некоторую последовательность нулей и единиц (или, как принято говорить, битов). Подобным образом можно поступить и с любым другим алфавитом.
На практике создаются специальные устройства, которые позволяют автоматически переводить вводимую человеком текстовую информацию в двоичную.
Более того, в настоящее время практически любая информация — речь, телевизионные сигналы, музыка и др. — может храниться и пересылаться в двоичном виде. Для работы с такой информацией используют специальные устройства: например, АЦП и ЦАП (аналого-цифровой и цифро-аналоговый преобразователи), устройства для цифровой записи и воспроизведения музыки.
Таким образом, двоичные слова и двоичные последовательности — типовые объекты в криптографических исследованиях.
Подумайте сами:
1. Докажите, что каждое натуральное число n единственным образом представляется в виде n=2k+ak−12k−1+...+a12+a0, где k — некоторе целое неотрицательное число, а каждое из чисел ak−1, ..., a0 — либо 0, либо 1.
2.2. Случайность и закономерность в двоичных последовательностях
Понятие последовательности известно еще со школьных лет. Однако последовательности, которые там изучались, были детерминированными — они однозначно восстанавливались по их нескольким элементам. Так, арифметическая и геометрическая прогрессии восстанавливаются по любым двум своим подряд идущим членам. Значения многочлена в целых точках также образуют детерминированную последовательность: она определяется любыми n+1 своими членами, где n — степень данного многочлена (докажите это!).
Но существуют и другие последовательности, так называемые случайные. Для них, в отличие от детерминированных, вообще говоря, нельзя определить очередной член последовательности, зная предыдущие. Опишем простейший способ получения двоичной случайной последовательности.
Пусть мы подбрасываем «правильную» монету. В зависимости от того, как она падает, полагаем очередной член последовательности равным 0 (орел) или 1 (решка). Как показывает опыт, обычно нельзя угадать, как монета упадет в очередной раз. Однако, если подбрасывать монету достаточно долго, примерно в половине случаев выпадет орел, а в половине — решка. Говорят, что монета падает случайным образом, причем в каждом подбрасывании с одинаковой вероятностью ½ выпадает орел (0) или решка (1).
Однако бывают ситуации («кривая монета»), когда орел и решка выпадают с разной вероятностью — p и q соответственно (p≠q). Отметим, что p+q=1! В случайной двоичной последовательности, полученной на основе подбрасывания «кривой монеты», p можно считать частотой появления нуля, а q — частотой появления единицы.
Для тех кто изучал пределы, уточним: если обозначить через S0(k) число нулей, а через S1(k) — число единиц среди k первых членов нашей последовательности, то тогда предел отношения S0(k)/k равен p и предел отношения S1(k)/k равен q при k стремящемся к бесконечности.
