Рейтинг:1

Оценка энтропии ключей, полученных из действительно случайных чисел

флаг ua

ПРИМЕЧАНИЕ: Этот вопрос основан на моем предположении, что $Х$ является «истинно случайным числом» тогда и только тогда, когда его длина, измеренная в битах, равна его энтропии, измеренной в битах.Другими словами, когда каждый бит $Х$ был сгенерирован случайным броском монеты.

Предположим, у меня действительно случайное число $R$ размером 256 бит (256 бит энтропии) и действительно случайное число $S$ длины $n * 256$, куда $n$ некоторое натуральное число, поэтому оно имеет $n * 256$ биты энтропии.

теперь я вывожу четыре ключа $T_1$ к $T_4$ от $R$

  • $T_1 = \text{concat}(R, \text{... n раз ...}, R)$
  • Рассчитать $t_1 = \text{sha256}(R)$, $t_2 = \text{sha256}(t_1)$, ..., $t_n = \text{sha256}(t_{n-1})$, и делать $T_2=\text{concat}(t_1, ..., t_n)$.
  • $T_3$ рассчитывается так же, как и выше, но с использованием HMAC вместо sha256.
  • $T_4 = \text{hkdf_expand}(R, \text{null}, n * 256/8)$.

Наконец, я вычисляю $K_i = T_i\text{ xor}S$.

Сколько бит энтропии $K_1$, $K_2$, $K_3$ и $K_4$ имеют?

Мои счастливые догадки:

  • $T1$ будет иметь столько энтропии, сколько $R$, поскольку конкатенация путем повторения не увеличивает энтропию вывода, но я подозреваю, что и не уменьшает ее.
  • $\text{sha256}$ и $\текст{HMAC}$ считаются сохраняющими биты энтропии входных данных, но поскольку процесс построения $T_2$ и $T_3$ детерминистически рассчитывается из $R$, энтропия $T_2$ и $T_3$ будет примерно равнозначно $T1$.
  • понятия не имею о $T_4$. Я думаю, преимущества $\text{hkdf_expand}$ срабатывает, когда его ввод не является действительно случайным числом.

О каждом $K_i$, Я не уверен. Недавно я узнал, что XOR двух действительно случайных чисел дает действительно случайное число, поэтому биты энтропии вывода по-прежнему являются его длиной, но поскольку $T_i$s больше не являются случайными числами, я не знаю, что здесь произойдет.

Моя интуиция подсказывает мне, что энтропия $S$ сохранится($n * 128$ биты), потому что $K_i$ эквивалентно шифрованию $T_i$ с использованием $S$ как ключ одноразового блокнота, делая $T_i$ или же $S$ теоретически нерушимый, так что $K_i$ по-прежнему является действительно случайным числом.

Paul Uszak avatar
флаг cn
Привет! Эээ, я в замешательстве. Можете ли вы упростить вопрос, учитывая, что у вас есть доступ к действительно случайным числам? Что ты пытаешься сделать?
sanscrit avatar
флаг ua
@PaulUszak Я заменил свою последнюю заметку своими собственными догадками в качестве примера ожидаемого уровня детализации.
sanscrit avatar
флаг ua
@PaulUszak Можно сказать, что мой вопрос в основном теоретический.
fgrieu avatar
флаг ng
Вопросы A) \[фрагмент, исправлен вопрос\]. Б) HMAC нужен ключ. C) Строго говоря, "Сколько битов энтропии имеют $K_1$, $K_2$, $K_3$ и $K_4$?" спрашивает что-то спорное, поскольку битовые строки не имеют энтропии (или не имеют ее); _процесс_, который их строит, имеет четко определенную энтропию.Г) Энтропия процессов, которые строят $K_1$, $K_2$, $K_3$ и $K_4$, зависит от того, независимы ли $R$ и $S$. Утвердительно, это \[лишняя подсказка убрана\] благодаря тому, что «я вычисляю $K_i=T_i\text{ xor }S$» и $T_i$ является функцией $R$.
sanscrit avatar
флаг ua
@fgrieu Я имел в виду, что каждый $T_i$ полностью зависит от $R$; и да, я знаю, что энтропия зависит от процесса, а не от числа. Я могу получить число 5 случайным выбором, или 2 + 3, где 2 и 3 — случайные числа, или 2 + 3, где 2 и 3 — известные числа. Первый процесс будет иметь 3 бита энтропии, второй процесс, вероятно, тоже (моя догадка, потому что добавление случайных чисел изменяет статистическое распределение, но это все еще случайный процесс), а третий процесс — 0 бит энтропии.
sanscrit avatar
флаг ua
@fgrieu и да, если быть более точным, мой вопрос был о том, что происходит с энтропией процесса до каждого $K_i$, когда я использую такие вещи, как concat, sha256 или hkdf_expand по ключу с меньшей энтропией ($R$) в сочетании позже с ключом с большей энтропией ($S$), но да, после вашего первого комментария я понимаю, что XORing не разрушает энтропию, поскольку $S$ и $T_i$ совершенно не связаны, поэтому тот факт, что $R$ имеет меньше энтропии, чем $S$, не рискует безопасностью $K_i$.
Рейтинг:1
флаг ng

XOR двух действительно случайных чисел дает действительно случайное число

Нет. Контрпример: $S$ равномерно случайный, $S\oплюс S$ представляет собой полностью нулевую битовую строку того же размера, что и $S$, и не является равномерно случайным (если только $S$ пустой).

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

В упражнении, $S$ является равномерно случайным, и $T_i$ зависит только от $R$ (и неустановленный ключ для HMAC в случае $T_3$, но давайте проигнорируем это), и все указывает на $R$ быть независимым от $S$. Таким образом $T_i$ быть независимым от $S$.

Вышеупомянутое, размер вещей и $K_i$ строится как $K_i=T_i\oплюс S$, достаточно, чтобы сделать вывод о

сколько бит энтропии $K_1$, $K_2$, $K_3$ и $K_4$ имеют

и это остается в качестве упражнения для читателя.

sanscrit avatar
флаг ua
Спасибо. Могу ли я заключить, что, поскольку у меня уже есть действительно случайные числа в качестве входных данных, чтобы расширить $R$ для построения $T_i$, более сложные и ресурсоемкие операции, такие как sha256 или hkdf_expand, не дают мне ничего (учитывая, что я буду использовать XOR с $S $ позже) и достаточно просто повторить $R$ (чтобы построить $T_1$)?
fgrieu avatar
флаг ng
@санскрит. Дело в том, что независимо от того, какой процесс строит $T_i$ того же размера, что и $S$, и независимо от равномерно случайного $S$ (в том числе, строит $T_i$ как функцию от $R$, не зависящую от $S$ ), можно сделать вывод об энтропии в $K_i=T_i\oplus S$. Это не совсем то, что вы утверждаете выше. В частности, вас не волнует, что $R$ равномерно случайна, важно только то, что она не зависит от $S$ (и что $S$ равномерно случайна).

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

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