GHR

GHR (буквенная аббревиатура от фамилий Gennaro, Halevi и Rabin) — схема цифровой подписи с открытым ключом.

В Праге в 1999 году на международной конференции по теории и применению криптографических методов (International Conference on the Theory and Application of Cryptographic Techniques) была представлена статья Росарио Дженнаро, Шай Халеви и Таль Рабин «Secure Hash-and-Sign Signatures Without the Random Oracle», в которой они описали схему цифровой подписи с доказуемой точностью (позже названную GHR-схемой подписи). Доказательство её стойкости, которое основывается на сильных предположениях RSA можно получить, не привлекая модель случайного оракула (недоступная ссылка).

(Задача RSA) Пусть дан модуль алгоритма RSA n = р*q , экспонента Е взаимно простая с φ(N) и случайное целое число С (C<n). Требуется найти целое число m (m<n), для которого выполняется следующее равенство. m^E=С mod n

Сильное предположение RSA состоит в трудноразрешимости следующей задачи:

(Слабая задача RSA) Пусть дан модуль n = р*q алгоритма RSA и случайное целое число C (C<n). Требуется найти целое число е > 1 и целое число m (m<n), для которых выполняется следующее равенство. m^ e=С mod n

Модель случайного оракула (недоступная ссылка) реально не моделирует вычислений, встречающихся на практике. Доказательства, полученные в рамках этой модели, говорят лишь о возможной стойкости алгоритмов, но не гарантируют её.

Введение. GHR схема напоминает стандартный алгоритм RSA подписи, но с некоторым изменением. Отличие состоит в том, что в алгоритме RSA сообщение представленное двоичным числом возводиться в некоторую заранее выбранную степень по модулю n. В GHR-схеме ищется решение уравнения ∑^H(M)=S mod n (∑-искомая неизвестная, S-заранее выбранное число, H(M)-значение хеш-функции от сообщения).

M — сообщение

e — открытая экспонента (общественная экспонента, фиксированное значение)

d — секретная экспонента (d*e mod φ(n) =1 φ(n) — функция Эйлера)

n — модуль RSA (n=p*q)

Пара (e, n) — открытый ключ

Пара (d, n) — секретный ключ

Алгоритм подписи.

Формирование подписи σ = M^d mod n

Передача пары (M, σ)

Проверка подписи.

Прием пары (M, σ)

Проверка равенства M = σ^e mod n

M — сообщение

экспонента H(M) (H — некоторая хеш-функция)

n — модуль RSA (n=p*q)

S — база (фиксированное значение)

Набор (S, H, n) — открытый ключ

Набор (S, p, q) — секретный ключ

Формирование подписи.

Σ^H(M) = S mod n (∑ — подпись на сообщение M). На данном этапе происходит вычисление ∑, что является вычислительно сложной задачей если n=p*q (p, q большие простые числа) и p, q не известны.

Передача пары (M, ∑)

Проверка подписи.

Прием пары (M, ∑)

Проверка равенства Σ^H(M) = S mod n

1) Формирование открытого ключа.

Открытым ключом является целое число n = p*q (n — модуль RSA), случайное целое S (S < n) и хеш-функция H.

Открытый ключ (n, S, H).

Секретный ключ (p, q, S).

2) Формирование подписи.

Чтобы подписать сообщение M открытым ключом (n, S), подписывающееся лицо сперва применяет хеш-функцию для вычисления значения e=H(M), а зетем использует полученное значение как экспоненту, то есть находит корень степени е из S по модулю n. Подпись на сообщение M представляет собой целое число ∑, такое что

∑^H(M)=S mod n.

3) Проверка подписи.

Для проверки подписи число ∑ возводится в степень H(M) и проверяется равенство ∑^H(M)=S mod n

a^b=s mod n

для того чтобы найти корень степени b из s по модулю n. Необходимо найти число r, такое что r*b = 1 mod φ(n), причём для существования числа r необходимо чтобы НОД(b,φ(n))=1.

a=s^r mod n

