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

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

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

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

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

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

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

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

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

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

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

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

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

Другим понятием, более близким к традиционной криптографии, в которой есть секретный ключ, является понятие односторонней функции с секретом . Иногда еще употребляются термины функция с ловушкой , функция опускной двери (английское название: one-way trap-door function).

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