Многочлены Диксона: Как перемешать алфавит без коллизий. Представьте, что мы пишем свой шифр. У нас есть алфавит. Для удобства работы с криптографией возьмем алфавит, размер (мощность) которого равен простому числу . Пусть это будет p = 7. Наш алфавит: числа от 0 до 6. Нам нужна функция замены f(x). Если мы возьмем что-то простое, вроде f(x) = x^2 mod 7, нас ждет катастрофа: 2^2 mod 7 = 4 5^2 mod 7 = 4 Коллизия! И двойка, и пятерка превратились в четверку. При расшифровке мы не сможем узнать исходное число. Нам нужна формула, которая работает как идеальная биекция (1:1), где каждому входу соответствует уникальный выход. На сцену выходит Леонард Диксон В начале XX века математик Леонард Юджин Диксон описал семейство многочленов, которые при определенных условиях становятся перестановочными многочленами (Permutation Polynomials) над конечными полями. Это именно то, что нам нужно: они перемешивают данные, математически гарантируя от...
О терминологии. Или почему «кошка» (которая изначально «лиса») не всегда «прыгает». Если вы когда-нибудь читали описание криптоалгоритмов (например, классическую сеть Хорста Фейстеля), а потом открывали учебник по высшей алгебре, у вас могло возникнуть ощущение легкого когнитивного диссонанса. Слова одни и те же, но значат они разное. Давайте внесем ясность, используя иронию и классическую фразу "The quick brown fox jumps over the lazy dog" . 1. Substitution (Замена): "Кошка вместо лисы" В инженерном смысле (в тех же S-блоках) Substitution — это когда мы берем один объект и подменяем его другим по таблице или формуле. Пример: Мы решили, что "fox" теперь всегда будет "cat". Фраза превращается в: "The quick brown cat jumps over..." . Объект подменили, но он остался на том же месте. Математик, глядя на это, скажет: "Это функция f(x) = y ". И если эта замена уникальна (без коллизий), он назовет её перес...