25 этюдов о шифрах - страница 18

Подумайте сами:

1. Разберите примеры работы системы RSA, приведённые на стр. 241–243 книги М. Гарднера «От мозаик Пенроуза к надёжным шрифтам».

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

1) вначале у A и B нет никакой общей секретной информации, но в конце процедуры такая общая секретная информация (общий ключ) у A и B появляется, т.е. вырабатывается;

2) противник, который перехватывает все передачи информации и знает, что хотят получить A и B, тем не менее не может восстановить выработанный общий ключ A и B.

Диффи и Хеллмэн предложили решать эти задачи с помощью функции F(x) = α^>x(modp), где p — большое простое число, x — произвольное натуральное число, α — некоторый примитивный элемент поля GF(p).

Примитивным называется такой элемент a из GF(p), что каждый элемент поля, за исключением нуля, может быть представлен в виде степени a. Можно доказать, хотя это и не просто, что примитивный элемент всегда существует.

Общепризнано, что инвертирование функции α^>x(modp), т.е. дискретное логарифмирование, является трудной математической задачей (см. этюд 3.4).

Сама процедура или, как принято говорить, протокол выработки общего ключа описывается следующим образом.

Числа p и α считаются общедоступными.

Абоненты A и B независимо друг от друга случайно выбирают по одному натуральному числу — скажем x(A) и x(B). Эти элементы они держат в секрете. Далее каждый из них вычисляет новый элемент:

y(A)=α^>x(A)(modp), y(B)=α^>x(B)(modp).

Потом они обмениваются этими элементами по каналу связи. Теперь абонент A, получив y(B) и зная свой секретный элемент x(A), вычисляет новый элемент

y(B)^>x(A)(modp)=(α^>x(B))^>x(A)(modp).

Аналогично поступает абонент B:

y(A)^>x(B)(modp)=(α^>x(A))^>x(B)(modp).

Из свойств поля следует, что тем самым у A и B появился общий элемент поля, равный α^>x(A)x(B). Этот элемент и объявляется общим ключом A и B.

Из описания протокола видно, что противник знает p, α, α^>x(A), α^>x(B), не знает x(A) и x(B) и хочет узнать a^>x(A)x(B). В настоящее время нет алгоритмов действий противника, более эффективных, чем дискретное логарифмирование, а это — трудная математическая задача. (Рекомендуем самостоятельно найти за противника общий ключ, используя алгоритм дискретного логарифмирования и не принимая во внимание вопросы его сложности.)

Идея цифровой подписи (иногда ее еще называют электронной подписью) была предложена Диффи и Хеллмэном. Суть идеи — в использовании односторонней функции с секретом F_>K (см. этюд 3.2). В настоящее время эта идея реализована в большом количестве систем передачи данных, особенно банковских. Сообщение, подписанное цифровой подписью, можно представлять себе как пару (x, y), где x — сообщение (платежное поручение в примере с банком и т.п.), F_>K: X → Y — односторонняя функция, известная всем взаимодействующим абонентам, y — решение уравнения F_>K(y)=x. Из определения функции F_>K (см. этюд 3.2) очевидны следующие достоинства цифровой подписи:

1) подписать сообщение x, т.е. решить уравнение F_>K(y)=x, может только абонент — обладатель данного секрета K; другими словами, подделать подпись невозможно;

2) проверить подлинность подписи может любой абонент, знающий открытый ключ, т.е. саму функцию F_>K;

3) при возникновении споров отказаться от подписи невозможно в силу ее неподделываемости;

4) подписанные сообщения (x, y) можно, не опасаясь ущерба, пересылать по любым каналам связи.

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