Генерация случайных чисел Андрей Гейн. Эталон 0 1. - презентация

1 Генерация случайных чисел Андрей Гейн

2 Эталон 0 1

3 Эталон 0 1

4 Генераторы

5 физические

6 Генераторы физические табличные

7 Генераторы физические табличные алгоритмические

8 Первые алгоритмы «Всякий, кто питает слабость к арифметическим методам получения случайных чисел, грешен вне всяких сомнений» Джон фон Нейман

9 Первые алгоритмы Метод серединных квадратов

10 Первые алгоритмы Метод серединных квадратов

11 Первые алгоритмы Метод серединных квадратов

12 Первые алгоритмы Метод серединных квадратов Метод серединных произведений R 0 × R 1

13 Первые алгоритмы Метод серединных квадратов Метод серединных произведений R 0 × R 1

14 Первые алгоритмы Метод серединных квадратов Метод серединных произведений R 0 × R 1 R 2 R 1 × R 2 R 3

15 Первые алгоритмы Метод серединных квадратов Метод серединных произведений Метод перемешивания

16 Первые алгоритмы Метод серединных квадратов Метод серединных произведений Метод перемешивания

17 Первые алгоритмы Метод серединных квадратов Метод серединных произведений Метод перемешивания

18 Первые алгоритмы Метод серединных квадратов Метод серединных произведений Метод перемешивания

19 Линейная конгруэнция

20 R i+1 = (K * R i + B) % M

21 Линейная конгруэнция R i+1 = (K * R i + B) % M B и M взаимно простые

22 Линейная конгруэнция R i+1 = (K * R i + B) % M B и M – взаимно простые K – 1 кратно любому простому делителю M

23 Линейная конгруэнция R i+1 = (K * R i + B) % M B и M – взаимно простые K – 1 кратно любому простому делителю M K – 1 кратно 4, если М кратно 4

24 Датчик Фибоначчи

25 R i = R i - a – R i - b

26 Датчик Фибоначчи R i = R i - a – R i - b a, b – лаги

27 Датчик Фибоначчи R i = R i - a – R i - b a, b – лаги циклическая очередь значений

28 Датчик Фибоначчи R i = R i - a – R i - b a, b – лаги циклическая очередь значений T = (2 max{a, b} – 1) · 2 l

29 LFSR

30 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

31 LFSR x 3 + x

32 Стоп-пошел LFSR – 1 LFSR – 2 LFSR – 3 = bit

33 Каскад Голлмана LFSR – 1LFSR – 2 LFSR – 3 LFSR – 4

34 Пороговый генератор LFSR – 1 LFSR – 2 LFSR – 3 LFSR – K …

35 Тестирование

36 NIST DIEHARD pLab Project CRYPT-X TEST-U01 Dieharder ENT Knuths

37 Тестирование NIST DIEHARD pLab Project CRYPT-X TEST-U01 Dieharder ENT Knuths

38 NIST

39 Частотный побитовый тест

40 NIST Частотный побитовый тест Частотный блочный тест

41 NIST Частотный побитовый тест Частотный блочный тест Последовательность одинаковых бит

42 NIST Частотный побитовый тест Частотный блочный тест Последовательность одинаковых бит Самая длинная последовательность единиц в блоке

43 NIST Ранговый тест

44 NIST Ранговый тест Спектральный тест

45 NIST Ранговый тест Спектральный тест Тест на шаблоны

46 NIST Ранговый тест Спектральный тест Тест на шаблоны Тест на пересекающиеся шаблоны

47 NIST Ранговый тест Спектральный тест Тест на шаблоны Тест на пересекающиеся шаблоны Тест Маурера

48 NIST Тест на линейную сложность

49 NIST Тест на линейную сложность Тест на периодичность

50 NIST Тест на линейную сложность Тест на периодичность Тест приблизительной энтропии

51 NIST Тест на линейную сложность Тест на периодичность Тест приблизительной энтропии Тест кумулятивных сумм

52 DIEHARD

53 Тест на парковку

54 DIEHARD Тест на парковку Тест сжатия

55 DIEHARD Тест на парковку Тест сжатия Тест игры в кости

56 Криптостойкость

57 Генерация ключей

58 Криптостойкость Генерация ключей Одноразовые случайные числа

59 Криптостойкость Генерация ключей Одноразовые случайные числа Одноразовые шифроблокноты

60 Криптостойкость Генерация ключей Одноразовые случайные числа Одноразовые шифроблокноты Генерация соли

61 Криптостойкость Тест на следующий бит

62 Криптостойкость Тест на следующий бит На основе блочного шифра

63 Криптостойкость Тест на следующий бит На основе блочного шифра На основе хеш-функции

64 Криптостойкость Тест на следующий бит На основе блочного шифра На основе хеш-функции Алгоритм Блюма Блюма Шуба x n+1 = x n 2 mod M

65 Криптостойкость Тест на следующий бит На основе блочного шифра На основе хеш-функции Алгоритм Блюма Блюма Шуба Алгоритм Блюма Микали

66 Аппаратные генераторы

67 Lavarand

68 Аппаратные генераторы Lavarand Чипы в процессоре (3 Гб/сек)

69 ПО

70 gLib – вихрь Мерсена

71 ПО gLib – вихрь Мерсена Java – Random, SecureRandom

72 ПО gLib – вихрь Мерсена Java – Random, SecureRandom C# - Random, Cryptography.RNG

73 ПО gLib – вихрь Мерсена Java – Random, SecureRandom C# - Random, Cryptography.RNG RFC 1750

74 Продолжи ряд …