Основы современной криптографии

       

Цифровые подписи, основанные на асимметричных криптосистемах


Для формирования системы ЭЦП можно использовать криптографическую систему Ривеста-Шамира-Эйделмана.

Пользователь A вырабатывает цифровую подпись предназначенного для пользователя B сообщения M с помощью следующего преобразования

SIG(M) =

(
(M)).

При этом он использует:

- свое секретное преобразование

;

-                        открытое преобразование

 пользователя B.

Затем он передает пользователю B пару <M, SIG(M)>.

Пользователь B может верифицировать это подписанное сообщение сначала при помощи своего секретного преобразования

с целью получения

(M) =
(SIG(M)) =
(
(
(M))).

и затем открытого

пользователя A для получения сообщения M:

M =

(
(M)).

Затем пользователь B производит сравнение полученного сообщения M с тем, которое он получил в результате проверки цифровой подписи, и принимает решение о подлинности/подложности полученного сообщения.

В рассмотренном примере проверить подлинность ЭЦП может только пользователь B. Если же требуется обеспечение возможности верификации ЭЦП произвольным пользователем (например, при циркулярной рассылке документа), то алгоритм выработки ЭЦП упрощается, и подпись вырабатывается по формуле



SIG(M) =

(M),

а пользователи осуществляют верификацию с использованием открытого преобразования отправителя (пользователя A):

M =

(SIG(M)) =
(
(M)).

Вместо криптосистемы RSA для подписи сообщений можно использовать и любую другую асимметричную криптосистему.

Недостатком подобного подхода является то, что производи­тельность асимметричной криптосистемы может оказаться недостаточной для удовлетворения предъявляемым требованиям. Возможным решением является применение специальной эффективно вычислимой функции, называемой хэш-функцией или функцией хэширования. Входом этой функции является сообщение, а выходом – слово фиксированной длины, много меньшей, чем длина исходного сообщения.


ЭЦП вырабатывается по той же схеме, но при этом используется не само сообщение, а значение хэш-функции от него. Это существенным образом ускорит выработку и верификацию ЭЦП. Требования, предъявляемые к функциям хэширования, а также примеры хэш-функций рассмотрены в п. 4.3.

Очень часто бывает желательно, чтобы электронная цифровая подпись была разной, даже если дважды подписывается одно и то же сообщение. Для этого в процесс выработки ЭЦП необходимо внести элемент "случайности". Способ сделать это был предложен Эль-Гамалем, аналогично тому, как это делается в системе шифрования, носящей его имя.

Выбирается большое простое число p и целое число g, являющееся примитивным элементом в Zp. Эти числа публикуются. Затем выбирается секретное число x и вычисляется открытый ключ для проверки подписи y = gx (mod p).

Далее для подписи сообщения M вычисляется его хэш-функция m = h(M). Выбирается случайное целое k: 1 < k < (p – 1), взаимно простое с p – 1, и вычисляется r = gk (mod p). После этого с помощью расширенного алгоритма Евклида решается относительно s

уравнение m = xr + ks (mod p – 1). Подпись образует пара чисел (r, s). После выработки подписи значение k уничтожается.

Получатель подписанного сообщения вычисляет хэш-функцию сообщения m = h(M) и проверяет выполнение равенства yrrs

(mod p) = = gm. Корректность этого уравнения очевидна:

yrrs = gxЧrgkЧs

= gxЧr

+ kЧs

= gm (mod p).

Еще одна подобная схема была предложена Шнорром. Как обычно, p – большое простое число, q – простой делитель (p – 1), g – элемент порядка q в Zp, k – случайное число, x и y = gx (mod p) – секретный и открытый ключи соответственно. Уравнения выработки подписи выглядят следующим образом:

r = gk (mod p); e  = h(m, r); s = k + xe (mod

q).

Подписью является пара (r, s). На приемной стороне вычисляется значение хэш-функции e = h(m, r) и проверяется выполнение равенства r = gsy?e(mod

p), при этом действия с показателями степени производятся по модулю q.


Содержание раздела