Инновационный метод производства энтропии
I am chaos. I am the substance from which your artists and scientists build rhythms. I am the spirit with which your children and clowns laugh in happy anarchy. I am chaos. I am alive, and I tell you that you are free.— Эрис, богиня хаоса, раздора и путаницыПорядок невозможен без беспорядка. Программисты часто ныряют в хаос в поиске гениальных мыслей, случайных чисел и волшебных коэффициентов, которыми должно обладать каждое уважающее себя приложение. В этой статье я расскажу, как практически из ничего получить высококачественные образцы случайности, которыми можно, например, поделиться со своими друзьями-хаосопоклонниками.
Предупреждение для юристов, политиков и других роботов: это полушуточная статья.
Для получения хаоса, нам понадобятся два файла, которые мы будем называть «Семя Хаоса» и «Земля». Семя Хаоса — небольшой файл, из которого и будет рождаться хаос. Земля — файл произвольного размера, который будет задавать объем результирующей энтропии, ну и немного увеличивать случайность результата. В принципе, без Земли можно было бы и обойтись, но, на всякий случай, лучше ей пользоваться — особенность случайных данных в том, что их сложно отличить от неслучайных. Вдруг у нас одни нули сгенерируются? Цельный, рабочий, файл гарантирует, что в результате всегда будет хоть что-то вещественное. Выбор подходящего кандидата на роль Семени Хаоса — сложная задача. Файл должен обладать хорошей начальной энтропией, к тому же, вы должны его искренне ненавидеть, потому что он будет, в дальнейшем, претерпевать ужасные болезненные изменения. Неплохие показатели случайности у изображений, к тому же, они валяются по всему Интернету. Если доступа к Интернету нет — вполне вероятно, что ваше пожирающее хаос приложение будет запущено на компьютере человека, который смотрит и сохраняет смешные картинки вместо того, чтобы жить насыщенной жизнью, поэтому, беспокоиться не стоит.Файлы, идеально подходящие на роль Семени Хаоса
Используем логотип DMCA. Теперь с ним нужно что-то сделать, как-то превратить его из порядочного набора бит в беспорядочный. С этой задачей хорошо справляется семейство псевдослучайных функций. По их определению, не существует эффективного алгоритма, который отличал бы их вывод от вывода функции, генерирующей истинно-случайную последовательность бит — именно то, что нужно.
Один из моих любимых криптографических шифров — AES — является псевдослучайным преобразованием, поэтому, будем использовать его.
Какая-либо криптостойкость нас не интересует совершенно, нам нужно лишь превратить Семя Хаоса в как можно более бесконечный поток случайности.
Возьмем первые 16 байт Семени как ключ для AES. После чего, просто зашифруем весь файл в режиме счетчика, обязательно 5 раз подряд. Если нам понадобится больше энтропии, чем содержится в Семени Хаоса — мы просто шифруем его еще 5 раз подряд. Вот так просто, не имея на входе никаких случайных данных, можно получить неограниченный источник качественного хаоса! Самое главное — удалить исходный файл после превращения его в чистую энтропию и никому не говорить что мы использовали, потому что иначе любой желающий сможет получить точно такой же хаос, как и мы. Хаос перестанет быть хаосом и его придется выбросить. Чтобы не всегда выбрасывать сгенерированную случайность в таких случаях, засеем Семя куда-то.
В качестве Земли можно использовать любой файл. Если подумать, можно было бы и без него обойтись, но существуют как минимум 5 причин, по которым без Земли не обойтись никак. Идеальными кандидатами на роль являются различные сжатые данные, к примеру, аудио- и видеозаписи — они достаточно большие и часто встречаются на компьютерах пользователей.Фильмы Михалкова обладают большой энтропией и, местами, та еще Земля. Хорошо бы использовать их для демонстрации концепта, но у меня нет ни одной приобретенной копии. Поэтому, используем композицию музыканта Brad Sucks, конкретно — «You’re not going anywhere». Брэд не должен обидеться, потому что выкладывает свою музыку под лицензией CC BY-SA, вместе со всеми исходниками. К тому же, в отличие от многих других рассмотренных кандидатов в Земли, его музыка совершенно не sucks.
Сажать Семя в Землю мы будем с помощью надежной и любимой всеми криптографами логической функции — XOR. Если смешать случайные данные с не очень случайными — получатся случайные данные! Причем, сколько бы неслучайных данных мы не смешивали со случайными данными, на выходе все равно будут случайные данные. Мечта гомеопата. К тому же, эта функция лежит в основе одноразового блокнота — единственного абсолютно стойкого шифра, известного на данный момент.
Занимает 20 строк на питоне, если у вас есть pyaes.Код from pyaes import AESModeOfOperationCTR as Cipher from os import sys
with open (sys.argv[1], «rb») as TheSeedOfChaosFile: key = TheSeedOfChaosFile.read (16) cypher = Cipher (key) TheSeedOfChaosFile.seek (0) TheSeedOfChaos = TheSeedOfChaosFile.read ()
with open (sys.argv[2], «rb») as TheEarthFile: with open (sys.argv[3], «wb») as TheEntropyFile: chunk = TheEarthFile.read (len (TheSeedOfChaos)) while chunk: for i in range (5): TheSeedOfChaos = cypher.encrypt (TheSeedOfChaos)
chunk = [x ^ y for x, y in zip (chunk, TheSeedOfChaos[0: len (chunk)])] TheEntropyFile.write (bytearray (chunk))
chunk = TheEarthFile.read (len (TheSeedOfChaos)) usage: python script.py seed_file earth_file output_fileВот результат смешивания песни Брэда с логотипом DMCA. Скачайте или сделайте его сами и убедитесь в полной случайности вывода! Всего 20 строк превращают два любых файла в драгоценный хаос.pyaes работает и прекрасен в своей простоте, но это самое медленное, что я когда-либо импортировал в свой интерпретатор. Буду рад, если кому-то понравится идея и ее перепишут в более быстрый вариант. Если кто-то создаст онлайн-сервис по обмену чистейшей энтропией во славу Эриды — я пойму, что жил не зря.
Очевидно, что хаотичность исходных файлов будет меньше, чем конечных. Как машина, так и человек, не разберут, что получилось на выходе. На всякий случай, напишем небольшой скрипт, считающий статистические показатели файлов, и проверим: Исходный код скрипта import sys import math
with open (sys.argv[1], «rb») as file: data = file.read ()
filesize = len (data)
frequencies = [0]*256 for byte in data: frequencies[byte] += 1
frequencies = [freq / float (filesize) for freq in frequencies]
entropy = -sum ([freq * math.log (freq, 2) for freq in frequencies])
mean = sum (frequencies) / len (frequencies) stddev = [(freq — mean) ** 2 for freq in frequencies] stddev = math.sqrt (sum (stddev) / len (stddev))
print ('Shannon:') print (entropy) print ('Mean: (ideal: ' + str (1/256) + ')') print (mean) print ('StdDev:') print (stddev) Статистика исходного Семени Хаоса Shannon:7.942118575257812Mean: (ideal: 0.00390625)0.003906250000000003StdDev:0.0011614891032870488
Статистика исходной Земли Shannon:7.973164196428091Mean: (ideal: 0.00390625)0.0039062499999999987StdDev:0.0008704476953482593
Статистика результата Shannon:7.999936528333672Mean: (ideal: 0.00390625)0.0039062499999999983StdDev:3.665423289519401e-05
Результат обладает почти идеальной энтропией и очень низким разбегом вероятностей появления различных байт. Всегда проверяйте свою энтропию, особенно, перед тем как переслать ее кому-то. Возможно, ваш хаос недостаточно хаотичен и человек не обрадуется такому подарку. Таким нехитрым образом, из часто встречающихся в хозяйстве файлов, можно быстро получить пару гигабайт весьма случайных байт. Главное — удалить исходник Семени Хаоса, иначе, злоумышленник сможет получить такой же хаос, как и у вас, испортив всю идею.Получившиеся потоки хаоса подойдут для затирания ранее удаленных вами файлов на диске (для этого хаос желательно хранить и удалять лишь по мере увеличения потребности в дисковом пространстве), пригодятся в различных прикладных программах, требующих много случайных данных, причем, быстро, а также, благодаря хорошим статистическим показателям, являются чудным подношением последователю дискордианизма.Ну и… почему бы не приютить у себя немного чистейшего беспорядка?
