Сергей Дориченко - 25 этюдов о шифрах
Отметим, что односторонняя функция существенно отличается от функций, привычных со школьной скамьи, из-за ограничений на сложность ее вычисления и инвертирования. Это новое понятие в математике введено в 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. Стоит отметить, что для некоторых кандидатов на звание односторонней функции были найдены полиномиальные алгоритмы инвертирования и тем самым доказано, что эти функции не являются односторонними.
3.2. Что даёт односторонняя функция для криптографии
Применение односторонней функции в криптографии позволяет:
1) организовать обмен шифрованными сообщениями с использованием только открытых каналов связи, т.е. отказаться от секретных каналов связи для предварительного обмена ключами;
2) включить в задачу вскрытия шифра трудную математическую задачу и тем самым повысить обоснованность стойкости шифра;
3) решать новые криптографические задачи, отличные от шифрования (цифровая подпись и др.).
Прежде чем разбирать конкретные примеры, опишем идею Диффи и Хеллмэна в общем виде.
Пользователь A, который хочет получать шифрованные сообщения, должен сначала выбрать какую-нибудь одностороннюю функцию FK с секретом K. Он сообщает всем заинтересованным (например, публикует) описание функции FK в качестве своего алгоритма шифрования. Но при этом значение секрета K он никому не сообщает и держит в секрете. Если теперь пользователь B хочет послать A защищаемую информацию x∈X, то он вычисляет FK(x) и посылает по открытому каналу к A. Поскольку A для своего секрета K умеет инвертировать FK, то он вычисляет x по полученному FK(x). Никто другой не знает K и поэтому в силу свойства б) односторонней функции с секретом не сможет за полиномиальное время по известному шифрованному сообщению FK(x) вычислить защищаемую информацию x.
Таким образом, построена система передачи защищаемой информации, причем выполнены два новых свойства:
1) для передачи сообщений не требуется предварительный обмен ключами по секретному каналу связи;
2) стойкость шифра зависит от сложности решения трудной математической задачи инвертирования односторонней функции с секретом.
Описанную систему называют криптосистемой с открытым ключом, поскольку алгоритм шифрования FK является общедоступным или открытым. В последнее время такие криптосистемы еще называют асимметричными, поскольку в них есть асимметрия в алгоритмах: алгоритмы шифрования и дешифрования различны. В отличие от таких систем традиционные шифры называют симметричными: в них ключ для шифрования и дешифрования один и тот же, и именно поэтому его нужно хранить в секрете. Для асимметричных систем алгоритм шифрования общеизвестен, но восстановить по нему алгоритм дешифрования за полиномиальное время невозможно.
Описанную выше идею Диффи и Хеллмэн предложили использовать также для цифровой подписи сообщений, которую невозможно подделать за полиномиальное время. Пусть пользователю A необходимо подписать сообщение x. Он, зная секрет K, находит такое y, что FK(y) = x, и посылает y пользователю B в качестве своей цифровой подписи. Пользователь B хранит y в качестве доказательства того, что A подписал сообщение x. Это доказательство неопровержимо, поскольку никто другой в силу свойства б) односторонней функции с секретом не сможет за полиномиальное время по известному сообщению x=FK(y) подделать цифровую подпись y.
В дальнейшем на основе аналогичных рассуждений был предложен еще целый ряд так называемых криптографических протоколов. Эти протоколы позволили решить много новых задач взаимодействия удаленных пользователей по техническим каналам связи в условиях различных угроз (подробнее об этом см. этюд 3.8).
3.3. Числа и поля
Занимаясь математикой, вы постоянно пользуетесь очевидными свойствами действительных чисел, даже не замечая этого, например: сумма чисел не зависит от порядка слагаемых.
Приведем основные свойства операций сложения и умножения на множестве действительных чисел F.
1) Для каждых трех элементов a, b, c ∈ F a+(b+c)=(a+b)+c.
2) В множестве F есть элемент 0 такой, что для каждого a ∈ F a+0=0+a=a.
3) Для каждого элемента a ∈ F существует такой элемент x ∈ F, что a+x=x+a=0 (такой элемент называется противоположным к данному).
4) Для каждых двух элементов a, b ∈ F a+b=b+a.
5) Для каждых трех элементов a, b, c ∈ F a∙(b∙c)=(a∙b)∙c.
6) В множестве F есть элемент 1 (не равный 0) такой, что для каждого a ∈ F a∙1=1∙a=a.
7) Для каждого элемента a ∈ F, a≠0 существует такой элемент x ∈ F, что a∙x=x∙a=1 (такой элемент называется обратным к данному).
8) Для каждых двух элементов a, b ∈ F a∙b=b∙a.
