Полный хеш домена

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

Точная безопасность полного хеша домена

В модели случайного оракула, если RSA $(t',\epsilon ')$-secure, то схема подписи RSA полного хэша домена будет $(t,\epsilon )$-безопасно где,

${\begin{aligned}t&=t'-(q_{\text{hash}}+q_{\text{sig}}+1)\cdot {\mathcal {O}}\left(k^{3}\right)\\\epsilon &=\left(1+{\frac {1}{q_{\text{sig}}}}\right)^{q_{\text{sig}}+1}\cdot q_{\text{sig}}\cdot \epsilon '\end{aligned}}$.

Для больших $q_{\text{sig}}$ это сводится к $\epsilon \sim \exp(1)\cdot q_{\text{sig}}\cdot \epsilon '$.

Это означает, что если существует алгоритм, который может подделать новую подпись FDH, работающую за время t , вычислит не более $q_{\text{hash}}$ хеши, запрашивает максимум $q_{\text{sig}}$ подписи и добивается успеха с вероятностью $\epsilon$, то также должен существовать алгоритм, который с вероятностью ломает RSA $\epsilon '$ вовремя $t'$.

Ссылки

• Жан-Себастьен Корон (AF): О точной безопасности полного хэша домена. КРИПТО 2000: стр. 229–235 ( PDF )
• Михир Белларе , Филип Рогауэй : Точная безопасность цифровых подписей — как подписывать с помощью RSA и Rabin. EUROCRYPT 1996: стр. 399–416 ( PDF )