В данной схеме p и q — простые либо И. М. Виноградов. Квазипростое число // Математическая энциклопедия. — М.: Советская энциклопедия (рус.). — 1977—1985. числа одинаковой длины, обладающие следующим дополнительным свойством: (p-1)/2, (q-1)/2 — простые числа. В частности такой выбор означает, что (p-1), (q-1) не имеют общих простых делителей отличных от 2, и что найти нечетное целое число не являющееся взаимно простым с φ(n) так же сложно, как и разложить n на простые множители. Это условие гарантирует, что нахождение корня степени е из S, при e=H(M), всегда возможно если наложить на хеш-функцию H соответствующее ограничение. Вывод хеш-функции H должен быть в виде нечетных целых чисел. Такую функцию легко построить, достаточно к значениям обычной хеш-функции, представленным в двоичном виде, приписывать дополнительный бит равный 1.

H*=H|1

Либо устанавливать младший бит хеш-функции H равным 1.

1) Отметим что с подавляющей вероятностью экспонента e=H(M) будет взаимно проста с φ(n). Так как найти нечетное число не являющееся взаимно простым с φ(n) сложная задача.

2) Длина вывода хеш-функции имеет значение для эффективности системы. Если мы зададим выход хеш-функции как двоичное число длиной равной длине числа n в двоичной записи, то процесс генерации подписи будет занимать примерно в два раза больше времени чем в процессе стандартной RSA подписи (так как для подписи сначала необходимо вычислить e^(−1) mod (n), а затем возвести базу S в степень e^(-1)). Проверка подписи примерно равна времени полного возведения в степень по модулю n. Сокращение времени работы GHR-схемы может быть достигнута путём сокращения длины вывода для H. Однако для обеспечения необходимой безопасности вывод H должен быть достаточно длинным. В своей работе 1999 года Дженнаро, Халеви и Рабин опубликовали экспериментальные результаты свидетельствующие о том, что для получения эквивалентной безопасности 1024-разрядной RSA-схемы, размер вывода хеш-функции должен быть около 512 бит. Для такого значения вывода хеш-функции, процесс вычисления подписи будет примерно в 1,5 раза медленнее, чем для стандартной 1024-разрядной подписи RSA. Однако в своей работе «Security Analysis of the Gennaro-Halevi-Rabin Signature Scheme» (EUROCRYPT2000) Jean-Sebastien Coron и David Naccache показали, что существуют атаки требующие увеличить длину вывода хеш-функции до 1024 бит для обеспечения безопасности соответствующей 1024-разрядной RSA-схеме.

Предположим, что активный противник намерен подписать сообщение M1, причем ему удалось найти такое сообщение М2, что H(M2) = Z*H(M1)

Допустим теперь, что этот нападающий использует алгоритм GHR c уже сформированным открытым ключом (n, S, H) для подписания сообщения М2. В результате нападающий получает подпись ∑2 на своё сообщение M2. (∑2^H(M2)=S mod n) В этой ситуации у нападающего появляется возможность подделать подпись на сообщение Ml, вычисляя

∑1=∑2^Z mod n

поскольку

∑1^H(M1) mod n = S mod n =∑2^H(M2) mod n = ∑2^(Z*H(M1)) mod n = (∑2^Z)^H(M1) mod n

Откуда получаем необходимое равенство

∑1=∑2^Z mod n

Решить данную проблему можно если наложить на хеш-функциб специальное ограничение — её результатом должны быть только простые числа. Это исключит возможность нахождения сообщения M2 такого, что H(M2) = Z*H(M1). Хеш-функции, значения которых - простые числа, могут быть спроектированы, однако на настоящее время они довольно слабо изучены .

Еще один вариант взлома это найти сообщение M2 такое, что H(M2) = H(M1)

В этом случае подпись на сообщение M1 очевидно равна подписи на сообщение M2.

Такой вариант исключают современные требования на криптографическую стойкость хеш-функций. Задача нахождения значения M2 такого, что H(M2) = H(M1), является вычислительно невозможной задачей.

1) «Secure Hash-and-Sign Signatures Without the Random Oracle» Rosario Gennaro, Shai Halevi, Tal Rabin. Advances in Cryptology — EUROCRYPT 1999. http://www.springerlink.com/content/bryhef8g51vwbl10/fulltext.pdf (недоступная ссылка)

2) «Security Analysis of the Gennaro-Halevi-Rabin Signature Scheme» Jean-Sebastien Coron and David Naccache. Advances in Cryptology — EUROCRYPT2000. http://www.springerlink.com/content/wgm9b431d0fnfjah/fulltext.pdf (недоступная ссылка)

3) Мир программирования «Криптография» Н. Смарт. Техносфера, 2005. 439—443 стр. ISBN 5-94836-043-1.