Сергей Дориченко - 25 этюдов о шифрах
Теперь мы уже понимаем, что чаще всего для защиты своей информации законные пользователи вынуждены применять неабсолютно стойкие шифры. Такие шифры, по крайней мере теоретически, могут быть вскрыты. Вопрос только в том, хватит ли у противника сил, средств и времени для разработки и реализации соответствующих алгоритмов.
Обычно эту мысль выражают так: противник с неограниченными ресурсами может вскрыть любой неабсолютно стойкий шифр.
Как же должен действовать в этой ситуации законный пользователь, выбирая для себя шифр? Лучше всего, конечно, было бы доказать, что никакой противник не может вскрыть выбранный шифр, скажем, за 10 лет и тем самым получить теоретическую оценку стойкости. К сожалению, математическая теория еще не дает нужных теорем — они относятся к нерешенной проблеме нижних оценок сложности задач.
Поэтому у пользователя остается единственный путь — получение практических оценок стойкости. Этот путь состоит из следующих этапов:
— понять и четко сформулировать, от какого противника мы собираемся защищать информацию; необходимо уяснить, что именно противник знает или сможет узнать о системе шифра, какие силы и средства он сможет применить для его вскрытия;
— мысленно стать в положение противника и пытаться с его позиций атаковать шифр, т.е. разрабатывать различные алгоритмы вскрытия шифра; при этом необходимо в максимальной мере обеспечить моделирование сил, средств и возможностей противника;
— наилучший из разработанных алгоритмов использовать для практической оценки стойкости шифра.
Здесь полезно для иллюстрации упомянуть о двух простейших методах вскрытия шифра: случайного угадывания ключа (он срабатывает с маленькой вероятностью, зато имеет маленькую сложность) и перебора всех подряд ключей вплоть до нахождения истинного (он срабатывает всегда, зато имеет очень большую сложность).
2.7. Всегда ли нужна атака на ключ
Нет, для некоторых шифров можно сразу, даже не зная ключа, восстанавливать открытый текст по шифрованному.
Эту мысль удобнее всего проиллюстрировать на примере шифра замены, для которого уже давно разработаны методы вскрытия.
Напомним, что шифр замены математически описывается с помощью некоторой подстановки g (см. этюд 2.4). Такой шифр преобразует открытый текст в шифрованный по следующему правилу: каждая буква x заменяется на букву g(x). Вскрытие шифра основано на двух следующих закономерностях:
1) в осмысленных текстах любого естественного языка различные буквы встречаются с разной частотой, а действие подстановки g «переносит» эту закономерность на шифрованный текст;
2) любой естественный язык обладает так называемой избыточностью, что позволяет с большой вероятностью «угадывать» смысл сообщения, даже если часть букв в сообщении неизвестна.
Приведем для примера относительные частоты букв алфавита русского языка.
NБукваОтносит. частота 1а0,062 2б0,014 3в0,038 4г0,013 5д0,025 6е, ё0,072 7ж0,007 830,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 22x0,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. Докажите, что наименьший элемент среди чисел {x1, ..., xn} нельзя найти меньше, чем за n−1 сравнение.
2. Предложите алгоритм расположения чисел {x1, ..., xn} в порядке возрастания, использующий меньше, чем n(n−1)/2 сравнений (т.е. более эффективный, чем тривиальный алгоритм последовательного сравнения каждого числа с каждым).
3. На полке в беспорядке стоят n томов собрания сочинений. Хозяин, увидев два тома, стоящие в неправильном порядке, меняет их местами. Докажите, что не позднее, чем через n2 таких перестановок, тома будут расставлены по порядку.
4. На сортировочной станции имеется несколько поездов. Разрешается либо расцепить поезд, состоящий из нескольких вагонов, на два поезда, либо удалить поезд, если в нём всего один вагон. Докажите, что, выполняя эти действия в произвольном порядке, мы рано или поздно удалим все вагоны.
5. Задумано и введено в компьютер n натуральных чисел a1, ..., an. За один шаг разрешается ввести в компьютер любые n других натуральных чисел b1, ..., bn. После этого компьютер вычисляет сумму a1b1+ ...+ anbn и выводит результат на экран. Ясно, что этот результат содержит некоторую информацию о задуманных числах. За какое минимальное число шагов всегда можно угадать задуманные числа?
Глава 3
Новые направления
В 1983 году в книжке «Коды и математика» М.Н. Аршинова и Л.Е. Садовского (библиотечка «Квант») было написано: «Приемов тайнописи — великое множество, и, скорее всего, это та область, где уже нет нужды придумывать что-нибудь существенно новое». Однако это было очередное большое заблуждение относительно криптографии. Еще в 1976 году была опубликована работа молодых американских математиков У. Диффи и М.Э. Хеллмэна «Новые направления в криптографии», которая не только существенно изменила криптографию, но и привела к появлению и бурному развитию новых направлений в математике. В настоящей главе мы опишем основные понятия «новой криптографии».
3.1. Односторонняя функция
Односторонней называется функция F:X→Y, обладающая двумя свойствами:
а) существует полиномиальный алгоритм вычисления значений F(x);
б) не существует полиномиального алгоритма инвертирования функции F, т.е. решения уравнения F(x)=y относительно x.
