Фрактальная криптография: может ли хаос стать основой постквантового шифрования?

—

от автора

Всем Q. А тем, у кого малиновые штаны много QqQq. Когда-то, n-лет тому назад, много и долго исследовал фракталы.

Нет, не вот эти:

и даже не вот эти:

Не тот ковер Серпинского, ох не то

Не тот ковер Серпинского, ох не тот

Исследовалось что-то и как-то, вдоль и поперёк, в общем drdφdθ насколько это было возможно. Возможность применения фрактального подхода в экономике, медицине, естественных науках. Но не суть. В этой статье хотел бы порассуждать о применении фрактального подхода в криптографии, а именно может ли хаос стать основой постквантового шифрования?

Дисклеймер:
  1. Статья не будет содержать базовую информацию из теории фракталов. С этим можно ознакомиться прочитав следующие книги:

    1. Фрактальная геометрия природы;

    2. Фракталы и хаос в динамических системах;

  2. Фрактальная криптография не является заменой AES, RSA или стандартизованных постквантовых алгоритмов и не факт что это когда-либо произойдет. Большинство исследований остаются экспериментальными и не имеют строгих доказательств стойкости. Но мне интересен потенциал.

Итак, начну:

Насколько мне известно, современная криптография зиждется на нескольких фундаментальных математических задачах. RSA опирается на сложность факторизации больших чисел, а криптография на эллиптических кривых расчёт на трудность вычисления дискретного логарифма. Десятилетиями этого было достаточно, задачи считались практически неразрешимыми для обычных компьютеров. Текущее развитие квантовых вычислений ставит под угрозу эти подходы: алгоритм Шора теоретически способен эффективно решать обе задачи на достаточно мощном квантовом компьютере. Последние годы активно развиваются постквантовые направления, а именно: решёточная криптография, кодовые схемы и другие.

Понятное дело, что можно придумать хитрые и архитектурно сложные системы защиты, но речь не про это.

У меня друг, тоже ученый, три класса образования. Приезжайте в гости, он вам быстро объяснит, что к чему!

Почему хаос вообще интересен криптографии ?

Любая криптосистема стремится к одному и тому же эффекту: небольшое изменение ключа должно полностью менять результат шифрования. В классической криптографии это достигается сложными сетями перестановок и подстановок, но в хаотических системах подобное поведение возникает естественным образом. Один из самых известных примеров это логистическое отображение:  x_{n+1} = r x_n (1 - x_n), где  x_n \in [0,1], \qquad r \in [0,4]  . При определённых значениях параметра r, примерно начиная с r≳3.57 система начинает вести себя хаотически. На практике это выглядит так: берём два начальных значения, например x_0 и x_0 + 10^{-15}, итерируем, затем еще раз итерируем и так несколько десятков раз. Траектории станут полностью различными. Математически скорость расхождения описывается показателем Ляпунова:

\lambda = \lim_{n \to \infty} \frac{1}{n} \sum_{i=0}^{n-1} \ln \left| r(1 - 2x_i) \right|

Если \lambda > 0 , то система хаотична. На первый взгляд это выглядит почти идеальной основой для криптографии: минимальное изменение параметров радикально меняет поведение системы. Но здесь возникает важная проблема, а именно в 1990-х и начале 2000-х годов витал логический, но ошибочный вывод:

Если система хаотична, значит она автоматически криптографически стойкая.

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

Где появляются фракталы?

Когда говорят о фракталах, большинство вспоминает знаменитое множество Мандельброта — бесконечно сложную фигуру на комплексной плоскости. Оно возникает из очень простой итерации: z_{n+1} = z_n^2 + c, z_n \in \mathbb{C},c \in \mathbb{C}. Для множества Мандельброта стартовое условие фиксировано: z_0 = 0. Если последовательность остаётся ограниченной, то  c принадлежит множеству Мандельброта. Для каждого конкретного c можно построить отдельное множество Жюлиа. Почему это попало в принципе в скоуп рассмотрения? Потому что фракталы обладают:

  1. высокой чувствительностью к параметрам;

  2. сложной самоподобной структурой;

  3. огромным пространством возможных состояний;

  4. труднопредсказуемой динамикой.

