Случайные числа

Не путайте псевдо и истинные случайные числа

В криптографии случайные числа используются для генерации таких вещей, как ключи шифрования. Если генерацию этих ключей можно было каким-то образом предсказать, возможно, удастся их угадать. Два основных типа генераторов случайных чисел:

  • Генераторы псевдослучайных чисел (ГПСЧ). Этот метод повторяет случайные числа через заданное время (периодически). Они быстрые, а также детерминированные и полезны для получения повторяемого набора случайных чисел.
  • Генераторы истинных случайных чисел (ГСЧЧ). Этот метод генерирует истинное случайное число и использует некоторые из них. Один из подходов - отслеживать движения указателя мыши на экране или во время пауз при нажатии клавиш. В целом метод обычно медленный, особенно если он предполагает взаимодействие с человеком, но он недетерминирован и апериодичен.

Обычно приложения моделирования и моделирования используют ГПСЧ, так что сгенерированные значения могут повторяться для разных прогонов, в то время как криптография, лотереи, азартные игры и игры используют ГПСЧ, поскольку каждое значение, которое выбирается случайным образом, не должно повторяться или быть предсказуемым. Таким образом, Ева могла угадать ключ, созданный методом, который Боб использует для генерации ключа. Таким образом, при генерации ключей шифрования для шифрования с открытым ключом пользователя обычно просят сгенерировать некоторую случайную активность. Затем на основе этого действия генерируется случайное число.

Однако компьютерные программы часто не могут генерировать TRNG, а аппаратные генераторы часто используются в приложениях с высокой степенью защиты. Один из методов заключается в генерации случайного числа на основе статистически случайных «шумовых» сигналов низкого уровня. Сюда входят такие вещи, как тепловой шум и фотоэлектрический эффект.

В криптографии важно, чтобы мы генерировали значения, которые почти случайны, чтобы Ева не могла угадать случайные числа, которые используются Бобом и Алисой. С помощью случайности мы не можем определить, насколько случайны значения, просто взяв несколько образцов. Для этого нам нужно большое количество выборок и сделать оценку общей случайности.

Взлом лотереи

К сожалению, компьютеры имеют тенденцию генерировать ГПСЧ. Эдди Типтон, который с 2003 по 2015 год был директором по компьютерной информационной безопасности в Multi-State Lottery Association, «сфальсифицировал» выигрышные номера в нескольких штатах США, где он получил миллионы выигрышей. В своем посте он написал большую часть программного обеспечения, используемого в лотереях, и где, по его словам, он воспользовался лазейкой в ​​генераторе случайных чисел.

Его защита состоит в том, что это не его вина, что была лазейка, и он просто использовал ее. Для этого он обнаружил, что если розыгрыш проводится по средам или субботам после 20:00, цифры могут быть предсказуемыми. Затем он выиграл в Колорадо в 2005 году, Висконсине в декабре 2007 года, Канзасе в декабре 2010 года и Оклахоме в 2011 году.

Он также попытался получить билет Hot Lotto на сумму 16,5 миллионов долларов в декабре 2010 года в Айове, но получил отказ, поскольку штат не заплатил анонимному заявителю. Затем это привело к расследованию Типтона и его связей. Сам Эдди не купил билеты, но передал информацию своему брату (Томми).

Считается, что по этой схеме они получили более 2,2 миллиона долларов. Это также привело к судебному иску против мультиштатной лотерейной ассоциации штата Айова (обслуживающей 33 штата). Таким образом, утверждается, что он не обслуживал случайные числа и которые использовались во многих онлайн-лотереях.

Лотерея всегда должна быть типа TRNG. Обычно приложения моделирования и моделирования используют ГПСЧ, так что сгенерированные значения могут повторяться для разных прогонов, в то время как криптография, лотереи, азартные игры и игры используют ГПСЧ, поскольку каждое значение не должно повторяться или быть предсказуемым. В случае взлома лотереи генерация ключа была детерминированной, и Ева могла угадать созданный ключ. Таким образом, при генерации ключей шифрования для шифрования с открытым ключом пользователей часто просят сгенерировать некоторую случайную активность, и где случайное число затем генерируется на основе этой активности. Это случайное число затем используется для генерации ключей шифрования.

Однако компьютерные программы часто не могут генерировать действительно случайные числа, поэтому аппаратные генераторы часто используются в приложениях с высокой степенью защиты. Один из методов - генерировать случайное число на основе статистически случайных сигналов шума низкого уровня. Сюда входят такие вещи, как тепловой шум и фотоэлектрический эффект. Если вас интересуют случайные числа, вот способ определить, являются ли они случайными… измерить энтропию [здесь].

