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.
9) Для каждых трех элементов a, b, c ∈ F a∙(b+c)=a∙b+a∙c.
Свойства 1) – 4) — это свойства операции сложения, свойства 5) – 8) — свойства операции умножения, а свойство 9) устанавливает связь между этими двумя операциями.
Оказывается, в математике существует много других множеств с парами операций на них, обладающих теми же самыми свойствами. Для таких множеств есть даже специальное название: поле.