Создаём аппаратный генератор случайных чисел

[@OLS]

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

Кстати, умело подбирая объем хешируемого блока данных, можно добиться, чтобы объем появляющихся на выходе хеш-функции данных был практически равен их энтропии (т.е. в Вашем случае отпадет этап «берем только младшие 4 бита», тем более, что у них тоже может обнаружиться определенная неочевидная корреляция).

[@dlinyj]

тем более, что у них тоже может обнаружиться определенная неочевидная корреляция)

Я больше, чем уверен, что там есть некоторая корреляция. И считаю, что разумеется сырцом данные использовать нельзя.

[@ZlodeiBaal]

50 герц там полюбому есть.

[@dlinyj]

Если бы она была, то распределение было бы, как в картинке про распределение синуса. У меня есть такие гистограммы: 50 Гц + шум. Вечером постараюсь показать.

[@ZlodeiBaal]

Может быть не 50 герц+шум, а что-то более хитрое, но с периодом 50 герц. Спектр получаемого сигнала какой? Это было бы интересно глянуть

[@dlinyj]

Вот интересный график. Я «бубучу» в микрофон, и смотрим получаемую гистограмму:


Осциллограмма


Полученная гистограмма

Пропавший столбик вызван небольшой ошибкой в программе, сути явления он не меняет. И вот второй вариант для примера:


Осциллограмма


Полученная гистограмма

По крайне мере любопытно ;).

[@ZlodeiBaal]

Ненене, интересна именно спектрограмма у шума) Я почти уверен что там будет несколько пиковых частот, где один будет на 50 герцах.
А если спектрограмма будет иметь отличное от равномерного распределение, то, по сути, уже появляется большая корреляция получаемых данных.

[@dlinyj]

Если мне будет не лень, то я попробую это сделать

[@ZlodeiBaal]

хотя это тоже забавно) Если говорить вслух около звуковухи, то она уже перестаёт быть генератором шума;)

[@Andrew_Crew_Kuznetsov]

В тексте есть прикольный момент:)

«Ололо пыщ-пыщ, никто же не читает.»

Чем-то напомнило, из анекдота «А сердечник мы сделаем из дерева, все равно дипломную работу никто не читает»

[@dlinyj]

Приятно, что внимательно читаете :).

[@alexyr]

Сначала читал внимательно… После этого сломался и начал листать до комментов, проверить я ли первый это увидел! :)

[@eugenets]

Рановато вставили :)

[@Coderr]

Мы со знакомым на сайте, где контент 50/50 — бесплатный и платный, платный покупается за поинты, которые можно оплатить платежной системой, либо комментируя статьи, и т.д., в правилах регистрации в середине написали, — «Если вы это видите, отправьте письмо администратору и получите 50000 поинтов бесплатно». До сих пор никто не написал.

[@donanykey]

Странно, я этот блок читал вдумчиво и эту надпись вообще не заметил :/

[@TheShock]

Я её раза четыре прочитал, стараясь понять, как она относится к теме.

[@DobroeZlo]

Из всего текста лучше всего я понял только «Ололо пыщ пыщ».

[@dlinyj]

Что же, лекция профессора не дала наглядности?

[@DobroeZlo]

Вечером из дома посмотрю и прочитаю повнимательнее.

[@SoLRoN]

Лично я вообще на этих видео-лекциях застрял (опять) и не осилил статью дальше.

[@coocheenin]

И действительно, интересная стилистика написания самого поста. Этакое «академическое графоманство». Но не всем же стопроцентно прикладные посты писать.

Респект, очень интересно!

[@dlinyj]

Я искренне старался максимально упростить и сделать максимально доступнее, но увы есть некий предел, когда простота превращается в бред :).

[@kreativf]

А мне как раз наоборот показалось что вы замечательно объяснили разные типы распределения.

[@dlinyj]

Лучше изложено в учебниках :). Я вечером добавлю в список литературы одну книженцию, где всё отлично разжованно.

[@dlinyj]

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

[@Gumanoid]

Сделали в 1999, вот тут интересная статья про это: habrahabr.ru/blogs/crypto/128666/

[@dlinyj]

Спасибо за ссылку!

[@Wildy]

Матчасть приятно описана.
А формулы в коде легче читаются, если хотя бы использовать пробелы вокруг операторов.
В целом понравилось, продолжайте пожалуйста =)

[@dlinyj]

Спасибо.

[@lorc]

А вы не пробовали прогонять полученные данные через тесты Die hard? Сами тесты в исходниках есть тут

[@dlinyj]

Нет, не пробовал.

[@OLS]

У нас лабораторная именно такая была — ввод со звуковухи — на DieHard

[@FloppyFormator]

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

[@dlinyj]

Не понял про реферат? :)

[@FloppyFormator]

Да весь этот вводный курс. Кому надо, в учебнике лучше прочитают, а кому не надо, можно было в двух словах объяснить. К тому же, в тексте много логических нестыковок, отсюда и мнение, что наскоро.

