Анализ слепых цифровых подписей на основе дискретного логарифмирования Фаль Алексей Михайлович, ведущий научный сотрудник Институт кибернетики им. В.М. Глушкова НАН Украины

В 1994 г. в работе [1] были предложены два алгоритма слепой подписи, использующие проблему нахождения дискретных логарифмов. Первый из них в качестве основной схемы цифровой подписи использовал схему, фактически равнозначную схеме российского стандарта Р Второй алгоритм в качестве основной схемы использовал цифровую подпись, предложенную в [2] Nyberg и Rueppel.

Для полноты приведем алгоритм, предложенный в работе [1]. Напомним, что общесистемными параметрами является простое число, делитель, также являющийся простым числом и элемент порядка. Секретным ключом подписывающего является случайный элемент, а соответствующим открытым ключом есть.

Протокол создания слепой подписи сообщения состоит в следующем. 1.а) Подписывающий выбирает случайное и вычисляет б)Подписывающий проверяет условие. В случае неудачи возвращается к а). В противном случае, он отсылает заказчику.

2.а) Заказчик проверяет, что б) Заказчик выбирает случайные и вычисляет в) Заказчик проверяет, что. Если неудача, то возвращается к б). В противном случае, он вычисляет и отсылает подписывающему

3. Подписывающий вычисляет и отправляет заказчику. 4. Заказчик вычисляет и.

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

Перенесем данный алгоритм на случай эллиптических кривых, изложенный в стандарте Р Изложим алгоритм этого стандарта в виде, в котором он представлен в ISO/IEC :2006, Amedment 1.

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

Генерирование секретного и открытого ключей Секретным ключом является случайно сгенерированное число,. Соответствующим открытым ключом является точка.

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

Процесс проверки подписи Вычисляют Подпись верна, если

Протокол создания слепой подписи, соответствующий стандарту Р Подписывающий выбирает случайное и вычисляет и отсылает заказчику. 2. Заказчик выбирает случайные и вычисляет. Далее вычисляется и и. отсылается подписывающему. 3. Подписывающий вычисляет и отправляет заказчику. 4. Заказчик вычисляет. Подписью является пара чисел

Процесс проверки подписи Вычисляем Подпись верна, если совпадает с.

Литература 1.J.A. Camenish, J-M Piveteau, M.A. StadlerBlind Signatures Based on the Discrete Logarithm Problem // Eurocrypt – K.Nyberg, R.A. Rueppel. A New Signature Scheme Based on the DSA Giving Message Recovery // 1 st ACM conf. on computer and commun. security