Рассуждать почему, как и для чего можно бесконечно долго, поэтому перейдем к деталям

Итерационные системы функций и генерация ключей

Первыми стали Iterated Function Systems (IFS). IFS — это набор аффинных преобразований вида

w_i \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} a_i & b_i \\ c_i & d_i \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} + \begin{pmatrix} e_i \\ f_i \end{pmatrix}

Из таких преобразований строится аттрактор: A = \bigcup_{i=1}^{N} w_i(A) . Именно так, например, генерируются многие классические фракталы.

Не будем углубляться, нам интересна не картинка, а фактическая динамика системы. Для генерации псевдослучайной последовательности используется так называемая «игра хаоса». На каждом шаге выбирается одно из преобразований, после чего вычисляется новая точка:

(x_{k+1}, y_{k+1}) = w_i(x_k, y_k)

Из координат извлекаем биты: bk =\left\lfloor xk 2^m \right\rfloor \bmod 2  . Полученная последовательность будет как потоковый ключ. Некоторые подобные генераторы действительно проходят статистические тесты NIST.

Фреймворки NIST (NIST CSF) — это золотой стандарт для защиты систем, выявления уязвимостей и управления рисками

Здесь важный поинт: хорошие статистические свойства вообще не означают криптографическую стойкость.

Вытекает логичный вопрос. Можно ли построить фрактальную асимметрическую криптографию?

Будем пытаться строить аналог RSA или ECC. Попробуем использовать множества Жюлиа и Мандельброта в качестве основы pub‑key.

закрытый ключ: K_{\mathrm{priv}} = (c, z_0)

открытый ключ: K_{\mathrm{pub}} = c

Шифрование строится на многократном применении отображения  J_c(z) = z^2 + c , а расшифровка — на обратной операции: J_c^{-1}(z) = \sqrt{z - c}  . Красиво? Именно так. Но на практике быстро все разваливается.

Возникающие проблемы:

  1. неоднозначность комплексного корня;

  2. накопление численных ошибок;

  3. отсутствие строгих доказательств безопасности;

  4. возможность атак через анализ динамики системы.

Именно поэтому подобные схемы так и не стали конкурентами RSA или ECC. Но кто знает, кто знает, какие идеи придут в голову чокнутому профессору?

Фракталы и постквантовая криптография

Несмотря на различные нюансы интерес к направлению не исчез. Наоборот — в последние годы появились новые идеи, сочетающие:

  1. символическую динамику;

  2. хеш‑функции;

  3. дискретные фрактальные траектории.

Одна из таких концепций использует отображения над конечными полями: T : \mathbb{Z}_q^2 \to \mathbb{Z} вида

T(x,y)=\begin{pmatrix}a & b \\c & d\end{pmatrix}\begin{pmatrix}x \\y\end{pmatrix}+\begin{pmatrix}e \\f\end{pmatrix}\pmod q

Многократное применение отображения создаёт символический путь: P = (p_0, p_1, \dots, p_{L-1}) . Путь хешируется: K = \mathrm{Hash}(P) обычно через SHA-3 или SHAKE. Такие штуки интересны тем, что отходят от классической алгебры и пытаются использовать сложность самой динамики. В отличие от RSA или ECC, проблема здесь не выглядит чисто алгебраической. Атакующий сталкивается одновременно с:

  1. реконструкцией нелинейной траектории;

  2. комбинаторным взрывом состояний;

  3. устойчивостью хеш‑функции к обращению;

  4. чувствительностью системы к начальным условиям.

Концептуально это больше напоминает обращение сложного динамического процесса, чем решение классического уравнения. Не будем переоценивать результаты. Квантовые алгоритмы наиболее эффективны против задач, обладающих:

  1. периодической структурой;

  2. скрытой алгебраической симметрией;

  3. эффективным представлением через преобразование Фурье.

Фрактальные динамические системы могут быть полностью лишены таких свойств. Достаточно сложный символический процесс может вести себя турбулентно, нелинейно, необратимо. Фактически подобные системы могут оказаться устойчивыми к атакам типа алгоритма Шора. Но здесь критически важно сохранять научную осторожность. На сегодняшний день:

  1. отсутствуют доказательства квантовой стойкости;

  2. нет стандартизации NIST;

  3. большинство схем не прошло серьёзный открытый криптоанализ.

