Тестирование энтропии с помощью NIST STS

1 min


Примерно в это же время в прошлом году я писал об энтропийном экстракторе, используемом в µRNG. Он принимает три смещенных случайных битовых потока и возвращает несмещенный битовый поток, при условии, что каждый поток имеет как минимум 1/3 бита минимальной энтропии.

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

Чтобы создать смещенный поток битов, я сначала создал несмещенный поток битов, используя генератор случайных чисел PCG, а затем взял побитовые или последовательные выборки. В нотации C я создал два 32-битных целых числа без знака u и v и использовал u|v, Результирующие биты равны единице три из четырех, поскольку бит равен 0, только если оба соответствующих бита равны 0. Мин-энтропия результирующего потока

-журнал2 макс (0,25, 0,75) = 0,415

который больше 1/3, поэтому мы должны иметь возможность применять энтропийный экстрактор µRNG. Для этого мы создаем три битовых потока. Позволять , б, и с быть 8-битными байтами, каждый из другого потока. Затем мы объединяем их в

×б + с

и использовать это как один байт вывода. Таким образом, требуется три байта ввода для получения одного байта вывода, что и следовало ожидать, поскольку мы начинаем с источников, которые могут содержать только 1/3 бита минимальной энтропии на бит вывода.

Умножение и сложение выше выполняются в поле Галуа GF (28). Это означает, что умножение может быть не таким, как вы ожидаете, а сложение – это XOR, то есть битовое исключение или. Умножение такое же, как и при шифровании AES.

Есть несколько тестовых наборов, которые мы могли бы использовать – DIEHARDER, PractRand, TestU01 и т. Д. – и ожидаем, что вскоре я напишу о них больше, но в этом посте мы сосредоточимся на NIST Statistic Test Suite или STS. Этот набор включает в себя следующие 15 тестов

  • Частота (монобит)
  • Частотный тест в блоке
  • Запускает тест
  • Тест для самого длинного пробега в блоке
  • Тест ранга двоичной матрицы
  • Тест дискретного преобразования Фурье (спектральный)
  • Неперекрывающийся тест соответствия шаблонов
  • Тест совпадения шаблонов с перекрытием
  • Универсальный статистический тест Маурера
  • Тест линейной сложности
  • Серийный тест
  • Приблизительный энтропийный тест
  • Тест совокупных сумм (cumsum)
  • Случайный экскурсионный тест
  • Случайный вариант экскурсии

Смотрите NIST Специальная публикация 800-22Набор статистических тестов для генераторов случайных и псевдослучайных чисел для криптографических приложений.

Когда мы запускаем ввод PCG в одиночку через STS, он проходит летающими цветами. Если мы выполним вывод PCG после ИЛИ пар целых чисел без знака вместе, то тест провалится эффектно, извергая предупреждения о недостаточном количестве. Но если мы возьмем три потока смещенных битов, каждый из которых потерпит неудачу, и сохраним извлеченный вывод, он пройдет все тесты, как и в случае с исходным выводом PCG.

В каждом случае я тестировал один миллион 32-битных целых чисел без знака. В необъективном случае я выбрал три миллиона целых

Обратите внимание, что в нашем примере мы знаем величину смещения, потому что мы намеренно создали смещение. Вы, возможно, не знаете смещения или, что эквивалентно, минимальной энтропии в целом. Пока минимальная энтропия больше 1/3, энтропийный экстрактор работает.

Подробнее о тестировании ГСЧ


0 Comments

Ваш адрес email не будет опубликован. Обязательные поля помечены *