Комментарии 34
Зачем эта статья? Или объяили неделю приложений линейной алгебры?
Содержание пар не имеет значения, главное чтобы они образовывали базис.
В остальном — если внутрь запихнуть aes то вообще можно не парится.
Ну, не обязательно aes запихивать. Композицию любых двух алгоритмов шифрования взломать сложнее чем оба алгоритма по-отдельности. Если у них ключи независимы, конечно же. И UB в реализации нет.
Не устаю приводить ссылку на замечательный пост.
Простых замен — да, эквивалентна. А вот простая замена с шифром Хила уже не упрощаются до более простого алгоритма.
Пост по вашей ссылке и правда замечательный, но с утверждением "содержание пар не имеет значения, главное чтобы они образовывали базис" как ответом на "шифры можно комбинировать" не согласен.
Я знаю доказательство того, что простая замена с Хиллом не упрощается до одной из составных частей.
Вот немного нестрогое доказательство, потому что строгое писать в комментарии неудобно из-за отсутствия нормальной разметки.
Если заметить, что композиция двух простых шифров — простой шифр, композиция двух Хиллов — Хилл, а обратные преобразования к простому шифту и Хиллу являются тоже простым шифром и Хиллом, то в уравнениях T * Х1 = Х2 и T1 * Х = T2 (где T — простой шифр, Х — алгоритм Хилла) можно перенести все простые шифры в левую часть, а всех Хиллов — в правую, получив уравнение вида T3 = Х3.
Таким образом, композиция указанных двух алгоритмов может быть эквивалентна одному из алгоритмов-компонент тогда и только тогда когда найдутся эквивалентные друг другу простой шифр и алгоритм Хилла. Но для нетривиальных алгоритмов это невозможно, потому что у них разные размеры блоков.
Поясните.
Тогда с таким ключем данная простая замена будет эквивалентна шифру Хилла. И композиция даст шифр Хилла.
Ок, согласен. Надо поправить формулировку теоремы, но мне лень.
Тем не менее, замечу, что предложенный вами алгоритм, хоть и относится к семейству простых замен — но с точки зрения принципа Керкгоффса простой заменой не является. Потому что у шифра простой замены ключ — это целая таблица подстановки, а у умножения в поле вычетов — один символ.
Секретный алгоритм способ получения ключа? :-)
Мы всего сможем получить столько различных вариантов ключа, сколько у нас есть различных символов, без возведения в степень — длину таблицы. Короче, существует вполне себе эффективный исследователь, «брутфорс», который различит ваш сфабрикованный ключ и настоящую случайную таблицу, значит, не эквивалентны.
Этот алгоритм поиска обратного элемента я подобрал экспериментальным путем, т.к. не мог найти ровным счетом ничего полезного по этой теме.
Не, ну вы серьёзно? Это ж база. Ищется тем же расширенным алгоритмом Евклида для пары (число, модуль). Подробнее здесь.
Получаем такую матрицу, тут важно не терять знаки у элементов (некоторые выполняют деление по модулю с потерей минусов, в данном алгоритме это недопустимо):
Скажите, а почему убрать отрицательные элементы на данном этапе — недопустимо?
Я бы напротив, советовал избавляться от отрицательных элементов на каждом этапе, добавляя к ним 37. Это избавило бы от "сложных и важных вещей" на шагах 4 и 5.
Вы считаете определитель матрицы, а он может оказаться нулем. Нужно ещё и чтобы столбцы были линейно-независимыми, и тут уже оперировать словами языка в качестве ключа становится невозможно. Вам повезло с альпинизмом.
Автор это учел:
Также важным фактором для данного шифра является определитель матрицы ключа: он должен быть отличным от нуля, иначе расшифровку зашифрованного текста будет невозможно осуществить.
Кстати, вероятность того, что случайный ключ будет "плохим" — чуть больше чем 1/37 (более точно: 1/37 + 1/372 — 1/373). Так что не так уж и сильно автору повезло с альпинизмом.
Шифр Хила. Подробный разбор