Поэтому возьмем за аксиому тезис:

Отсутствие известных квантовых атак не является эквивалентом доказанной постквантовой стойкости

Поехали далее….

Почему фрактальная криптография может быть особенно популярна для изображений?

Неужели в одной области фрактальные методы оказались хоть как то ± эффективно применимы? Изображения обладают огромной избыточностью и сильной корреляцией между соседними пикселями. Хаотические отображения хорошо подходят для разрушения этой структуры. Например, координаты пикселей могут переставляться по правилу:

(x', y') = \left( \left\lfloor N f(x,\mathrm{key}) \right\rfloor, \left\lfloor M g(y,\mathrm{key}) \right\rfloor \right)

После перестановки выполняется диффузия значений пикселей. Альтернативный подход использует фрактальное сжатие: R_k\approx s_k \tau_k(D_{m(k)}) + o_k, где доменные блоки преобразуются в ранговые с помощью аффинных операций. Для оценки качества таких схем обычно используют метрики NPCR и UACI.

Справка по NCPR и UACI:
  1. NPCR (Number of Pixel Change Rate) определяет долю пикселей (в процентах), которые изменили свое значение (интенсивность) после шифрования при внесении минимального изменения в исходное изображение

    1. Для изображений в градациях серого (где пиксели кодируются от 0 до 255) идеальный показатель NPCR составляет примерно 99,6%.

  2. UACI (Unified Averaged Changed Intensity) измеряет среднюю разницу в интенсивности (яркости) между двумя зашифрованными изображениями

    1. Для 8-битных изображений (шкала от 0 до 255) идеальный показатель UACI находится в районе 33%. Это значит, что в среднем значение каждого пиксела меняется примерно на треть.

NPCR показывает, насколько сильно меняется изображение при минимальном изменении исходных данных:

NPCR = \frac{1}{MN} \sum_{i=1}^{M} \sum_{j=1}^{N} D(i,j)\times100\%

Хорошие схемы обычно дают: NPCR>99\%. Метрика UACI оценивает среднюю интенсивность изменений:

UACI = \frac{1}{MN} \sum_{i,j} \frac{|C_1(i,j)-C_2(i,j)|}{255} \times100\%

Для качественного шифрования обычно получают: UACI≈33\%

Вроде бы заманчиво, но главная проблема у всей этой приблуды: отсутствие формальной теории безопасности

Криптография требует гораздо большего, чем интуитивная сложность. Практическая криптосистема должна иметь:

  1. строгие предположения о сложности;

  2. доказательство с помощью сводимости;

  3. формальные модели безопасности;

  4. открытый криптоанализ;

  5. анализ реализации;

  6. устойчивость к side-channel атакам.

У фрактальной криптографии сегодня большинства этих элементов нет. Именно поэтому стандартизация NIST сосредоточена на:

  1. решётках;

  2. кодах;

  3. изогениях;

  4. многомерных-системах;

а не на хаотических или фрактальных схемах. Без строгой теории одной лишь хаотичности недостаточно.

Какие еще есть подводные камни?

Конечная точность вычислений

Есть и ещё одна фундаментальная проблема. Математический хаос существует в непрерывных системах с бесконечной точностью. Компьютеры так не работают. Реальные реализации используют конечную арифметику: x∈  \{0,1,\dots,2^n-1\}. Это радикально уменьшает сложность системы. Теоретически хаотическая динамика иногда вырождается в коротких циклах, повторяющихся состояниях и предсказуемых аттракторах. Многие ранние хаотические криптосистемы были взломаны именно из-за этого эффекта. Поэтому современные исследования всё чаще используют вместо чистого хаоса с плавающей точкой:

  1. символическую динамику;

  2. целочисленные системы;

  3. модульную арифметику;

  4. дискретную эволюцию состояний;

