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

Какие входные биты обнаруживаются при раскрытии первых 256 бит выходной перестановки Keccak-f?

флаг cn
cryptobeginner

Учитывая перестановку Keccak-f[1600], меня интересует следующее свойство: какие биты на выходе зависят от того, какие биты на входе? То есть, если я изменю, например, второй бит ввода, на какие биты вывода это повлияет?

Другими словами: предположим, что у меня есть первые 256 бит вывода функции Keccak. Затем, поскольку Keccak-f[1600] является биективным, существует только 1600-256 прообразов, которые все еще могут отображаться на выходе с «правильными» первыми 256 битами. Есть ли способ оценить, сколько битов одинаковы во всех оставшихся значениях 1600-256?

48
0 + 0
kelalaka avatar
флаг in
kelalaka
Первый вопрос — это свойство лавины, которое мы хотим получить от хеш-функций.
0
Ответить
Рейтинг:1
poncho avatar Crypto
флаг my
poncho

Какие биты на выходе зависят от того, какие биты на входе? То есть, если я изменю, например, второй бит ввода, на какие биты вывода это повлияет?

Насколько нам известно, все выходные биты являются сложной функцией всех входных битов. Переворот любого определенного входного бита (скажем, второго) потенциально может перевернуть любой выходной бит.

Предположим, у меня есть первые 256 бит вывода функции Keccak. Затем, поскольку Keccak-f[1600] биективен, существует только 1600-256 прообразов, которые все еще могут отображаться на выходе с «правильными» первыми 256 битами.

На самом деле, вы просчитались; Есть $2^{1600-256}$ прообразы, то есть:

383984923062992702193107238768305990575971314802788874095145673202075995393018055488645297669674812185833211621938100469973519720714697045576788566898683254440275883795786334484525778054071087861396060398229434719927672395650215231472663143090071728679350725089418264731278276442800414037787428461842409521168393903855600900323733353159466811689332335765898192891862061280747855198528180896166938113212416

прообразы. Это чуть больше, чем 1600-256 = 1344...

0 + 0
cryptobeginner avatar
флаг cn
cryptobeginner
Ааа, точно, спасибо! Вы упомянули, что «переключение любого определенного входного бита (скажем, второго) потенциально может перевернуть любой выходной бит». Теперь предположим, что мы знаем 1599 бит вывода. Тогда есть только 2 потенциальных прообраза, которые могут привести к такому результату в функции Keccak-f, верно? Действительно ли гарантируется, что эти прообразы всегда различны в каждом бите?
0
Ответить
poncho avatar
флаг my
poncho
@cryptobeginner: очевидно, что только с двумя прообразами некоторые выходные биты (вероятно, около половины) будут согласованы между двумя постизображениями. Однако, если вы измените один из 1599 фиксированных битов, биты, которые остаются неизменными между этими двумя модифицированными постизображениями, скорее всего, изменятся...
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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