Интернет магазин китайских планшетных компьютеров


Компьютеры - DSA - Подпись сообщения

29 мая 2011


Оглавление:
1. DSA
2. Параметры схемы цифровой подписи
3. Подпись сообщения
4. Реализация алгоритма
5. Генерация псевдопростых чисел для использования в алгоритме
6. Генерация псевдослучайных чисел для использования в алгоритме



Подпись сообщения выполняется по следующему алгоритму:

1 Выбор случайного числа k \in
2 Вычисление r=\mod q
3 Вычисление s=k^{-1}+x\cdot r)\mod q
4 Выбор другого k, если оказалось, что r=0 или s=0

Подписью является пара чисел, общая длина подписи 2*N.

Проверка подписи

Проверка подписи выполняется по алгоритму:

1 Вычисление w=s^{-1} \mod q
2 Вычисление u_1 = H\cdot w \mod q
3 Вычисление u_2 = r\cdot w \mod q
4 Вычисление v = \mod q

Подпись верна, если v = r

Корректность схемы

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

Во-первых, если g=h^{/q} \mod p, то из этого по Малой теореме Ферма следует g^q=h^{p-1}=1 \mod p. Поскольку g>1 и q простое число, то g должно иметь мультипликативный порядок q по модулю p.

Для подписи сообщения вычисляется

s=k^{-1}+x \cdot r) \mod{q}.

Из этого следует

k=H \cdot s^{-1}+x \cdot r \cdot s^{-1}=H \cdot w + x \cdot r \cdot w \mod{q}.

Так как g имеет порядок q, получим

g^k=g^{H \cdot w \mod q}g^{x \cdot r \cdot w \mod q}=g^{H \cdot w \mod q}y^{r \cdot w \mod q}=g^{u1}y^{u2} \mod{p}.

Наконец, корректность схемы DSA следует из

r= \mod q= \mod q=v.

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



Просмотров: 7416


<<< Distributed.net
Dual EC DRBG >>>


Компьютерное аппаратное обеспечение   
Вычислительные комплексы   
Компьютерные данные   
Компьютерные журналы   
Классы компьютеров   
Компьютеры   
Программное обеспечение   
Производители компьютеров   
Профессии в ИТ   
Системное администрирование   
Компьютерный сленг   
Списки компьютерных терминов   
Человеко-компьютерное взаимодействие