Вскользь хотелось бы обозначить направления, где потенциально возможно дальнейшее развитие фрактальных динамик:

  1. Гибридные направления: фракталы + классическая PQC
    — Возможно, наиболее реалистичное будущее фрактальной криптографии — не замена постквантовых алгоритмов, а их дополнение. Уже сейчас исследуются гибридные подходы.

  2. Фрактальные источники энтропии
    — Хаотические системы могут усиливать энтропию в решёточных схемах.

  3. Фрактальная генерация ключей
    — Символические траектории позволяют строить высокоразмерные неповторяющиеся ключи сеанса.

  4. Защита мультимедиа
    — Фрактальное шифрование изображений может дополнять классические постквантовые протоколы.

  5. Аппаратная случайность
    — Физические хаотические процессы могут использоваться как источник аппаратной энтропии. В этом смысле фрактальная криптография может стать не заменой RSA или lattice‑based PQC, а дополнительным технологическим слоем.

Заключение

Может ли фрактальная криптография стать практической? Пока это неизвестно. Сегодня область напоминает ранние исследования по нейросетям:

Всё очень интересно, но ничего непонятно.

Фрактальная криптография остаётся одной из самых необычных областей современной криптографии. Она объединяет хаос, нелинейную динамику, комплексный анализ и теорию информации в попытке создать новые криптографические примитивы. Пока это направление нельзя поставить в один ряд с AES, RSA или современными постквантовыми алгоритмами. Большинство схем остаются исследовательскими и не имеют строгих доказательств безопасности. Но сама идея использовать сложность динамических систем вместо классических алгебраических задач выглядит чрезвычайно интересной. Возможно, именно на стыке хаоса, символической динамики и криптографических хеш‑функций в будущем появятся новые подходы к построению действительно постквантовых криптосистем. А может….. и не появятся.

P. S.

Экспериментальный пример кода на python:

Ниже упрощённый пример «хаотического» шифрования изображения на основе логистического отображения. Это не промышленная криптосистема, а демонстрация того, как нелинейная динамика может использоваться для генерации псевдослучайной последовательности.

