2.6. Криптографическая подпись Фиат-Шамира

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

(2.78)

В качестве секретного ключа каждый абонент должен сгенерировать различных случайных чисел а в качестве открытого ключа значения:

(2.79)

Тогда алгоритм вычисления криптографической подписи для сообщения будет состоять в следующем.

1). Выбираем случайное число , . Например, полагая значения имеем и можем выбрать

2). Вычисляем значение: . Для нашего примера это

3). Вычисляем хеш-функцию для сообщения вида . Значение используем как первый элемент подписи.

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

(2.80)

Тогда, значение сигнатуры, определим с помощью функций счета:

(2.81)

4). Выбираем ряд случайных чисел больших нуля и находим второй элемент подписи по формуле:

. (2.82)

Для нашего примера это число . Открытый ключ (2.79) при заданных будет равен .

Итак, криптографической подписью для сообщения следует считать пару чисел

Алгоритм проверки подписи состоит в выполнении следующих действий.

1). По открытому ключу и значению определяется параметр:

, (2.83)

который при и будет равен:

2). Определяется значение хеш-функции :

(2.84)

3). Сравнивается, переданное по информационному каналу и расчетное значение . Совпадение кодов свидетельствует о достоверности передачи данных.