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


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


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

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

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

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

yrrs = gxЧrgkЧs

= gxЧr

+ kЧs

= gm (mod 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). На приемной стороне вычисляется значение хэш-функции h(mr) и проверяется выполнение равенства r = gsy?e(mod

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




- Начало -  - Назад -  - Вперед -



Книжный магазин