Смещения и корреляции

Главной проблемой подобных систем являются возможные закономерности в генерируемой последовательности. Используемые физические процессы могут быть случайны, но между физическим процессом и компьютером находятся различные измерительные инструменты. Эти инструменты могут легко привести к появлению проблем.

Способом устранить смещение, или отклонение, является XOR нескольких битов друг с другом. Если случайный бит смещен к 0 на величину e, то вероятность 0 можно записать как:

P(0) = 0.5 + e

XOR двух из таких битов дает:

P(0) = (0.5 + e)²+ (0.5 - e)² = 0.5 + 2e²

Те же вычисления для XOR 4 битов дают:

P(0) = 0.5 + 8e⁴

XOR mбитов экспоненциально сходится к равной вероятности 0 и 1. Если известно максимальное смещение, которое допустимо в вашем приложении, вы можете вычислить, сколько битов вам нужно объединить с помощью XOR, чтобы уменьшить смещение до этого значения.

Еще лучше рассматривать биты попарно. Если 2 бита одинаковы отбросьте их и взгляните на следующую пару. Если 2 бита различны, используйте первый бит в качестве выхода генератора. Это полностью устраняет смещение. Другие методы уменьшения смещения используют распределение переходов сжатие и быстрое преобразование Фурье [511].

Потенциальной проблемой обоих методов является то, что при наличии корреляции между соседними битами эти методы увеличивают смещение. Одним из способов исправить это является использование нескольких случайных источников. Возьмите четыре случайных источника и выполните XOR битов друг с другом или возьмите два случайных источника и взгляните на их биты попарно.

Например, возьмите радиоактивный источник и присоедините счетчик Гейгера к вашему компьютеру. Возьмите пару шумящих диодов и записывайте в качестве события каждое превышение определенного значения. Измерьте атмосферный шум. Извлеките из каждого источника случайный бит и выполните их XOR друг с другом, получая случайный бит. Возможности бесконечны.

Одно то, что генератор случайных чисел смещен не обязательно означает его бесполезность. Это только означает, что он менее безопасен. Например, рассмотрим проблему Алисы, генерирующей 168-битовый ключ для тройного DES. A все, что у нее есть, - это генератор случайных битов со смещением к 0: с вероятностью 55 процентов он выдает нули и с вероятностью 45 процентов - единицы. Это означает, что энтропия на бит ключа составит только 0.99277 (для идеального генератора она равна 1). Мэллори, пытаясь раскрыть ключ, может оптимизировать выполняемое вскрытие грубой силой, проверяя сначала наиболее вероятные ключи (000 . . . 0) и двигаясь к наименее вероятному ключу (111 . . . 1). Из-за смещения Мэллори может ожидать, что ему удастся обнаружить ключ за 2¹⁰⁹ попыток. При отсутствии смещения Мэллори потребуется 2¹¹¹ попыток. Полученный ключ менее безопасен, но это практически неощутимо.