Инновационный метод производства энтропии

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)

Результат обладает почти идеальной энтропией и очень низким разбегом вероятностей появления различных байт. Всегда проверяйте свою энтропию, особенно, перед тем как переслать ее кому-то. Возможно, ваш хаос недостаточно хаотичен и человек не обрадуется такому подарку.

Вывод

Таким нехитрым образом, из часто встречающихся в хозяйстве файлов, можно быстро получить пару гигабайт весьма случайных байт. Главное — удалить исходник Семени Хаоса, иначе, злоумышленник сможет получить такой же хаос, как и у вас, испортив всю идею.

Получившиеся потоки хаоса подойдут для затирания ранее удаленных вами файлов на диске (для этого хаос желательно хранить и удалять лишь по мере увеличения потребности в дисковом пространстве), пригодятся в различных прикладных программах, требующих много случайных данных, причем, быстро, а также, благодаря хорошим статистическим показателям, являются чудным подношением последователю дискордианизма.
Ну и… почему бы не приютить у себя немного чистейшего беспорядка?

Автор: HurrTheDurr

Источник