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

Атака прообразом суммы двух хеш-функций по модулю 2

флаг cn
user766787

Если хэш-функция $Ч$ определяется как $H(x_1,x_2) = H_1(x_1) \oplus H_2(x_2)$ для двух n бит хороших хеш-функций $H_1$ и $H_2$ тогда как мы можем построить атаку прообраза на $Ч$ это из $O(2^\frac{n}{2})$ учитывая некоторые y ?

Здесь мы можем запросить $H_1$ и $H_2$ ?

Я был бы очень признателен за некоторые подсказки.

67
1 + 3
Patriot avatar
флаг cn
Patriot
Возможно, вы захотите проголосовать за ответ, который вы приняли.
0
Ответить
флаг cn
user766787
@Patriot Да, я пытался. Мне нужно как минимум 15 репутации, чтобы показать.
0
Ответить
Patriot avatar
флаг cn
Patriot
Хорошо, вы почти у цели.
0
Ответить
Рейтинг:2
Meir Maor avatar Crypto
флаг in
Meir Maor

Это похоже на домашнюю работу, поэтому я остановлюсь на полном решении. Да, вам разрешено запрашивать функции $H_1$ и $H_2$ это почти единственное, что вы можете сделать. Таким образом, вы можете собрать пул пар ввода-вывода для каждого. И что тогда можно сделать с двумя такими наборами пар вход-выход? Вы можете захотеть проиндексировать один из них для эффективного поиска.

0 + 3
флаг cn
user766787
Я могу выбрать набор запросов размером 2 ^ (n/2) и запросить H_1 (x) и H_2 (x) в этом наборе. Затем мне нужно будет сравнить значения y + H_1 (x) и H_2 (x), используя запрошенные, чтобы найти коллизию. Это правильно?
0
Ответить
Meir Maor avatar
флаг in
Meir Maor
да, это разумный метод.
0
Ответить
флаг cn
user766787
Спасибо большое
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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