Презентация на тему "Генерация случайных чисел"

Содержание

• 
  Слайд 1

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

  Андрей Гейн

• 
  Слайд 2

  Эталон

  0 1

• 
  Слайд 3
  

  0 1

• 
  Слайд 4

  Генераторы

• 
  Слайд 5
  

  физические

• 
  Слайд 6
  

  физические табличные

• 
  Слайд 7
  

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

• 
  Слайд 8

  Первые алгоритмы

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

• 
  Слайд 9
  

  Метод серединных квадратов

• 
  Слайд 10
  

  Метод серединных квадратов

• 
  Слайд 11
  

  Метод серединных квадратов

• 
  Слайд 12
  

  Метод серединных квадратов Метод серединных произведений R0× R1

• 
  Слайд 13
  

  Метод серединных квадратов Метод серединных произведений R0× R1

• 
  Слайд 14
  

  Метод серединных квадратов Метод серединных произведений R0× R1 R2 R1 × R2 R3

• 
  Слайд 15
  

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

• 
  Слайд 16
  

  Метод серединных квадратов Метод серединных произведений Метод перемешивания 3 4 5 6 7 8 1 2 5 6 7 8 1 2 3 4

• 
  Слайд 17
  

  Метод серединных квадратов Метод серединных произведений Метод перемешивания 3 4 5 6 7 8 1 2 5 6 7 8 1 2 3 4 1 2 3 4 5 6 7 8

• 
  Слайд 18
  

  Метод серединных квадратов Метод серединных произведений Метод перемешивания 3 4 5 6 7 8 1 2 5 6 7 8 1 2 3 4 1 2 3 4 5 6 7 8 +

• 
  Слайд 19

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

• 
  Слайд 20
  

  Ri+1 = (K * Ri + B) % M

• 
  Слайд 21
  

  Ri+1 = (K * Ri + B) % M B и M взаимно простые

• 
  Слайд 22
  

  Ri+1 = (K * Ri + B) % M B и M – взаимно простые K – 1 кратно любому простомуделителю M

• 
  Слайд 23
  

  Ri+1 = (K * Ri + B) % M B и M – взаимно простые K – 1 кратно любому простомуделителю M K – 1 кратно 4, если М кратно 4

• 
  Слайд 24

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

• 
  Слайд 25
  

  Ri = Ri- a – Ri - b

• 
  Слайд 26
  

  Ri = Ri- a – Ri - b a, b – лаги

• 
  Слайд 27
  

  Ri = Ri- a – Ri - b a, b – лаги циклическая очередь значений

• 
  Слайд 28
  

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

• 
  Слайд 29

  LFSR

• 
  Слайд 30
  

  Ri = (c1 × Ri-1) ⊕ (c2 × Ri-2) ⊕ … ⊕ (cL × Ri-L) C(x) = 1 + c1x + c2x2 + … + cLxL

• 
  Слайд 31
  

  x3 + x + 1 0 1 0 1 1 1 0 1 0 0 1 1 1 0 1 0 0 7

• 
  Слайд 32

  Стоп-пошел

  LFSR – 1 LFSR – 2 LFSR – 3 ⊕ = bit

• 
  Слайд 33

  Каскад Голлмана

  LFSR – 1 LFSR – 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 Knuth’s

• 
  Слайд 37
  

  NIST DIEHARD pLab Project CRYPT-X TEST-U01 Dieharder ENT Knuth’s

• 
  Слайд 38

  NIST

• 
  Слайд 39
  

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

• 
  Слайд 40
  

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

• 
  Слайд 41
  

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

• 
  Слайд 42
  

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

• 
  Слайд 43
  

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

• 
  Слайд 44
  

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

• 
  Слайд 45
  

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

• 
  Слайд 46
  

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

• 
  Слайд 47
  

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

• 
  Слайд 48
  

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

• 
  Слайд 49
  

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

• 
  Слайд 50
  

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

• 
  Слайд 51
  

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

• 
  Слайд 52

  DIEHARD

• 
  Слайд 53
  

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

• 
  Слайд 54
  

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

• 
  Слайд 55
  

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

• 
  Слайд 56

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

• 
  Слайд 57
  

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

• 
  Слайд 58
  

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

• 
  Слайд 59
  

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

• 
  Слайд 60
  

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

• 
  Слайд 61
  

  Тест на следующий бит

• 
  Слайд 62
  

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

• 
  Слайд 63
  

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

• 
  Слайд 64
  

  Тест на следующий бит На основе блочного шифра На основе хеш-функции Алгоритм Блюма — Блюма — Шуба xn+1 = xn2 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

  Продолжи ряд 

  1 0 0 1 1 0 1 0 0 1 0 0 0 1 1 0 1 1 1 0 0 1 0 1 1 0 1 1 0 0 0 1 0 1 1 0 0 1 1 0 0 1 0 0 1 0 1 0 0 1 …