Full domain hash

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

В криптографии Full Domaine Hash (FDH или полный хеш домена) является схемой подписи на основе RSA, которая следует парадигме хеширования и подписи. Он доказуемо защищён (то есть не поддавался влиянию адаптивных атак с использованием выбранных сообщений) в модели случайного оракула. FDH включает в себя хеширование сообщения с использованием функции, размер изображения которой равен размеру модуля RSA, а затем возведение результата в степень секретной экспоненты RSA.

С момента открытия Уитфилдом Диффи (англ. Whitfield Diffie) и Мартином Хеллманом (англ. Martin Hellman) криптографии с открытым ключом[1] одной из наиболее важных тем исследования является разработка практичных и доказуемо (в практическом понимание) безопасных криптосистем. Доказательством практичной безопасности обычно является вычислительная сложность от решения хорошо известной задачи до взлома криптосистемы. Хорошо известные задачи включают в себя факторизацию больших целых чисел, вычисление дискретного логарифма по модулю простого числа p или извлечение корня по модулю составного целого числа, на которой основана криптосистема RSA[2].

Очень распространённая практика для подписи с RSA — сначала хешировать сообщение, добавить к сообщению соль , а затем возвести в степень открытого ключа. Эта парадигма «хеширования и расшифровки»(hash and decrypt) является основой многочисленных стандартов, таких как PKCS # 1 v2.0[англ.][3]. Схема состоит в том, чтобы взять хеш-функцию, выходной размер которой точно равен размеру модуля: это полнодоменная схема хеширования (FDH), введённая Белларом[англ.] и Рогэвеем[англ.] в статье "Random oracles are practical: a paradigm for designing efficient protocols"[4]. Схема FDH доказуемо безопасна в модели случайного оракула, предполагая, что инвертировать RSA, то есть извлечь корень по модулю составного целого числа, сложно. Методология случайного оракула была введена Белларом и Рогэвеем в "Random oracles are practical: a paradigm for designing efficient protocols"[4], где они показывают, как разрабатывать надёжно защищённые схемы подписи из любой функции с потайным входом. В модели случайного оракула хеш-функция рассматривается как оракул, который выдаёт случайное значение для каждого нового запроса . В оригинальной статье случайный оракул преобразует последовательность из 0 и 1 фиксированной длины в последовательность бесконечной длины и случайным образом выбирает из последовательности подпоследовательность необходимой длины. Основополагающая работа Беллара и Рогэвея подчёркивает, что для практического применения доказуемой безопасности важно учитывать «жёсткое» снижение безопасности. Снижение безопасности является «жёстким», когда любые действия криптоаналитика для взлома схемы подписи приводит к решению хорошо установленной задачи с достаточной вероятностью, в идеале с вероятностью, равной 1. В этом случае схема подписи почти так же безопасна, как и устоявшаяся задача. Напротив, если сокращение является «слабым», то есть вышеупомянутая вероятность слишком мала, гарантия на схему подписи может быть довольно слабой.

Определение

[править | править код]

Схема подписи полного доменного хеша (Gen, Sign, Verify) определяется следующим образом. Алгоритм генерации ключей запускает RSA для получения . Он выводит , где и . Алгоритм подписи и проверки имеет доступ к оракулу c хеш-функцией

Подпись и проверка выполняются следующим образом:

Анализ безопасности схемы FDH

[править | править код]

Подход Беллара и Рогвея

[править | править код]

Теорема 1 Предположим, что RSA -безопасен (на взлом с вероятностью ɛ′ потребуется t′ времени ) Тогда схема FDH-подписи является -безопасным, где

.

Недостатком данного результата является то, что может быть намного меньше . Например, если мы предположим, что криптоаналитик может запрашивать количество подписей и вычислять хеши на сообщениях , даже если вероятность инверсии RSA составляет всего , то все, что мы получаем, это что вероятность составляет почти , что не является удовлетворительным. Чтобы получить приемлемый уровень безопасности, мы должны использовать больший размер модуля, который будет положительно влиять на эффективность схемы.

Чтобы получить наиболее подходящую границу безопасности, Беллар и Рогавей разработали новую схему — схему вероятностной подписи , которая обеспечивает строгое снижение безопасности: вероятность подделки подписи практически также мала как и при инвертировании . Вместо этого, существует альтернативный подход, который может быть применён по отношению к FDH схеме для получения лучшей границы.[5]

Альтернативный подход

[править | править код]

Иное сокращение, которое даёт лучшую оценку безопасности для FDH, основано на доказательстве теоремы

Теорема 2 Пусть RSA  — безопасен. Тогда схема FDH подписи является -безопасной, где

.

Для больших , .

Определение 1

[править | править код]

Инвертором - будем называть алгоритм взламывающий RSA , вероятность успеха которого по истечении не более t времени обработки составляет не менее ɛ .

Определение 2

[править | править код]

