GMR

GMR — криптографический алгоритм, используемый для создания цифровой подписи. Назван по первым буквам создателей — Рональда Ривеста, Сильвио Микали и Шафи Гольдвассер.

GMR базируется на высокой вычислительной сложности факторизации больших целых чисел, как и криптосистема RSA. Но, в отличие от неё, GMR устойчива к атакам на основе подобранного открытого текста .

Что значит взломать цифровую подпись?

Можно говорить, что криптоаналитик «взломал» цифровую подпись [math]\displaystyle{ A }[/math], если совершенная атака позволяет ему с ненулевой вероятностью совершить следующее:

• Полный взлом (total break): вычислить закрытый ключ [math]\displaystyle{ A }[/math]
• Универсальная подделка (universal forgery): найти эффективный алгоритм, эквивалентный алгоритму цифровой подписи [math]\displaystyle{ A }[/math] (используется, вообще говоря, другой, но эквивалентный секретный ключ)
• Выборочная подделка (selective forgery): подделать подпись некоторого сообщения, выбранного криптоаналитиком априори
• Экзистенциальная подделка (existential forgery): подделать подпись хотя бы одного сообщения. При этом криптоаналитик не выбирает сообщение для подделки подписи, подделка может быть случайной и лишённой смысла. Подделка такого типа может нести минимальный урон для [math]\displaystyle{ A }[/math]. Авторами схемы GMR доказана ее устойчивость именно к такому типу атаки.

Описание алгоритма

Предположим, что Алисе нужно отправить Бобу последовательность сообщений, подтверждённых цифровой подписью. Пусть Алиса предполагает подписать [math]\displaystyle{ 2^b }[/math] сообщений, случайный параметр шифрования - [math]\displaystyle{ k }[/math]. Открытый ключ состоит из следующих компонент:

Максимальное число сообщений, которые необходимо зашифровать [math]\displaystyle{ B=2^b, b \in \mathbb{N} \cup \left\lbrace 0 \right\rbrace }[/math] Два случайно выбранных числа Блума [math]\displaystyle{ n_1=p_1q_1 }[/math] и [math]\displaystyle{ n_2=p_2q_2 }[/math], то есть два числа, являющихся произведением простых чисел, сравнимых с числом [math]\displaystyle{ 3 }[/math] по модулю [math]\displaystyle{ 4 }[/math] Два бесконечных семейства односторонних функций с потайным входом [math]\displaystyle{ f_{i, n}\left(x\right) }[/math] Случайное число [math]\displaystyle{ r }[/math], выбранное из области значений [math]\displaystyle{ f_{i, n_1}\left(\cdot\right) }[/math]

.

Закрытый ключ состоит из простых чисел [math]\displaystyle{ p_1, q_1, p_2, q_2 }[/math], позволяющих эффективно вычислять обратные функции [math]\displaystyle{ f^{-1}_{i, n_1}\left(y\right) }[/math] и [math]\displaystyle{ f^{-1}_{i, n_2}\left(y\right) }[/math].

Рассмотрим случай генерации подписи для одного сообщения [math]\displaystyle{ m }[/math], то есть [math]\displaystyle{ B=1 }[/math] и [math]\displaystyle{ b=0 }[/math]. Алиса выбирает случайное число [math]\displaystyle{ r_0 }[/math] из области значений [math]\displaystyle{ f_{i, n_1}\left(\cdot\right) }[/math] и вычисляет подпись сообщения [math]\displaystyle{ \left(t, r_0, s\right) }[/math]:

[math]\displaystyle{ t=f^{-1}_{r_0, n_1}\left(r\right) }[/math] и [math]\displaystyle{ s=f^{-1}_{m, n_2}\left(r_0\right) }[/math].

Получив подписанное сообщение, Боб последовательно проверяет, что

• [math]\displaystyle{ f_{m, n_2}\left(s\right)=r_0 }[/math]

• [math]\displaystyle{ f_{r_0, n_1}\left(t\right)=r }[/math].