Стена

Мир полон страшных историй о кибербезопасности и о киберпреступниках, которые преследуют вас. Так что иногда просто приятно сесть перед чем-нибудь успокаивающим - например, перед лавовой лампой. Ах! Просто сказав слово «лавовая лампа», вы снизили стресс. Теперь посмотрите на картинку справа, и вы уже будете в расслабленном состоянии.

В кибербезопасности одна из самых больших проблем - найти действительно генератор случайных чисел, и CloudFlare, похоже, нашла один из самых интересных методов. В их офисе в Сан-Франциско стена из 100 лавовых ламп. Но для них это не просто радость, а часть их инфраструктуры генератора случайных чисел. В настоящее время они используют их для генерации случайных чисел, что составляет около 10% всего интернет-трафика.

CloudFlare окрестил генератор случайных чисел - стеной энтропии. Он был вдохновлен инженером из Silicon Graphics, который использовал предположение о том, что движение жидкости в лавовых лампах можно увидеть действительно случайным образом, поскольку моделировать поток практически невозможно. Они создают случайные числа, фотографируя лампы каждые несколько миллисекунд, на которые будет влиять свет снаружи и люди, движущиеся вокруг них. Они создают небольшие изменения, которые затем используются для создания случайных чисел. Это каждый раз создает 16 384 бит энтропии.

Идея использования лавовой лампы для генерации чисел существует уже давно. В 1996 году Лэндон Курт Нолл, Роберт Г. Менде, Санджив Сисодия из Silicon Graphics определили запатентованную систему под названием Lavarand (Патент 5732138: Метод заполнения генератора псевдослучайных чисел криптографическим хешем оцифровки. хаотической системы ). А к 2007 году у lavarnd даже появился собственный сайт для генерации чисел для своих пользователей.

В Лондоне CloudFlare используют систему двойного маятника, которая подвешивает один маятник к другому, движения предсказать движение крайне сложно:

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

Проверка на случайность

Существуют различные тесты на случайность. Например, мы могли бы определить среднее значение, которое находится на полпути между диапазоном чисел, а затем определить соотношение значений выше и ниже половинного значения. Это будет работать, но не покажет нам, хорошо ли распределены значения. Наряду с этим мы могли определить среднее арифметическое значений и сопоставить его с центральным значением в диапазоне чисел. Улучшенный метод проверки распределения значений - это значение Монте-Карло для теста Pi. С помощью этого метода мы берем случайные числа и масштабируем их от 0,0 до 1,0. Затем мы берем два значения за раз и вычисляем:

√(x²+y²)

Если это значение меньше или равно единице, мы помещаем в круг (с радиусом 1), в противном случае оно выходит за пределы круга. Тогда оценка PI равна четырехкратному количеству точек в круге (M), деленному на общее количество точек (N). На рисунке синие точки находятся вне круга, а желтые - внутри:

Ниже приводится краткое изложение кода:

import sys
import math
values = [5,125,10,1,32, 101,33, 54,200,230,215,93,50,100,3,6,43]
max=255.0
inval=0
outval=0
ptr=0
print "Values:",values
print "Pairs:"
print "\tX\t\Y\tZ:"
for i in range(0,len(values)/2):
	x = (values[ptr]-max/2)/(max/2)
	y = (values[ptr+1]-max/2)/(max/2)
	z = math.sqrt(x*x+y*y)
	print "\t",round(x,3),"\t",round(y,3),"\t",round(z,3)
	if (z<1):
		inval=inval+1
	else:
		outval=outval+1
	ptr=ptr+2
print "\nInval:",inval," Outval:",outval
print "\nResult: ",4.0*inval/(inval+outval)

Пример выполнения для значений 5, 125, 10, 1, 32, 101, 33, 54, 200, 230, 215, 93, 50, 100, 3, 6, 43:

First Five Pairs:
        X       Y       Z:
        -0.961  -0.02   0.961
        -0.922  -0.992  1.354
        -0.749  -0.208  0.777
        -0.741  -0.576  0.939
        0.569   0.804   0.985
Inval: 6  Outval: 2
Result:  3.0

Чем ближе мы приближаемся к π (3,14159265359…), тем более случайны данные. Поскольку мы используем только несколько точек, похоже, что данные являются хорошим приближением к случайным, но для уверенности нам понадобится гораздо больше выборок.

Демо этого находится здесь.

Выводы

Случайные числа часто бывают не такими уж случайными, поэтому убедитесь, что у вас есть истинные случайные числа, когда они вам нужны, и псевдо, когда они вам нужны, и не путайте их.