Схема Нюберг-Рюппеля. 
Криптографические методы защиты информации

Одним из нормативных документов, представляющих собой комплексное решение целого спектра задач в области криптографии с открытым ключом, является стандарт IEEE Р1363, разработанный американским институтом IEEE (Institute of Electrical and Electronics Engineers). Стандарт регламентирует несколько семейств криптографических схем, стойкость которых основывается на следующих трудноразрешимых математических задачах:

• • задаче разложения больших целых чисел на множители (задаче факторизации),
• • задаче вычисления дискретного логарифма в циклической подгруппе простого порядка мультипликативной группы простого поля F_;«
• • задаче дискретного логарифмирования в группе точек эллиптической кривой.

Одним из предлагаемых стандартом IEEE Р1363 решений в области электронной подписи является схема Нюберг-Рюппеля^[1], стойкость которой основывается на сложности решения задачи дискретного логарифмирования в группе точек эллиптической кривой. Данную схему принято обозначать ECNR.

Будем считать, что открытые параметры схемы и ключевая система аналогичны введенным нами ранее в разделах 11.2.1.1 и.

11.2.1.2.

Для выработки электронной подписи необходимо выполнить следующие шаги.

Алгоритм 11.7 (Алгоритм выработки подписи Нюберг-Рюппеля) Вход: Параметры алгоритма a, b, p, q, P, отображение Я, сообщение s. Выход: Цифровая подпись с под сообщением s.

1. Вычислить случайное число к е {1____.q — 1} и определить точку.

С = [к]Р.

• 2. Вычислить значение хэш-функции от сообщения *•, h = H (s), где h € F₉. Если выполнено равенство h = 0, то положить h равным 1.
• 3. Определить г = h + хс (mod q), где хс — ж-координата точки С.
• 4. Вычислить s = к — rd (mod q) и определить цифровую подпись

с=(Ф)-_?

Проверка корректности электронной подписи в схеме НюбергРюппеля основывается на равенстве точек эллиптической кривой.

и проверке выполнимости равенства г = h. + хс (mod q), где хс — ж-координата точки С, а величина к определяется равенством к = H (s).

Как видно из приведенного выше равенства точек эллиптической кривой, основным достоинством схемы Нюбсрг-Рюппеля является экономия операций в поле ?_р при проверке подписи и, как следствие, ускорение времени ее проверки. Это может являться важным в автоматизированных системах централизованной обработки электронной документации.

• [1] См. статью Kaisa Nyberg, Rainer Rueppel A New Signature Scheme Basedon the DSA Giving Message Recovery // 1st ACM Conference on Computer andCommunication Security. ACM Press. — 1993. — pp. 58 — 61.