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

в 6:52, , рубрики: aes, sos меня держат на фабрике энтропии, госдума запретила ГПСЧ, как сломать юриста, копирайт, криптография, сарказм, случайные числа, хаос

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.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

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

Вывод

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

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

Автор: HurrTheDurr

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js