[@dlinyj]

Если мне укажут на нестыковки, я с готовностью их поправлю. Данный «реферат» писался около трёх-четырёх дней, с полным обдумыванием каждой детали, чтобы не осложнять понимание.

В учебниках без сомнения лучше описано, в особенности в тех, где есть примеры. Я не ставил цель переписать учебник своими словами. Однако для понимания картины, привёл здесь некоторое моё понимание тервера :).

[@FloppyFormator]

Да не вопрос, отписал в личку.

[@coocheenin]

habrahabr.ru/blogs/DIY/133320/#comment_4425333

[@dlinyj]

Системный и мой генератор стоят полностью в одинаковых условиях. Просто вместо /dev/sound в массив поступают данные из /dev/random. Вы можете сами попробовать.

[@Calvrack]

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

[@doobrik]

Не факт что сломается.

[@f0b0s]

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

Рассказывает и показывает очень уж хорошо!

[@coocheenin]

«Сегодня атеисты бьют тревогу,
И я не знаю, кто бы им помог.
Ведь если Бога нет, то слава Богу,
А ежели он есть, то не дай Бог!» ^©

Это не только в ваш адрес, конечно, ничего личного. Просто удивляет воинствующая тенденция хабровчан всё и вся перепроверять и ставить под сомнение ;)

[@coocheenin]

Упс! Адресовано было на каммент sanix

[@dlinyj]

а, ок :)

[@dlinyj]

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

[@coocheenin]

Да нет, я и сам отчасти такой:) Но тенденция опасная.

[@Gol]

Такие воинствующие ещё и коллайдер построили. Чтоб всё и вся проверять и перепроверять. Короче, хорошо что мы есть :-)

[@ZlodeiBaal]

Графики распределений, нарисованные вручную в пэинте жгут)
Вы бы их лучше в википедии взяли, а то тут у них какие-то горбы лишние…

[@dlinyj]

Не пойму, почему этот комментарий минусуют. Ведь он в общем-то по делу.

[@ZlodeiBaal]

Думают что придрался) Но я это, любя, из перфекционизма только) Статья хорошая))

[@betrachtung]

Вместо ололо пыщ пыщ можно применять и более интересные приёмы. Я, например, вставил в середину одного из текстов песен строки о том, что даю всем добравшимся до сюда мороженое. Пока только одна подруга заявила своё право на пломбир.

[@Ppord]

Идея не нова, но использовать ее в таком виде нельзя, слишком уж подвержена система внешним воздействиям. Таки да, коэффициент автокорреляции будет стремиться к нулю, но вот атакующий специально сформированными наводками сможет сместить распределение в нужную ему сторону.
Кстати, интересные генераторы случайных чисел получаются из весьма необычных вещей — например, транзистор МП26 со спиленной крышкой, направленный на солнышко, дает почти гауссово распределение. В светлое время суток :)

[@Eternalko]

Из всех теорем тевера, наиболее люблю Central Limit Theorem. Она прекрасна.
Суть ее в том, что какое бы странное и кривое у нас бы не было изначальное разложение вероятностей, то если брать пробы и суммировать результаты, все равно получится чистый Гаусс (:

[@g3ar]

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

[@Iehbr]

«Случайности не случайны, мой друг...»

[@pcholberg]

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

[@Iehbr]

картинка

[@amarao]

Вы столько раз повторили тезис про детерминированность событий внешнего мира, что мне просто стало интересно — вы квантовую физику хоть как-то учили? Хотя бы на школьном уровне?

[@dlinyj]

Когда-то учил, лет 6-7 назад. Даже экзамен по ней сдавал. Но я её прошёл :). А что?

[@amarao]

М… Я полагал, что после некоторого рода неравенств, которые изучаются в оном курсе, вопросы о детерминированности явлений больше не поднимаются.

[@dlinyj]

Быть может вы конкретизируете, что вы имете в виду?

На меня квантовая физика в институте произвела впечатление полностью нелогичной области. такое ощущение, что процессы которые протекают в ней не понимает никто. Да, математически описанно, явления все используются, но почему вот так не понимает никто.

[@amarao]

Конкретизирую: неравенство Гейзенберга.

Как можно говорить про детерминированность распада атома?

[@dlinyj]

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

[@dlinyj]

Я хочу ещё сказать, что статья писалась для людей, которые могут ничего не понимать ни в квантовой физике, ни в программировании, ни в теории вероятности. По этому я хотел особо подчеркнуть, что «ничто не случайно» (с) Ричард Бах.

Для меня, то что всё имеет свои закономерности стало ясно ещё лет в 7-10.

[@coocheenin]

Для меня, то что всё имеет свои закономерности стало ясно ещё лет в 7-10.

… включая то, что случайно. Полностью согласен!

[@dlinyj]

