— Эрис, богиня хаоса, раздора и путаницы
Порядок невозможен без беспорядка. Программисты часто ныряют в хаос в поиске гениальных мыслей, случайных чисел и волшебных коэффициентов, которыми должно обладать каждое уважающее себя приложение. В этой статье я расскажу, как практически из ничего получить высококачественные образцы случайности, которыми можно, например, поделиться со своими друзьями-хаосопоклонниками.
Предупреждение для юристов, политиков и других роботов: это полушуточная статья.
Входные данные
Для получения хаоса, нам понадобятся два файла, которые мы будем называть «Семя Хаоса» и «Земля». Семя Хаоса — небольшой файл, из которого и будет рождаться хаос. Земля — файл произвольного размера, который будет задавать объем результирующей энтропии, ну и немного увеличивать случайность результата. В принципе, без Земли можно было бы и обойтись, но, на всякий случай, лучше ей пользоваться — особенность случайных данных в том, что их сложно отличить от неслучайных. Вдруг у нас одни нули сгенерируются? Цельный, рабочий, файл гарантирует, что в результате всегда будет хоть что-то вещественное.
Семя Хаоса
Выбор подходящего кандидата на роль Семени Хаоса — сложная задача. Файл должен обладать хорошей начальной энтропией, к тому же, вы должны его искренне ненавидеть, потому что он будет, в дальнейшем, претерпевать ужасные болезненные изменения. Неплохие показатели случайности у изображений, к тому же, они валяются по всему Интернету. Если доступа к Интернету нет — вполне вероятно, что ваше пожирающее хаос приложение будет запущено на компьютере человека, который смотрит и сохраняет смешные картинки вместо того, чтобы жить насыщенной жизнью, поэтому, беспокоиться не стоит.
Используем логотип 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.942118575257812
Mean: (ideal: 0.00390625)
0.003906250000000003
StdDev:
0.0011614891032870488
Shannon:
7.973164196428091
Mean: (ideal: 0.00390625)
0.0039062499999999987
StdDev:
0.0008704476953482593
Shannon:
7.999936528333672
Mean: (ideal: 0.00390625)
0.0039062499999999983
StdDev:
3.665423289519401e-05
Результат обладает почти идеальной энтропией и очень низким разбегом вероятностей появления различных байт. Всегда проверяйте свою энтропию, особенно, перед тем как переслать ее кому-то. Возможно, ваш хаос недостаточно хаотичен и человек не обрадуется такому подарку.
Вывод
Таким нехитрым образом, из часто встречающихся в хозяйстве файлов, можно быстро получить пару гигабайт весьма случайных байт. Главное — удалить исходник Семени Хаоса, иначе, злоумышленник сможет получить такой же хаос, как и у вас, испортив всю идею.
Получившиеся потоки хаоса подойдут для затирания ранее удаленных вами файлов на диске (для этого хаос желательно хранить и удалять лишь по мере увеличения потребности в дисковом пространстве), пригодятся в различных прикладных программах, требующих много случайных данных, причем, быстро, а также, благодаря хорошим статистическим показателям, являются чудным подношением последователю дискордианизма.
Ну и… почему бы не приютить у себя немного чистейшего беспорядка?
ссылка на оригинал статьи http://habrahabr.ru/post/229473/
Добавить комментарий