GMR

Можно говорить, что криптоаналитик «взломал» цифровую подпись ${\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.

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