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

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

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

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

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

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

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

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

Литература

• Goldwasser S., Micali S., Rivest R. L. // 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. // Theory of Cryptography Conference. — Springer, Berlin, Heidelberg, 2004. — С. 77-100 .

Ссылки

• (англ.)