Рейтинг:2

Запрос относительно выходной хеш-структуры SHA256 и входной энтропии?

флаг br

Дана входная строка из N байтов, где некоторые позиции байтов в строке являются фиксированными/неизменяемыми (F байтов), а остальные позиции байтов могут содержать любое значение, которое мы хотим, или являются настраиваемыми/переменными (V = N-F байтов).

SHA256 (SHA256 (N)) = H (256 бит).

Теперь, учитывая входную строку из N байтов, значения N, F, V и позиции, которые могут измениться и которые не могут:

Как мы вычисляем вероятность/формулу того, что по крайней мере для 1 присвоения значений в V вычисленный H имеет k ведущих байтов как 0?

Например: для случайной входной строки размера N, N = 80, F = 40, V = 40 (при условии, что информация о положении также дана), как мы узнаем/рассчитываем вероятность того, что по крайней мере для 1 присвоения значений в V первые k байтов H равны 0?

Я попытался найти какой-то анализ по этому вопросу, но не нашел ответа. Может кто-нибудь помочь?

Рейтинг:0
флаг in

Как упоминалось ранее, расположение фиксированного байта или их количество не имеет значения, если мы предполагаем, что вывод рандомизирован.

Предположим, биты, так что $v = 8 \cdot V$.

Теперь для одного значения вероятность того, что оно начнется с $к$ биты можно свести к шансу, что первый $к$ биты имеют постоянное значение. Размер хэша не имеет значения. Так что для одной попытки это просто $1 \более 2^к$.

Поскольку выходные данные рандомизированы, мы также можем сделать вывод, что выходные данные не связаны между собой; каждая попытка имеет одинаковый шанс. В этом случае это очень похоже на бросание игральных костей, так что вычисление похоже на единицу минус шанс выпадения. нет бросая 6 в количестве бросков.

Таким образом, это означает, что вероятность равна единице минус вероятность того, что постоянное значение $к$ биты не выбрасываются:

$$1 - \bigg({{2^k-1} \over {2^k}}\bigg)^{2^v} = 1 - (1 - 2^{-k})^{2^v} $$

Теперь это кажется пугающим, но вы можете поиграть с (небольшими) значениями. с использованием WolframAlpha.

Обратите внимание, что если $v$ становится больше, чем $к$ то вероятность быстро приближается к 1, а при $к$ становится больше, чем $v$ - что имеет смысл, ведь они используются как экспоненты.

Поскольку мы предполагаем, что SHA-256 уже рандомизирует вывод, похоже, это вообще не имеет ничего общего с энтропией, счетчик с размером $v$ будет работать так же хорошо, как случайный ввод - лучше, даже если нет шансов на дублирование.

Maarten Bodewes avatar
флаг in
Обратите внимание, что WolframAlpha пытается рассчитать точную сумму; если у кого-то есть хорошее приближение (например, в форме $\log_2$), то я весь внимание.

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

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