StanSemenoff 5 июн в 14:55

Новый кандидат в односторонние функции для криптографии и PRNG

Средний

7 мин

837

Криптография*Математика*Информационная безопасность*

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

Что такое односторонние функции и зачем они нужны?

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

Односторонняя функция (One-Way Function, OWF) — это математическая функция, которую легко вычислить в одном направлении, но чрезвычайно трудно или практически невозможно обратить (то есть, найти входные данные по известным выходным). Представьте себе мясорубку: легко перемолоть мясо, но невозможно собрать фарш обратно в цельный кусок.

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

Хеширование данных

Хеш-функции позволяют создавать уникальные "отпечатки" для файлов или сообщений. Даже малейшее изменение в исходных данных приводит к совершенно другому хешу. Это используется для проверки целостности данных (не был ли файл изменён?), в цифровых подписях и для безопасного хранения паролей (мы храним хеш пароля, а не сам пароль, чтобы его нельзя было украсть).

Генерация ключей и обмен ключами

В таких протоколах, как Diffie-Hellman, участники могут вычислить общий секретный ключ, обмениваясь только публичной информацией. Односторонняя функция делает невозможным для подслушивающего получить секретный ключ из публичных данных.

Доказательство работы (Proof of Work)

В криптовалютах майнинг обычно основан на поиске числа, которое в сочетании с другими данными даёт хеш, начинающийся с определённого количества нулей. Это вычислительно сложно (требует много попыток), но легко проверяемо — типичное применение односторонней функции.

Создание псевдослучайных чисел (PRNG)

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

Без односторонних функций было бы крайне сложно обеспечить конфиденциальность, целостность и подлинность данных в цифровом мире.

Краткое описание системы

Чтобы было легче описывать и воспринимать читателю, и не углубляться в строгие математические термины вроде "магмы" или "унитальной магмы", далее по тексту мы будем называть эту алгебраическую структуру просто M3-системой.

M3-система — это алгебраическая структура, определённая на трёхмерных векторах над конечным полем или кольцом. Это означает, что мы работаем с векторами вида a = [a_0, a_1, a_2] , где каждый компонент a_i является целым числом из заданного диапазона (например, от до N-1 , где — это модуль).

В основе M3-системы лежит уникальный бинарный оператор умножения *, который действует на два таких вектора. Если у нас есть два вектора a = [a_0, a_1, a_2] и b = [b_0, b_1, b_2] , их произведение a * b вычисляется по следующим формулам (все операции выполняются по модулю ):

(ab)_0 = a_0 + b_0 + a_0 b_0 + A a_1 b_1 + C a_2 b_1 + B a_2 b_2

(ab)_1 = a_1 + b_1 + a_1 b_0 + a_0 b_1 + D a_1 b_1 + E a_1 b_2

(ab)_2 = a_2 + b_2 + a_2 b_0 + a_0 b_2 + D a_2 b_1 + E a_2 b_2

Здесь A, B, C, D, E — это фиксированные параметры системы, которые определяются при её создании. Эти параметры играют роль "коэффициентов смешивания", существенно влияющих на поведение оператора и, как следствие, на криптографические свойства всей системы.

Проще говоря, M3-система — это набор векторов и специальное правило, как эти векторы "перемножаются" между собой. Именно это уникальное правило умножения делает систему такой интересной для применения, поскольку оно порождает сложную и нелинейную динамику.

Гипотеза об отсутствии замкнутой формы

Одним из важнейших аспектов, который придает M3-системе ценность, является гипотеза об отсутствии общей замкнутой формы для a^n . Это означает, что для вычисления -й степени элемента не существует простой, фиксированной полиномиальной формулы. Каждый шаг a^k рекурсивно и нелинейно зависит от $a^{k-1}$ , что приводит к экспоненциальному росту сложности выражений с каждым новым .

Это критически важно для односторонности: если бы такая формула существовала, было бы потенциально легче обратить операцию и вычислить по a^n . Отсутствие такой формы делает обращение крайне сложным, что подкрепляет следующую гипотезу.

Проблема Дискретной Итерации (DIP)

Из отсутствия замкнутой формы логично вытекает гипотеза о вычислительной сложности Проблемы Дискретной Итерации (Discrete Iteration Problem, DIP): Даны элемент и его -я степень a^n , найти показатель .

Предполагается, что эта задача вычислительно сложна для общего случая. В отличие от классических алгебраических систем, где для нахождения из g^n существуют алгоритмы (например, алгоритмы дискретного логарифмирования), здесь рекурсивная, комбинаторно-взрывная природа операции делает прямое алгебраическое обращение чрезвычайно трудным. Это означает, что для нахождения обычно требуется последовательное вычисление $a^1, a^2, \dots$ до совпадения, что имеет экспоненциальную сложность относительно длины .