from PIL import Imageimport numpy as npimport osimport structimport hashlibfrom cryptography.hazmat.primitives.ciphers.aead import ChaCha20Poly1305from cryptography.hazmat.primitives.kdf.scrypt import Scryptfrom cryptography.exceptions import InvalidTagMAGIC = b"FRACTALCRYPT1"      # сигнатура форматаNONCE_SIZE = 12               # 96 бит для ChaCha20-Poly1305SALT_SIZE = 16                # соль для ScryptKEY_SIZE = 32                 # 256-битный ключ# Хаотический генератор энтропии (фрактальный)class ChaoticPRNG:    def __init__(self, seed, r1=3.9999, r2=0.9999):        if not (0.0 < seed < 1.0):            raise ValueError("Seed must be in (0, 1)")        self.x = seed        # Второе состояние со сдвигом, избегаем нуля        self.y = (seed + 0.5) % 1.0        if self.y == 0.0:            self.y = 0.001        self.r1 = r1        self.r2 = r2    def next_byte(self) -> int:        # Логистическое отображение        self.x = self.r1 * self.x * (1.0 - self.x)        # Синусоидальная карта (всегда остаётся в (0,1) при 0 < r2 ≤ 1)        self.y = self.r2 * np.sin(np.pi * self.y)        # Преобразуем в байты и перемешиваем XOR        a = int(self.x * 256) % 256        b = int(self.y * 256) % 256        return a ^ b    def generate_entropy(self, length: int) -> bytes:        return bytes(self.next_byte() for _ in range(length))# Формирование ключа с использованием хаотической энтропииdef derive_key(password: str, salt: bytes, chaotic_entropy: bytes) -> bytes:    # Смешивание пароля с хаотической добавкой    mixed = password.encode('utf-8') + chaotic_entropy    # Дополнительное выбеливание (не даёт злоумышленнику напрямую атаковать Scrypt)    whitened = hashlib.sha3_256(mixed).digest()    # Ключевая функция формирования    kdf = Scrypt(        salt=salt,        length=KEY_SIZE,        n=2**14,        r=8,        p=1    )    return kdf.derive(whitened)# Шифрование изображенияdef encrypt_image(input_path: str, output_path: str, password: str) -> None:    try:        # ---------- Чтение изображения ----------        img = Image.open(input_path)        mode = img.mode                     # сохраняем исходный режим (L, RGB, RGBA, …)        arr = np.array(img, dtype=np.uint8)        if arr.ndim == 2:            height, width = arr.shape            channels = 1        else:            height, width, channels = arr.shape        plaintext = arr.tobytes()        # ---------- Хаотическая энтропия ----------        seed_bytes = os.urandom(8)        seed_int = int.from_bytes(seed_bytes, 'big')        seed = (seed_int % 10**12) / 10**12   # нормализуем в (0,1)        if seed == 0.0:            seed = 0.123456789        chaos = ChaoticPRNG(seed)        chaotic_entropy = chaos.generate_entropy(4096)  # 4 КБ энтропии        # ---------- Формирование ключа ----------        salt = os.urandom(SALT_SIZE)        key = derive_key(password, salt, chaotic_entropy)        # ---------- AEAD шифрование ----------        nonce = os.urandom(NONCE_SIZE)        cipher = ChaCha20Poly1305(key)        # Дополнительные аутентифицированные данные – метаданные изображения        aad = (            mode.encode('ascii') +            struct.pack('!III', height, width, channels)        )        ciphertext = cipher.encrypt(nonce, plaintext, aad)        # ---------- Сохранение контейнера ----------        with open(output_path, 'wb') as f:            f.write(MAGIC)            f.write(struct.pack('!d', seed))            f.write(salt)            mode_bytes = mode.encode('ascii')            f.write(struct.pack('!B', len(mode_bytes)))            f.write(mode_bytes)            f.write(struct.pack('!III', height, width, channels))            f.write(nonce)            f.write(ciphertext)        print(f"Зашифровано: {output_path}")    except Exception as e:        print(f"Ошибка шифрования: {e}")# Расшифрование изображенияdef decrypt_image(input_path: str, output_path: str, password: str) -> None:    try:        with open(input_path, 'rb') as f:            # ---------- Проверка формата ----------            magic = f.read(len(MAGIC))            if magic != MAGIC:                raise ValueError("Неверный формат файла (отсутствует сигнатура)")            # ---------- Чтение заголовка ----------            seed = struct.unpack('!d', f.read(8))[0]            salt = f.read(SALT_SIZE)            mode_len = struct.unpack('!B', f.read(1))[0]            mode = f.read(mode_len).decode('ascii')            height, width, channels = struct.unpack('!III', f.read(12))            nonce = f.read(NONCE_SIZE)            ciphertext = f.read()        # ---------- Восстановление хаотической энтропии ----------        chaos = ChaoticPRNG(seed)        chaotic_entropy = chaos.generate_entropy(4096)        # ---------- Получение ключа ----------        key = derive_key(password, salt, chaotic_entropy)        # ---------- AEAD расшифрование ----------        cipher = ChaCha20Poly1305(key)        aad = (            mode.encode('ascii') +            struct.pack('!III', height, width, channels)        )        plaintext = cipher.decrypt(nonce, ciphertext, aad)        # ---------- Проверка размера ----------        expected_size = height * width * channels        if len(plaintext) != expected_size:            raise ValueError("Размер расшифрованных данных не соответствует ожидаемому")        # ---------- Восстановление изображения ----------        arr = np.frombuffer(plaintext, dtype=np.uint8)        if channels == 1:            arr = arr.reshape((height, width))        else:            arr = arr.reshape((height, width, channels))        img = Image.fromarray(arr, mode=mode)        img.save(output_path)        print(f"Расшифровано: {output_path}")    except InvalidTag:        print("Ошибка аутентификации! Неверный пароль или повреждённый файл.")    except Exception as e:        print(f"Ошибка расшифрования: {e}")# Пример использованияif __name__ == "__main__":    PASSWORD = "UltraSecurePassword123"    # Шифрование    encrypt_image("input.jpg", "encrypted.frc", PASSWORD)    # Расшифрование    decrypt_image("encrypted.frc", "decrypted.png", PASSWORD)

ссылка на оригинал статьи https://habr.com/ru/articles/1045408/