?

Log in

No account? Create an account

masterok


Мастерок.жж.рф

Хочу все знать


Previous Entry Share Next Entry
Как сгенерировать настоящие случайные числа
masterok


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

Вот вам история из 90-х:


Представьте, что сейчас 1995 год и вы собираетесь совершить первую покупку в онлайне. Вы открываете браузер Netscape и прихлёбываете из чашечки кофе, пока главная страница медленно загружается. Ваш путь лежит на Amazon.com — новый онлайн-магазинчик, о которой рассказал вам друг. Когда наступает этап оформить покупку и ввести персональные данные, адрес в браузере меняется с «http» на «https». Это сигнализирует о том, что компьютер установил зашифрованное соединение с сервером Amazon. Теперь можно передавать серверу данные кредитной карты, не опасаясь мошенников, которые хотят перехватить информацию.





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

Проблема в том, что секретные ключи, которые использовал Netscape, были недостаточно случайными. Их длина составляла всего 40 бит, что означает около триллиона возможных комбинаций. Это кажется большим числом, но хакерам удалось взломать эти коды, даже на компьютерах 1990-х годов, примерно за 30 часов. Якобы случайное число, которое Netscape использовал для генерации секретного ключа, базировалось всего на трёх значениях: времени суток, идентификационном номере процесса и идентификационном номере материнского процесса — все они являются предсказуемыми. Из-за этого злоумышленник имел возможность сократить количество вариантов для перебора и найти нужный ключ гораздо раньше, чем предполагали в Netscape.

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

Исследователям удалось изобрести генераторы псевдослучайных чисел, которые признаны криптографически надёжными. Но их нужно запускать с качественного случайного начального значения (random seed), иначе они всегда сгенерируют один и тот же набор чисел. И для этого начального значения вам нужно нечто такое, что действительно невозможно подобрать или предсказать.





И вот группа ученых из МГУ разработала и сконструировала компактный высокоскоростной квантовый генератор истинно случайных чисел.

«Развитие современных квантовых технологий открыло новые перспективы для создания систем защищенной связи. Наиболее яркий пример — квантовая криптография. Для распределения секретных ключей в системах квантовой криптографии требуется большое количество случайных последовательностей 0 и 1. Для этих целей используются квантовые генераторы случайных чисел», — поясняет Сергей Кулик, доктор физико-математических наук, профессор кафедры квантовой электроники физического факультета МГУ.

Учёные МГУ разработали и сконструировали такой генератор, последовательности чисел которых можно считать истинно случайными. Дело в том, что в основе действия новой разработки лежат законы релятивистской, а не классической физики. Исследователям удалось оптимально выбрать и сгруппировать фотоотсчёты для исходной последовательности и добиться скорости генерации случайной последовательности скоростью в 64 Мбит/с, 75 Мбит/с и 100 Мбит/с. Сгенерированные последовательности успешно прошли статистические тесты NIST на случайность.

«Результаты измерений над квантовой системой, приготовленной каждый раз в одном и том же состоянии, носят принципиально случайный характер. Поэтому истинная случайность имеет место только в квантовой области», — заключил Сергей Кулик.

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

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

Результаты исследования опубликованы в журнале Laser Physics Letters.

[источники]источники
https://habrahabr.ru/post/151187/
https://habrahabr.ru/post/128666/
https://www.popmech.ru/technologies/news-398402-v-mgu-nauchilis-generirovat-istinno-sluchaynye-chisla


Subscribe to  masterok

Posts from This Journal by “Наука” Tag


promo masterok январь 2, 12:00 46
Buy for 300 tokens
Вот так выглядит ушедший от нас 2017 год. А вот кстати, начало 2018 года показывает еще больший трафик, чем декабрь 2017: И вот один из дней - рекордсменов за всю историю журнала тоже уже в 2018 году: Красная цифра - это общее количество уникальных посетителей попавших в блог. В…

  • 1
Да...Случайность - закономерность...

---Дело в том, что в основе действия новой разработки лежат законы релятивистской, а не классической физики.

Не релятивистской, а квантовой. В принципе, я так понял, люди заюзали принцип непределенности. Интересно, что они меряли и как... И да - такой компактный генератор для компьютера может оказаться весьма интересным...

Нет. сгруппировать фотоотсчёты это не сгенерировать математически.

таприча будут все вскрывать карточки на раз... хорошо предупредил...

(Deleted comment)
Ничего нового. Сгенерировать случайные числа чисто математически невозможно. А использовать в качестве случайного элемента в алгоритме можно всё, что угодно. Скажем, тысячные доли градусов в температуре внутри вашего холодильника. Градусы будут изменяться в зависимости от загрузки и внешней температуры, но тысячные доли будут скакать.

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

Edited at 2017-11-24 07:40 pm (UTC)

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

а ещё если кто-то берсеркера читал (Фред Сапенбахен) там идея с радиокативным слитком была, который нужен.
достаточно обычный счётчки ионизирубщих частиц взять, фоновой радиации много, и структура шума который такой датчик создаёт, вообще никак не предсказуема

Edited at 2017-11-24 08:57 pm (UTC)

/dev/urandom

А вообще юзер - лучший источник случайной величины

Некоторые пользователи, более, чем на звание псевдослучайных не дотягивают. Например, какова вероятность, что "творец" данной ветви не использует слово из трёх букв, в любом другом сообщении? Исчезающе мала, я думаю.

Кажется вы не понимаете что такое случайная величина

Можно брать значение числа тактов процессора после инструкции rdtsc, плюс смешивать с временем, рандомной математической функцией, ещё с чем-то смешивать... Микрофон и шум кулера, фон сети 50гц в некий момент и прочие звуки...

А истинной случайности логически не возможно, воде бы.. Есть информация(следствие) - есть причины(цепь событий откуда взялось именно такое). Не нашли причину результата-следствия - ну чтож, это не значит что нету, что ничего до не обуславливало результат!!!
Может - быть есть-таки скрытые параметры, и ещё не нашли. А неравенства белла неубедительны.

Как шутил у нас преподаватель ТАУ (теории автоматического управления):
- На всемирном конкурсе генераторов случайных чисел победила женская логика...

Квантовые генераторы случайных чисел уже давно разработаны и эксплуатируются в тех же банках. Интерфейс - хочешь USB, хочешь PCI-E. Один из представителей - Quantis Random Number Generator.

Новый квантовый метод генерирует действительно случайные числа https://vnauke.in.ua/techno/novyiy-kvantovyiy-metod-generiruet-deystvitelno-sluchaynyie-chisla/

  • 1