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

Описанную систему называют криптосистемой с открытым ключом, поскольку алгоритм шифрования F_K является общедоступным или открытым. В последнее время такие криптосистемы еще называют асимметричными, поскольку в них есть асимметрия в алгоритмах: алгоритмы шифрования и дешифрования различны. В отличие от таких систем традиционные шифры называют симметричными: в них ключ для шифрования и дешифрования один и тот же, и именно поэтому его нужно хранить в секрете. Для асимметричных систем алгоритм шифрования общеизвестен, но восстановить по нему алгоритм дешифрования за полиномиальное время невозможно.

Описанную выше идею Диффи и Хеллмэн предложили использовать также для цифровой подписи сообщений, которую невозможно подделать за полиномиальное время. Пусть пользователю A необходимо подписать сообщение x. Он, зная секрет K, находит такое y, что F_K(y) = x, и посылает y пользователю B в качестве своей цифровой подписи. Пользователь B хранит y в качестве доказательства того, что A подписал сообщение x. Это доказательство неопровержимо, поскольку никто другой в силу свойства б) односторонней функции с секретом не сможет за полиномиальное время по известному сообщению x=F_K(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) устанавливает связь между этими двумя операциями.

Оказывается, в математике существует много других множеств с парами операций на них, обладающих теми же самыми свойствами. Для таких множеств есть даже специальное название: поле.

Полем называется множество F с двумя отображениями («операциями»), каждое из которых сопоставляет любой паре элементов из F однозначно определенный третий элемент из F, и эти отображения (условно обозначаемые «+» и «∙») удовлетворяют девяти аксиомам (свойствам), приведенным выше.

Особенно важными для криптографии являются конечные поля. Сконструируем одно из таких полей.

Пусть p — простое число. Рассмотрим множество чисел {0, 1, 2, ..., p−1} с операциями сложения и умножения по модулю p (суммой двух чисел считаем остаток от деления на p обычной суммы, произведением — остаток от деления на p обычного произведения). Легко проверить, что свойства 1) – 4) выполнены: для свойств 1) и 4) это очевидно, элемент 0 в свойстве 2) — это обычный нуль, противоположный к элементу a в свойстве 3) — это элемент p — a. Так же легко проверяются свойства 5), 6), 8) и 9). Свойство 7) надо доказывать. Предлагаем вам доказать это самостоятельно, поясним только идею: для каждого a ∈ {0, 1, 2, ..., p−1} требуется найти такие x и y, что ax=1+py, т.е. ax−py=1, а такие x и y всегда можно найти с помощью алгоритма Евклида.

Конечное поле — очень интересный математический объект. Оказывается, например, что число элементов в конечном поле может быть только степенью простого числа, и наоборот, для любого простого числа p и для любого натурального числа n существует и в некотором смысле единственное поле из pⁿ элементов. Для него введено даже специальное обозначение: GF(pⁿ).