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.
usage: python script.py seed_file earth_file output_file
Вот результат смешивания песни Брэда с логотипом DMCA. Скачайте или сделайте его сами и убедитесь в полной случайности вывода! Всего 20 строк превращают два любых файла в драгоценный хаос.
pyaes работает и прекрасен в своей простоте, но это самое медленное, что я когда-либо импортировал в свой интерпретатор. Буду рад, если кому-то понравится идея и ее перепишут в более быстрый вариант. Если кто-то создаст онлайн-сервис по обмену чистейшей энтропией во славу Эриды — я пойму, что жил не зря.
Очевидно, что хаотичность исходных файлов будет меньше, чем конечных. Как машина, так и человек, не разберут, что получилось на выходе. На всякий случай, напишем небольшой скрипт, считающий статистические показатели файлов, и проверим:
Результат обладает почти идеальной энтропией и очень низким разбегом вероятностей появления различных байт. Всегда проверяйте свою энтропию, особенно, перед тем как переслать ее кому-то. Возможно, ваш хаос недостаточно хаотичен и человек не обрадуется такому подарку.
Таким нехитрым образом, из часто встречающихся в хозяйстве файлов, можно быстро получить пару гигабайт весьма случайных байт. Главное — удалить исходник Семени Хаоса, иначе, злоумышленник сможет получить такой же хаос, как и у вас, испортив всю идею.
Получившиеся потоки хаоса подойдут для затирания ранее удаленных вами файлов на диске (для этого хаос желательно хранить и удалять лишь по мере увеличения потребности в дисковом пространстве), пригодятся в различных прикладных программах, требующих много случайных данных, причем, быстро, а также, благодаря хорошим статистическим показателям, являются чудным подношением последователю дискордианизма.
Ну и… почему бы не приютить у себя немного чистейшего беспорядка?
— Эрис, богиня хаоса, раздора и путаницы
Порядок невозможен без беспорядка. Программисты часто ныряют в хаос в поиске гениальных мыслей, случайных чисел и волшебных коэффициентов, которыми должно обладать каждое уважающее себя приложение. В этой статье я расскажу, как практически из ничего получить высококачественные образцы случайности, которыми можно, например, поделиться со своими друзьями-хаосопоклонниками.
Предупреждение для юристов, политиков и других роботов: это полушуточная статья.
Входные данные
Для получения хаоса, нам понадобятся два файла, которые мы будем называть «Семя Хаоса» и «Земля». Семя Хаоса — небольшой файл, из которого и будет рождаться хаос. Земля — файл произвольного размера, который будет задавать объем результирующей энтропии, ну и немного увеличивать случайность результата. В принципе, без Земли можно было бы и обойтись, но, на всякий случай, лучше ей пользоваться — особенность случайных данных в том, что их сложно отличить от неслучайных. Вдруг у нас одни нули сгенерируются? Цельный, рабочий, файл гарантирует, что в результате всегда будет хоть что-то вещественное.
Семя Хаоса
Выбор подходящего кандидата на роль Семени Хаоса — сложная задача. Файл должен обладать хорошей начальной энтропией, к тому же, вы должны его искренне ненавидеть, потому что он будет, в дальнейшем, претерпевать ужасные болезненные изменения. Неплохие показатели случайности у изображений, к тому же, они валяются по всему Интернету. Если доступа к Интернету нет — вполне вероятно, что ваше пожирающее хаос приложение будет запущено на компьютере человека, который смотрит и сохраняет смешные картинки вместо того, чтобы жить насыщенной жизнью, поэтому, беспокоиться не стоит.
Файлы, идеально подходящие на роль Семени Хаоса
Используем логотип 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
Результат обладает почти идеальной энтропией и очень низким разбегом вероятностей появления различных байт. Всегда проверяйте свою энтропию, особенно, перед тем как переслать ее кому-то. Возможно, ваш хаос недостаточно хаотичен и человек не обрадуется такому подарку.
Вывод
Таким нехитрым образом, из часто встречающихся в хозяйстве файлов, можно быстро получить пару гигабайт весьма случайных байт. Главное — удалить исходник Семени Хаоса, иначе, злоумышленник сможет получить такой же хаос, как и у вас, испортив всю идею.
Получившиеся потоки хаоса подойдут для затирания ранее удаленных вами файлов на диске (для этого хаос желательно хранить и удалять лишь по мере увеличения потребности в дисковом пространстве), пригодятся в различных прикладных программах, требующих много случайных данных, причем, быстро, а также, благодаря хорошим статистическим показателям, являются чудным подношением последователю дискордианизма.
Ну и… почему бы не приютить у себя немного чистейшего беспорядка?