Фальсификатором - будем называть алгоритм нарушающий схему подписи (Gen, Sign, Verify), если после не более чем запросов к хеш-оракулу, подписанных запросов и времени обработки, выводит подделку подписи с вероятностью не менее ɛ .


Доказательство Пусть  — фальсификатор , который взламывает FDH. Мы предполагаем, что никогда не повторяет один и тот же запрос хеш-оракулу или запрос на подпись. Строим инвертор , который взламывает RSA. Инвертор получает в качестве входных данных , где  — открытый ключ, а выбирается случайным образом в (подмножества всех хешированных сообщений) . Инвертор пытается найти , где  — функция RSA, определённая из . Инвертор запускает для этого открытого ключа. Фальсификатор делает запросы к хеш-оракулу и запросы на подпись. получая ответ от хеш-оракула самостоятельно подписывает их.

Для простоты мы предполагаем, что когда делает запрос на подпись сообщения , он уже сделал соответствующий запрос хеш-оракулу для . Если нет - продолжаем и самостоятельно создаём запрос хеш- оракулу для сообщения .В инверторе используется счётчик , изначально установленный на ноль. Когда делает запрос хеш-оракулу для сообщения , инвертор увеличивает , устанавливает соответствие хешированного сообщения и изначального сообщения , а также выбирает случайное число в . затем возвращает с вероятностью и с вероятностью . Здесь  — фиксированная вероятность, которая будет определена позже. Когда делает запрос на подпись для , он уже запросил хеш , так что для некоторых .Если , тогда возвращает в качестве подписи. В противном случае, процесс останавливается и происходит сбой инвертора.

В конце концов, заканчивает работу и выводит подделку . Мы предполагаем, что запрашивал хеш ранее. Если нет, самостоятельно делает запрос хеш-оракулу, так что в любом случае для некоторого . Тогда, если , мы получаем, и выводит в качестве обратной величины для . В противном случае процесс останавливается и происходит сбой инвертора.

Вероятность того, что мы ответим на все запросы сигнатур, составляет не менее . Затем выводит обратное для с вероятностью . Таким образом, с вероятностью, по крайней мере, , выводит обратное для . Функция максимальна для и

Следовательно, мы получаем:

.

Для больших ,

.

Время работы  — это время работы , добавленное ко времени, необходимому для вычисления значений . По сути, это одно вычисление RSA, которое является кубическим временем (или лучше). Это даёт формулу для .

Итоговое сокращение

[править | править код]

Качество нового сокращения не зависит от количества хеш-вызовов, выполненных фальсификатором, и зависит только от количества запросов на подписи. Это имеет практическое значение, поскольку в реальных приложениях число вызовов хеш-функции ограничено только вычислительной мощностью фальсификатора, тогда как количество запросов на подпись может быть ограничено: подписывающее лицо может отказаться подписывать более или сообщений. Тем не менее, сокращение по-прежнему не является жестким и остаётся значительный разрыв между точной безопасностью FDH и точной безопасностью PSS.

Во многих доказательствах безопасности в модели случайного оракула инвертор должен «угадать», какой хеш-запрос будет использоваться противником для подделки, что приводит к коэффициенту в вероятности успеха. Доказано, что лучшим методом является включение запроса в ответ на многие хеш-запросы, чтобы подделка с большей вероятностью была полезна для инвертора. Это наблюдение также применимо к схеме подписи Рабина[6] , схеме подписи Пейе[7], а также к схеме подписи Дженнаро-Галеви-Рабина[8] , для которой коэффициент в доказательстве безопасности случайного оракула также может быть уменьшен до .

Примечания

[править | править код]
  1. New directions in cryptography. Дата обращения: 25 декабря 2018. Архивировано 12 октября 2019 года.
  2. A method for obtaining digital signatures and public key cryptosystems. Дата обращения: 25 декабря 2018. Архивировано 26 декабря 2018 года.
  3. RSA cryptography specifications. Дата обращения: 25 декабря 2018. Архивировано 12 декабря 2018 года.
  4. 1 2 Random oracles are practical: a paradigm for designing efficient protocols. Дата обращения: 25 декабря 2018. Архивировано 24 декабря 2018 года.
  5. The exact security of digital signatures - How to sign with RSA and Rabin. Дата обращения: 25 декабря 2018. Архивировано 23 декабря 2018 года.
  6. Digitalized signatures and public-key functions as intractable as fac- torization. Дата обращения: 25 декабря 2018. Архивировано 3 ноября 2018 года.
  7. Public-key crypto systems based on composite degree residuosity classes. Proceedings of Eurocrypt’99. Дата обращения: 25 декабря 2018. Архивировано 6 мая 2021 года.
  8. Secure hash-and-sign signatures without the ran- dom oracle, proceedings of Eurocrypt’99. Дата обращения: 25 декабря 2018. Архивировано 14 июля 2012 года.