Подпись Нюберг — Руэппеля

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

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

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

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

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

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)}$^[2][6][7].

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

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. Пользователь Алиса должна выполнить следующее:^[8]

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) пользователя Алиса и извлечь из подписи сообщение от Алисы. Пользователь Боб должен выполнить следующее:^[8]

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 )}$.

Подпись сообщения^[9]

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)}$ — это подпись.

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

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, подпись и восстановление не коммутируют, следовательно, алгоритм не может быть использован для шифрования. Преимущества восстановления сообщения заключаются в том, что применение схемы осуществляется без использования хеш-функций, более короткая подпись на коротких сообщениях, возможность прямого применения в схемах на основе идентификационной системы с открытым ключом, где пользователь после регистрации в центре ключей может аутентифицировать себя любому другому пользователю без дальнейшего обращения в центр ключей, или в протоколах согласования ключа, которые устанавливают общий ключ между двумя сторонами на основе взаимной аутентификации^[2][10][11].

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

Модифицированная подпись Нюберга-Руэппеля заменяет функцию избыточности дискретным возведением в степень. Более явно, пусть ${\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)}$^[13].

Модифицированная версия схемы подписи при заданном 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}}$, подпись вычисляется следующим образом^[14]:

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. A public key cryptosystem and a signature scheme based on discrete logarithms // 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. Message Recovery for Signature Schemes Based on the Discrete Logarithm Problem // Designs, Codes and Cryptography : журнал. — 1996. — № Volume 7, Issue 1-2. — С. 61—81.