GMR

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

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

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

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

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

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

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

• Максимальное число сообщений, которые необходимо зашифровать $B=2^b,b\in \mathbb{N}\cup \left\{0\right\}$
• Два случайно выбранных числа Блума $n_1=p_1{q}_1$ и $n_2=p_2{q}_2$, то есть два числа, являющихся произведением простых чисел, сравнимых с числом $3$ по модулю $4$ Шаблон:Sfn
• Два бесконечных семейства односторонних функций с потайным входом $f_{i,n}\left(x\right)$
• Случайное число $r$, выбранное из области значений $f_{i,n_1}(\cdot )$

Шаблон:Col-end.

Закрытый ключ состоит из простых чисел $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}(\cdot )$ и вычисляет подпись сообщения $(t,r_0,s)$:

$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}(\cdot )$, аналогично $r_0$ в случае одного сообщения. Каждая внутренняя вершина $R$ криптостойко связывается со обоими своими дочерними вершинами путём вычисления значения $f_{R_0\parallel R_1,n_1}\left(R\right)$, помещаемого в вершину аналогично тому, как выше вычисляется $t$. Наконец, сообщение $m_j(0⩽j⩽B-1)$ криптостойко связывается с $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$ выше)Шаблон:Sfn.

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

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

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

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

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

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

Литература

• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья

Ссылки

• Схемы цифровой подписиШаблон:Ref-en