Истинный ГСЧ (True RNG, TRNG)

[needbmw]

недавно в недрах тренда о нове зародилась мысль об истинном ГСЧ (TRNG).
я откровенно говоря давно подумывал о необходимости такой приблуды для каждого уважающего себя криптомана, но мысль дальше чем "пошуметь стабилитроном" не распространялась.

мне очень понравилась идея квантового ГСЧ на основе счетчика Гейгера-Мюллера.
в результате после небольшого обсуждения был собран подопытный девайс из Raspberry PI и советского дозиметра "Север" на трубке самой распространенной марки СБМ-20. быдлокод пока только в зародыше, буду выкладывать обновления и результаты тестов по факту их появления.

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



работая на фоновых значениях гамма-излучения, глупо ожидать высокой скорости от TRNG, в среднем сейчас генератор выдает 1 случайный бит в 8-12 секунд (возбуждать счетчик от источника гамма-ИИ просьба не предлагать, чтобы не иметь проблем со здоровьем и законом).

Code:

root@raspberrypi:~/rng# ./rng 
01010000 0x50 0.086 bps 0.12 uSv/h
11100110 0xE6 0.066 bps 0.09 uSv/h
10101000 0xA8 0.080 bps 0.11 uSv/h
10011111 0x9F 0.089 bps 0.12 uSv/h
00110101 0x35 0.096 bps 0.13 uSv/h
00111101 0x3D 0.080 bps 0.11 uSv/h
00011100 0x1C 0.092 bps 0.13 uSv/h
10101101 0xAD 0.096 bps 0.13 uSv/h

возможные варианты ускорения процесса - внедрение хорошего ГПСП, сидируемого от TRNG, или переход на трубку со слюдяным окном, чувствительную к альфа-излучению от какого-нибудь легального источника. думаю, рано или поздно попробуем оба варианта. а пока нужно набраться терпения и собрать побольше бит, чтобы было что анализировать на предмет энтропии.

для ответа на закономерный вопрос "накой это вообще нужно" приведу две картинки с этого сайта:

True random bitmap


PHP rand() on Windows bitmap


а теперь представьте, что частные ключи к вашим монетам были сгенерированы вторым генератором  



_{ввиду отсутствия модератора на форуме топик само-модерируемый, трёп не по теме буду выпиливать без всякого сожаления}  

[1714772798]

1714772798

[1714772798]

1714772798

[1714772798]

1714772798

[1714772798]

1714772798

[needbmw]

резерв

[Balthazar]

Значительная часть постов из данной темы может быть найдена тут ещё:

https://bitcointalk.org/index.php?topic=704756.msg10205657#msg10205657

P.S. На посты becool внимание можно не обращать.

[fruit]

А не проще ли, для домашнего использования, ГСЧ на основе рисунка (пузырьки) среза буханки чёрного хлеба?
Надо ещё сгенерить - срезал ещё ломоть.

Прошу, громко не смеяться - я не специалист по криптографии.



Картинки со срезами хлеба

[needbmw]

А не проще ли, для домашнего использования, ГСЧ на основе рисунка (пузырьки) среза буханки чёрного хлеба?
Надо ещё сгенерить - срезал ещё ломоть.
Прошу, громко не смеяться - я не специалист по криптографии.

точно так же можно реализовать близкий к ИГСЧ генератор на основе движений мышки пользователя, как это сделано например в TrueCrypt.  нужно ключ сгенерить - подрыгал мышкой и оно сгенерилось. но к сожалению это не вариант для круглосуточно доступного решения...

[OZR]

Задумался. Privkey сгенерированный мне в VanityGen по логике явно должен быть псевдо-рандомным и потенциально уязвим...

*Впрочем, велика вероятность, что сгенерированные адреса Bitcoin Core, такие же псевдо-рандомные, а это уже чрезвычайно серьёзная проблема... Очередной и очень важный повод добить программирование и увидеть картинку своими глазами... Грусть.*

[needbmw]

такие же псевдо-рандомные, а это уже чрезвычайно серьёзная проблема...

продам свежие квантовые случайные числа, недорого 

[Balthazar]

<кэп>Ну продавать их смысла уже нет, потому что ты их видел.</кэп> 

[needbmw]

пока копятся данные, я решил исследовать RNG чипа BCM2708, на котором собственно сделана сама распи.
как выяснилось, помимо обычного /dev/urandom существует еще драйвер bcm2708-rng, открывающий доступ к аппаратному ГСЧ чипа через устройство /dev/hwrng

root@raspberrypi:~/rng# dd if=/dev/urandom bs=1M count=1 | ent
1+0 records in
1+0 records out
1048576 bytes (1.0 MB) copied, 1.36604 s, 768 kB/s
Entropy = 7.999849 bits per byte.

Optimum compression would reduce the size
of this 1048576 byte file by 0 percent.

Chi square distribution for 1048576 samples is 219.28, and randomly
would exceed this value 90.00 percent of the times.

Arithmetic mean value of data bytes is 127.4724 (127.5 = random).
Monte Carlo value for Pi is 3.150364496 (error 0.28 percent).
Serial correlation coefficient is 0.001382 (totally uncorrelated = 0.0).
root@raspberrypi:~/rng#

красным выделены результаты Chi²-теста, на котором как раз и сыпятся ГПСЧ

root@raspberrypi:~/rng# modprobe bcm2708-rng
root@raspberrypi:~/rng# dd if=/dev/hwrng bs=1M count=1 | ent
1+0 records in
1+0 records out
1048576 bytes (1.0 MB) copied, 10.8145 s, 97.0 kB/s
Entropy = 7.999822 bits per byte.