Случайностей нет

[@side2k]

Как и ложки.

[@SHVV]

Спасибо за статью, напомнило проект LavaRnd, где использовали «баночку» внешней энтропии (закрытую веб-камеру) для генерации чисел.

Кстати, кроме гистограммы распределения было бы еще интересно взглянуть на корреляцию между соседними значениями, или спектр полученного шума, чтобы выбрать оптимальную частоту дискретизации. Так как не думаю, что все звуковые карты оцифровывают микрофон с частотой 96кГц.

[@dlinyj]

Я тоже об этом думал, но мне уже было лениво реализовывать БПФ и функцию корреляции.

[@EvgeniyLazarev]

Кто первый сделает и разместит на Amazon Cloud JSON-генератор? :)

[@galaxy]

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

Потому что в конце строки 13 пара неведомых символов притаилась (D1 и 8E, что как раз stray \321 и stray \216 в восьмеричной системе счисления)

[@dlinyj]

Бью челом поклоны!

[@lightman]

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

[@Beholder]

Готов инструмент для исследования EVP?

[@dlinyj]

Спасибо.

[@Iehbr]

«При помощи совпадений Бог сохраняет анонимность.» — Альберт Эйнштейн.

[@Vayun]

В качестве доп. литературы habrahabr.ru/blogs/python/62237/ )
Там заодно написано как получить равномерное распределение.

[@dlinyj]

добавил

[@geirby]

В силу того, что знаком с автором лично, комментировать в духе «ура-ура» и «превосходно» было бы небольшим лицемерием))
Но при ее устной озвучке сама идея показалась классной и напомнила что-то из фантастики.
Круто, короче, что есть такая партия такие люди)
Предлагаю посильную таки помощь.

[@vaxXxa]

«ничего не мешает частицам лечь равномерно...»
Мешает то, что частицы высыпают по центру отностительно ряда каналов, соответственно вероятность того, что частица допрыгает до края самая маленькая, а то, что останется по центру — самая большая…

[@dlinyj]

Тут важное слово «вероятность», т.е. значит существует сверх-малая вероятность, что все частицы лягут равномерно?

[@vaxXxa]

Существует, но эта вероятность на столько «сверх-малая», что для того, чтобы увидеть равномерное распределение, вашему преподователю явно нужно ждать этого не 50 лет.

[@boolivar]

Боюсь, как раз, что частицы никогда не лягут равномерно, их достаточно большое количество чтобы теория вероятностей, так сказать, сработала. То что подвержено закону распределения, будет ему подчиняться, будь тому 50 лет, 500 или 500млн лет.

[@dlinyj]

Всё это не факт. Раз есть вероятность, значит это возможно.

[@boolivar]

Вероятность здесь относится к попаданию зерна в тот или иной канал, распределение вероятностей обусловлено схемой самого стенда

[@dlinyj]

спасибо КЭП. Я говорю вот о чём, бросив монету 10 раз, она может все десять раз выпасть решкой.

[@boolivar]

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

[@dlinyj]

Я согласен. Тут речь идёт о том, что могут ли зёрна упасть в виде равномерного распределения. Утверждаю, что могут. Вопрос в другом, сколько для этого потребуется опытов.

[@boolivar]

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

[@boolivar]

Раз уж есть возможность снять данные с микроконтроллера, может попробуете в каком-нибудь виде построить график плотности распределения случайных чисел, собирая их с младшего разряда АЦП микроконтроллера? Уж очень интересно посмотреть «случайность» таких данных.

[@dlinyj]

Там в списке литературы есть такая ссылочка tegir.ru/ml/k66.html. Там есть этот график. Можете ознакомиться.

[@boolivar]

Ой спасибо, а распределение то похоже очень даже неплохое

[@dlinyj]

В общем, есть простой алгоритм, чтобы убирать наклон в сторону единиц или нулей, если такой вдруг возникает в твоем физическом процессе.
Из последовательности выбираешь два бита. Если там 01, в выход ставишь 0, если 10, в выход ставишь 1, если 00 или 11, выкидываешь их и берешь следующие два бита.
Есть улучшенный вариант алгоритма, у которого лучше выход, но он немного сложнее.
Берется четыре бита и из них получаем от нуля до двух бит.
0000 выкидываем
0001 00
0010 10
0011 0
0100 01
0101 00
0110 01
0111 01
1000 11
1001 10
1010 11
1011 11
1100 1
1101 00
1110 10
1111 выкидываем

via dlinyj.livejournal.com/560925.html?replyto=6789405 (типа комментарии к этому посту у меня в ЖЖ)

[@boolivar]

Еще раз спасибо, уже попробовал внедрить.
Немного смущает недетерминированность времени генерации конечной последовательности бит. Зато приведенный в статье метод взлома SMART-карт тут неприменим :)

[@dlinyj]

А можете рассказать, что вы делаете?

[@boolivar]

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