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

02.02.2021

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

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

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

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

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

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

  • Секретный ключ представляет собой число x ∈ ( 0 , Q ) {displaystyle xin (0,Q)}
  • Открытый ключ вычисляется по формуле Y = G x mod p {displaystyle Y=G^{x}mod p}
  • Открытыми параметрами являются ( P , Q , G , Y ) {displaystyle (P,Q,G,Y)} . Закрытый параметр — x {displaystyle x} . Ключевая пара ( Y , x ) {displaystyle (Y,x)} .

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

    Подпись сообщения выполняется по следующему алгоритму:

  • Выбрать случайное число k ∈ Z / Q Z {displaystyle kin mathbb {Z} /Qmathbb {Z} } и найти R = G k ( m o d P ) {displaystyle R=G^{k}(modP)} .
  • Найти E = f ( M ) ⋅ R ( m o d P ) {displaystyle E=f(M)cdot R(modP)} .
  • Определить S = x ⋅ E + k ( m o d Q ) {displaystyle S=xcdot E+k(modQ)} .
  • Подписью является пара ( E , S ) {displaystyle (E,S)} .

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

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

  • Вычислить U 1 = G S ⋅ Y − E = G S − E x = G k ( m o d P ) {displaystyle U_{1}=G^{S}cdot Y^{-E}=G^{S-Ex}=G^{k}(modP)} .
  • Вычислить U 2 = E U 1 ( m o d P ) {displaystyle U_{2}={E over U_{1}}(modP)} .
  • Теперь нужно убедиться в том, что U 2 {displaystyle U_{2}} является значением функции избыточности, то есть U 2 = f ( M ) {displaystyle U_{2}=f(M)} . Если равенство не выполняется, то подпись ложная и отклоняется. В ином случае восстанавливается сообщение M = f − 1 ( U 2 ) {displaystyle M=f^{-1}(U_{2})} и принимается подпись.

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

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

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

    Пример

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

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

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