В статье есть список источников, но не хватает сносок.

Без сносок сложно определить, из какого источника взято каждое отдельное утверждение. Вы можете улучшить статью, проставив сноски на источники, подтверждающие информацию. Сведения без сносок могут быть удалены. (20 апреля 2015)

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.

На эту статью не ссылаются другие статьи Википедии.

Это делает её менее доступной для читателей. Пожалуйста, установите ссылки, используя инструмент с подсказками для облегчения поиска. (12 декабря 2011)