Реферат: Тест числа на простоту

Выбирается случайное число 1 < k < p − 1 взаимно простое с p-1 и вычисляется .

С помощью расширенного алгоритма Евклида вычисляется число s, удовлетворяющее сравнению:

Подписью сообщения M является пара (r,s).

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

Зная открытый ключ (p,g,y), подпись (r,s) сообщения M проверяется следующим образом:

Проверяется выполнимость условий: 0 < r < p и 0 < s < p − 1. Если хотя бы одно из них не выполняется, то подпись считается неверной.

Вычисляется дайджест m = h (M).

Подпись считается верной, если выполняется сравнение:

.

DSS (Digital Signature Standard) цифровой подпись

Алгоритм:

выбирается простое число q приблизительно в 160 бит (для этого используются генератор случайных чисел и тест на простату)

выбирается другое простое число р, сравнимое с 1 по модулю q размером приблизительно в 512 бит

выбирается порождающий элемент, для этого вычисляется для случайного целого g₀ , если g ≠1, то он и будет порождающим элементом

выбирается секретный ключ как случайное целое число х из диапазона 0<x<q. В качестве открытого ключа берется .

Пример. Пусть А хочет подписать сообщение. Сначала А принимает своему ОТ хеш функцию и получает целое число h из диапазона 0<h<q. Затем А выбирает случайное целое kиз того же диапазона и вычисляет . Пусть r- наименьший неотрицательный вычет по модулю qпоследнего выражение. Значит, g^k сначала вычисляется по модулю р, а результат приводиться по меньшему простому модулю q. Наконец, А находит такое целое s, что . Пара (r,s) вычетов по модулю q является ее подписью.

Чтобы проверить подпись, получатель В вычисляет и . Потом он вычисляет . Если результат сравним с r по модулю q, то подпись считается подлинной.

Литература

1. Дж. Андерсон, Дискретная математика и комбинаторика, М.: Вильямс - 2003.

2. Н. Коблиц, Курс теории чисел и криптографии, М.: научное изд-во ТВП, 2001.

3. http://ru. wikipedia.org