Хотя представленные гипотезы пока не имеют строгих доказательств, текущие наблюдения и анализ структуры M3-системы указывают на её значительный потенциал. Если дальнейшие исследования не выявят уязвимостей, а предложенные криптографические свойства сохранятся, M3-система может стать весьма привлекательной основой для новых криптографических примитивов.

Подход к созданию псевдослучайных чисел

Как мы видели, M3-система оперирует с трёхмерными векторами. Рассмотрим что делает эту систему интересной для PRNG и хеш-функций.

Общая неассоциативность и некоммутативность

В отличие от большинства "традиционных" алгебраических структур, операция в M3-системе не является ассоциативной ( $(a * b) * c \ne a * (b * c)$ ) и некоммутативной ( $a * b \ne b * a$ ). Это важное свойство, которое может усложнить криптоанализ и делает атаки, основанные на алгебраических свойствах, более сложными.

Степенная ассоциативность и коммутативность

Что наиболее привлекательно, при всей своей общей неассоциативности, M3-система обладает свойством степенной ассоциативности (power associativity). Это означает, что если мы многократно умножаем один и тот же элемент на самого себя ( $a^n = a * a * \dots * a$ ), то результат всегда будет однозначным, независимо от расстановки скобок. Также выполняется $a^m * a^n = a^{m+n}$ .

Сложность и диффузия

Каждый компонент a^n представляет собой сложный многомерный полином от исходных компонентов a_0, a_1, a_2 . С каждой итерацией (увеличением ) степень полинома растёт линейно, а количество слагаемых — комбинаторно. Это обеспечивает эффект лавины: даже незначительное изменение в начальном "зерне" приводит к кардинальным изменениям в последующих числах последовательности.

Произвольные орбиты

Развивая идею PRNG на основе M3-системы, стоит отметить, что генерация последовательности из одного элемента ( a^n ) — это лишь отправная точка. Для достижения максимального разнообразия и непредсказуемости орбит, можно смешивать несколько таких генераторов. Представьте, что у нас есть несколько M3-систем, каждая со своим уникальным набором параметров ( A, B, C, D, E ) и начальным вектором. Мы можем чередовать их значения, например, беря компоненты из разных систем, умножать сгенерированные векторы друг на друга, возводить их в последовательно меняющиеся степени или даже использовать результат одного генератора для модификации параметров другого. Теоретически, существует невычислимое количество комбинаций, что позволяет создавать генераторы с колоссальной сложностью и разнообразием выходных последовательностей, практически исключая повторения и предсказуемость.

Как работает M3-PRNG?

Выбор системы

Определяются параметры A, B, C, D, E и модуль .

Выбор "зерна" (seed)

Выбирается начальный вектор a = [a_0, a_1, a_2] .

Генерация

Последовательные псевдослучайные числа генерируются путём многократного умножения: $a^1, a^2, a^3, \dots, a^k, \dots$ . Каждый a^k — это новый псевдослучайный вектор.

Протокол обмена ключами на основе коммутативных степеней

Свойства степенной ассоциативности и внутренней коммутативности открывают путь для реализации протокола обмена ключами, аналогичного знаменитому протоколу Диффи-Хеллмана, но в рамках неассоциативной M3-системы.

Как это работает?

Общая база

Алиса и Боб публично договариваются о базовом элементе $a \in K^3$ .

Секретные показатели

Алиса выбирает секретный показатель $m \in \mathbb{N}$ и вычисляет . Затем отправляет Бобу.
Боб выбирает секретный показатель $n \in \mathbb{N}$ и вычисляет . Затем отправляет Алисе.

Вычисление общего ключа

Алиса получает и вычисляет общий ключ .
Боб получает и вычисляет общий ключ .

Таким образом, $K = a^{m \cdot n}$ , и оба участника приходят к одному и тому же секретному ключу.

Безопасность протокола основывается на сложности Проблемы Дискретной Итерации: внешний наблюдатель, имея публичные , A=a^m и B=a^n , не может вычислить или , а следовательно, и общий ключ $a^{m \cdot n}$ . Это формирует Алгебраическую Проблему Диффи-Хеллмана (ADHP) для M3-системы.

Применение в Хеш-Функциях

Поскольку M3-система демонстрирует сильные свойства односторонности и эффекта лавины, она является отличным кандидатом для создания криптографических хеш-функций.

Как это может быть построено?

Разделение на блоки

Входные данные (сообщение/документ) делятся на блоки. Каждый блок преобразуется в M3-элемент.

Итеративная обработка

Каждый блок обрабатывается с помощью операции возведения в степень (например, B_i^k ), где может быть фиксированным или меняться в зависимости от блока.

Агрегация

Обработанные блоки последовательно объединяются с помощью операции умножения . Из-за неассоциативности и некоммутативности операции , порядок объединения блоков имеет решающее значение.

Параллелизуемость

Одним из ключевых преимуществ является высокая степень параллелизуемости. Преобразование каждого блока может выполняться одновременно на множестве ядер, что значительно ускоряет процесс для больших объемов данных.

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

Заключение

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

Хабы: