Цифровые подписи, основанные на асимметричных криптосистемах
Для формирования системы ЭЦП можно использовать криптографическую систему Ривеста-Шамира-Эйделмана.
Пользователь A вырабатывает цифровую подпись предназначенного для пользователя B сообщения M с помощью следующего преобразования
SIG(M) =
При этом он использует:
- свое секретное преобразование
- открытое преобразование
Затем он передает пользователю B пару <M, SIG(M)>.
Пользователь B может верифицировать это подписанное сообщение сначала при помощи своего секретного преобразования
и затем открытого
M =
Затем пользователь B производит сравнение полученного сообщения M с тем, которое он получил в результате проверки цифровой подписи, и принимает решение о подлинности/подложности полученного сообщения.
В рассмотренном примере проверить подлинность ЭЦП может только пользователь B. Если же требуется обеспечение возможности верификации ЭЦП произвольным пользователем (например, при циркулярной рассылке документа), то алгоритм выработки ЭЦП упрощается, и подпись вырабатывается по формуле
SIG(M) =
а пользователи осуществляют верификацию с использованием открытого преобразования отправителя (пользователя A):
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.
