Цифровая подпись на основе алгоритмов с открытыми ключами. Схема Фиата-Шамира

Пусть h – некоторая хэш-функция, преобразующая исходное сообщение в битовую строку длины m.

Выберем различные простые числа p и q, положим n = pq.

В качестве секретного ключа каждый абонент должен сгенерировать m различных случайных чисел a₁,a₂,…a_mÎZ_n.

Открытым ключом объявляется набор чисел b₁,b₂,…b_mÎZ_n, где b_i=(a_i^-1)² mod n.

Алгоритм вычисления цифровой подписи

1. Выбрать случайное число , .

2. Вычислить .

3. Вычислить .

4. Вычислить

5. Подписью для сообщения М положить пару

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

Недостатки: большая длина ключа (определяется числом m).

Алгоритм проверки

1. По открытому ключу и значению вычислить

.

2. Вычислить .

3. Проверить равенство