Рейтинг:3

Разница между неравномерно случайным и равномерно случайным

флаг bt

Я читаю о функциях получения ключей (KDF) и в разделе Книга о реальной криптографии Дэвид Вонг, сравнение проводится с генератором псевдослучайных чисел (PRNG). Говорят, что одно из отличий состоит в том, что KDF принимает неравномерно случайный ввод произвольной длины, в то время как PRNG использует равномерно случайный k-битный ключ. Несмотря на то, что оба имеют равномерно случайный вывод произвольной длины.

В основном говорится, что основные отличия заключаются в том, что KDF не ожидает полностью равномерно случайного секрета в качестве входных данных (пока у него достаточно энтропии).

Что именно подразумевается под неравномерно случайным и равномерно случайным в этом контексте? Кроме того, что означает энтропия в этом контексте?

Кажется, что лучшее понимание этих терминов поможет лучше понять разницу между KDF и PRNG.

Ievgeni avatar
флаг cn
Не могли бы вы добавить цитату и/или ссылку, чтобы иметь больше контекста?
Рейтинг:5
флаг ng

Равномерно случайно означает, что все возможные значения равновероятны.Где «все возможные значения» будут значениями в некотором наборе, который, если не определено иное, представляет собой набор битовых строк размера рассматриваемой переменной.

Примером неоднородного ввода в KDF является ситуация, когда KDF получает результат обмена ключами Диффи-Хеллмана в $\mathbb Z_p^*$ с $г$ генератор всей этой группы. Вводом KDF может быть значение $g^{a\,b}\bmod p$ выражается в виде строки байтов (например, с обратным порядком байтов) фиксированного размера (размер $р$, округленное до числа, кратного 8 битам), с $а$ и $b$ случайные эфемерные секреты. Некоторые строки байтов, которые допустимы на входе KDF, никогда не могут встречаться в этом фактическом использовании: входные строки байтов, которые не представляют целое число в $[1,p-1]$, включая строки байтов all-0x00 и all-0xFF. А среди тех, до которых можно добраться, квадратичные вычеты (достигнутые, когда либо $а$ или же $b$ четные) встречаются в три раза чаще, чем неквадратичные остатки (достигаются при $а$ и $b$ являются нечетными).

Другим примером неоднородного ввода является парольная фраза, которая является обычным вводом для некоторых KDF (таких как современный Argon2 или устаревший PBKDF2).


Энтропия Шеннона (в битах) процесса, создающего переменную $Х$ это может занять $n$ значения различные значения с вероятностью $p_i$ с $0\le i<n$, таким образом с таким образом $1=\displaystyle\sum_{0\le i<n}p_i$ и $0\le p_i\le1$, определяется как количество $$H(X)=\sum_{0\le i<n\text{ и }p_i\ne0}p_i\log_2(1/p_i)$$

Другая полезная энтропия мин-энтропия, определяется как $$H_\text{min}(X)=\log_2(1/\max_{0\le i<n}{p_i})$$

Он всегда держит $H_\text{мин}(Х)\le Н(Х)$.

Процесс, создающий $b$битовая строка $Х$ имеет $b$-битовая энтропия (для любого определения) тогда и только тогда, когда она генерирует равномерно случайные битовые строки. При неравномерной случайности его энтропия меньше $b$-бит, вплоть до $0$ когда он всегда генерирует одну и ту же битовую строку.

Неформально на входе KDF достаточно энтропии, если выход этого KDF является по существу равномерно случайным (для более или менее строгого определения этого). Это возможно, когда входные данные KDF не являются равномерно случайными, но только если эти входные данные имеют (минимальную) энтропию, по крайней мере, выходную ширину KDF $b$ немного (или хотя бы $b$ такой, что $2^б$ не поддается исчислению противниками). И тогда это не является строго достаточным условием.

dade avatar
флаг bt
в основном, если все возможные значения - не равновероятны - из-за каких-либо ограничений - тогда у вас неравномерная случайность?
fgrieu avatar
флаг ng
@dade: вот и все. За исключением того, что мы говорим «неравномерно случайный» или «неравномерный случайный».
dade avatar
флаг bt
Тогда связанный с этим вопрос ... как «неравномерно случайный» может иметь «достаточную энтропию»?
Paul Uszak avatar
флаг cn
@dade Не заморачивайся - это просто. Представьте, что вам нужно 128 штук, чего достаточно для криптографии. Если он поступает со скоростью 8 (равномерное распределение внутри байтов), то вам нужно всего 16 переходов. Но вы можете получить 128 «этих» со скоростью 5,3 (странное распределение), если вы возьмете 25 попыток.
Рейтинг:4
флаг cn

Что именно подразумевается под неравномерно случайным и равномерно случайным в этом контексте? Кроме того, что означает энтропия в этом контексте?

Это случайность с неравномерным распределением, показанная как функция массы вероятности (PMF):

пмф

Вы можете видеть, что нули преобладают. Если бы случайность была равномерной, все значения совпадали бы с синей линией при p = 0,0039, что соответствует $\фракция{1}{256}$. Поскольку в криптографии нас интересует мин. энтропия $\big(H_{\infty} = -\log_2 (p_{max}) \big)$, приведенное выше распределение (если I.I.D) имеет $H_{\infty} \примерно 5,3$ бит/байт.

Если бы PMF была равномерно случайной, мы бы имели $H_{\infty} = 8$ бит/байт. Это максимальная энтропия, характерная для равномерных распределений.

Таким образом, неравномерная случайность входит в KDF (возможно, пароль типа «123456»), а получается однородная случайность.

fgrieu avatar
флаг ng
«неоднородная случайность входит в KDF, а однородная случайность выходит» _if_ на входе достаточно энтропии.
Paul Uszak avatar
флаг cn
@fgrieu Ах, старый каштан - разница между колмогоровской сложностью, криптографической энтропией и информационной энтропией. Мы действительно должны решить это однажды...

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

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