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

Компьютеры - Digital Signature Standard - Проверка подписи

Числа p, q, g и открытый ключ находятся в открытом доступе.

Пусть M', r' и s' полученные версии M, r и s, соответственно, и пусть y — открытый ключ. При проверке подписи сначала нужно посмотреть, выполняются ли следующие неравенства:

0 < r' < q 
0 < s' < q.

Если хотя бы одно неравенство не выполнено, подпись должна быть отвергнута. Если условия неравенств выполнены, производятся следующие вычисления:

w = mod q 
u1 =w) mod q 
u2 =w) mod q 
v =) mod p) mod q. 

Если v = r', то подлинность подписи подтверждена.

Если v ≠ r', то сообщение могло быть изменено, сообщение могло быть неправильно подписано или сообщение могло быть подписано мошенником. В этом случае полученные данные следует рассматривать как поврежденные.

Генерация простых чисел для DSA

Этот раздел включает алгоритмы для генерации простых чисел p и q для DSA. В этих алгоритмах используется генератор случайных чисел.

Вероятностный тест на простоту

Для генерации простых p и q необходим тест на простоту. Есть несколько быстрых вероятностных тестов. В нашем случае будет использоваться упрощенная версия теста Миллера-Рабина. Если повторить тест n раз, он выдаст простое число с вероятностью ошибки не больше 1/4. Для проверки целого числа на простоту нужно:

Шаг 1. Устанавливаем i = 1 и выбираем n>=50.
Шаг 2. Приравниваем w тестируемому числу и представляем его в виде w = 1 + 2m, где m – нечетное число.
Шаг 3. Генерируем случайное число b: 1 < b < w. 
Шаг 4. Устанавливаем j = 0 и z = b mod w.
Шаг 5. Если j = 0 и z = 1, или если z = w - 1, то переходим на шаг 9. 
Шаг 6. Если j > 0 и z = 1, то переходим на шаг 8.
Шаг 7. j = j + 1. Если j < a, то устанавливаем z = z mod w и переходим на шаг 5.
Шаг 8. w не простое. Стоп.
Шаг 9. Если i < n, то устанавливаем i = i + 1 и переходим на шаг 3. Иначе, возможно w – простое число.

Генерация простых чисел

Для DSS нужны 2 простых числа p и q, которые должны удовлетворять следующим условиям:

2 < q < 2 
2 < p < 2, где L = 512 + 64j, причем 0 <= j < = 8 
p - 1 делится на q. 

Для генерации простого q: 2 < q < 2 используется SHA и начальное число SEED. После этого число SEED используется для создания числа X: 2 < X < 2. Простое p получается округлением X таким образом, чтобы полученное число было равно 1 mod 2q.

Пусть L — 1 = n*160 + b, где b и n целые и принимают значения от 0 до 160.

Шаг 1. Выбираем произвольную последовательность из как минимум 160 бит и называем ее SEED. Пусть g – длина SEED в битах.
Шаг 2. Вычисляем U = SHA XOR SHA.
Шаг 3. Создаем q из U устанавливая младший и старший бит равным 1:
       q = U OR 2 OR 1.
       Заметим, что 2 < q < 2. 
Шаг 4. Проверяем q на простоту. 
Шаг 5. Если q непростое, переходим на шаг 1. 
Шаг 6. Пусть counter = 0 и offset = 2. 
Шаг 7. Для k = 0,...,n вычисляем Vk = SHA.
Шаг 8. Вычисляем W = V0 + V1*2 + ... + Vn-1*2 + * 2 
       X = W + 2. 
       Заметим, что 0 < = W < 2  и 2 < = X < 2. 
Шаг 9. Пусть c = X mod 2q и p = X -. Заметим, что p равно 1 mod 2q. 
Шаг 10. Если p < 2, тогда переходим на шаг 13. 
Шаг 11. Проверяем p на простоту. 
Шаг 12. Если p прошло тест переходим на шаг 11, иначе на шаг 15. 
Шаг 13. counter = counter + 1 и offset = offset + n + 1. 
Шаг 14. Если counter >= 2 = 4096 переходим на шаг 1, иначе переходим на шаг 7. 
Шаг 15. Сохраняем SEED и counter для  того, чтобы подтвердить правильную генерацию p и q.