Как KECCAK работает с массивом состояний, заполненным нулями?
Я пытаюсь реализовать губку на Java. Состояние начинается с пустого 200-байтового массива всех нулей. В документе примеров KMAC от NIST происходит следующее:
(черная линия - разрыв страницы pdf)
Я читаю это так: в KECCAK было отправлено состояние с кучей нулей, а затем было возвращено состояние с явно случайными данными. Превращает ли SHA3 / KECCAK пустые данные в случайные? Я задаю здесь правильные вопросы? Любая помощь приветствуется.
Ответы
Я лично считаю, что документ Keccak.team Psuedo Code очень полезен для понимания того, как Keccak-p.
Как сказал ДэнниНиу в комментариях, в большинстве (всех?) Криптографических перестановках используются «круглые константы». Эти константы как-то смешаны в состоянии Keccak.
В документе псевдокода круглые константы представлены в виде таблицы:
RC[0] 0x0000000000000001 RC[12] 0x000000008000808B
RC[1] 0x0000000000008082 RC[13] 0x800000000000008B
RC[2] 0x800000000000808A RC[14] 0x8000000000008089
RC[3] 0x8000000080008000 RC[15] 0x8000000000008003
RC[4] 0x000000000000808B RC[16] 0x8000000000008002
RC[5] 0x0000000080000001 RC[17] 0x8000000000000080
RC[6] 0x8000000080008081 RC[18] 0x000000000000800A
RC[7] 0x8000000000008009 RC[19] 0x800000008000000A
RC[8] 0x000000000000008A RC[20] 0x8000000080008081
RC[9] 0x0000000000000088 RC[21] 0x8000000000008080
RC[10] 0x0000000080008009 RC[22] 0x0000000080000001
RC[11] 0x000000008000000A RC[23] 0x8000000080008008
и объясняет, как они используются. На йота-шаге$n^\text{th}$ Keccak-p круглый, $n^\text{th}$ круглая постоянная $RC[n]$ вводится и получает XOR в первом слове, первой полосе.
Помимо круглых констант, перестановка Keccak имеет очень хорошее распространение: единственный бит где-то в начальном состоянии будет вносить значительный вклад во многие выходные биты.
Комбинация обоих означает, что ваша перестановка Keccak выглядит очень случайной. Конечно, он не может превратить нулевую энтропию в случайную, поскольку никакой конечный алгоритм не может этого сделать, но цель Keccak состоит в том, чтобы смешать вещи и заставить их казаться случайными.
Функция перестановки Keccak обычно отображает нулевой вход (все биты равны 0) на нулевой выход, если бы не йота-шаг, в котором одно слово состояния подвергается операции XOR с ненулевой константой.
Около трех (из 24) раундов достаточно для полного распространения, т.е. каждый бит состояния влияет на каждый другой бит тремя раундами позже. Можно сказать, перестановка полностью перемешивает состояние восемь раз. Это означает, что если только один бит равен 1, он будет быстро распространяться по состоянию, так что через 3 раунда примерно половина битов состояния будет равна 1.
Позволять $R$быть набором значений состояния, которые можно разумно назвать «нормально выглядящими» (каким бы точным определением ни было), например, все или почти все биты имеют одинаковое значение, или короткий битовый шаблон повторяется регулярно. Среди всех$2^{1600}$ государства, те, кто в $R$являются очень маленькой долей. Маловероятно, что какое-либо государство в$R$ отображается на выход также в $R$. Это действует до тех пор, пока$|R| \ll 2^{800}$ (см. «парадокс дня рождения»).
Это означало бы, что не существует обычных входных данных, которые отображаются на обычные выходные данные. И вероятность того, что любое данное состояние будет отображено на выход в$R$ пренебрежимо мала, т.е. результат всегда будет выглядеть случайным, за исключением случаев, когда кто-то намеренно создает ввод, вычисляя обратную перестановку.