О рандоме, энтропии и статистических тестах
Рандом вездесущ. Рандом необходим. На рандоме строится криптография - верная служанка информационной эры и коммуникации как таковой. Но что есть - рандом? Просто случайные числа? А как это - случайные? Почему, к примеру, последовательность 1, 2, 3, 4, 5, 6 не является рандомной? Как числа можно оценить на "рандомность"? И откуда эти рандомные числа берутся вообще?
Вступление: ГСЧ и ГПCЧ
ГСЧ - Генератор случайных чисел.
ГПСЧ - Генератор псевдо-случайных чисел.
Разница между случайными (они же истинно-случайные) и псевдо-случайными числами основательна. Источником случайных чисел предстают физические процессы, протекающие в реальном мире, результат которых тяжело или невозможно предсказать, даже имея начальные условия. Иными словами, нас интересует хаос. Такими могут служить, к примеру, перепады напряжения (внешние помехи вносят достаточный уровень шума), погода, распад урана, восковые лампы. В общем, всё, что несёт в себе хаос.
Однако, если абстрагироваться, откуда может браться хаос в компьютере? В машине, детерминированной по природе своей, не имея иных внешних источников неопределённости?
А фокус в том, что его и правда нет.
Если с физическими источниками случайных данных всё ясно, то вот компьютеру приходится создавать хаос самостоятельно (ну, почти). Генератор псевдо-случайных чисел представляет из себя самое обычное уравнение, которое берёт на вход 1 или 2 параметра: состояние генератора и опционально хэш, и возвращает 2 значения: новое состояние и непосредственно случайное число. Подробно о том, что это за уравнение, какие есть виды генераторов, и чем они отличаются - будет описано в следующей статье (если будет).
Дополнительно: (неожиданные) преимущества ГПСЧ перед ГСЧ
У генераторов истинно-случайных чисел есть два основных недостатка:
Иногда требуется много рандома. Скажем, 8гб/с. Физические источники, как, например, те же восковые лампы или полураспад урана, условно не могут обеспечить такой поток, не будучи комично масштабированными. При этом, и качество иногда может страдать: никто не отменяет 1024 выключенных бита подряд, например. Пускай вероятность этого и довольно низка, отнюдь физические процессы иногда могут таки вносить некую предвзятость.
Энтропия
Преамбула 1: энтропия есть понятие абстрактное, и её определение может (и будет) разиться кардинально в зависимости от раздела, в котором его собственно и определяют. Посему следует заранее оговорить, что в дальнейшем, говоря об энтропии, речь будет идти об оной из теории информации, она же - энтропия Шеннона.
Преамбула 2: дальше будет использован логарифм по основанию 2. Основание, на самом деле, может быть взято произвольное, однако мы будем говорить о двоичных последовательностях, а следовательно - юнитом важно взять именно бит.
Возьмём некую систему с вероятностями. Имея набор исходов и вероятность каждого из них, мы можем оценить, насколько эта система будет случайной, или же непредсказуемой. Эта оценка и называется энтропией. Фактически, энтропия показывает, насколько равномерно распределены вероятности: чем более равновероятны все исходы, тем больше непредсказуемость системы. Если один из исходов вероятностно доминирует над другим, тогда система становится более предсказуемой, поскольку этот доминирующий исход мы получаем чуть чаще, чем другие - соответственно, и предугадать результат становится чуть проще. Такой доминирующий исход также называется предвзятым: тогда мы говорим, что система более предвзята по отношению к этому исходу.
Математически, мы можем оценить, насколько удивительным является наблюдаемый исход, зная его вероятность, с помощью так званой функции "сюрприза":
(поскольку вероятность p лежит в промежутке (0, 1), то логарифм для таких значений будет отрицательным, перед ним и стоит минус.)
Соответственно, чем меньше вероятность исхода, тем более "удивительным" будет его происшествие.
Энтропия же вычисляется следующим образом:
(сумма произведений вероятности исхода на его "сюрприз". Для упрощения, эту сумму могут назвать количеством бит, требуемых для хранения исхода системы - однако это неверно, поскольку кодирование и энтропия всё же не одно и то же самое.)
Как уже и было сказано, тем больше энтропия, чем равномернее распределены вероятности. Это важное свойство для рандома в целом: имея выходное число фиксированной ширины как двоичную строку, вероятность каждого бита должна стремиться к 1/2: вероятности бита занять значение 0 либо 1 должны быть равными. Если применить формулу просчёта энтропии, то идеально честный бит будет иметь энтропию:
Поскольку биты в строке не являются взаимосвязанными, вероятность каждого отдельного бита не влияет на вероятности всех остальных, и таким образом энтропия идеального генератора чисел будет равняться ширине выходного числа. Например, идеальный генератор 32-битных чисел имеет энтропию 32, а генератор 64-битных чисел - 64. Доказывается это тривиально:
Дополнительно: слабые биты, хэш-функции
Если вероятности выпадения 0 и 1 в бите не равны, тогда такой бит называют предвзятым, или же слабым. Каждый генератор имеет свои особенности, и некоторые из них могут выдавать более слабые нижние или верхние биты, т.е. старшая либо младшая часть числа могут иметь энтропию ниже, чем противоположная. Это следует держать в уме, поскольку иногда эта информация может напрямую повлиять на производительность. Например, принимая, что хэш-функции являют собою подмножество ГПСЧ, в Go, до введения SwissMap, верхние биты хэша ключа использовались для быстрого сравнения при переборе ключей в бакете (глубокое сравнение проводилось только в случае совпадения верхних 8 битов хэша - оптимизация нацелена на ключи, сравнения которых есть операция потенциально дорогая, как, например, строки). Если бы хэш-функция выдавала слабые верхние биты, то вероятность коллизии была бы выше - следовательно, приходилось бы совершать больше глубоких сравнений, что не просто отображалось бы негативно на производительности, но и могло бы потенциально представлять вектор атаки. Что и послужило причиной появления криптографически-стойких ГПСЧ и, следовательно, хэш-функций.
Дополнительно: материал по энтропии
Для более подробного ознакомления с энтропией, рекомендую к прочтению следующую статью, на которую я в своём объяснении и опирался: https://jasonfantl.com/posts/What-is-Entropy/
Оценка рандома
Как вообще можно оценить рандом?
Но можно прогнать несколько тестов так, чтобы генератор можно было назвать "в принципе норм" или "ну плох", пусть и с некоторой вероятностью ошибиться.
Такие тесты называются статистическими. Всё, так или иначе, сводится к одному из двух:
- Последовательность достаточно рандомная: нулевая гипотеза принимается (последовательность случайна).
- Последовательность недостаточно рандомная: нулевая гипотеза отвергнута, таким образом автоматически принимается альтернативная гипотеза (последовательность неслучайна).
Теперь стоит объяснить подробнее, почему такие тесты называют статистическими. Первопричина кроется в том, что все они построены по одной и той же схеме:
- Построить референсное распределение статистик, предполагая истинность нулевой гипотезы (основываясь на предположении, что последовательность случайна).
- Посчитать статистику от последовательности.
- Сравнить полученную статистику с референсным распределением. Если наша статистика входит в, скажем, 99й персентиль, тогда последовательность принимается, как случайная.
А теперь стоит подробнее обсудить терминологию.
Статистика
Статистика сама по себе - подытоживание последовательности. В зависимости от контекста, подразумеваться может как функция от последовательности, так и результат этой функции - число. Важно понимать, что статистика и референсное распределение строятся под каждый отдельный паттерн эксклюзивно. Функция статистики приводит ряд к итоговому числу, положение в распределении которого и играет финальную роль в оценке прохождения генератором тестового кейса.
Референсное распределение
Под референсным распределением подразумевают нормальное распределение, как и функция статистики, построенное под строго определённый паттерн.
P-value
Я не уверен, присутствует ли это понятие где-либо, помимо сьюта NIST, однако это значение репрезентирует вероятность, что настоящий случайный генератор выдал бы последовательность менее рандомную, нежели рассматриваемая нами.
Critical value
Принимая, что у нас есть взаимоисключающие нулевая и альтернативная гипотезы, мы также можем построить следующую таблицу 2х2:
Ошибку II типа контроллировать нельзя, поскольку паттернов существует бесконечное количество. И если мы действительно возьмём все возможные паттерны, тогда ни одна последовательность не окажется рандомной - на совершенно любую найдётся свой паттерн, один из бесконечности. Молчаливый и внезапный проблеск девственности и одиночества, простите.
Однако с ошибкой I типа дела обстоят получше. Мы можем самостоятельно задать приемлимый порог, который и является нашим critical value, он же альфа-значение.
Альфа-значение - это и есть та крайняя (хвостовая) часть распределения, вхождение наблюдаемой статистики в которую и знаменует проваливание теста. Иными словами, задавая значение в 0.01, мы соглашаемся, что с шансом 1% случайная последовательность будет принята за неслучайную, приводя к ложно-негативному срабатыванию. На практике, мы обычно сразу получаем критическое значение статистики посредством получения среза значения, находящегося как раз на пороге распределения. Тест в таком случае считается провальным, если статистика превышает это критическое значение.
Паттерн
Паттернов есть бесконечно. Пусть и невозможно сказать достоверно, истинно случайна ли последовательность, отнюдь некоторое удовлетворяющее нас подмножество мы вынести всё же можем, оценка которого будет приемлимой для нас. Всё-таки тестируемые генераторы мы будем использовать в прикладных задачах, посему математическая безупречность более и недоступна. Всё тот же NIST test suit в пример, предоставляет набор из следующих 15 тестов:
Частотный (монобитный) тест
Рассмотрим его для наглядности вышеописанного.
Суть его сводится к тому, чтобы оценить, что вероятность каждого бита стремится к 1/2. Начнём с самого важного: ведения статистики.
В NIST пошли следующим образом: беря на вход двоичную строку,
Получая, таким образом, "баланс" между единицами и нулями в промежутке [-n, n], где n - длина строки:
Дальнейшие шаги я приведу прямиком из документа NIST:
Небольшие разъяснения: беря модуль от S, мы наш "баланс" превращаем в отклонение; делим на корень от n чтобы нормализовать данные, приведя их к промежутку [0, 1]; функция erfc - это в сущности гауссов интеграл:
Зачем он нужен - будет объяснено через один абзац.
Дабы лучше понять, зачем всё это делается, следует сделать шаг назад. Вместо всего этого, мы могли бы построить нормальное распределение N(-n, n) ещё на моменте, когда заимели баланс между единицами и нулями. А то и вовсе на порядок проще поступить: поделить сумму битов на их количество, чтобы получить среднее значение, и проверить уже его по нормальному распределению N(0, 1). Проблема здесь заключается в том, что точность теста тогда начинает зависеть от n, т.е. от длины строки. Например, последовательность 1011 вполне себе реалистична, однако перевес единиц по отношению к нулям здесь - 3/4. Можно было бы задать минимальную границу количества входных битов, тогда бы и эффект зависимости нивелировался с ростом длины входной строки. Отнюдь, даже звучит это костыльно. Да и духу математической строгости, в общем-то, мало отвечает.
И как раз гауссов интеграл решает проблему зависимости от длины строки в решении NIST. В оригинале, его назначение характеризуется, как "вероятность, что истинно-случайный генератор выдал бы последовательность менее случайную". В сущности - чем короче строка, тем больше допустимый перевес в соотношении включённых бит к выключенным.
Эпилог
В данной статье был сделан упор на определение рандома и его оценку. Вскользь были упомянуты особенности ГПСЧ и совершенно забыты криптографически стойкие ГПСЧ, однако более подробно их разновидности, особенности и различия будут описаны в следующей статье. Также малый упор был сделан на математическую составляющую - не в силу собственной некомпетентности, а лишь из прагматичных рассуждений о сохранении объёма материала в пределах разумных. Надеюсь, сия небрежность будет мне прощена.