WikiSort.ru - Не сортированное

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

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

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

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

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

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][5][6].

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

Подпись сообщения выполняется по следующему алгоритму^[2][5][6]:

1. Выбрать случайное число ${\displaystyle k\in \mathbb {Z} /Q\mathbb {Z} }$ и найти ${\displaystyle R=G^{k}(modP)}$ .
2. Найти ${\displaystyle E=f(M)\cdot R(modP)}$ .
3. Определить ${\displaystyle S=x\cdot E+k(modQ)}$ .

Подписью является пара ${\displaystyle (E,S)}$ .

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

Исходя из пары ${\displaystyle (E,S)}$ и целого числа по модулю ${\displaystyle Q}$ необходимо убедиться в том, что подпись принадлежит пользователю с открытым ключом ${\displaystyle Y}$ и восстановить сообщение ${\displaystyle M}$ . Проверка подписи выполняется по алгоритму:

1. Вычислить ${\displaystyle U_{1}=G^{S}\cdot Y^{-E}=G^{S-Ex}=G^{k}(modP)}$ .
2. Вычислить ${\displaystyle U_{2}={E \over U_{1}}(modP)}$ .

Теперь нужно убедиться в том, что ${\displaystyle U_{2}}$ является значением функции избыточности, то есть ${\displaystyle U_{2}=f(M)}$ . Если равенство не выполняется, то подпись ложная и отклоняется. В ином случае восстанавливается сообщение ${\displaystyle M=f^{-1}(U_{2})}$ и принимается подпись^[2][5][6].

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

Достоинства и недостатки схемы

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

Пример

Подпись сообщения^[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}$ .

См. также

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

Примечания

Литература

• Бауер Ф. Расшифрованные секреты. Методы и принципы криптологии. — Мир, 2007. — 550 с.
• Смарт, Н. Криптография. — Техносфера, 2005. — 528 с.
• Elgamal, T. A public key cryptosystem and a signature scheme based on discrete logarithms // Advances in Cryptology : книга. — 1985.
• 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.
• 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.