Алгоритмы электронной цифровой подписи

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

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

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

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

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

Часто бывает желательно, чтобы электронная цифровая подпись была разной, даже если дважды подписывается одно и то же сообщение.

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

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

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

(р — 1)]. Подпись образует пара чисел (г, s). После выработки подписи значение к уничтожается.

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

Корректность этого уравнения очевидна.

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

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

Другой вариант подписи Шнорра выглядит так. Для подписи сообщения т автор выбирает случайное k Zq, вычисляет gk (mod р), е = h (gk, т) и z = к + хе (mod q). Подписью является тройка (т, е, z). Проверка подписи заключается в проверке равенства h (gzy-e, m) = e.