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.
Отметим, что односторонняя функция существенно отличается от функций, привычных со школьной скамьи, из-за ограничений на сложность ее вычисления и инвертирования. Это новое понятие в математике введено в 1975 году Диффи и Хеллмэном. Но за истекшие 19 лет так и не удалось построить ни одного примера односторонней функции. Тем не менее, активное изучение свойств этого, пока гипотетического, математического объекта позволило установить его связь с другими более изученными объектами. При этом удалось доказать, что проблема существования односторонней функции эквивалентна одной из хорошо известных нерешенных проблем — «совпадают ли классы сложностей Р и NP»? Строгое определение классов P и NP выходит далеко за рамки настоящей книги. Подготовленным читателям рекомендуем фундаментальную монографию М. Гэри и Д. Джонсона «Вычислительные машины и труднорешаемые задачи».
Говоря неформально, класс P состоит из задач с полиномиальной сложностью. Более строго, класс P — это класс языков, распознаваемых за полиномиальное время на детерминированной машине Тьюринга. Если такую машину Тьюринга дополнить гипотетической способностью «угадывания», получается более сильная модель — недетерминированная машина Тьюринга. Класс NP — это класс языков, распознаваемых за полиномиальное время на недетерминированной машине Тьюринга. Проблема совпадения классов P и NP — это проблема соотношения возможностей двух моделей вычислений: детерминированная и недетерминированная машина Тьюринга.
Другим понятием, более близким к традиционной криптографии, в которой есть секретный ключ, является понятие односторонней функции с секретом. Иногда еще употребляются термины функция с ловушкой, функция опускной двери (английское название: one-way trap-door function).
Односторонней функцией с секретом K называется функция FK: X→Y, зависящая от параметра K и обладающая тремя свойствами:
а) при любом K существует полиномиальный алгоритм вычисления значений FK(x);
б) при неизвестном K не существует полиномиального алгоритма инвертирования FK;
в) при известном K существует полиномиальный алгоритм инвертирования FK.
Про существование односторонних функций с секретом можно сказать то же самое, что было сказано ранее про односторонние функции. Для практических целей криптографии было построено несколько функций, которые могут оказаться односторонними. Это означает, что для них свойство б) пока строго не доказано, но известно, что задача инвертирования эквивалентна некоторой давно изучаемой трудной математической задаче. Примеры таких функций приводятся в этюдах 3.5, 3.6, 3.7. Стоит отметить, что для некоторых кандидатов на звание односторонней функции были найдены полиномиальные алгоритмы инвертирования и тем самым доказано, что эти функции не являются односторонними.