Русская Википедия:GMR
GMR — криптографический алгоритм, используемый для создания цифровой подписи. Назван по первым буквам создателей — Рональда Ривеста, Сильвио Микали и Шафи Гольдвассер.
GMR базируется на высокой вычислительной сложности факторизации больших целых чисел, как и криптосистема RSA. Но, в отличие от неё, GMR устойчива к атакам на основе подобранного открытого текста Шаблон:Sfn.
Что значит взломать цифровую подпись?
Можно говорить, что криптоаналитик «взломал» цифровую подпись <math>A</math>, если совершенная атака позволяет ему с ненулевой вероятностью совершить следующееШаблон:Sfn:
- Полный взлом (total break): вычислить закрытый ключ <math>A</math>
- Универсальная подделка (universal forgery): найти эффективный алгоритм, эквивалентный алгоритму цифровой подписи <math>A</math> (используется, вообще говоря, другой, но эквивалентный секретный ключ)
- Выборочная подделка (selective forgery): подделать подпись некоторого сообщения, выбранного криптоаналитиком априори
- Экзистенциальная подделка (existential forgery): подделать подпись хотя бы одного сообщения. При этом криптоаналитик не выбирает сообщение для подделки подписи, подделка может быть случайной и лишённой смысла. Подделка такого типа может нести минимальный урон для <math>A</math>. Авторами схемы GMR доказана ее устойчивость именно к такому типу атакиШаблон:Sfn.
Описание алгоритма
Предположим, что Алисе нужно отправить Бобу последовательность сообщений, подтверждённых цифровой подписью. Пусть Алиса предполагает подписать <math>2^b</math> сообщений, случайный параметр шифрования - <math>k</math>. Открытый ключ состоит из следующих компонент: Шаблон:Col-begin Шаблон:Col-2
- Максимальное число сообщений, которые необходимо зашифровать <math>B=2^b, b \in \mathbb{N} \cup \left\lbrace 0 \right\rbrace </math>
- Два случайно выбранных числа Блума <math>n_1=p_1q_1</math> и <math>n_2=p_2q_2</math>, то есть два числа, являющихся произведением простых чисел, сравнимых с числом <math>3</math> по модулю <math>4</math> Шаблон:Sfn
- Два бесконечных семейства односторонних функций с потайным входом <math>f_{i, n}\left(x\right)</math>
- Случайное число <math>r</math>, выбранное из области значений <math>f_{i, n_1}\left(\cdot\right)</math>
Закрытый ключ состоит из простых чисел <math>p_1, q_1, p_2, q_2</math>, позволяющих эффективно вычислять обратные функции <math>f^{-1}_{i, n_1}\left(y\right)</math> и <math>f^{-1}_{i, n_2}\left(y\right)</math>.
Рассмотрим случай генерации подписи для одного сообщения <math>m</math>, то есть <math>B=1</math> и <math>b=0</math>. Алиса выбирает случайное число <math>r_0</math> из области значений <math>f_{i, n_1}\left(\cdot\right)</math> и вычисляет подпись сообщения <math>\left(t, r_0, s\right)</math>:
- <math>t=f^{-1}_{r_0, n_1}\left(r\right)</math> и <math>s=f^{-1}_{m, n_2}\left(r_0\right)</math>.
Получив подписанное сообщение, Боб последовательно проверяет, что
- <math>f_{m, n_2}\left(s\right)=r_0</math>
- <math>f_{r_0, n_1}\left(t\right)=r</math>.
Для подписи <math>B=2^b > 1</math> сообщений Алиса строит из корневого элемента <math>r</math> хэш-дерево с <math>B</math> листьями <math>r_0, r_1, \dots, r_{B-1}</math>. Все внутренние вершины дерева выбираются случайно и равновероятно из множества значений <math>f_{i, n_1}\left(\cdot\right)</math>, аналогично <math>r_0</math> в случае одного сообщения. Каждая внутренняя вершина <math>R</math> криптостойко связывается со обоими своими дочерними вершинами путём вычисления значения <math>f_{R_0 \parallel R_1, n_1}\left(R\right)</math>, помещаемого в вершину аналогично тому, как выше вычисляется <math>t</math>. Наконец, сообщение <math>m_j \left(0 \leqslant j \leqslant B - 1\right)</math> криптостойко связывается с <math>j</math>-ым листом дерева аутентификации <math>r_j</math> путём вычисления значения <math>s_j = f^{-1}_{m_j, n_2}\left(r_j\right)</math> аналогично тому, как выше вычислено <math>s</math>. Подпись сообщения <math>m_j</math> состоит из
- Последовательности <math>b</math> вершин дерева от корня <math>r</math> до листа <math>r_j</math>
- <math>b</math> значений, помещённых в вершины (аналогично <math>t</math> выше)
- <math>s_j</math> (аналогично <math>s</math> выше)Шаблон:Sfn.
Односторонние функции с потайным входом
В качестве односторонних функций могут быть использованы <math>f_{i, n}\left(x\right) = \pm 4^{\text{rev}\left(i\right)}x^{2^{\text{len}\left(i\right)}}\mod{n}</math> для <math> n=n_1 </math> и <math>n=n_2</math>, где функция <math>\text{rev}\left(\cdot\right)</math> принимает на вход битовую строку <math> i \in \left\lbrace 0,1\right\rbrace^+</math> и возвращает целое число, представленное битами <math>i</math> в обратном порядке Шаблон:Sfn. Функция <math>\text{len}\left(\cdot\right)</math> также принимает битовую строку <math> i \in \left\lbrace 0,1\right\rbrace^+,</math> возвращая её длину. Знак плюс или минус выбирается таким образом, чтобы значение <math>f_{i, n}</math> было положительно и не превышало <math>n/2</math>. В таком случае вычисление обратной функции осуществляется за время, пропорциональное <math>k^3</math>, где <math>k</math> — длина строки <math>i</math>, при условии, что подписываемые сообщения имеют такую же длину. Таким образом образом, подпись <math>k</math>-битового сообщения может быть подсчитана за время <math>O\left(bk^3\right)</math>Шаблон:Sfn.
Криптостойкость алгоритма
Гольдвассер, Микали и Ривестом доказаноШаблон:Sfn, что алгоритм GMR не позволяет криптоаналитику успешно совершить адаптивную атаку на основе подобранного сообщения, а именно, осуществить экзистенциальную подделку подписи, сгенерированной по схеме GMR. Криптоаналитик, получивший подписи к ряду сообщений, не может подделать подпись для любого дополнительного сообщения.
Обобщения схемы
Возможны обобщения схемы GMR для использования как подписи назначенного подтверждающего (designated confirmer signature scheme)Шаблон:Sfn.
Примечания
Литература
Ссылки
Шаблон:Криптосистемы с открытым ключом
