Будущее анализа ГСЧ
Как узнать, действительно ли что-то случайно? При тестировании генераторов случайных чисел (ГСЧ) на случайность вы быстро сталкиваетесь с дилеммой «действительно ли это случайность». Как существа, ищущие шаблоны, мы, естественно, постоянно ищем шаблоны. Как и многие другие вещи, случайность бывает разной. В большинстве случаев генераторы псевдослучайных чисел (ГПСЧ) в основном создают случайность с множеством неслучайных процессов.
Как узнать, что что-то случайно?
Случайно ли «111111»? Или «0100100101001011110111010»? Сложно сказать. Почему? Потому что в тот момент, когда вы начинаете определять параметры случайности, вы теряете свою случайность.
Лучший метод, который придумали ученые и программисты, - это создать серию тестов. Существует множество тестов и множество наборов тестов. Популярные тесты включают набор тестирования ГСЧ NIST, набор тестов Dieharder [8], тест Кнута, тест Crypt-x и этот список можно продолжить. ГСЧ бывают всех форм и размеров, поэтому вы можете себе представить, что будет сложно организовать тестирование для всех различных типов генераторов случайных чисел.
Тестирование процесса генератора случайных чисел состоит из двух этапов. Для начала вам нужен источник энтропии [1], который невозможно угадать, как погода. Во-вторых, вам нужен детерминированный алгоритм, чтобы разложить начальное число на множество последовательностей ключей и т.п. Обычно тестирование начинается с проверки вашей энтропии.
Предварительное тестирование ГСЧ
Первая проблема, с которой вы сталкиваетесь при попытке определить, что является случайным, заключается в том, что почти все может быть случайным.
Как видно выше, практически невозможно точно доказать, что последовательность чисел случайна. Создание последовательности с миллионом «0» может быть очень случайным, но не очень желательным. Легко сделать корреляцию на основе того, что логически выглядит случайным, но действительно ли это случайность? Трудно сказать. К счастью, существует множество тестов, которые могут дать вам довольно хорошую оценку случайности.
Предвзятый тест
Первое, что вам нужно сделать, это проверить свой источник энтропии с помощью предвзятого теста. Как и на рисунке выше, вы не хотите, чтобы ваше число было смещено или смещено в сторону 0 или 1. Чтобы исправить это, очень известный математик по имени Джон фон Нейман разработал алгоритм коррекции перекоса. Этот процесс исправления перекоса очень прост, но при этом очень эффективен.
Он основан на подбрасывании монеты, поскольку есть только две переменные: «1» и «0». Общий вывод должен быть примерно равным количеством единиц и нулей. Чтобы сохранить это равное соотношение, алгоритм коррекции перекоса просматривает каждые два подбрасывания и сравнивает их. Если два бита в паре идентичны (т.е. 00 или 11), оба бита отбрасываются. Если два бита различны (например, 01 или 10), первый бит добавляется к потоку обработанных битов.
Обратной стороной является потеря значительного количества случайных данных [8]. Коррекция также будет принимать случайные данные, когда источник уже расшит. Но опять же, это всего лишь базовый тест для анализа источника энтропии. Следующим шагом является оценка генератора детерминированных случайных чисел, который будет усиливать начальные числа во множестве чисел.
Визуальный тест
Один из быстрых и простых способов определить качество генератора случайных чисел - это создать быстрый визуальный тест. Человеческий мозг довольно хорошо распознает закономерности. Визуальные эффекты могут стать отличным тестом снимков, чтобы увидеть общие закономерности, которые вы могли пропустить, углубляясь в электронные таблицы и числа. «Случайное блуждание» - это широко используемый метод для визуализации случайности и моделирования. Генерация битов - это еще один способ обнаружить закономерности, которые нельзя увидеть, просто глядя на числовые последовательности.
Тест информационной энтропии
Генераторы случайных чисел в значительной степени ориентированы на получение больших вероятных результатов. Вот где в игру вступает информационная энтропия. В случайности задано количество исходов, информационная энтропия - это вероятность каждого отдельного исхода [7]. Чем больше возможных переменных содержится в каждом бите информации, тем сложнее предсказать, какой будет следующий бит, на основе битов, которые вы уже видели.
Этот график выше показывает низкий уровень информационной энтропии в данных в процентах от теоретического максимума. Вы не хотите иметь более вероятные результаты для определенных значений, таких как «A» 50%, вероятность, когда на самом деле вам нужна равная вероятность (см. Изображение ниже). В большинстве случаев высокий уровень информационной энтропии указывает на случайность данных, а низкий уровень указывает на то, что данные не являются случайными.
Информационная энтропия - это не просто средний объем информации, охватываемой событием, с учетом всех результатов. Это также то, сколько информации вы можете упаковать в биты. Вы хотите создать среду, в которой все результаты равновероятны.
В Linux даже есть сообщение об ошибке, в котором говорится, что ваш компьютер не может продолжить работу без нажатия нескольких клавиш для увеличения энтропии [7]. Сообщение, описанное на изображении выше, - это один из самых распространенных способов сбора энтропии в программах. Ваш источник энтропии - это не единственный ваш важный фактор - насколько важны и насколько велики значения. Все сводится к той же концепции, что требуется порог энтропии для генерации реальной случайности.
Набор тестов NIST
Существует почти бесконечное количество статистических тестов, которые вы можете запустить на ГСЧ. Каждый тест направлен на обнаружение чего-то, что не будет считаться случайным или чего можно ожидать от случайной последовательности чисел. Поскольку определение неслучайности - это обнаружение шаблонов, а шаблоны могут варьироваться и отличаться бесконечным количеством способов, нет надежного способа рассмотреть набор тестов для подтверждения случайности.
Национальный институт стандартов и технологий (NIST) предоставляет очень полезное руководство по тестированию ГСЧ. Тесты NIST являются самыми популярными и разнообразными.
Статистика частоты (монобит)
При генерации битов случайных чисел 0 и 1 соотношение между ними обычно оказывается 1: 1 для действительно случайной последовательности. Чтобы воспроизвести этот процесс, нам нужно исследовать поток чисел как блоки.
Для каждого блока рассчитайте, чтобы убедиться, что соотношение единиц и нулей настолько близко к 0,5, насколько это было бы действительно случайной последовательностью. Если соотношение слишком мало, это означает, что соотношение отключено (слишком много единиц). Довольно простой тест. Если этот блок склонен к отказу, то он, вероятно, не пройдёт многие другие тесты.
Статистика частоты (блокировки)
Так же, как и тест частоты (монобит), этот тест проверяет, совпадает ли количество сгенерированных нулей и единиц с числом, сгенерированным из действительно случайного источника [5]. Однако способ его работы отличается. Этот тест принимает поток чисел как серию блоков. Затем каждый блок делится на подблоки. Затем каждый подблок анализируется на предмет оптимального соотношения единиц и нулей, которое близко к тому, как ожидается, что действительно случайное соотношение единиц и нулей будет выглядеть.
И если вы спрашиваете себя, как выглядит действительно генератор случайных чисел, не смотрите дальше. Вот настоящий генератор случайных чисел, основанный на радиоактивном распаде [4].
После анализа подблоков вычисляются значения отношения, и если соотношение меньше 0,5, то этот блок не проходит проверку. Это способ микросканировать биты на предмет неточностей. Помните, что хороший генератор случайных чисел также будет создавать блоки, которые не выглядят случайными, поэтому мы ожидаем, что некоторые из блоков не пройдут проверку. (На самом деле, мы должны быть подозрительными, если все блоки прошли проверку.
Тестирование на «запуски»
ГСЧ создают поток битов (единицы и нули). «Запуск теста» разбивает поток на распознаваемые шаблоны и вычисляет, похож ли он на действительно случайный поток битов. Прогон состоит из идентичных битов в потоке, например 0000 или 111111111.
Основное внимание в этом тесте уделяется суммированию общего количества запусков в последовательности. Тест проверяет количество битов, которые переходят из 0 → 1 или 1 → 0. Это «прогоны» в последовательности. Прогоны используются для оценки «P-значения».
Это P-значение - это ожидаемое количество прогонов в блоке. Блоки не проходят тест, когда значение P слишком мало, что означает, что количество прогонов в блоке меньше (или больше) по сравнению с результатами истинного случайного числа «прогонов».
Для этого теста необходим частотный тест, чтобы вычислить начальные переменные, чтобы начать работу, и это верно и для многих других тестов. Не существует единого теста ГСЧ, который подходил бы всем, и поэтому большинство тестов проводится в виде комплектов. Обычно их объединяют вместе, чтобы обеспечить максимальную уверенность в случайности.
Самая длительная серия тестов в блоке
Этот тест фокусируется на M-битовых блоках. Как видно выше, в этом тесте подсчитывается длина самого длинного прогона тестов, а затем сравнивается его с тем, что вы ожидаете от самого длинного прогона действительно случайного генератора [5].
Ранговый тест двоичной матрицы
Бинарный тест предназначен для анализа векторных паттернов в матрице потока случайных чисел. Позвольте мне разбить это на более понятные термины. Цель этого теста - найти линейную зависимость в сегментах потока случайных битов [5]. Это паттерны, которые без матриц вы бы не увидели.
Линейно зависимый означает, что выходы находятся на одной линии. Есть линейный узор. Двоичная матрица делает это с помощью двоичных матриц. По сути, это смешивание потока случайных битов и проверка наличия каких-либо конкретных шаблонов.
Тест на соответствие шаблонов без перекрытия
Этот тест предназначен для поиска апериодических паттернов [5]. Это непериодический паттерн. Короче говоря, этот тест в основном ищет шаблоны, которые могут перекрываться интересными способами, например, на рисунке ниже:
Апериодический набор прототипов (источник Википедия)
Процесс тестирования в основном проходит через m-битное окно и пытается найти шаблоны [5]. Если шаблонов не найдено, он переходит к следующему биту и повторяется. Если образец найден, тогда if возобновляет тест до бита после найденного образца.
Доказуемо истинные будущие тесты ГСЧ
NIST описывает несколько различных тестов, на самом деле они насчитывают более 14, о которых вы можете прочитать больше здесь. Мы рассмотрели только 6 из них, которые, по мнению автора, были особенно интересными. ГСЧ, даже истинные ГСЧ, вряд ли пройдут все тесты. Фактически, если бы они смогли пройти все свои тесты, это, вероятно, было бы немного подозрительно, поскольку тесты NIST предназначены для анализа выходных данных в нескольких векторах, многие из которых перекрываются.
Какова форма следующего поколения этих типов тестов на случайность? Войдите в машинное обучение (ML). Машинное обучение меняет практически все, что мы делаем сегодня. Он узнает, что вам нравится и когда вам что-то нужно - насколько машинное обучение может проникнуть в нашу жизнь, пока неизвестно. Мы в Unitychain считаем, что машинное обучение идеально подходит для анализа случайности, в конце концов, машинное обучение - это определение закономерностей, а качественный ГСЧ не должен иметь никаких очевидных закономерностей.
Вот почему мы анализируем выходные данные ГСЧ наших алгоритмов преобразования с помощью машинного обучения. Теоретически качественный ГСЧ не генерирует паттернов. Следовательно, чем меньше мы способны обнаруживать аномалии или очевидные закономерности, тем лучше работает наш ГСЧ. Еще слишком рано говорить о том, превзойдет ли этот подход тесты NIST, но если да, то мы определенно услышим о нем гораздо больше.
У нас есть более интересные новости и обновления, которые мы опубликуем в ближайшем будущем, о нашем протоколе RNG. А пока помните, как важно "подвергать себя как можно большему количеству случайностей". - Бен Касноча
Никогда не знаешь, что откроешь.
Использованная литература:
[1] Границы энтропии и статистические тесты.
[2] Изучение псевдослучайности с помощью искусственной нейронной сети.
[3] Криптоаналитические атаки на генераторы псевдослучайных чисел.
[4] Истинные случайные числа, порожденные радиоактивным распадом.
[6] ПРИМЕРЫ РАННЕГО КОМПЬЮТЕРНОГО ИСКУССТВА.
[7] Помогаем генератору случайных чисел набрать достаточную энтропию с помощью rng-tools.
