Стандарт цифровой подписи DSS

Електронні цифрові підписи DSS, Шнорра, Ніберга-Руппеля

Схема подписи Эль-Гамаля

Подписывание сообщения Алисой.

Предположим, что Алиса хочет послать Бобу подписанное сообщение. Сообщение снова представлено числом из .

Алиса выбирает случайное целое , взаимно простое с , и вычисляет . Затем Алиса использует свой секретный показатель для вычисления числа , удовлетворяющего сравнению

Чтобы эффективно найти , можно использовать расширенную версию алгоритма Эвклида.

Алиса посылает Бобу тройку , где пара служит подписью к сообщению .

Проверка подписи Бобом.

Боб получает подпись вместе с сообщением и проверяет эту подпись, убеждаясь, что

Это сравнение должно выполняться, так как в силу соотношения (8.2)

Пример 8.5 (часть 3)

Продолжаем пример 8.5 с публичными параметрами , и . Число известно только Алисе. Предположим, что Алиса хочет подписать для Боба сообщение . Пусть случайное число, выбранное Алисой (оно простое). Алиса вычисляет

p=197; a=2; mA=56;

r=97; u=123; S=.;

R=PowerMod[a,r,197]

S/.Solve[{r*S==u-mA*R,Modulus==p-1},S][[1]]

|| 98

|| 171

чтобы найти подпись , которую она добавляет к своему сообщению . Боб проверяет эту подпись, убеждаясь, что

cA = 178; R = 98; S = 171;

PowerMod[a,u,p]==Mod[PowerMod[cA,R,p]*PowerMod[R,S,p],p]

|| True

Подпись к сообщению в схеме Эль-Гамаля состоит из двух частей:

· , равного со случайным , и

· , являющего решением сравнения (см. (8.2)).

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

DSS (Digital Signature Standard) — американский стандарт, описывающий Digital Signature Algorithm (DSA), который может быть использован для генерации цифровой подписи.

В американском стандарте цифровой подписи DSS (Digital Signature Standard; см. [7]) уравнение подписи имеет вид

Эта система разработана Агентством национальной безопасности (АНБ, по-английски NSA) и принята в качестве стандарта Национальным институтом стандартов и технологии (NIST) США.

1) простое число , двоичное представление которого имеет длину , кратную и лежащую между и ;

2) простой делитель числа , имеющий длину от 160 битов до ;

3) значение ‑ генератор (примитивный элемент) подгруппы порядка , такой что , т.е.

Так как по теореме Ферма , мультипликативный порядок элемента делит . Но поскольку простое, этот порядок равен .

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

Когда Алиса хочет подписать файл , она сначала сжимает документ с помощью криптографически безопасной хэш-функции, называемой SHA (Secure Hash Algorithm), и получает SHA хэш-значение длиной (160-256) битов. Затем она выбирает случайное число и добавляет в качестве подписи к числа и длиной по (160-256) битов, определяемые равенствами

1.

2. , которое найдено из

Получатель проверяет аутентичность и целостность полученного сообщения путем самостоятельного вычисления (используя публичный ключ Алисы ) и сравнением его с полученным значением . Для этого берётся выражение , из которого находятся составные части :

а именно вычисляются

после чего можно найти

Если , документ считается подлинным и пришедшим от Алисы.

Назначение случайного числа — спрятать секретный ключ Алисы.