Регистрация Войти
Рейтинг:3
killertoge avatar Crypto

Почему RSA не является хэш-функцией?

флаг lk
killertoge

RSA-предположение говорит, что $(GenSP,F,SampleX)$ является односторонним. Итак, если мы инициализируем экземпляр RSA $(n,e), (n,d)$ и честно забудьте о секретном ключе и SampleX, равномерно распределенных по $X, F = x^e \bmod N$ должен быть односторонним.

Теперь также известно, что инъективные функции предполагают устойчивость к коллизиям, но, конечно, не одностороннюю.

На данный момент у нас есть сопротивление прообразу и сопротивление столкновению. И второе прообразное сопротивление должно быть оказано, если мы возьмем $х$ только от $\{0,\ldots,n-1\}$.

Мы говорим о детерминированном RSA, поэтому рандомизированный процесс не связан со случайным заполнением. Поэтому наше F также детерминировано.

Я что-то пропустил?

146
0 + 0
Morrolan avatar
флаг ng
Morrolan
Одна простая проблема заключается в том, что мы обычно хотим, чтобы наши хеш-функции имели бесконечно большую область — или, по крайней мере, одну достаточно большую, чтобы быть бесконечной для практических целей. RSA не предлагает этого, вместо этого ограничивая сообщения размером модуля.
4
Ответить
Morrolan avatar
флаг ng
Morrolan
Другая — менее техническая — проблема заключается в том, что вам нужно каким-то образом убедить пользователей вашей пары `(e, N)` (которую пришлось бы стандартизировать, если бы мы использовали RSA в качестве хеш-функции), что вы действительно сделали это. выбросить соответствующий закрытый ключ, соответственно факторизация модуля.
4
Ответить
Mark avatar
флаг ng
Mark
RSA также гомоморфен по умолчанию, так что это будет, по крайней мере, плохая модель случайного оракула, поскольку $H(a)H(b) = H(ab)$. Вы могли бы потенциально «исправить» это с помощью заполнения или просто иметь сконструированную хеш-функцию, которая имеет некоторое свойство устойчивости к коллизиям, но не быть хорошим случайным оракулом (например, не иметь свойств псевдослучайности).
2
Ответить
Рейтинг:3
kelalaka avatar Crypto
флаг in
kelalaka

RSA — это лазейка.перестановка, с вашим дизайном вы просто предлагаете RSA-HASH с этими проблемами;

  • Ограниченный домен с перестановкой: криптографические хэш-функции, хотя они и могут хешировать произвольный размер, их домен гораздо больше, чем их диапазон; рассмотреть возможность

    • SHA-256, хотя он может иметь 256-битный размер вывода, диапазон домена $2^{64}$ биты.
    • SHA-3, хотя он может иметь выходной размер 256 или более бит, диапазон домена $2^{128}$ биты.

    Хотя Keccak (SHA-3) использует перестановки, это не перестановка в конце, поскольку используется больший размер ввода. $2^{128}$. Одна перестановка может вызвать некоторые проблемы.

    С другой стороны, премутация в виде хэша мало используется, если вы не рассматриваете очень большие размеры модуля, хеширование файлов или подписи невозможны с RSA-HASH.

  • Стандарт: Предположим, что NIST опубликовал функцию RSA-HASH-3 как $H(m) = m^3 \bmod n$. Теперь все в криптосообществе будут утверждать, что при создании RSA-HASH-3 они не уничтожили $р$ и $q$ и они держат $д$ как частный. Нет никакой гарантии, сделают они это или нет. Так что наивно полагать, что стерли - это не так, как работает криптография ( Комментарий Морралана).

  • Мы ожидаем, что хеш-функции могут имитировать Случайные оракулы и некоторые из них потерпели неудачу из-за их атаки на увеличение длины. RSA-HASH, с другой стороны, далек от случайного оракула. Мультипликативное свойство RSA предотвращает это. В Random Oracle мы не ожидаем, что общая связь между входами переносится в какую-то связь между выходами, однако в RSA-HASH она есть. $$RSA(m_1)RSA(m_2) = RSA(m_1 m_2)$$

  • Короткое поле ввода: Чтобы сократить время хеширования, вы можете использовать $е=3$, затем атаковать кубическим корнем все сообщения < $\sqrt[3]{N}$ может быть легко. Увеличение $е$ увеличит стоимость хеширования. Помните о необходимости использовать 2048-битный RSA.

  • Постквант: в настоящее время блочные шифры и хеш-функция снова безопасны для алгоритма Гровера. Просто используйте 256-битный ключ для блочных шифров и используйте как минимум 256-битную выходную хеш-функцию. Существует улучшенная работа (Брассар и др.) для хеш-функций, которые уменьшают размер до кубического корня (вместо квадратного корня Гровера - асимптотически оптимально!), однако стоимость площади равна той же стоимости, поэтому существует там нет опасности.

    С другой стороны, RSA будет уничтожен, как только будет построен алгоритм Шора. Так, RSA-HASH не является постквантово безопасным.

Любое использование?: RSA-HASH может служить хорошей случайной перестановкой, если размер модуля подходит для вашего приложения.

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

Использовать SHA-2, SHAKE серии SHA-3, BLAKE2 (очень быстро), BLAKE3 (смехотворно быстро) и т. д. для ваших приложений.

0 + 0
флаг cn
Maeher
«у них гораздо больший диапазон, чем их домен» нет, вся суть хеш-функции в том, что ее кодовый домен (и, следовательно, обязательно его диапазон) намного меньше, чем его домен. Позже вы используете термин «диапазон доменов», о котором я никогда не слышал. То, о чем вы говорите, это домен.
0
Ответить
kelalaka avatar
флаг in
kelalaka
@Maeher, да, там была ошибка. Спасибо.
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.