Шифрование
Для того, чтобы зашифровать какой-либо текст по алгоритму Хилла необходимо проделать следующие шаги:
- Создаем кодированный алфавит. Допустим мы хотим шифровать русский текст. Тогда длина алфавита будет 33 буквы. Целесообразно добавить к алфавиту еще 4 символа на выбор, я добавлю такие: "?", ".", ","," ". Это делается для того, чтобы длина алфавита была простым числом, т.е. числом, которое делится нацело только на себя и на 1. Это, конечно, не обязательно, но очень удобно, потому что для расшифровки необходимо, чтобы детерминант ключа и длина алфавита были взаимно простыми, т.е. не имели общих делителей кроме 1. Если длина алфавита – простое число, то таких ключей, для которых выполняется это условие значительно больше. Каждому символу нашего алфавита ставим в соответствие целочисленный код. Удобнее всего использовать просто номера букв. Таким образом получаем кодированный алфавит:
- Теперь берем текст, который хотим зашифровать и кодируем его с помощью нашего алфавита. Возьмем для примера слово «ШИФР», его код будет таким: 25 9 21 17.
- Теперь выбираем ключевое слово, или просто набор букв, который будем использовать в качестве ключа. Тут важно, чтобы длина этого ключевого слова была равна квадрату целого числа, т.е. 4, 9, 16, 25 и т.д. Только тогда мы сможем сделать из него квадратную матрицу, необходимую для шифрования. Я выбрал слово «АЛЬПИНИЗМ». Кодируем его с помощью нашего алфавита. Получаем: 0 12 29 16 9 14 9 8 13. Запишем ключ в виде матрицы 3х3:
Ключ можно задавать сразу матрицей, если вам так удобней. Я же использовал ключевое слово.
- Теперь надо разбить текст на блоки по n символов в каждом, где n-размерность матрицы, в моем случае – 3. Начнем разбивать:
Первый блок: (25 9 21)
На второй блок у нас осталось всего одно число – 17. Самое простое решение в таком случае: добавить столько символов, чтобы образовать целый блок. Я решил добавить пробелы.
Тогда второй блок: (17 35 35)
- Теперь шифруем наш текст. Для шифрования текста требуется провести матричное умножение каждого блока на матрицу ключа. Тут стоит заметить, что блоки можно было бы записывать не в строки, а в столбцы. Тогда мы бы умножали ключ на столбец, это не существенное различие.
Также важным фактором для данного шифра является определитель матрицы ключа: он должен быть отличным от нуля, иначе расшифровку зашифрованного текста будет невозможно осуществить.
Итак, умножаем первый блок на ключ:
Умножаем второй блок на ключ:
Матричное умножение — это не сложная операция, поэтому расписывать его подробно я не стал.
Теперь нам нужно получившиеся матрицы разделить по модулю на 37, т.е. взять остаток от деления на 37.
Делим первую матрицу:
Делим вторую матрицу:
Почему делим на 37? Потому что это длина нашего алфавита, будь у вас алфавит другой длины, вы бы делили на другое число. Например, для английского алфавита делим на 26, или 29, если вы добавили какие-то символы.
- Теперь декодируем полученные матрицы с помощью нашего алфавита.
Первая матрица: АЮН
Вторая матрица: ЧХЯ
Склеиваем две матрицы и получаем зашифрованный текст: АЮНЧХЯ
Дешифрование
Теперь переходим к дешифрованию. Дешифрование производим по следующему алгоритму:
- Обратно кодируем шифротекст в цифры и разбиваем на блоки.
- Находим определитель матрицы ключа:
Нахождение определителя тоже очень простая операция, так что я ее не расписывал.
- Теперь по расширенному алгоритму Евклида находим d, x, y.
Описание и сам алгоритм я расписывать не буду. Информацию об этом алгоритме легко можно найти в Интернете. На вход алгоритма подаем det K и длину нашего алфавита. На выходе мы получим d=1, x=-4, y=41. Нас интересует только x.
- Теперь сложная и важная вещь. Нам надо найти обратный детерминанту элемент в кольце по модулю 37. Для этого делаем следующее:
• Если детерминант отрицательный, а x – положительный, то обратный элемент детерминанта будет равен x.
• Если детерминант положительный, а x – отрицательный, то обратный элемент детерминанта будет равен 37+x.
• Если детерминант положительный, и x – положительный, то обратный детерминанту элемент будет равен x.
• Если детерминант и x – отрицательные, то обратный элемент будет равен -x.
Этот алгоритм поиска обратного элемента я подобрал экспериментальным путем, т.к. не мог найти ровным счетом ничего полезного по этой теме. В любом случае, даже если этот алгоритм примитивный, он работает.
Итак, наш детерминант равен 379, он положительный, а x равен -4 – отрицательный. Тогда обратный детерминанту элемент находим по формуле 37+x=37+(-4)=37-4=33.
- Теперь еще один момент, с которым я долго мучился, потому что никакой полезной информации в Интернете найти не удалось. Надо найти матрицу обратную матрице ключа по модулю 37. Для того чтобы найти эту матрицу нам необходимо найти матрицу алгебраических дополнений ключа и обратный детерминант матрицы ключа (уже нашли в предыдущем пункте). Матрица алгебраических дополнений ищется тоже очень просто, это я расписывать не буду. В нашем случае она выглядит так:
Теперь эту матрицу делим по модулю на 37, это я уже расписывал в шифровании. Получаем такую матрицу, тут важно не терять знаки у элементов (некоторые выполняют деление по модулю с потерей минусов, в данном алгоритме это недопустимо):
Умножаем матрицу алгебраических дополнений на обратный детерминанту элемент. Получаем такую матрицу:
Делим данну матрицу по модулю на 37:
Транспонируем ее (меняем строки и столбцы местами):
Теперь если элемент матрицы отрицательный, меняем его на другой, вычисленный по формуле 37+<элемент>:
Последняя полученная матрица является обратной по модулю к матрице ключа. Если перемножить матрицу ключа и эту матрицу, а потом результат разделить по модулю на 37, мы получим единичную матрицу, т.е. матрицу вида:
- Для дешифровки шифротекста умножаем строки шифротекста на матрицу обратную ключу.
Умножаем первую строку:
Умножаем вторую строку:
Делим полученные строки на 37 по модулю:
Склеиваем матрицы (25 9 21 13 35 35) и декодируем с помощью нашего алфавита: ШИФР.
В итоге мы получили исходный текст с двумя лишними пробелами в конце, которые никакой роли не играют.
Спасибо за внимание!
Комментарии (36)
koldyr
09.07.2017 21:57+1Если последовать принципу Керкгоффса, то для определения ключа необходимо n пар открытый-закрытый текст.
Зачем эта статья? Или объяили неделю приложений линейной алгебры?
den_golub
10.07.2017 10:50-1Да только вот можно и промахнуться, пары открытый-закрытый текст может быть полной бессмыслицей, например если помимо всего прочего вы используете еще какой-то алгоритм для шифровки, взять хотя бы простейший шифр Цезаря, да понятно что перебрать все его варианты это O (n), где n — длина алфавита, но это уже время, а если при этом сдвиг меняется после каждого сеанса по заранее обговоренным условиям, например по корням определителя матрицы многочленов, над кольцом многочленов по модулю скажем 45 — го знака числа ?, то это уже проблема.
koldyr
10.07.2017 11:03Ознакомтесь с принципом Кергоффса.
Содержание пар не имеет значения, главное чтобы они образовывали базис.
В остальном — если внутрь запихнуть aes то вообще можно не парится.mayorovp
10.07.2017 11:19Ну, не обязательно aes запихивать. Композицию любых двух алгоритмов шифрования взломать сложнее чем оба алгоритма по-отдельности. Если у них ключи независимы, конечно же. И UB в реализации нет.
koldyr
10.07.2017 11:23+1Композиция двух простых замен на разных ключах эквивалентна простой замене на третьем ключе.
Не устаю приводить ссылку на замечательный пост.mayorovp
10.07.2017 11:31Простых замен — да, эквивалентна. А вот простая замена с шифром Хила уже не упрощаются до более простого алгоритма.
Пост по вашей ссылке и правда замечательный, но с утверждением "содержание пар не имеет значения, главное чтобы они образовывали базис" как ответом на "шифры можно комбинировать" не согласен.
koldyr
10.07.2017 11:36Вы знаете доказательство того, что простая замена с Хиллом не упрощается?
mayorovp
10.07.2017 11:56Я знаю доказательство того, что простая замена с Хиллом не упрощается до одной из составных частей.
koldyr
10.07.2017 12:20Предъявите пожалуйста.
mayorovp
10.07.2017 13:50+2Вот немного нестрогое доказательство, потому что строгое писать в комментарии неудобно из-за отсутствия нормальной разметки.
Если заметить, что композиция двух простых шифров — простой шифр, композиция двух Хиллов — Хилл, а обратные преобразования к простому шифту и Хиллу являются тоже простым шифром и Хиллом, то в уравнениях T
*Х1 = Х2 и T1*Х = T2 (где T — простой шифр, Х — алгоритм Хилла) можно перенести все простые шифры в левую часть, а всех Хиллов — в правую, получив уравнение вида T3 = Х3.
Таким образом, композиция указанных двух алгоритмов может быть эквивалентна одному из алгоритмов-компонент тогда и только тогда когда найдутся эквивалентные друг другу простой шифр и алгоритм Хилла. Но для нетривиальных алгоритмов это невозможно, потому что у них разные размеры блоков.
koldyr
10.07.2017 13:53-2В последнем предложении — ошибка.
mayorovp
10.07.2017 13:54+1Поясните.
koldyr
10.07.2017 13:57+1Рассмотрим простую замену при которой каждый символ меняется путем умножения наобратимый элемент кольца.
Тогда с таким ключем данная простая замена будет эквивалентна шифру Хилла. И композиция даст шифр Хилла.mayorovp
10.07.2017 14:10Ок, согласен. Надо поправить формулировку теоремы, но мне лень.
Тем не менее, замечу, что предложенный вами алгоритм, хоть и относится к семейству простых замен — но с точки зрения принципа Керкгоффса простой заменой не является. Потому что у шифра простой замены ключ — это целая таблица подстановки, а у умножения в поле вычетов — один символ.
koldyr
10.07.2017 14:12И опять вы заметили не правильно, с помощью указанной операции сформируйте таблицу замены. И пользуйтесь на здоровье.
merlin-vrn
10.07.2017 16:59Один символ будет в этом фактически этим ключом.
Мы всего сможем получить столько различных вариантов ключа, сколько у нас есть различных символов, без возведения в степень — длину таблицы. Короче, существует вполне себе эффективный исследователь, «брутфорс», который различит ваш сфабрикованный ключ и настоящую случайную таблицу, значит, не эквивалентны.koldyr
10.07.2017 17:02В простой замене не сказано какая должна быть таблица замены. В том числе она может быть такой, как я написал.
merlin-vrn
10.07.2017 17:04В простой замене предполагается, что мощность пространства ключей — N^M, где M — длина таблицы. А вы делаете замену с пространством всего лишь N, а потом распространяете выводы, полученные для неё, на все простые замены. Это некорректно.
koldyr
10.07.2017 17:10Я не писал про все. Я писал про то что существуют такие ключи для которых…
merlin-vrn
10.07.2017 17:17Ну, N слабых ключей из N^M — это для практических N и M пренебрежимо малая вероятность.
daiver19
10.07.2017 00:30+5Этот алгоритм поиска обратного элемента я подобрал экспериментальным путем, т.к. не мог найти ровным счетом ничего полезного по этой теме.
Не, ну вы серьёзно? Это ж база. Ищется тем же расширенным алгоритмом Евклида для пары (число, модуль). Подробнее здесь.mayorovp
10.07.2017 10:44Так он его и использовал. Только он не догадался перед применением алгоритма загнать определитель в кольцо вычетов, отсюда и появился случай с отрицательным определителем, который пришлось докостыливать.
mayorovp
10.07.2017 10:52Получаем такую матрицу, тут важно не терять знаки у элементов (некоторые выполняют деление по модулю с потерей минусов, в данном алгоритме это недопустимо):
Скажите, а почему убрать отрицательные элементы на данном этапе — недопустимо?
Я бы напротив, советовал избавляться от отрицательных элементов на каждом этапе, добавляя к ним 37. Это избавило бы от "сложных и важных вещей" на шагах 4 и 5.
den_golub
10.07.2017 10:54Тут скорее автор имел ввиду что многие просто про них забывают и модулируют без них. ИМХО
mayorovp
10.07.2017 11:01… и что же такого страшного при этом случается? Независимо от того, какая из двух операций нахождения остатка используется — ее можно применить и так и забыть. Оба варианта эквивалентны в используемом поле вычетов.
Duha666
10.07.2017 11:05Тут скорее автор комментария имел в виду, что автор имел а виду, что многие просто при слове модуль считают числа -13 и 13 эквивалентными (на самом деле не знаю кто так может считать)
Duha666
10.07.2017 11:02+1Только длина ключа равная квадрату числа — не единственное требование к нему.
Вы считаете определитель матрицы, а он может оказаться нулем. Нужно ещё и чтобы столбцы были линейно-независимыми, и тут уже оперировать словами языка в качестве ключа становится невозможно. Вам повезло с альпинизмом.mayorovp
10.07.2017 11:08Автор это учел:
Также важным фактором для данного шифра является определитель матрицы ключа: он должен быть отличным от нуля, иначе расшифровку зашифрованного текста будет невозможно осуществить.
Кстати, вероятность того, что случайный ключ будет "плохим" — чуть больше чем 1/37 (более точно: 1/37 + 1/372 — 1/373). Так что не так уж и сильно автору повезло с альпинизмом.
Catharsis96
пофиксите пожалуйста опечатку в топике.
GRaAL
У меня сложилось впечатление, что опечатка намеренная (уж больно очевидная). Может, в заголовке что-то зашифровано?