GMR
GMR — криптографический алгоритм, используемый для создания цифровой подписи. Назван по первым буквам создателей — Рональда Ривеста, Сильвио Микали и Шафи Гольдвассер.
GMR базируется на высокой вычислительной сложности факторизации больших целых чисел, как и криптосистема RSA. Но, в отличие от неё, GMR устойчива к атакам на основе подобранного открытого текста [1].
Что значит взломать цифровую подпись?
Можно говорить, что криптоаналитик «взломал» цифровую подпись , если совершенная атака позволяет ему с ненулевой вероятностью совершить следующее[2]:
- Полный взлом (total break): вычислить закрытый ключ
- Универсальная подделка (universal forgery): найти эффективный алгоритм, эквивалентный алгоритму цифровой подписи (используется, вообще говоря, другой, но эквивалентный секретный ключ)
- Выборочная подделка (selective forgery): подделать подпись некоторого сообщения, выбранного криптоаналитиком априори
- Экзистенциальная подделка (existential forgery): подделать подпись хотя бы одного сообщения. При этом криптоаналитик не выбирает сообщение для подделки подписи, подделка может быть случайной и лишённой смысла. Подделка такого типа может нести минимальный урон для . Авторами схемы GMR доказана ее устойчивость именно к такому типу атаки[3].
Описание алгоритма
Предположим, что Алисе нужно отправить Бобу последовательность сообщений, подтверждённых цифровой подписью. Пусть Алиса предполагает подписать сообщений, случайный параметр шифрования - . Открытый ключ состоит из следующих компонент:
|
.
Закрытый ключ состоит из простых чисел , позволяющих эффективно вычислять обратные функции и .
Рассмотрим случай генерации подписи для одного сообщения , то есть и . Алиса выбирает случайное число из области значений и вычисляет подпись сообщения :
- и .
Получив подписанное сообщение, Боб последовательно проверяет, что
- .
Для подписи сообщений Алиса строит из корневого элемента хэш-дерево с листьями . Все внутренние вершины дерева выбираются случайно и равновероятно из множества значений , аналогично в случае одного сообщения. Каждая внутренняя вершина криптостойко связывается со обоими своими дочерними вершинами путём вычисления значения , помещаемого в вершину аналогично тому, как выше вычисляется . Наконец, сообщение криптостойко связывается с -ым листом дерева аутентификации путём вычисления значения аналогично тому, как выше вычислено . Подпись сообщения состоит из
- Последовательности вершин дерева от корня до листа
- значений, помещённых в вершины (аналогично выше)
- (аналогично выше)[5].
Односторонние функции с потайным входом
В качестве односторонних функций могут быть использованы для и , где функция принимает на вход битовую строку и возвращает целое число, представленное битами в обратном порядке [6]. Функция также принимает битовую строку возвращая её длину. Знак плюс или минус выбирается таким образом, чтобы значение было положительно и не превышало . В таком случае вычисление обратной функции осуществляется за время, пропорциональное , где — длина строки , при условии, что подписываемые сообщения имеют такую же длину. Таким образом образом, подпись -битового сообщения может быть подсчитана за время [6].
Криптостойкость алгоритма
Гольдвассер, Микали и Ривестом доказано[3], что алгоритм GMR не позволяет криптоаналитику успешно совершить адаптивную атаку на основе подобранного сообщения, а именно, осуществить экзистенциальную подделку подписи, сгенерированной по схеме GMR. Криптоаналитик, получивший подписи к ряду сообщений, не может подделать подпись для любого дополнительного сообщения.
Обобщения схемы
Возможны обобщения схемы GMR для использования как подписи назначенного подтверждающего (designated confirmer signature scheme)[7].
Примечания
- ↑ S. Goldwasser, S. Micali, R. L. Rivest, 1988.
- ↑ S. Goldwasser, S. Micali, R. L. Rivest, 1988, p. 284.
- ↑ 1 2 S. Goldwasser, S. Micali, R. L. Rivest, 1988, p. 298—304.
- ↑ H. C. A. Van Tilborg, S. Jajodia, 2014, p. 50.
- ↑ H. C. A. Van Tilborg, S. Jajodia, 2014, p. 240.
- ↑ 1 2 S. Goldwasser, S. Micali, R. L. Rivest, 1988, p. 305.
- ↑ S. Goldwasser, E. Waisbard, 2004, p. 95.
Литература
- 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.
Ссылки
- Схемы цифровой подписи (англ.)