Optimum compression would reduce the size
of this 1048576 byte file by 0 percent.

Chi square distribution for 1048576 samples is 259.20, and randomly
would exceed this value 50.00 percent of the times.

Arithmetic mean value of data bytes is 127.4226 (127.5 = random).
Monte Carlo value for Pi is 3.140568316 (error 0.03 percent).
Serial correlation coefficient is 0.001274 (totally uncorrelated = 0.0).

у аппаратного генератора все в порядке, Chi² девиация 50%

UPD: при множественных запусках тоже бывают забросы до 90%, надо разбираться с ним плотнее

[tvskit]

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

[A-Bolt]

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

А как отделить космический шум от сигналов радиостанций и помех от зарядки мобильника, воткнутой в розетку рядом с приёмником?

[tvskit]

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

А как отделить космический шум от сигналов радиостанций и помех от зарядки мобильника, воткнутой в розетку рядом с приёмником?

Иногда это сигнал/шум, а иногда, каждую секунду/1000000000, мошность излучения гамма - солнце, мангитары, пульсары и т.д.  и это четко отделяется.

[needbmw]

Иногда это сигнал/шум, а иногда, каждую секунду/1000000000, мошность излучения гамма - солнце, мангитары, пульсары и т.д.  и это четко отделяется.

а конкретизировать алгоритм "четкого" отделения можно?
ведь он напрямую будет влиять на результат.

детектор ИИ в данном случае как раз и является предпочтительней прослушивания радиоэфира и шумов pn-переходов именно тем, что регистрирует отдельные кванты, а промодулировать их поток невозможно в принципе. можно только менять интенсивность, что не влияет на качество "продукции" генератора, а только на его производительность.

[Balthazar]

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

[Subw]

велосипедисты, про  /dev/random не слышали?

[fsb4000]

велосипедисты, про  /dev/random не слышали?

смешно, шутку оценил 

[needbmw]

велосипедисты, про  /dev/random не слышали?

нет, а что это? 

[Balthazar]

велосипедисты, про  /dev/random не слышали?

нет, а что это?  

Системное устройство для поиска жопы.

https://twitter.com/brainslug/status/11814377181

Code:

$ time grep -i жопа /dev/urandom
Binary file /dev/urandom matches

real 0m13.895s
user 0m0.615s
sys 0m13.165s

[Subw]

велосипедисты, про  /dev/random не слышали?

нет, а что это? 

то же что ты сделал только бесплатно

[needbmw]

эх, жаль пропала увлекательная дискуссия  

итак, промежуточные результаты

режим TRUE_RNG ("швейцарский" алгоритм "4 кванта на бит"):

Code:

root@raspberrypi:~/rng# ent out1.bin
Entropy = 7.829581 bits per byte.

Optimum compression would reduce the size
of this 1199 byte file by 2 percent.

Chi square distribution for 1199 samples is 265.05, and randomly
would exceed this value 50.00 percent of the times.

Arithmetic mean value of data bytes is 125.2644 (127.5 = random).
Monte Carlo value for Pi is 3.256281407 (error 3.65 percent).
Serial correlation coefficient is 0.033513 (totally uncorrelated = 0.0).

все очень неплохо даже при такой небольшой выборке в 1199 байт

далее самый быстрый конвеерный алгоритм "1 квант на бит":

Code:

root@raspberrypi:~/rng# ent out2.bin
Entropy = 7.253107 bits per byte.

Optimum compression would reduce the size
of this 2094 byte file by 9 percent.

Chi square distribution for 2094 samples is 2354.83, and randomly
would exceed this value 0.01 percent of the times.

Arithmetic mean value of data bytes is 126.8706 (127.5 = random).
Monte Carlo value for Pi is 3.426934097 (error 9.08 percent).
Serial correlation coefficient is 0.010534 (totally uncorrelated = 0.0).

следует обратить внимание что при выборке почти в 2 раза больше чем предыдущая, средняя энтропия стала гораздо хуже, а параметр разброса Chi² вообще 0.01%, что говорит о том, что эти данные не являются случайными!
почему это произошло я пока не понимаю, реализацию алгоритма я проверил, он довольно примитивный.
возможно дело в том, что присутствует связь между событиями, т.к. каждый следующий интервал является предыдущим для следующей пары.

сейчас дополнительно реализован алгоритм "3 кванта на бит", результат ниже:

Code:

root@raspberrypi:~/rng# ent out3.bin
Entropy = 7.874998 bits per byte.

Optimum compression would reduce the size
of this 1420 byte file by 1 percent.

Chi square distribution for 1420 samples is 244.36, and randomly
would exceed this value 50.00 percent of the times.

Arithmetic mean value of data bytes is 124.7901 (127.5 = random).
Monte Carlo value for Pi is 3.169491525 (error 0.89 percent).
Serial correlation coefficient is 0.019137 (totally uncorrelated = 0.0).

видим, что с энтропией и Chi² все нормально.

также реализован алгоритм "2 кванта на бит", но данные пока только набираются.

UPD:

Code:

root@raspberrypi:~/rng# ent out.bin
Entropy = 7.841278 bits per byte.

Optimum compression would reduce the size
of this 1173 byte file by 1 percent.

Chi square distribution for 1173 samples is 248.86, and randomly
would exceed this value 50.00 percent of the times.

Arithmetic mean value of data bytes is 130.0068 (127.5 = random).
Monte Carlo value for Pi is 3.117948718 (error 0.75 percent).
Serial correlation coefficient is -0.003621 (totally uncorrelated = 0.0).

что же, все три варианта кроме "1 квант - 1 бит" демонстрируют отличные и очень схожие результаты.
буду искать альфа-счетчик