Подпись Нюберг — Руэппеля ( англ. Nyberg-Rueppel Signature Scheme ) — схема электронной подписи с использованием открытого ключа , основанная на задаче дискретного логарифмирования в конечном поле . Алгоритм не может использоваться для шифрования (в отличие от RSA и схемы Эль-Гамаля ). Подпись создается секретно, но может быть публично проверена. Это значит, что только один может создать подпись сообщения, но любой может проверить её . Схема была предложена (англ.) ( и Райнером Руэппелем в 1993 году на первой конференции ACM ( англ. 1st ACM conference on Computer and communications security ) как модификация DSA .

История

В 1993 году Кайса Нюберг и Райнер Руэппель представили новую схему подписи, основанную на тех же принципах, что и DSA. Основное отличие заключается в том, что новая схема обеспечивает восстановление сообщений. Но в отличие от RSA, преобразования подписи и восстановления не коммутируют. Следовательно, новая схема не может быть использована для шифрования. Преимуществами восстановления сообщений являются: приложения без хэш-функции, меньшая пропускная способность для подписей небольших сообщений, прямое использование в других схемах, таких как системы открытого ключа на основе идентификации или протоколы согласования ключей .

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

Использование алгоритма

Схема подписи с восстановлением сообщения подразумевает собой процедуру, когда сообщение восстанавливается после проверки подписи. Иными словами, пусть имеются два пользователя, Алиса и Боб, и незащищенный канал связи между ними. Пользователь Алиса подписывает открытое сообщение секретным ключом , а полученную подпись пересылает пользователю Бобу, который в свою очередь с помощью открытого ключа проверяет подлинность подписи и восстанавливает сообщение. При положительном результате проверки, Боб убеждается в целостности сообщения, в его оригинальности (то есть в том, что сообщение было послано именно пользователем Алисой), а также лишается возможности утверждать, что Алиса не посылала это сообщение. Важно, что только Алиса способна подписать своё сообщение, потому что только она знает свой секретный ключ , и то, что её подпись может быть проверена любым пользователем, так как для этого нужен лишь открытый ключ .

Параметры схемы цифровой подписи

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

1. Выбрать открытую функцию избыточности ${\displaystyle f}$ , которая преобразует фактическое сообщение в данные, которые затем подписываются. Это похоже на хеш-функцию в схемах подписи с приложением, но в отличие от них, функция избыточности должны быть легко обратима.
2. Выбрать большое простое число ${\displaystyle Q}$ .
3. Выбрать большое простое число ${\displaystyle P}$ , такое, что ${\displaystyle (P-1)}$ делится на ${\displaystyle Q}$ .
4. Сгенерировать случайное число ${\displaystyle H<P}$ и вычислить ${\displaystyle G=H^{(P-1)/Q}\mod P}$ . Если ${\displaystyle G=1}$ , то искать другое случайное ${\displaystyle H}$ , пока ${\displaystyle G}$ будет не равным ${\displaystyle 1}$ , что обеспечит выполнение условия ${\displaystyle G^{Q}=1\mod P}$

Открытый и секретный ключи

1. Секретный ключ представляет собой число ${\displaystyle x\in (0,Q)}$
2. Открытый ключ вычисляется по формуле ${\displaystyle Y=G^{x}\mod p}$

Открытыми параметрами являются ${\displaystyle (P,Q,G,Y)}$ . Закрытый параметр — ${\displaystyle x}$ . Ключевая пара ${\displaystyle (Y,x)}$ .

Вычисление ключей

Каждый пользователь создает свой открытый ключ и ему соответствующий секретный ключ. Каждый пользователь должен выполнить следующее:

1. Выбрать простые числа ${\displaystyle P}$ и ${\displaystyle Q}$ , для которых ${\displaystyle Q}$ делит ${\displaystyle P-1}$ .
2. Выбрать генератора ${\displaystyle G\in \mathrm {Z} _{p}^{*}}$ для циклической подгруппы порядка ${\displaystyle Q}$ в группе.

Для этого пользователь должен выполнить следующее:

1. Выбрать элемент ${\displaystyle {\displaystyle H\in \mathrm {Z} _{p}^{*}}}$ , и найти ${\displaystyle G=H^{(p-1)/q}{\pmod {p}}}$ .
2. Если ${\displaystyle G=1}$ , то перейти к шагу 1 с другим ${\displaystyle H}$ .

Продолжить действия в соответствии с шагами:

1. Выбрать произвольное число ${\displaystyle H}$ , ${\displaystyle 1\leq G\leq Q-1}$
2. Вычислить ${\displaystyle Y=G^{Q}{\pmod {p}}}$
3. Открытый ключ адресата есть ( Р, Q, G, Y ). Секретный ключ пользователя есть число H .

Вычисление подписи

Пользуясь своим секретным ключом, пользователь Алиса подписывает бинарное сообщение m. Пользователь Алиса должна выполнить следующее:

1. Вычислить ${\displaystyle m=R(m)}$ .
2. Выбрать случайное секретное целое ${\displaystyle k}$ , ${\displaystyle 1\leq k\leq Q-1}$ и вычислить ${\displaystyle r=G-k{\pmod {p}}}$
3. Вычислить ${\displaystyle e=m\prime r{\pmod {p}}}$ .
4. Вычислить ${\displaystyle s=ae+k{\pmod {Q}}}$ .
5. Подпись А под ${\displaystyle m}$ есть пара ( ${\displaystyle e}$ , ${\displaystyle s}$ ) .

Проверка подписи и вычисление сообщения

Пользуясь открытым ключом пользователя Алиса, адресат Боб может проверить подпись (e, s) пользователя Алиса и извлечь из подписи сообщение от Алисы. Пользователь Боб должен выполнить следующее:

1. Получить открытый ключ ( Р, Q, G, Y ) пользователя Алиса.
2. Проверить, что ${\displaystyle e\in [1,P-1]}$ . Если нет, то отклонить подпись.
3. Проверить, что ${\displaystyle {\displaystyle s\in [1,Q-1]}}$ . Если нет, то отклонить подпись.
4. Вычислить ${\displaystyle v=G^{s}*Y^{-e}{\pmod {P}}}$ и ${\displaystyle m\prime =Ve{\pmod {P}}}$ .
5. Проверить, что ${\displaystyle m\prime \in M_{R}}$ . Если нет, то отклонить подпись.
6. Вычислить ${\displaystyle m=R^{-1}(m\prime )}$ .

Схема алгоритма

Пример

Подпись сообщения

1. Выберем параметры схемы: ${\displaystyle Q=101,P=607,G=601.}$
2. Ключевая пара пусть выглядит как ${\displaystyle (391,3)}$ .
3. Чтобы подписать сообщение ${\displaystyle M=12}$ , вычисляем временный ключ ${\displaystyle k=45}$ и ${\displaystyle R=G^{k}(modP)=143}$ .
4. Пусть ${\displaystyle f(M)=M+2^{4}\cdot M}$ , тогда ${\displaystyle f(M)=204}$ и

${\displaystyle E=f(M)\cdot R(modP)=36}$ , ${\displaystyle S=x\cdot E+k(modQ)=52}$ .

Итого, пара чисел ${\displaystyle (E,S)}$ , то есть ${\displaystyle (36,52)}$ — это подпись.

Проверка подписи и восстановление сообщения

1. Вычисляем ${\displaystyle U_{1}=G^{S}\cdot Y^{-E}=143}$ . Следует заметить, что значение ${\displaystyle U_{1}}$ совпадает со значением ${\displaystyle R}$ .
2. Вычисляем ${\displaystyle U_{2}={E \over U_{1}}(modP)=204}$ .
3. Теперь нужно проверить, что ${\displaystyle U_{2}=204}$ представляется в виде ${\displaystyle M+2^{4}\cdot M}$ для некоторого целого числа ${\displaystyle M}$ , и убедившись в этом, делаем заключение в корректности подписи.
4. Восстанавливаем сообщение ${\displaystyle M=12}$ как решение уравнения ${\displaystyle M+2^{4}\cdot M=204}$ .

Достоинства и недостатки

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

Модифицированная подпись Нюберга-Руэппеля

Модификация сигнатуры Нюберга-Руэппеля позволяет избежать трудностей проектирования функции избыточности за счет отказа от свойства восстановления сообщений. Её производительность немного хуже, чем у Elgamal, который аналогично не обеспечивает восстановление сообщений, но более эффективен, чем двойные подписи Нюберга-Руэппеля, которые доказуемо безопасны в той же модели. Хотя двойная подпись Нюберга-Руэппеля действительно обеспечивает восстановление сообщений, для этого по-прежнему требуется передача четырёх значений подписи, в то время как для модифицированной версии подписи требуется только три значения (включая сообщение). Поскольку смысл восстановления сообщений заключается в экономии полосы пропускания, эта схема достигает цели с помощью других средств .

Модифицированная подпись Нюберга-Руэппеля заменяет функцию избыточности дискретным возведением в степень. Более явно, пусть ${\displaystyle g1}$ — другой генератор той же группы порядка ${\displaystyle q}$ , такой, что дискретные логарифмы ${\displaystyle g1}$ по отношению как к ${\displaystyle g}$ , так и к y неизвестны. Пространство сообщений ${\displaystyle M_{S}}$ − это целочисленный интервал ${\displaystyle I}$ , то есть равный ${\displaystyle [1,q-1]}$ в случае известного порядка или ${\displaystyle [-2^{n},2^{n}-1]}$ в случае неизвестного порядка. Если ( ${\displaystyle r}$ , ${\displaystyle s}$ ) является подписью в сообщении ${\displaystyle m}$ , модифицированное уравнение проверки выглядит следующим образом:

${\displaystyle g_{1}^{m}=ry^{p(r)}g^{s}}$

Процедура подписания работает как и прежде, поскольку сообщение m в I сначала изменяется на ${\displaystyle m'=g_{1}^{m}}$ как сообщение в ${\displaystyle G}$ , а затем подписывается, как в предыдущем алгоритме.

Безопасность

В своей простой форме подпись Нюберга-Руэппеля уязвима для атак экзистенциальной подделки. А именно, можно произвольно выбрать ${\displaystyle r\in [1,p-1]}$ и ${\displaystyle s\in [1,q-1]}$ , и эти значения подписывают уникальное сообщение, которое получается путем применения алгоритма восстановления к ( ${\displaystyle r}$ , ${\displaystyle s}$ ) . Хотя это сообщение не может быть выбрано злоумышленником заранее, это все равно означает, что схема подписи небезопасна.

Типичным решением проблемы такого типа является использование функции резервирования. Пусть ${\displaystyle R}$ — эффективно вычислимая взаимно однозначная функция от { ${\displaystyle {0,1}}$ } до ${\displaystyle [1,p-1]}$ , которая является разреженной, то есть набор изображений R соответствует небольшой доле всех значений в диапазоне. При заданном ${\displaystyle Z}$ в изображении ${\displaystyle R}$ существует эффективный алгоритм вычисления ${\displaystyle R-1(Z)}$ .

Модифицированная версия схемы подписи при заданном m вычисляет ${\displaystyle m\prime =R(m)}$ , а затем подписывает m' в соответствии с простой схемой Нюберга-Руэппеля. Чтобы восстановить подписанное сообщение, верификатор сначала восстанавливает ${\displaystyle m\prime }$ в соответствии с механизмом восстановления простой подписи Нюберга-Руэппеля, а затем фактическое сообщение ${\displaystyle m}$ как ${\displaystyle R-1(m\prime )}$ . Безопасность модифицированной версии зависит от сложности выбора значений ${\displaystyle r}$ и ${\displaystyle s}$ таким образом, чтобы выходные данные алгоритма восстановления были в виде ${\displaystyle R}$ . На практике разработка функций резервирования, обеспечивающих надлежащую безопасность, является деликатной задачей.

Кольцевая подпись версии Нюберга-Руэппеля

Для подписи сообщения ${\displaystyle m}$ при наличии секретного ключа ${\displaystyle S_{S}}$ , и открытых ключах всех участников кольца — ${\displaystyle P_{1},P_{2},...,P_{r}}$ , подпись вычисляется следующим образом :

1. Вычислить ${\displaystyle h(m)}$ как симметричный ключ ${\displaystyle k}$ : ${\displaystyle k=h(m)}$ .
2. Выбрать значение инициализации ${\displaystyle v}$ равномерно случайным образом из ${\displaystyle {(0,1)}^{b}}$ .
3. Выбирать случайное ( ${\displaystyle e_{i},y_{i}}$ ) равномерно и независимо от ${\displaystyle Z_{p}*Z_{q}(1\leq i\leq r,i\neq s)}$ и вычислить: ${\displaystyle x_{i}=f_{i}(e_{i},y_{i})}$ .
4. Решить следующее кольцевое уравнение для ${\displaystyle x_{s}}$ : ${\displaystyle C_{k,v}(x_{1},x_{2},...,x_{r})=v.}$
5. Использовать секретный ключ ${\displaystyle S_{i}}$ , чтобы инвертировать ${\displaystyle f_{s}}$ на ${\displaystyle x_{s}}$ для получения ( ${\displaystyle e_{s},y_{s}}$ ) .
6. Подпись в сообщении m определяется как ${\displaystyle (2r+1)}$ -запись: ${\displaystyle (P_{1},P_{2},...,P_{r};v;(e_{1},y_{1}),...,(e_{r},y_{r}))}$ .
7. Проверить подпись ${\displaystyle (P_{1},P_{2},...,P_{r};v;(e_{1},y_{1}),...,(e_{r},y_{r}))}$ .
8. В сообщении ${\displaystyle m}$ подпись будет принята верификатором тогда и только тогда, когда ${\displaystyle C_{H(m)},v(f_{1}(e_{1},y_{1}),f_{2}(e_{2},y_{2}),...,f_{r}(e_{r},y_{r}))=v}$ .

См. также

• Электронная цифровая подпись
• Схема Эль-Гамаля
• RSA
• DSA
• ECDSA
• ГОСТ Р 34.10-2001
• Случайное простое число

Примечания

Литература

• Авдошин С. М. Дискретная математика. Модулярная алгебра, криптография, кодирование. — М. : ДМК Пресс, 2017. — 352 с.
• Бауер Ф. Расшифрованные секреты. Методы и принципы криптологии. — Мир, 2007. — 550 с.
• Смарт, Н. Криптография. — Техносфера, 2005. — 528 с.
• Ateniese, G and Breno de Medeiros. «A Provably Secure Nyberg-Rueppel Signature Variant with Applications.» IACR Cryptol. ePrint Arch. 2004 (2004): 93.
• Elgamal, T. // Advances in Cryptology : книга. — 1985.
• Gao, Cz., Yao, Za., Li, L. (2003). A Ring Signature Scheme Based on the Nyberg-Rueppel Signature Scheme. In: Zhou, J., Yung, M., Han, Y. (eds) Applied Cryptography and Network Security. ACNS 2003. Lecture Notes in Computer Science, vol 2846. Springer, Berlin, Heidelberg.
• Nyberg, K., Rueppel, R. A. A new signature scheme based on the DSA giving message recovery // 1st ACM Conference on Computer and Communications Security, Fairfax, Virginia (Nov. 3–5, 1993). — 1993.
• Nyberg, K., Rueppel, R. A. // Designs, Codes and Cryptography : журнал. — 1996. — № Volume 7, Issue 1-2 . — С. 61—81 .