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

Строительство Меркле-Дамгард

флаг bw
ram kumar

Позволять $H^f$ быть хеш-функцией, разработанной с использованием конструкции Меркла-Дамгарда на $f:\{0,1\}^{2n}\to\{0,1\}^n$. Напишите алгоритм, который делает примерно $2,2^{n/2}$ много запросов к $f$ и найдите четыре сообщения, которые все имеют одинаковое значение в разделе $H^f$.

У меня появилась идея использовать расширение длины и атаку 2 дня рождения, чтобы получить четыре столкновения. Но я не могу написать соответствующее решение. Может ли кто-нибудь помочь мне разобраться.

95
0 + 4
fgrieu avatar
флаг ng
fgrieu
Я предлагаю вам (A) записать полученное вами определение хэш-функции для наибольшего входного значения, которое требует двух вычислений $f$; (B) объясните, как вы находите внутреннее столкновение, изменяя входное сообщение первого $f$; (C) объясните, как вы находите коллизию, изменяя входное сообщение второго $f$; (Д) сделать вывод. Я не понимаю, как мы получаем $2,2^{n/2}$, я думаю, что ожидаемое количество оценок $f$ равно $2^{n/2+1,326}$ (что меньше для больших $n$) .
0
Ответить
флаг bw
ram kumar
да, это приблизительное значение @fgrieu
0
Ответить
poncho avatar
флаг my
poncho
Возможно, вместо $2.2^{n/2}$ имелось в виду $2 \cdot 2^{n/2} = 2 \times 2^{n/2}$
1
Ответить
kelalaka avatar
флаг in
kelalaka
[кросс-пост в CS] (https://cs.stackexchange.com/q/141917/94479)
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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