Рейтинг:2

Метод постобработки для генератора истинных случайных чисел

флаг de

Я нахожу метод постобработки для улучшения случайности генератора истинных случайных чисел. В частности, TRNG может пройти NIST SP 800-22 после применения постобработки.

Я попытался применить генератор псевдослучайных чисел Enocoro-128_v2 в качестве метода постобработки для TRNG. TRNG поставит семена для Enocoro. Затем работает Enocoro и генерирует вывод. После применения этого метода результат можно улучшить. TRNG может пройти NIST SP 800-22.

Мой вопрос: почему Генератор псевдослучайных чисел Enocoro-128_v2 может улучшить производительность TRNG?

SAI Peregrinus avatar
флаг si
Каково ваше определение «Генератора истинных случайных чисел»? Что делает его «истинным» в отличие от обычного аппаратного генератора случайных чисел? IME a TRNG — это гипотетическая конструкция, очень похожая на случайный оракул, который испускает совершенно равномерно распределенные некоррелированные непредсказуемые биты, поэтому нет необходимости обрабатывать выходные данные. Это полезная конструкция для доказательства некоторых теорем, а не реальное устройство.
флаг de
Настоящий генератор случайных чисел означает, что мы используем источники физического шума (кольцевой осциллятор, PLL, метастабильный генератор и т. д.) для генерации случайного числа.
Рейтинг:0
флаг cn

Он не может, даже не зная, как работает «Генератор псевдослучайных чисел Enocoro-128_v2», так как PRNG будет иметь $H_{выход} < H_{вход}$

Кажется, у вас есть источник энтропии, который предположительно генерирует случайные выборки Колмогорова. Они имеют неравномерное распределение, которое вы сможете увидеть из функции/гистограммы массы вероятности, и что оно не соответствует SP 800-22. И они могут быть автокоррелированы. Это означает $H_{\infty} \ll 1$ бит/бит. Запустите NIST 800 90b ea_iid тест для подтверждения.

Размазывание ГПСЧ поверх просто маскирует основную энтропию Колмогорова предсказуемой псевдоэнтропией ($H_{\infty} =0 $ с точки зрения TRNG). Некоторые люди охарактеризовали такую ​​конструкцию как аппаратный ГПСЧ. Однако для того, чтобы любой TRNG был достоин этого имени, он должен удовлетворять наиболее важному аспекту конструкции TRNG, а именно тому, что генерируемая энтропия > выходная длина. Более формально: $H_{выход} \ngtr H_{вход}$.


С небольшой подтасовкой PRNG любой источник энтропии может производить выходную энтропию с почти бесконечной скоростью. Например, встроенный в чип Intel TRNG (RDRAND) предположительно производит почти 2 Гбит/с. Четко Мусор и чушь. Этот чип явно имеет $H_{выход} \gg H_{вход}$.

Итак, пост-экстракция, слабослучайный источник кажется появиться с гораздо большей случайностью и отклонением от совершенства, ограниченным Лемма об остатках хэша:-

$$ \epsilon = 2^{-(sn-k)/2} $$

где у нас есть $n$ = входные биты в $s$ бит/бит сырой энтропии из источника, $к$ - количество выходных битов из экстрактора (и $<n$). $\эпсилон$ отклонение от идеально однородного $к$ строка битовой длины, т.е. $H(k) = 1 - \epsilon$ бит/бит. НИСТ признает, что $\эпсилон < 2^{-64}$ для криптографических приложений.

Однако, $\эпсилон$ можно легко сделать намного меньше. я стремлюсь к $2^{-128}$. Для экстрактора вы можете использовать SHA-512 ($к=512$), чтобы минимизировать потерю энтропии. Вы можете увидеть $n/k$ отношения и относительная эффективность в этих диаграммах: -

диаграмма 1

диаграмма2


Итак, в заключение, вам не нужно/не следует использовать PRNG поверх вашего источника энтропии. Если вы делаете TRNG, сделайте его правильным TRNG. Скорость не так уж и важна.

В конце концов, что можно сделать со всем этим колмогоровским хламом?

Maarten Bodewes avatar
флаг in
Пример Intel напрямую следовал утверждению, что энтропия должна быть больше, чем размер вывода. Я отредактировал ответ, чтобы было ясно, что Intel ** не ** делает это. Обратите внимание, что для Intel RDRAND был определен как «Относительно таксономии RNG, обсуждавшейся выше, DRNG следует модели RNG каскадной конструкции, используя резидентный источник энтропии процессора для **повторного заполнения аппаратно-реализованного CSPRNG.**». если вы хотите атаковать Intel, вам, вероятно, придется атаковать RDSEED, а не RDRAND (что вы, кажется, делаете в своем ответе, связанном с).
Maarten Bodewes avatar
флаг in
Не могли бы вы попробовать добавить немного меньше негативных эмоций в свои посты? Такие утверждения, как теперь удаленное «... и мне все равно», вызовут негативные чувства, которые не улучшат качество ответа. Точно так же вы указываете, что у Intel «мусорный» RDSEED, но ссылаетесь только на свой собственный ответ. Почему бы не назвать это «крайне сомнительным»? Это привело меня к более раннему отрицательному голосованию, прежде чем я решил, что на самом деле согласен с сутью того, что вы записываете, и выполнил редактирование, чтобы сделать его более понятным / немного более формальным.
Maarten Bodewes avatar
флаг in
Может быть, вы могли бы привести пример размера ввода для SHA-512 w.r.t.ожидаемое количество битов, генерируемых энтропийным устройством? Я предполагаю, что впоследствии вы используете конкатенацию сгенерированных хэшей?

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

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