Рейтинг:4

Как безопасно получить ключ из списка отсортированных случайных байтов?

флаг us

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

Каков был бы лучший подход к этому вопросу?

Maarten Bodewes avatar
флаг in
Я предполагаю, что разрешены повторяющиеся значения байтов? В противном случае после 256 байт остается нулевая энтропия. Я пытаюсь придумать расчет того, сколько энтропии существует для определенного количества байтов, но терпит неудачу.
флаг us
Да, повторяющиеся значения разрешены. Спасибо
Maarten Bodewes avatar
флаг in
Хорошо. После того, как мы узнаем, как получить 128-битную энтропию с упорядоченными байтами, вы можете просто использовать KDF для получения ключа. Некоторые шифры также могут использовать ключ любого размера и формы, поэтому вы даже можете использовать байты напрямую, если у вас их достаточно (но я, вероятно, по умолчанию использую KDF, чтобы быть уверенным).
kelalaka avatar
флаг in
Это проблема вероятности, учитывая 16 ячеек с номерами от 0 до 255 в порядке возрастания, и разрешены повторения. [Вероятность увеличения последовательности] (https://www.cut-the-knot.org/Probability/IncreasingSequence.shtml)
kelalaka avatar
флаг in
Интересуется источником проблемы. Каков источник, почему вы получаете возрастающие случайные последовательности?
kelalaka avatar
флаг in
Чтобы получить точный ответ, вам нужно определить источник байтов. У вас есть источник, который производит возрастающую последовательность байтов, или источник создает вам случайные байты, после чего вы их сортируете.
Рейтинг:4
флаг ru

Предполагая, что вы знаете, что ваш источник создает байты IID, в этом случае у вас есть выборка из мультиномиальное распределение с $к=256$. Если у вас есть хорошее представление о вероятности каждого байта (например, 1/256, если они равновероятны), то вы можете вычислить энтропию в распределении, которая будет расти с ростом $n$ (размер массива), как предложено в комментариях. Формула энтропии приведена в статье в Википедии.

Однако энтропия Шеннона все еще может скрывать индивидуальные вероятности, которые возникают слишком часто для хорошего криптографического ключа. Вместо этого вы должны убедиться, что минимальная энтропия $H_\infty$ несколько превышает требуемый размер ключа. Для равновероятных байтов и для $256|n$, это будет $$-\log \left(\frac{n!}{\left(\frac n{256}\right)!^{256}}256^{-n}\right) .$$

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

ETA: @fgrieu запрашивает формулу минимальной энтропии для более общих значений $n$. Следующее более громоздко, но я думаю, что оно правильно отражает модальное значение полинома. За $n=256d+r$ с $0\le r<256$ формула $$-\log \left(\frac{n!}{(d!)^{256-r}((d+1)!)^r}256^{-n}\right) .$$

Paul Uszak avatar
флаг cn
Это _"отсортированные байты"_, следовательно, НЕ I.I.D. Таким образом, также не может быть равновероятным. Так что простой Шэннон здесь не подходит.
Daniel S avatar
флаг ru
@Paul Я неправильно понял? Я понял, что вопрос означает, что байты были сгенерированы методом IID, а затем отсортированы.
kelalaka avatar
флаг in
Да, вы это сделали. Массив отсортирован, и на вопрос нельзя полностью ответить. И я не уверен, что это чистое любопытство со стороны ОП. Если новичок, всегда заботьтесь о том, что это может быть hw.
флаг us
Спасибо за ответ. Причина, по которой я спрашивал, заключалась в том, что у меня есть доступ к квантовой машине, которую я надеялся использовать для генерации ключей шифрования, но результаты, которые я получил от повторных выстрелов, содержат результаты, отсортированные, а не в хронографическом порядке.
kelalaka avatar
флаг in
Если результат отсортирован, как он может быть случайным?
флаг us
Как заметил @DanielS, случайность исходит не от самих чисел, а от того, как часто они встречаются. По крайней мере, я так понял его ответ.
Daniel S avatar
флаг ru
@fgrieu: Спасибо за орлиный взгляд: я пропустил факториал, который, очевидно, имеет большое значение! Обратите внимание, что формула верна только для $256|n$. Это журнал модальной вероятности в полиномиальном распределении.
fgrieu avatar
флаг ng
@Daniel: я согласен с новой формулой как минимум для $n=0$ и $n=256$ (для $0$ и $364,004$ бита минимальной энтропии). Формула для промежуточных значений была бы хороша.

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

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