Для подписи [math]\displaystyle{ B=2^b \gt 1 }[/math] сообщений Алиса строит из корневого элемента [math]\displaystyle{ r }[/math] хэш-дерево с [math]\displaystyle{ B }[/math] листьями [math]\displaystyle{ r_0, r_1, \dots, r_{B-1} }[/math]. Все внутренние вершины дерева выбираются случайно и равновероятно из множества значений [math]\displaystyle{ f_{i, n_1}\left(\cdot\right) }[/math], аналогично [math]\displaystyle{ r_0 }[/math] в случае одного сообщения. Каждая внутренняя вершина [math]\displaystyle{ R }[/math] криптостойко связывается со обоими своими дочерними вершинами путём вычисления значения [math]\displaystyle{ f_{R_0 \parallel R_1, n_1}\left(R\right) }[/math], помещаемого в вершину аналогично тому, как выше вычисляется [math]\displaystyle{ t }[/math]. Наконец, сообщение [math]\displaystyle{ m_j \left(0 \leqslant j \leqslant B - 1\right) }[/math] криптостойко связывается с [math]\displaystyle{ j }[/math]-ым листом дерева аутентификации [math]\displaystyle{ r_j }[/math] путём вычисления значения [math]\displaystyle{ s_j = f^{-1}_{m_j, n_2}\left(r_j\right) }[/math] аналогично тому, как выше вычислено [math]\displaystyle{ s }[/math]. Подпись сообщения [math]\displaystyle{ m_j }[/math] состоит из

• Последовательности [math]\displaystyle{ b }[/math] вершин дерева от корня [math]\displaystyle{ r }[/math] до листа [math]\displaystyle{ r_j }[/math]
• [math]\displaystyle{ b }[/math] значений, помещённых в вершины (аналогично [math]\displaystyle{ t }[/math] выше)
• [math]\displaystyle{ s_j }[/math] (аналогично [math]\displaystyle{ s }[/math] выше).

Односторонние функции с потайным входом

В качестве односторонних функций могут быть использованы [math]\displaystyle{ f_{i, n}\left(x\right) = \pm 4^{\text{rev}\left(i\right)}x^{2^{\text{len}\left(i\right)}}\mod{n} }[/math] для [math]\displaystyle{ n=n_1 }[/math] и [math]\displaystyle{ n=n_2 }[/math], где функция [math]\displaystyle{ \text{rev}\left(\cdot\right) }[/math] принимает на вход битовую строку [math]\displaystyle{ i \in \left\lbrace 0,1\right\rbrace^+ }[/math] и возвращает целое число, представленное битами [math]\displaystyle{ i }[/math] в обратном порядке . Функция [math]\displaystyle{ \text{len}\left(\cdot\right) }[/math] также принимает битовую строку [math]\displaystyle{ i \in \left\lbrace 0,1\right\rbrace^+, }[/math] возвращая её длину. Знак плюс или минус выбирается таким образом, чтобы значение [math]\displaystyle{ f_{i, n} }[/math] было положительно и не превышало [math]\displaystyle{ n/2 }[/math]. В таком случае вычисление обратной функции осуществляется за время, пропорциональное [math]\displaystyle{ k^3 }[/math], где [math]\displaystyle{ k }[/math] — длина строки [math]\displaystyle{ i }[/math], при условии, что подписываемые сообщения имеют такую же длину. Таким образом образом, подпись [math]\displaystyle{ k }[/math]-битового сообщения может быть подсчитана за время [math]\displaystyle{ O\left(bk^3\right) }[/math].

Криптостойкость алгоритма

Гольдвассер, Микали и Ривестом доказано, что алгоритм GMR не позволяет криптоаналитику успешно совершить адаптивную атаку на основе подобранного сообщения, а именно, осуществить экзистенциальную подделку подписи, сгенерированной по схеме GMR. Криптоаналитик, получивший подписи к ряду сообщений, не может подделать подпись для любого дополнительного сообщения.

Обобщения схемы

Возможны обобщения схемы GMR для использования как подписи назначенного подтверждающего (designated confirmer signature scheme).

Литература

• Goldwasser S., Micali S., Rivest R. L. A digital signature scheme secure against adaptive chosen-message attacks // SIAM Journal on Computing. — 1988. — Т. 61, № 3. — С. 281—308.
• Van Tilborg H. C. A., Jajodia S. Encyclopedia of cryptography and security. — Springer Science & Business Media, 2014.
• Goldwasser S., Waisbard E. Transformation of digital signature schemes into designated confirmer signature schemes // Theory of Cryptography Conference. — Springer, Berlin, Heidelberg, 2004. — С. 77-100.

Ссылки

• Схемы цифровой подписи (англ.)