Генерация случайных чисел Андрей Гейн
Эталон 0 1
Эталон 0 1
Генераторы
физические
Генераторы физические табличные
Генераторы физические табличные алгоритмические
Первые алгоритмы «Всякий, кто питает слабость к арифметическим методам получения случайных чисел, грешен вне всяких сомнений» Джон фон Нейман
Первые алгоритмы Метод серединных квадратов
Первые алгоритмы Метод серединных квадратов
Первые алгоритмы Метод серединных квадратов
Первые алгоритмы Метод серединных квадратов Метод серединных произведений R 0 × R 1
Первые алгоритмы Метод серединных квадратов Метод серединных произведений R 0 × R 1
Первые алгоритмы Метод серединных квадратов Метод серединных произведений R 0 × R 1 R 2 R 1 × R 2 R 3
Первые алгоритмы Метод серединных квадратов Метод серединных произведений Метод перемешивания
Первые алгоритмы Метод серединных квадратов Метод серединных произведений Метод перемешивания
Первые алгоритмы Метод серединных квадратов Метод серединных произведений Метод перемешивания
Первые алгоритмы Метод серединных квадратов Метод серединных произведений Метод перемешивания
Линейная конгруэнция
R i+1 = (K * R i + B) % M
Линейная конгруэнция R i+1 = (K * R i + B) % M B и M взаимно простые
Линейная конгруэнция R i+1 = (K * R i + B) % M B и M – взаимно простые K – 1 кратно любому простому делителю M
Линейная конгруэнция R i+1 = (K * R i + B) % M B и M – взаимно простые K – 1 кратно любому простому делителю M K – 1 кратно 4, если М кратно 4
Датчик Фибоначчи
R i = R i - a – R i - b
Датчик Фибоначчи R i = R i - a – R i - b a, b – лаги
Датчик Фибоначчи R i = R i - a – R i - b a, b – лаги циклическая очередь значений
Датчик Фибоначчи R i = R i - a – R i - b a, b – лаги циклическая очередь значений T = (2 max{a, b} – 1) · 2 l
LFSR
R i = (c 1 × R i-1 ) (c 2 × R i-2 ) … (c L × R i-L ) C(x) = 1 + c 1 x + c 2 x 2 + … + c L x L
LFSR x 3 + x
Стоп-пошел LFSR – 1 LFSR – 2 LFSR – 3 = bit
Каскад Голлмана LFSR – 1LFSR – 2 LFSR – 3 LFSR – 4
Пороговый генератор LFSR – 1 LFSR – 2 LFSR – 3 LFSR – K …
Тестирование
NIST DIEHARD pLab Project CRYPT-X TEST-U01 Dieharder ENT Knuths
Тестирование NIST DIEHARD pLab Project CRYPT-X TEST-U01 Dieharder ENT Knuths
NIST
Частотный побитовый тест
NIST Частотный побитовый тест Частотный блочный тест
NIST Частотный побитовый тест Частотный блочный тест Последовательность одинаковых бит
NIST Частотный побитовый тест Частотный блочный тест Последовательность одинаковых бит Самая длинная последовательность единиц в блоке
NIST Ранговый тест
NIST Ранговый тест Спектральный тест
NIST Ранговый тест Спектральный тест Тест на шаблоны
NIST Ранговый тест Спектральный тест Тест на шаблоны Тест на пересекающиеся шаблоны
NIST Ранговый тест Спектральный тест Тест на шаблоны Тест на пересекающиеся шаблоны Тест Маурера
NIST Тест на линейную сложность
NIST Тест на линейную сложность Тест на периодичность
NIST Тест на линейную сложность Тест на периодичность Тест приблизительной энтропии
NIST Тест на линейную сложность Тест на периодичность Тест приблизительной энтропии Тест кумулятивных сумм
DIEHARD
Тест на парковку
DIEHARD Тест на парковку Тест сжатия
DIEHARD Тест на парковку Тест сжатия Тест игры в кости
Криптостойкость
Генерация ключей
Криптостойкость Генерация ключей Одноразовые случайные числа
Криптостойкость Генерация ключей Одноразовые случайные числа Одноразовые шифроблокноты
Криптостойкость Генерация ключей Одноразовые случайные числа Одноразовые шифроблокноты Генерация соли
Криптостойкость Тест на следующий бит
Криптостойкость Тест на следующий бит На основе блочного шифра
Криптостойкость Тест на следующий бит На основе блочного шифра На основе хеш-функции
Криптостойкость Тест на следующий бит На основе блочного шифра На основе хеш-функции Алгоритм Блюма Блюма Шуба x n+1 = x n 2 mod M
Криптостойкость Тест на следующий бит На основе блочного шифра На основе хеш-функции Алгоритм Блюма Блюма Шуба Алгоритм Блюма Микали
Аппаратные генераторы
Lavarand
Аппаратные генераторы Lavarand Чипы в процессоре (3 Гб/сек)
ПО
gLib – вихрь Мерсена
ПО gLib – вихрь Мерсена Java – Random, SecureRandom
ПО gLib – вихрь Мерсена Java – Random, SecureRandom C# - Random, Cryptography.RNG
ПО gLib – вихрь Мерсена Java – Random, SecureRandom C# - Random, Cryptography.RNG RFC 1750
Продолжи ряд …