25 этюдов о шифрах - [11]

— в рассказе Э. По «Золотой жук»;

— в рассказе А. Конан-Дойля «Пляшущие человечки»;

— в книге М.Н. Аршинова и Л.Е. Садовского «Коды и математика».

2.8. Криптография, комбинаторные алгоритмы и вычислительная техника

Зададимся теперь вопросом: от прогресса в каких областях науки зависят оценки практической стойкости шифров? Внимательный читатель сам из предыдущего изложения ответит на этот вопрос: в первую очередь это — теория сложности алгоритмов и вычислений, а также сложность реализации алгоритмов на вычислительной технике. В последние годы эти области бурно развиваются, в них получены интересные результаты, которые, в частности, влияют на оценки практической стойкости шифров. Многие полезные результаты носят характер «ухищрений» для ускорения алгоритмов и поэтому быстро входят в массовую практику программистов. Особенно это относится к области комбинаторных алгоритмов, выросшей из хорошо известных типичных задач быстрого поиска и сортировки данных. Систематическое подробное изложение этих вопросов содержится в популярном трехтомнике Д. Кнута «Искусство программирования для ЭВМ».

Отметим, что к области комбинаторных алгоритмов относятся также алгоритмы для хорошо известных игр-головоломок типа «кубика Рубика».

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

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

1. Докажите, что наименьший элемент среди чисел {x₁, ..., x_n} нельзя найти меньше, чем за n−1 сравнение.

2. Предложите алгоритм расположения чисел {x₁, ..., x_n} в порядке возрастания, использующий меньше, чем n(n−1)/2 сравнений (т.е. более эффективный, чем тривиальный алгоритм последовательного сравнения каждого числа с каждым).

3. На полке в беспорядке стоят n томов собрания сочинений. Хозяин, увидев два тома, стоящие в неправильном порядке, меняет их местами. Докажите, что не позднее, чем через n² таких перестановок, тома будут расставлены по порядку.

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

5. Задумано и введено в компьютер n натуральных чисел a₁, ..., a_n. За один шаг разрешается ввести в компьютер любые n других натуральных чисел b₁, ..., b_n. После этого компьютер вычисляет сумму a₁b₁+ ...+ a_nb_n и выводит результат на экран. Ясно, что этот результат содержит некоторую информацию о задуманных числах. За какое минимальное число шагов всегда можно угадать задуманные числа?

Глава 3 Новые направления

В 1983 году в книжке «Коды и математика» М.Н. Аршинова и Л.Е. Садовского (библиотечка «Квант») было написано: «Приемов тайнописи — великое множество, и, скорее всего, это та область, где уже нет нужды придумывать что-нибудь существенно новое». Однако это было очередное большое заблуждение относительно криптографии. Еще в 1976 году была опубликована работа молодых американских математиков У. Диффи и М.Э. Хеллмэна «Новые направления в криптографии», которая не только существенно изменила криптографию, но и привела к появлению и бурному развитию новых направлений в математике. В настоящей главе мы опишем основные понятия «новой криптографии».

3.1. Односторонняя функция

Односторонней называется функция F:X→Y, обладающая двумя свойствами:

а) существует полиномиальный алгоритм вычисления значений F(x);

б) не существует полиномиального алгоритма инвертирования функции F, т.е. решения уравнения F(x)=y относительно x.

Отметим, что односторонняя функция существенно отличается от функций, привычных со школьной скамьи, из-за ограничений на сложность ее вычисления и инвертирования. Это новое понятие в математике введено в 1975 году Диффи и Хеллмэном. Но за истекшие 19 лет так и не удалось построить ни одного примера односторонней функции. Тем не менее, активное изучение свойств этого, пока гипотетического, математического объекта позволило установить его связь с другими более изученными объектами. При этом удалось доказать, что проблема существования односторонней функции эквивалентна одной из хорошо известных нерешенных проблем — «совпадают ли классы сложностей Р и NP»? Строгое определение классов P и NP выходит далеко за рамки настоящей книги. Подготовленным читателям рекомендуем фундаментальную монографию М. Гэри и Д. Джонсона «Вычислительные машины и труднорешаемые задачи».

Говоря неформально, класс P состоит из задач с полиномиальной сложностью. Более строго, класс P — это класс языков, распознаваемых за полиномиальное время на детерминированной машине Тьюринга. Если такую машину Тьюринга дополнить гипотетической способностью «угадывания», получается более сильная модель — недетерминированная машина Тьюринга. Класс NP — это класс языков, распознаваемых за полиномиальное время на недетерминированной машине Тьюринга. Проблема совпадения классов