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

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

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

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

Предположим, что Алисе нужно отправить Бобу последовательность сообщений, подтверждённых цифровой подписью. Пусть Алиса предполагает подписать ${\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}$ выше)^[5].

В качестве односторонних функций могут быть использованы ${\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}$ в обратном порядке ^[6]. Функция ${\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)}$^[6].

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

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

• 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.

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

Криптосистемы с открытым ключом
Алгоритмы	Факторизация целых чисел Криптосистема Бенало Блюма — Гольдвассер Cayley–Purser Дамгорда — Юрика GMR Гольдвассер — Микали Накаша — Штерна Пэйе Рабина RSA Окамото — Утиямы Schmidt–Samoa Дискретное логарифмирование BLS Крамера – Шоупа Протокол Диффи — Хеллмана DSA ECDH Curve25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Обмен зашифрованными ключами Схема Эль-Гамаля signature scheme MQV Схема Шнорра SPEKE SRP STS Криптография на решётках NTRUEncrypt NTRUSign Обмен ключами на основе обучения с ошибками Подпись на основе обучения с ошибками в кольце BLISS NewHope Другие AE CEILIDH EPOC Скрытые уравнения поля IES Подпись Лэмпорта McEliece Ранцевая криптосистема Меркла — Хеллмана Naccache–Stern knapsack cryptosystem Трёхэтапный протокол XTR
Теория	Дискретное логарифмирование на эллиптической кривой Эллиптическая криптография Hash-based cryptography Некоммутативная криптография RSA problem Односторонняя функция с потайным входом
Стандарты	CRYPTREC IEEE P1363 NESSIE NSA Suite B Post-Quantum Cryptography
Темы	Электронная подпись OAEP Fingerprint PKI Web of trust Размер ключа Identity-based cryptography Постквантовая криптография OpenPGP card