25 этюдов о шифрах

_>n и выводит результат на экран. Ясно, что этот результат содержит некоторую информацию о задуманных числах. За какое минимальное число шагов всегда можно угадать задуманные числа?

Глава 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 называется функция F_K: X→Y, зависящая от параметра K и обладающая тремя свойствами:

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

б) при неизвестном K не существует полиномиального алгоритма инвертирования F_K;

в) при известном K существует полиномиальный алгоритм инвертирования F_K.

Про существование односторонних функций с секретом можно сказать то же самое, что было сказано ранее про односторонние функции. Для практических целей криптографии было построено несколько функций, которые могут оказаться односторонними. Это означает, что для них свойство б) пока строго не доказано, но известно, что задача инвертирования эквивалентна некоторой давно изучаемой трудной математической задаче. Примеры таких функций приводятся в этюдах 3.5, 3.6, 3.7. Стоит отметить, что для некоторых кандидатов на звание односторонней функции были найдены полиномиальные алгоритмы инвертирования и тем самым доказано, что эти функции не являются односторонними.

3.2. Что даёт односторонняя функция для криптографии

Применение односторонней функции в криптографии позволяет:

1) организовать обмен шифрованными сообщениями с использованием только открытых каналов связи, т.е. отказаться от секретных каналов связи для предварительного обмена ключами;

2) включить в задачу вскрытия шифра трудную математическую задачу и тем самым повысить обоснованность стойкости шифра;

3) решать новые криптографические задачи, отличные от шифрования (цифровая подпись и др.).

Прежде чем разбирать конкретные примеры, опишем идею Диффи и Хеллмэна в общем виде.

Пользователь A, который хочет получать шифрованные сообщения, должен сначала выбрать какую-нибудь одностороннюю функцию F_K с секретом K. Он сообщает всем заинтересованным (например, публикует) описание функции F_K в качестве своего алгоритма шифрования. Но при этом значение секрета K он никому не сообщает и держит в секрете. Если теперь пользователь B хочет послать A защищаемую информацию x∈X, то он вычисляет F_K(x) и посылает по открытому каналу к A. Поскольку A для своего секрета K умеет инвертировать F_K, то он вычисляет x по полученному F_K (x). Никто другой не знает K и поэтому в силу свойства б) односторонней функции с секретом не сможет за полиномиальное время по известному шифрованному сообщению F_K(x) вычислить защищаемую информацию x.

Таким образом, построена система передачи защищаемой информации, причем выполнены два новых свойства:

1) для передачи сообщений не требуется предварительный обмен ключами по секретному каналу связи;