Pull to refresh

Comments 72

Возможно, что качество возрастет, если иначе получить 1 бит из каждого отсчета, например, принимая за 0 отклонение значения в данном отсчете от среднего значения в данном окне/фрейме в меньшую сторону, и за 1 — отклонение значения отсчета от среднего значения для окна/фрейма в большую сторону.
В смысле группировать сэмплы и брать по одному биту от группы? Это немного лишнее усложнение, приведенный пример unbiasing'а хоть и примитивный, но надежный. Если он не даст равномерное распределение, то последовательность не случайная 100%.

Сказанное справедливо для записи «тишины». Если есть сигнал, то можно/лучше не делать unbiasing, а замешать порцию данных чем-нибудь вроде SHA1 и использовать как seed для качественного генератора ПСЧ.

Разные схемы аналого-цифровых преобразователей могут давать свои индивидуальные асимметрии в младших битах. Плюс могут использоваться разные техники для преобразования истинной частоты дискретизации при оцифровке в ту частоту, которую отдают софту, и они тоже внесут свои особенности в младшие биты.
В итоге может оказаться, что младший бит в каждом сэмпле всегда равен нулю. Или, например, что три младших бита принимают только значения {5, 6, 7}. Поэтому думаю, что лучше не использовать младший бит напрямую (даже с последующей заменой по шаблону). Вместо этого попробовать для какого-то «окна» (например, для одного считанного фрейма) рассчитать среднее (как вещественное число) и далее смотреть, в какую сторону каждый из семплов отклоняется от этого среднего, и в зависимости от этого генерировать 0 или 1, а точное попадание на середину игнорировать.
Согласен, я писал что структура случайности зависит даже от софтовых настроек (они могут включить предобработку внутри карты). Поэтому статью не стоит рассматривать скорее, как направление, в котором надо копать, а не безапелляционное руководство к действию. Условия в которых описанный подход работает с моими звуковыми картами четко указаны, я не отрицаю возможность существования других ситуаций)

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

Если же известно что в потоке есть случайность но не известно в каких именно битах (или она плавает между битами), то надо брать все целиком и скармливать SHA1)
Согласен, что звуковая карта дает дополнительный источник случайных битов. Но на качество этого источника сложно полагаться.
Например, я замечал, что старые АЦП хорошо улавливали различные шумы от работы оборудования внутри компьютера, например, от HDD, да и вообще от 50/60 Hz. :)
Если бы шум при оцифровке нулевого сигнала был идеален, то Ваша процедура unbiasing была бы вообще ненужна… Если она нужна — значит там не совсем шум. Скорее всего там спектр будет совсем неровным (если взять исходные данные без обработки).
А вообще Ваша статья — понравилась.
> Если бы шум при оцифровке нулевого сигнала был идеален, то Ваша процедура unbiasing была бы вообще ненужна… Если она нужна — значит там не совсем шум.

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

То что распределение процесса не равномерно, отнюдь не значит, что он не случайный. Абсолютно все аппаратные ГСЧ (будь то радиоактивный распад, оцифровка «голосов космических цивилизацай» или пролет фотонов через полупрозрачное зеркало), требуют последующего unbiasing. Даже если источник идеальный, процесс оцифровки вносит сдвиг в распределение (тот самый bias).

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

> Если бы шум при оцифровке нулевого сигнала был идеален, то Ваша процедура unbiasing была бы вообще ненужна… Если она нужна — значит там не совсем шум.

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

Спасибо за интересные комментарии.)
>> К сожалению, 100%-ых критериев в статистике нет, тк с определнной вероятность ваша звуковая карта может сгенерировать эту статью (собственно так я её и получил — шучу).

Только за одну эту шутку я готов инкрементировать ваши персональные хабрапараметры, спасибо за настроение :)
Ну и за статью конечно!
спасибо, это моя первая статья на хабре
(о! и я опечатку заметил, ща пофиксим)
Весьма неплохое начало, так держать.
Эта шутка полностью отражает смысл статьи. Суть — сведение мозга у теоретика. Нет ни одного практического примера, где качественный генератор ПСЧ не может быть применён. И уязвимость его как раз и будет равна вероятности генерации этой статьи звуковой картой.
Имею ввиду готовые исполняемые файлы для windows. Для *nix придется собрать.
Для Debian (lenny, squeeze, sid) есть готовый пакет randomsound
randomsound — судя по описанию, передает данные в random pool ядра линукса. Это специальная часть ядра, которая может принимать «случайность» данных в любых формах из разных источников. Внутри (ядра линукса) применяется ряд алгоритмов, чтобы равномерно распределить «случайность» среди битов массива (кажется там MD5 или что-то на подобии), также ведется учет имеющихся битов случайности.

Единственная возможная проблема (в код не смотрел) может быть, что надо каким-то образом оценить «количество случайности» перед передачей данных ядру.

cyorand — для именно исследования поведения аудиокарт на мой взгляд подходит слабо, т.к. там применен некий доморощенный алгоритм смешения исходных данных, который случайности не добавляет (ибо это не возможно:) ), а картину запутывает. Интересно было бы посмотреть на тесты более продвинутыми пакетами типа diehard или NIST.

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

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

В 2004-м году я своим студентам специальности «Программное обеспечение» на курсовую по «Защите информации» давал задание сделать то же самое, что делаете Вы (с тестированием случайности по FIPS). Результаты следующие:
самые младшие биты шумового потока не всегда достаточно случайны, на некоторых звуковых картах
самый младший бит даже банально не распределен равномерно. Наибольшую энтропию несут 2-3-4 бит при 16 битном семплировании.
Скажем так, в том месте статьи, где это утверждение стоит, его можно считать гипотезой (достаточно разумной :) ).

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

Равномерность распределения это не проблема, она практически ни в одном аппаратном ГСЧ не достигается «из коробки». У меня равномерность лечится алгоритмом фон Неймана, можно также криптографические хеши использовать, но только после того как установлена случайность источника.
В жизни нет ничего случайного и физика нам это доказывает с каждым днём. Но данная имитация полезна, но где она может применяться на практике?
после соответствующей обработки — при генерации одноразовых (сессионных) криптографических ключей
А может случится такой вариант что, воссоздать уровень шумов влияющих на получение уникального значения получится сторонним лицам?
Гипотеза утверждает, что содержимое младшего бита сигнала после АЦП — это результат теплового шума (хаотичного движения электронов), поэтому, принимая данную гипотезу, повлиять на это не возможно. В реальности, прямой доступ к младшему разряду АЦП может быть сильно затруднён или вовсе невозможен. Поэтому, для какого-то набора аппаратуры, такое, наверное, можно сделать. Поэтому, применять напрямую эту схему в ответственных местах нельзя — нужно тщательно исследовать каждый конкретный набор аппаратных и программных средств. Как-то так.
Естественно для серьезного применения желательно комбинировать несколько независимых источников.

Еще можно поиграть в теорию заговора и предположить, что производители звуковых карт в сговоре с ...(подставить нужное) вычищают случайность и подставляют предсказуемую последовательность ПСЧ)
Как теорфизик (еще и работающий по специальности) я бы сказал, что в нашей жизни всё случайно. Но вероятность разных событий естественно подчиняется физическим законам (а касательно жизни — здравому смыслу). Т.е. если учиться в университете умным 100% не станешь, но вероятность поумнеть там значительно выше, чем если вместо универа лежать на диване и смотреть сериалы.

Данная имитация полезна тем, что просто интересна) Ну и в принципе, после должной проверки может использоваться как дополнительный источник случайности там, где она нужна (в криптографии например).

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

Если подумать то в практическом отношении разницы нет) В науке это называется «теория скрытых параметров». См. ru.wikipedia.org/wiki/Теория_скрытых_параметров
Но вы наверно согласны с тем, что методы подсчёта вероятности очень уж погрешны и требуют альтернатив?
Это вопрос больше философский) Задача физики — описать эксперимент и предсказать резульат аналогичного эксперимента в будущем.

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

Да что в квантовую физику лезть? Пример из классической: нелинейная динамика с.м. ru.wikipedia.org/wiki/Эффект_бабочки
«Задача физики — описать эксперимент и предсказать резульат аналогичного эксперимента в будущем.»

Этот эксперимент ещё нужно создать, задача физики создать предпосылке к эксперименту а потом и сам эксперимент а описать и предсказать могут и техники.
Главной предпосылкой к эксперименту, является окружающий нас мир) Эксперимент это изучение явлений природы в контролируемых, повторяемых условиях (определение «из головы», на истину в последней инстанции не претендую).

«Описать» не смысле записать числа на бумажку, а ответить (постараться) на вопросы «как» и «почему».
Тогда всё сводится к поиску новых явлений природы и это основная задача физики :)
Раз вы с физикой на ты, может быть сможете объяснить принцип квантовой неопределенности?
Пошёл писать диссертацию.
В двух словах описать я не возьмусь, тряпками закидают) Гляньте Википедию или какие-нибудь популярные статьи.
Чего я не понимаю так это зачем все это было писать на питоне. Чем С++ не подходит?
На Питоне короче, легче и быстрее вносить изменения, т.к. это эксперимент и параметры приходится варьировать) Считайте, что прототип мы пишем на Питоне, чтобы потом реализовать сразу как надо на С++ (если нужна скорость например, или хотим сделать библиотеку)
Большое вам спасибо за адаптацию кода на python!
Для людей без специальной академической подготовки (высшего мат. или физ. образования) код на питоне доступнее, нагляднее и элементарно понятнее.
1. Преобразование случайной величины её функцией распределения u =F(x) даст равномерное на [0, 1]. То есть полученную выборку можно просто ранжировать.
2. Коэффициент коррелляции (Пирсона, Кендалла, Спирмана) равный нулю не свидетельствует о независимости пары случайных величин.
1. Функция распределения у звуковой карты нам не известна. Так же не известно является ли она постоянной во времени или зависит от температуры/ветра на Марсе или еще чего.

2. Но вы не отрицаете, что он стремится к нулю для случайных величин? Как минимум он позволяет отсеять величины явно не случайные. Более сложные статистические тесты приведены по ссылкам.
1. Значение в выборке предлагается заменить рангом = место в отсортированном по возрастанию массиве / объем выборки. То есть преобразовать эмпирической функцией распределения.
2. Я хотел сказать, что это не критерий. Для независимых СВ корреляция равна нулю, обратное не верно. Но отсеять можно, вы правы.)
1. Чтобы преобразовать эмпирической функцией распределения, придется групировать биты в числа и в даже в этом случае будет ошибка дискретизации в равномерности ответа (это не критично, но зачем?).

Сами биты так преобразовать не получится. Например функция распределения (0 — 13%, 1 — 87%), что делать?
Товарищи минусующие, это не holywar, а дополнение к статье.
Зато в вашем Линуксе нет DirectX, поддерживающего 24-битный звук!
Он не «наш». У меня все десктопы — Windows (дома — Windows 7, на работе — Windows XP), а вот сервера — Hardy.
Насколько мне помнится, urandom как раз и пополняется из random pool, про который упоминали выше в контексте randomsound. Кроме того, туда падают движения мышью и нажатия клавиш.
Если быть точным то urandom становится чистым ГПСЧ, после того как накопленный ядром запас энтропии будет исчерпан. А вот random в этом случае просто приостановит вывод.
Когда на компьютеры будут ставить встроенные звуковые карты с очень хорошим АЦП, как сейчас на профессиональных конвертерах, тогда все начнут скупать старые аудиокарты, потому что они дают очень хорошие случайные числа!
Это так же как сейчас с допотопными ламповыми усилителями и проигрывателями виниловых дисков.
Возможно, сделают специальный шумящий выход для получения случайных чисел.
Об аппаратных ГСЧ время от времени вспоминают все производители чипсетов — там побывали и Intel и AMD и VIA…
К сожалению нормального единого стандарта так и не разработали.
Microsoft CryptoAPI умеет в случае установленного на материнке чипа и драйверов предоставлять доступ к такому ГСЧ.
Последнее веяние, которое я слышал, может меня поправят, — это стандарт TPM от Trusted Computing Group.
У хороших карт разрешение выше. В 24 битах избежать шума практически не возможно (да и не рационально). А вот вырезать/подменять могут.
Очень хочется запостить картинку с летчиком (ну, которую на дёрти любят постить).
А вы попробуйте. Может быть многе вас поддержат :)
Хорошо бы, да карма слита. Может, вы? :)
Ладно, можно рискнуть :)

хорошая статья ;) в свое время bass.dll использовал из delphi для получения начального seedа для обычного дельфийского ГСЧ. Было это в системе пакетного тестирования различных ГА для задачи о рюкзаке. Но насколько улучшается точность тестов при задании таким образом seedа осталось для меня загадкой.$)))
А первоначально использовалось что-то в духе md5 от GetTickCount xor GetCurrentProcessID.
В таком варианте большую роль играет качество ГПСЧ.
Несомненно. Где я утверждал обратное?)
Можно суммировать плюсики за топики, чем не случайное число (вот только маленькое)…
Попробуйте протестировать полученные с аудио-карты случайные числа набором тестов Die Hard (http://en.wikipedia.org/wiki/Diehard_tests).

и после этого сравните, например, с тестами набора случайных чисел Marsaglia (целый CD-ROM с шумом) (http://www.stat.fsu.edu/pub/diehard/).

Вы будете неприятно удивлены.

Вы можете сколько угодно долго оттачивать программные алгоритмы и аппаратную часть, но Ваши труды не будут ничего стоить, т.к. на другой такой же звуковой карте (той же модели и даже из той же серии) вы получите совсем другие результаты и не факт, что они будут отличаться в лучшую сторону.
Лично я удивлен не буду, тк тестировал)

Die Hard'ом тестировался вывод SB Live 24bit (когда она у меня была) в 24 битном режиме. Данные прошли тест, уже не помню точно вероятность, но близко к 99%.

Сейчас мне было лень его пересобирать, поэтому я использовал «NIST Statistical Test Suite», который не хуже, я бы сказал лучше, тк их методика подробно расписана в статье csrc.nist.gov/publications/nistpubs/800-22-rev1/SP800-22rev1.pdf (англ.). В моем тесте использовалась выборка из 100 последовательностей по 5000000 бит. Преодолен установленный порог для всех тестов, кроме двух (по понятным причинам, для них нужны очень длинные последовательности). Генератор случайный с 99% вероятностью.

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

А то что для разного харда, разные результаты, я не отрицаю (хотя формулировочка у вас далека от нейтральной). И шифровать государственные тайны этими ключами не агитирую)
Звуковые карты особенно распространены на серверах, в стойках.
А что, действительно бывают аудиоинтерфейсы, монтирующиеся в стойку.
Младший бит не всегда будет случайным, потому что после АЦП может производиться округление и нормализация. На неслучайность также сильно может повлиять наводка сигнала от какой-нибудь микросхемы (мало их чтоли). Вообще, кому уж очень нужен сильно рандомный генератор, лучше купить для этого соответствующий хард.
Статья не для тех кому сильно нужно, а для интересующихся. Тема младших битов, наводок и тд раскрыта к комментариях.
Безумно интересная статья! Побольше бы таких! Спасибо. Как раз занимаюсь имитационными моделями с стохастическими параметрами, есть над чем задуматься!
Если понравилось, рекомендую почитать и комментарии (те что без картинок). В них затронуты несколько интересных моментов не освещенных в статье.
Помню, в чипсете Intel 815, кажется, был аппаратный генератор случайных чисел, основанный на тепловом шуме и т.д. Ну неужели нельзя встраивать такой во все современные чипсеты и даже процессоры? Решили бы много проблем в тех областях, где нужны истинно случайные последовательности. Есть ведь подобные аппаратные решения от третих лиц.
Sign up to leave a comment.

Articles