GMR (GMR)

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

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

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

Можно говорить, что криптоаналитик «взломал» цифровую подпись $A$, если совершенная атака позволяет ему с ненулевой вероятностью совершить следующее:

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

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

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

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

.

Закрытый ключ состоит из простых чисел $p_{1},q_{1},p_{2},q_{2}$, позволяющих эффективно вычислять обратные функции $f_{i,n_{1}}^{-1}\left(y\right)$ и $f_{i,n_{2}}^{-1}\left(y\right)$.

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

$t=f_{r_{0},n_{1}}^{-1}\left(r\right)$ и $s=f_{m,n_{2}}^{-1}\left(r_{0}\right)$.

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

• $f_{m,n_{2}}\left(s\right)=r_{0}$

• $f_{r_{0},n_{1}}\left(t\right)=r$.

Для подписи $B=2^{b}>1$ сообщений Алиса строит из корневого элемента $r$ хэш-дерево с $B$ листьями $r_{0},r_{1},\dots ,r_{B-1}$. Все внутренние вершины дерева выбираются случайно и равновероятно из множества значений $f_{i,n_{1}}\left(\cdot \right)$, аналогично $r_{0}$ в случае одного сообщения. Каждая внутренняя вершина $R$ криптостойко связывается со обоими своими дочерними вершинами путём вычисления значения $f_{R_{0}\parallel R_{1},n_{1}}\left(R\right)$, помещаемого в вершину аналогично тому, как выше вычисляется $t$. Наконец, сообщение $m_{j}\left(0\leqslant j\leqslant B-1\right)$ криптостойко связывается с $j$-ым листом дерева аутентификации $r_{j}$ путём вычисления значения $s_{j}=f_{m_{j},n_{2}}^{-1}\left(r_{j}\right)$ аналогично тому, как выше вычислено $s$. Подпись сообщения $m_{j}$ состоит из

• Последовательности $b$ вершин дерева от корня $r$ до листа $r_{j}$
• $b$ значений, помещённых в вершины (аналогично $t$ выше)
• $s_{j}$ (аналогично $s$ выше).

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

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

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

Гольдвассер, Микали и Ривестом доказано, что алгоритм 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.

Ссылки

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