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


The Presentation inside:

Slide 0

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


Slide 1

Эталон 0 1


Slide 2

Эталон 0 1


Slide 3

Генераторы


Slide 4

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


Slide 5

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


Slide 6

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


Slide 7

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


Slide 8

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


Slide 9

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


Slide 10

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


Slide 11

Первые алгоритмы Метод серединных квадратов Метод серединных произведений R0 ? R1


Slide 12

Первые алгоритмы Метод серединных квадратов Метод серединных произведений R0 ? R1


Slide 13

Первые алгоритмы Метод серединных квадратов Метод серединных произведений R0 ? R1 R2 R1 ? R2 R3


Slide 14

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


Slide 15

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


Slide 16

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


Slide 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 +


Slide 18

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


Slide 19

Линейная конгруэнция Ri+1 = (K * Ri + B) % M


Slide 20

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


Slide 21

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


Slide 22

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


Slide 23

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


Slide 24

Датчик Фибоначчи Ri = Ri - a – Ri - b


Slide 25

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


Slide 26

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


Slide 27

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


Slide 28

LFSR


Slide 29

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


Slide 30

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


Slide 31

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


Slide 32

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


Slide 33

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


Slide 34

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


Slide 35

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


Slide 36

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


Slide 37

NIST


Slide 38

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


Slide 39

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


Slide 40

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


Slide 41

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


Slide 42

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


Slide 43

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


Slide 44

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


Slide 45

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


Slide 46

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


Slide 47

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


Slide 48

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


Slide 49

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


Slide 50

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


Slide 51

DIEHARD


Slide 52

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


Slide 53

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


Slide 54

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


Slide 55

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


Slide 56

Криптостойкость Генерация ключей


Slide 57

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


Slide 58

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


Slide 59

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


Slide 60

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


Slide 61

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


Slide 62

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


Slide 63

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


Slide 64

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


Slide 65

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


Slide 66

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


Slide 67

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


Slide 68

ПО


Slide 69

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


Slide 70

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


Slide 71

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


Slide 72

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


Slide 73

Продолжи ряд ? 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 …


×

HTML:





Ссылка: