Случайные числа из звуковой карты

    Многие когда-либо интересовались случайными числами. Хочу поделиться моими экспериментами по получению истинно случайных чисел с помощью «аппаратного генератора» встроенного в практически любой компьютер — звуковой карты.

    При подготовке материала, я переписал свой старый Си код на Питоне, поэтому данный опус также является примером по использованию Windows DLL из Питона с использованием стандартной библиотеки ctypes.

    В конце статьи сравниваются данные полученные от двух звуковых карт Realtek и Audigy 2, приведены результаты статистических тестов на случайность.

    UPD Исправил пропавшие в коде нули, которые съело НЛО.

    Скучное теоретическое введение


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

    С другой стороны, есть ограниченный круг проблем, для которых важна истинная случайность полученной последовательности. Главный пример — криптография. Именно в контексте шифрования люди всегда интересовались вопросом получения истинно случайных чисел. Простейший пример — единственный шифр, для которого доказана абсолютная криптографическая стойкость, Шифр Вернама (англ. One-time pad) требует для ключа последовательность истинно случайных чисел равную по длине секретному сообщению. Для обеспечения криптостойкости случайные данные используемые для генерации ключей (будь то шифр Вернама, AES, RSA или что-то еще) никогда не должны использоваться повторно. Что приводит нас к вопросу о поиске надежного источника случайных чисел.

    Звуковая карта, в отличие от большинства остальных компонентов компьютера, имеет в себе не только цифровую часть, но и аналоговую.

    Рассмотрим (примитивно) процесс оцифровки звукового сигнала на линейном входе звуковой карты:
    1. Исходно у нас есть электрический сигнал от какого-то источника, несущий информацию о звуке
    2. Сигнал поступает в аналоговую часть звуковой карты, где он усиливается, чтобы соответствовать динамическому диапазону АЦП (аналогово-цифрового преобразователя).
    3. Сигнал оцифровывается на АЦП с определенными разрешением и частотой дискретизации и поступает в цифровую часть аудиокарты откуда его уже можно получить программно.

    Нас интересует пункт 2. Как известно, любой аналоговый электрический сигнал неизбежно содержит шум, компоненты шума можно примерно разделить на несколько категорий:
    • радиопомехи и наводки от соседних устройств и радиоэфира (слышали когда-нибудь как плохо экранированный усилитель ловит радио?)
    • помехи электропитания (принципиально тоже можно отнести к радиопомехам)
    • тепловой шум случайного движения электронов в компонентах электрической схемы

    Если случайность помех и питания вопрос спорный, то третий тип шума чисто квантовый и истинно случайный.

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

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

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


    Запись звука в Windows


    Простейшим способом записать звук в Windows является использование интерфейсов Waveform Audio из библиотеки winmm.dll. Стандартной библиотеки для работы со звуком в Питоне нет, поэтому мы будет пользоваться библиотекой ctypes, которая предоставляет интерфейс к обычным DLL.

    Импортируем библиотеки sys (для доступа к стандартному выводу) и time (для доступа к функции sleep). Также импортируем все имена из ctypes.

    import sys
    import time
    from ctypes import *


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

    Затем идет цикл, который для каждой функции библиотеки winmm.dll (Питон объект windll.winmm импортирован из ctypes) из списка, мы создаем переменную в текущем контексте vars(), это позволит позднее обращаться к функции просто по имени (waveInOpen вместо windll.winmm.waveInOpen). Также мы присваиваем возвращаемому типу нашу «контролирующую» функцию MMSYSERR_NOERROR.

    def MMSYSERR_NOERROR(value):
        if value ! 0 :
            raise Exception("Error while running winmm.dll function", value)
        return value
     
    for funcname in ["waveInOpen""waveInPrepareHeader",
                     "waveInAddBuffer""waveInStart",
                     "waveInStop""waveInReset",
                     "waveInUnprepareHeader""waveInClose"]:
        vars()[funcname] = windll.winmm[funcname]
        vars()[funcname].restype = MMSYSERR_NOERROR


    Определим необходимые для работы с Windows Audio Си-структуры. Класс структуры должен наследоваться от класса Structure импортированного из ctypes, и должен содержать поле _fields_, перечисляющее имена и Си-типы элементов структуры. Классы для Си-типов мы импортировали из ctypes, их названия говорят сами за себя: c_int, c_uint и тд

    Первая структура WAVEFORMATEX содержит информацию о формате звуковых данных. Без параметров конструктор создаст структуру с типичными значениями для большинства звуковых карт: 16бит 48кГц моно.

    Вторая WAVEHDR описывает буфер для звуковых данных. В качестве параметра конструктор требует объект типа WAVEFORMATEX и выделяет буфер способный хранить 1 секунду аудио данного формата. Массив С-символов создается функцией create_string_buffer.

    class WAVEFORMATEX(Structure):
        WAVE_FORMAT_PCM = 1
        _fields_ = [("wFormatTag", c_ushort),
                    ("nChannels", c_ushort),
                    ("nSamplesPerSec", c_uint),
                    ("nAvgBytesPerSec", c_uint),
                    ("nBlockAlign", c_ushort),
                    ("wBitsPerSample", c_ushort),
                    ("cbSize", c_ushort)]
     
        def __init__(self, samples=48000, bits=16, channels=1):
            self.wFormatTag = WAVEFORMATEX.WAVE_FORMAT_PCM
            self.nSamplesPerSec = samples
            self.wBitsPerSample = bits
            self.nChannels = channels
            self.nBlockAlign = self.nChannels*self.wBitsPerSample/8
            self.nAvgBytesPerSec = self.nBlockAlign*self.nSamplesPerSec
            self.cbSize =  0
     
    class WAVEHDR(Structure):
        _fields_ = [("lpData", POINTER(c_char)),
                    ("dwBufferLength", c_uint),
                    ("dwBytesRecorded", c_uint),
                    ("dwUser", c_uint)# User data dword or pointer
                    ("dwFlags", c_uint),
                    ("dwLoops", c_uint),
                    ("lpNext", c_uint)# pointer reserved
                    ("reserved", c_uint)] # pointer reserved
        def __init__(self, waveformat):
            self.dwBufferLength = waveformat.nAvgBytesPerSec
            self.lpData = create_string_buffer('\000' * self.dwBufferLength)
            self.dwFlags =  0


    Далее мы создаем объект waveFormat. И три буфера для звуковых данных.

    К сожалению с большинством драйверов winmm.dll (тк это достаточно старый интерфейс) не позволяет оцифровывать точнее 16 бит даже если аудиокарта это поддерживает. Мне известна только одна карта: SB Live24bit, которая это могла. Сейчас её под рукой нет, а есть Audigy 2 Notebook, которая пишет 24 бит только в DirectX или ASIO. Поэтому сегодняшний пример рассчитан на 16 бит (место которое надо изменить для 24 бит помечено комментарием, на случай если ваша карта это поддерживает).

    waveFormat = WAVEFORMATEX(samples=48000,bits=16)
    waveBufferArray = [WAVEHDR(waveFormat) for i in range(3)]


    Следующаяя функция основная в программе, она будет вызываться Windows, когда winmm.dll заполнит один из наших буферов.

    Тк это Си-callback, сначала необходимо создать класс. Это делается функцией WINFUNCTYPE из ctypes, аргументы: возвращаемый тип, типы аргументов. Тк наша функция ничего не должна возвращать, первый аргумент None, остальные согласно MSDN. Обратите внимание на аргумент POINTER(c_uint) — это указатель на пользовательские данные, в примере это просто число, но там может быть что угодно, например класс указывающий куда писать данные или сколько данных необходимо и тд. POINTER(WAVEHDR) это указатель на буфер с данными.

    Параметр uMsg указывает на причину вызова, нас интересует MM_WIM_DATA — доступны аудиоданные.

    WRITECALLBACK = WINFUNCTYPE(None, c_uint, c_uint, POINTER(c_uint), POINTER(WAVEHDR), c_uint)
    def pythonWriteCallBack(HandleWaveIn, uMsg, dwInstance, dwParam1, dwParam2):
        MM_WIM_CLOSE = 0x3BF
        MM_WIM_DATA = 0x3C0
        MM_WIM_OPEN = 0x3BE
        if   uMsg == MM_WIM_OPEN:
            print "Open handle =", HandleWaveIn
        elif uMsg == MM_WIM_CLOSE:
            print "Close handle =", HandleWaveIn
        elif uMsg == MM_WIM_DATA:
            #print "Data handle =", HandleWaveIn
            wavBuf = dwParam1.contents
            if wavBuf.dwBytesRecorded >  0 :
                bits = [ord(wavBuf.lpData[i]) & 1 for i in range( 0 ,wavBuf.dwBytesRecorded,2)]
                # для 24 бит: заменить в конце 2 на 3 в предыдущей строке
                bias = [bits[i] for i in range( 0 ,len(bits),2) if bits[i] != bits[i+1]]
                bytes =  [chr(reduce(lambda v,b:v<<1|b,bias[i-8:i], 0 )) for i in range(8,len(bias),8)]
                rndstr = ''.join(bytes)
                #print bytes,
                sys.stdout.write(rndstr)
            if wavBuf.dwBytesRecorded == wavBuf.dwBufferLength:
                waveInAddBuffer(HandleWaveIn, dwParam1, sizeof(waveBuf))
            else:
                print "Releasing one buffer from", dwInstance[ 0 ]
                dwInstance[ 0 ]-=1
        else:
            raise "Unknown message"


    Ключевые моменты:
    bits = [ord(wavBuf.lpData[i]) & 1 for i in range( 0 ,wavBuf.dwBytesRecorded,2)]

    Тк данные упакованы по 2 байта (3 байта в случае 24 бит) мы проходим по массиву с шагом 2: range(0,wavBuf.dwBytesRecorded,2) и отбираем младший бит младшего байта в паре: ord(wavBuf.lpData[i])&1. Результатом будет список bits младших битов каждого сэмпла.

    Небольшое метематическое отступление:

    Случайные данные могут иметь различное распределение, т.е. частоту выпадения того или иного числа. Например, если у нас последовательность бит 0000100000000, и положение единицы меняется случайно, это тоже случайная последовательность, но очевидно, что вероятность выпадения нуля гораздо выше чем единицы. Наиболее удобно т.н. «равномерное распределение» в котором вероятность появления нуля и единицы равна. Процедура приведения к равномерному распределению называется unbiasing. Наиболее простой метод это замена: 10 -> 1, 01 -> 0, 11 -> отбрасываем, 00 -> отбрасываем.

    Unbiasing выполняет следующая строка
    bias = [bits[i] for i in range( 0 ,len(bits),2) if bits[i] != bits[i+1]]

    Проходим с шагом 2: range(0,len(bits),2), выкидывая одинаковые пары: bits[i] != bits[i+1], из оставшихся берем первый: bits[i].

    Наконец, это выражение собирает наши биты в байты и сливает все в строку
     bytes =  [chr(reduce(lambda v,b:v<<1|b,bias[i-8:i], 0 )) for i in range(8,len(bias),8)]

    Проходим с шагом 8, для каждых 8ми битов вызывается функция reduce(lambda v,b:v<<1|b,bias[i-8:i],0). Здесь использован элемент функционального программирования, анонимная функция(назовем её временно F) lambda v,b:v<<1|b, вызывается функцией reduce так: F(...F(F(0,bias[i-8]),bias[i-7]),...,bias[i-1]) — получается байт, который преобразуется в символ функцией chr.

    Список байт преобразуется в строку, которая пишется в stdout, тк это двоичные данные лучше вывод перенаправить в файл. Если хотите писать в консоль, то лучше это делать через "print bytes,", тк при бинарном выводе в консоль Винда плохо ловит Ctrl+C.

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

    Создаем экземпляр С-функции класса WRITECALLBACK из нашей функции pythonWriteCallBack.

    Далее, определив несколько полезных констант, открываем устройство WAVE_MAPPER (можно напрямую задать номер звковой карты, они нумеруются, начиная с нуля: 0, 1, 2) сначала с параметром WAVE_FORMAT_QUERY, чтобы проверить что формат поддерживается, затем с параметром CALLBACK_FUNCTION, указав нашу функцию и пользовательские данные (в нашем случае число ExitFlag).

    Обратите внимание как передаются указатели из Питона в Си-функции, с помощью функции byref. Также мы передали указатель на наши «пользовательские данные» в byref(ExitFlag), который Windows будет передавать нашему callback в виде dwInstance при каждом событии (заполнения буфера например).

    Затем мы вызываем waveInPrepareHeader для каждого созданного буфера и передаем их winmm.dll с помощью waveInAddBuffer. Наконец, вызов waveInStart(HandleWaveIn) дает команду начать ввод аудио. Конца мы ждем в цикле time.sleep(1).

    Выход из программы осуществляется по перехвату комбинации клавиш Ctrl+C (Питон KeyboardInterrupt).
    writeCallBack=WRITECALLBACK(pythonWriteCallBack)
    try:
        ExitFlag = c_uint(3)
        HandleWaveIn = c_uint( 0 )
        WAVE_MAPPER = c_int(-1)
        WAVE_FORMAT_QUERY = c_int(1)
        CALLBACK_FUNCTION = c_int(0x30000)
     
        waveInOpen( 0 , WAVE_MAPPER, byref(waveFormat) 0 0 , WAVE_FORMAT_QUERY)
        waveInOpen(byref(HandleWaveIn), WAVE_MAPPER, byref(waveFormat), writeCallBack, byref(ExitFlag), CALLBACK_FUNCTION)
     
        for waveBuf in waveBufferArray:
            waveInPrepareHeader(HandleWaveIn, byref(waveBuf), sizeof(waveBuf))
            waveInAddBuffer(HandleWaveIn, byref(waveBuf), sizeof(waveBuf))
     
        waveInStart(HandleWaveIn)
     
        while 1:
            time.sleep(1)
     
    except KeyboardInterrupt:
        waveInReset(HandleWaveIn)
     
        while 1:
            time.sleep(1)
            if ExitFlag.value ==  0 :
                break
     
        for waveBuf in waveBufferArray:
            waveInUnprepareHeader(HandleWaveIn, byref(waveBuf), sizeof(waveBuf))
     
        waveInClose(HandleWaveIn)


    Чтобы отключить автоматическое преобразование конца строки, вызов скрипта следует осуществлять с параметром "-u":
    c:\...\python.exe -u Скрипт.py > файл.rnd

    Выводы



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

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

    Оптимальные настройки микшера для записи, полученные экспериментальным путем: выбираем канал записи (не воспроизведения!) Line-In, громкость канала в максимум, все остальные каналы отключаем.

    Канал Microphone показал худшее качество случайных чисел, объясняется это тем, что многие аудиокарты пытаются «улучшить» сигнал с микрофона и применяют различные цифровые фильтры. На одной из протестированных аудиокарт (а именно Realtek) микрофонный канал выдавал негодный для получения СЧ вывод. На Audigy 2 включение усиления микрофонного сигнала «Mic Boost +20DBA», также приводило к удалению случайной компоненты.

    Протестировать качество полученных случайных чисел можно при помощи нескольких программ. Простейшая в использовании ent (скачать с http://www.fourmilab.ch/random/random.zip). Запускается из консоли
    > type data.rnd | ent.exe
    Где data.rnd двоичный файл со случайными данными (не забудьте закомментировать лишние print'ы в программе, они могут немного подпортить статистику). Оптимальный размер файла для теста ок. 500КБ. Программа подсчитывает несколько параметров:
    • Энтропию (для случайных данных: стремится к 8 — количество бит в байте)
    • Арифметическое среднее (для случайных данных: стремится к 127.5)
    • Число Пи методом Монте-Карло (для 500кБ данных ошибка порядка 0.1%)
    • Хи-Квадрат (в идеале лежит в пределах 10-90%)
    • Коэффициент (для случайных данных близок к 0)


    Следует помнить, что критерии случайности — статистические по своей природе и применяются не к последовательности самой по себе, а к источнику. Поэтому для получения надежных результатов надо провести серию тестов на выборках одного источника. Наример 20 кусков по 500КБ. Если большинство прошло тест (ок. 90%), то источник случаен с определенной вероятностью.

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

    Также, я протестировал случайность «нулевого» вывода обеих звуковых карт с помощью более навороченного пакета программ от NIST (Национального Института Стандартов США). Обе карты показали хорошее качество случайных чисел.

    Занимательно, что встроенное аудио от Realtek, дает чуть лучшую равномерность распределения, видимо из-за более низкого качества АЦП и высокой шумности. Audigy 2 была бы вне конкуренции в 24 битном режиме, который Реалтеком не поддерживается (в любом случае для него нужен DirectX, а DirectX в Питоне это отдельная история).

    Ссылки на другие тестовые пакеты:
    http://stat.fsu.edu/pub/diehard/
    http://www.phy.duke.edu/~rgb/General/dieharder.php
    http://csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html

    Пример вывода программы ent на файле полученном записью тишины с линейного входа Audigy 2:
    Entropy = 7.999609 bits per byte.

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

    Chi square distribution for 500000 samples is 270.78, and randomly
    would exceed this value 23.75 percent of the times.

    Arithmetic mean value of data bytes is 127.5890 (127.5 = random).
    Monte Carlo value for Pi is 3.139644559 (error 0.06 percent).
    Serial correlation coefficient is 0.001109 (totally uncorrelated = 0.0).
    Метки:
    Поделиться публикацией
    Реклама помогает поддерживать и развивать наши сервисы

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

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

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

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

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

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

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

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

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

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

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

        Только за одну эту шутку я готов инкрементировать ваши персональные хабрапараметры, спасибо за настроение :)
        Ну и за статью конечно!
        • +1
          спасибо, это моя первая статья на хабре
          (о! и я опечатку заметил, ща пофиксим)
          • 0
            Весьма неплохое начало, так держать.
          • –3
            Эта шутка полностью отражает смысл статьи. Суть — сведение мозга у теоретика. Нет ни одного практического примера, где качественный генератор ПСЧ не может быть применён. И уязвимость его как раз и будет равна вероятности генерации этой статьи звуковой картой.
          • +1
            Нашел готовые решения для windows и *nix, если кому интересно, как и мне:
            www.cyotec.com/resources/cyorand/ — для windows
            www.digital-scurf.org/software/randomsound — для *nix
            • 0
              Имею ввиду готовые исполняемые файлы для windows. Для *nix придется собрать.
              • 0
                Для Debian (lenny, squeeze, sid) есть готовый пакет randomsound
              • +1
                randomsound — судя по описанию, передает данные в random pool ядра линукса. Это специальная часть ядра, которая может принимать «случайность» данных в любых формах из разных источников. Внутри (ядра линукса) применяется ряд алгоритмов, чтобы равномерно распределить «случайность» среди битов массива (кажется там MD5 или что-то на подобии), также ведется учет имеющихся битов случайности.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

                                                    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% вероятностью.

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

                                                    А то что для разного харда, разные результаты, я не отрицаю (хотя формулировочка у вас далека от нейтральной). И шифровать государственные тайны этими ключами не агитирую)
                                                  • 0
                                                    Звуковые карты особенно распространены на серверах, в стойках.
                                                    • 0
                                                      А что, действительно бывают аудиоинтерфейсы, монтирующиеся в стойку.
                                                    • 0
                                                      Младший бит не всегда будет случайным, потому что после АЦП может производиться округление и нормализация. На неслучайность также сильно может повлиять наводка сигнала от какой-нибудь микросхемы (мало их чтоли). Вообще, кому уж очень нужен сильно рандомный генератор, лучше купить для этого соответствующий хард.
                                                      • 0
                                                        Статья не для тех кому сильно нужно, а для интересующихся. Тема младших битов, наводок и тд раскрыта к комментариях.
                                                      • 0
                                                        Безумно интересная статья! Побольше бы таких! Спасибо. Как раз занимаюсь имитационными моделями с стохастическими параметрами, есть над чем задуматься!
                                                        • +1
                                                          Если понравилось, рекомендую почитать и комментарии (те что без картинок). В них затронуты несколько интересных моментов не освещенных в статье.
                                                        • 0
                                                          Помню, в чипсете Intel 815, кажется, был аппаратный генератор случайных чисел, основанный на тепловом шуме и т.д. Ну неужели нельзя встраивать такой во все современные чипсеты и даже процессоры? Решили бы много проблем в тех областях, где нужны истинно случайные последовательности. Есть ведь подобные аппаратные решения от третих лиц.
                                                        • 0
                                                          В качестве доп. литературы habrahabr.ru/blogs/python/62237/ )
                                                          Там заодно написано как получить равномерное распределение.

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