Сергей Дориченко - 25 этюдов о шифрах

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

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

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

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

y ( A )= α x ( A )(mod p ), y ( B )= α x ( B )(mod p ).

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

y ( B ) x ( A )(mod p )=( α x ( B )) x ( A )(mod p ).

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

y ( A ) x ( B )(mod p )=( α x ( A )) x ( B )(mod p ).

Из свойств поля следует, что тем самым у 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 . Клиент подписывает платежное поручение x с помощью функции F K со своим секретом K и посылает подписанное платежное поручение в банк. Банк, получив сообщение от клиента и зная открытый ключ, проверяет подлинность подписи клиента и только после этого выполняет его платежное поручение. В силу отмеченных выше достоинств цифровой подписи и банк, и клиент уверены, что их интересы не пострадают.

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