Электронная подпись RSA

ЭЛЕКТРОННАЯ, ИЛИ ЦИФРОВАЯ ПОДПИСЬ

Прежде чем начать рассмотрение криптографической цифровой подписи, сформулируем три свойства, которым (в идеале) должна удовлетворять любая, в частности, обычная рукописная подпись:

1. Подписать документ может только «законный» владелец подписи (и, следовательно, никто не может подделать подпись).

2. Автор подписи не может от нее отказаться.

3. В случае возникновения спора возможно участие третьих лиц (например, суда) для установления подлинности подписи.

В этом разделе мы рассмотрим электронную подпись, базирующуюся на схеме RSA.

Если некоторое лицо А планирует подписывать документы, то она должна вначале выбрать параметры RSA точно так же, как это описано в разд 3.6. Для этого А выбирает два больших простых числа Р и Q, вычисляет N=PQ и =(Р- 1 )(Q- 1). Затем он выбирает число d, взаимно простое с , и вычисляет с = d ^-1 mod . Наконец, публикует числа N и d, например, помещает их на своем сайте, ассоциировав со своим именем, и хранит в секрете число с (остальные числа Р, Q и можно забыть, они больше не потребуются). Теперь А готов ставить свои подписи на документах или сообщениях.

Пусть А хочет подписать сообщение . Тогда вначале он вычисляет так называемую хеш-функцию

у=h(m ₁ ,..., m_n),

которая ставит в соответствие сообщению m число у. Предполагается, что алгоритм вычисления хеш-функции всем известен. Отметим наиболее важное свойство хеш-функции: практически невозможно изменить основной текст т ₁,.., т_п, не изменив у. Поэтому на следующем шаге А достаточно снабдить подписью только число у, и эта подпись будет относиться ко всему сообщению т

А вычисляет число

s=y^c mod N, (4.1)

т е. возводит число у в свою секретную степень. Число s это и есть цифровая подпись. Она просто добавляется к сообщению , и тем самым А имеет сформированное подписанное сообщение

(). (4.2)

Теперь каждый, кто знает открытые параметры А, ассоциированные с ее именем, т.е. числа N и d, может проверить подлинность ее подписи. Для этого необходимо, взяв подписанное сообщение (4.2), вычислить значение хеш-функции h (), число

w=s^d mod N (4.3)

и проверить выполнение равенства w = h(m).

Утверждение 4.1. Если подпись подлинная, то w = h( ).

Доказательство. Из (4.3), (4.1) и свойств схемы RSA (разд. 2.6) следует

w=s^d mod N = y^cd mod N =у = h( ).

Утверждение 4.2. Описанная электронная подпись удовлетворяет всем требованиям, предъявляемым к подписи.

Доказательство. Проверим первое свойство подписи. Никто не может разложить число N на простые множители (при больших N порядка 1024 бит по состоянию на 2005 год эта задача практически неразрешима). Поэтому, зная N и d невозможно найти с. Действительно, чтобы вычислить с=d ^-1 mod , нужно знать =(Р- 1)(Q -1), а для этого нужно знать простые множители Р и Q. Таким образом, первое свойство выполнено — никто, кроме Алисы, не может знать число с и поэтому не может подписать сообщение.

Второе свойство выполнено вследствие первого. Автор подписи не может от нее отказаться, так как никто другой не может «сфабриковать» подпись от его имени.

Третье свойство также очевидно - в случае спора заинтересованная сторона может предъявить судье все вычисления для их проверки и выяснения истины.

Утверждение 4.4. Описанная электронная подпись удовлетворяет всем требованиям, предъявляемым к подписи.

Доказательство. Проверим первое свойство подписи (никто не может подделать подпись, другими словами, никто кроме Алисы не может подписать сообщение ее подписью). Действительно, из (4.6) мы видим, что при формировании подписи используется секретное число х. Более того, сомножитель хr, используемый при формировании подписи в (4.6), меняется от сообщения к сообщению (так как k выбирается случайно, то и r случайно).

По той же самой причине Алиса не сможет отказаться от своей подписи, так как никто кроме нее не знает х, т.е. выполняется второе свойство подписи.

Понятно также, что в случае возникновения конфликта между Алисой и Бобом, они могут обратиться к третьим лицам для выявления истины. Судья может проверить все вычисления, если ему предъявят числа х, и r.

3. Вычисляем u ₁ =s·h ^-1 mod q, u ²= - r·h ^-1 mod q.

4. Вычисляем v= ( mod p) mod q.

5. Проверяем выполнение равенства v=r.

Если хотя бы одна из проверок на шагах 2 и 5 не дает нужного результата, то подпись считается недействительной. Если же все проверки удачны, то подпись считается подлинной.

Утверждение 4.5. Если подпись к сообщению была сформирована законно, т.е. обладателем секретного ключа х, то v = r.

Доказательство. Запишем следующую цепочку равенств, которая следует непосредственно из описания метода (напомним, что показатели степени приводятся по модулю q):

Дата добавления: 2014-01-11