Матричные шифры
Имеется еще один метод подстановки n-грамм, который заключается в применении к последовательным n-граммам некоторой матрицы, имеющей обратную. Предполагается, что буквы занумерованы от 0 до 25 и рассматриваются как элементы некоторого алгебраического кольца. Если к n-грамме сообще-
ния применить матрицу , то получится n-грамма криптограммы:
Матрица является ключом, и расшифровка выполняется с помощью обратной матрицы. Обратная матрица будет существовать тогда и только тогда,
когда определитель имеет обратный элемент в нашем кольце.
Аналитические методы шифрования
качестве матричного шифрования информации могут использоваться аналитические преобразования, основанные на преобразованиях матричной алгебры.
Шифрование k-го блока исходной информации, представленного в виде вектора В^ = || bj ||, осуществляется путем перемножения этого вектора на матрицу А = || ау ||, используемую в качестве ключа. В результате перемножения получается блок шифротекста в виде вектора Ск = || q ||, где элементы вектора Ск определяются по формуле:
Приведем пример, взяв в качестве ключа квадратную матрицу третьего по- 1 4 8
Пусть требуется с помощью этого ключа зашифровать слово
Для этого необходимо выполнить следующие шаги.
1. Определяется числовой эквивалент Тэ исходного слова как последовательность соответствующих порядковых номеров букв этого слова в алфавите: 
2. Умножается ключевая матрица А на векторы В( = <8,1,2>и В2 = <1,3,1>:
3. Зашифрованное слово записывается в виде последовательности чисел
Расшифрование осуществляется также с использованием правил матричной алгебры, только в качестве ключа берется матрица, обратная той, с помощью которой осуществлялось шифрование, а в качестве вектора-сомножителя — соответствующие фрагменты символов зашифрованного текста. Тогда компонентами вектора-результата будут цифровые эквиваленты букв открытого текста.
Для расшифрования полученной в предыдущем примере последовательности чисел Т[ необходимо выполнить следующие шаги.
1. Вычисляется определитель матрицы-ключа | А | =-115.
Тема б. Шифры замены
- 17 -3 -15
- 2. Находится присоединенная матрица А* = 52 -43 15 , каждый элемент
- -48 22 -5
ajj которой является алгебраическим дополнением элемента а у матрицы-ключа
А, то есть ajj =(-l) l+J Ajj, где — определитель матрицы, получаемой вычеркиванием i-й строки и j-oro столбца исходной матрицы А.
- 17 52 -48
- 3. Получается транспонированная матрица А т= -3 -43 22 , элементы
- -15 15 -5
- -17/115 -52/115 48/115
- 4. Вычисляется обратная матрица А -1 = 3/115 43/115 -22/115 , эле-
- 15/115 -15/115 5/115
менты которой aj. 1 =а! /|а| .
5. Определяются векторы Bj = A *Ci и В2 = А ^2:
6. Числовой эквивалент расшифрованного слова = заменяется соответствующими символами алфавита, в результате чего получается исходное слово Т0 = .
Шифр Хила. Подробный разбор
Для того, чтобы зашифровать какой-либо текст по алгоритму Хилла необходимо проделать следующие шаги:
-
Создаем кодированный алфавит. Допустим мы хотим шифровать русский текст. Тогда длина алфавита будет 33 буквы. Целесообразно добавить к алфавиту еще 4 символа на выбор, я добавлю такие: «?», «.», «,»,» «. Это делается для того, чтобы длина алфавита была простым числом, т.е. числом, которое делится нацело только на себя и на 1. Это, конечно, не обязательно, но очень удобно, потому что для расшифровки необходимо, чтобы детерминант ключа и длина алфавита были взаимно простыми, т.е. не имели общих делителей кроме 1. Если длина алфавита – простое число, то таких ключей, для которых выполняется это условие значительно больше. Каждому символу нашего алфавита ставим в соответствие целочисленный код. Удобнее всего использовать просто номера букв. Таким образом получаем кодированный алфавит:
Ключ можно задавать сразу матрицей, если вам так удобней. Я же использовал ключевое слово.
Первый блок: (25 9 21)
На второй блок у нас осталось всего одно число – 17. Самое простое решение в таком случае: добавить столько символов, чтобы образовать целый блок. Я решил добавить пробелы.
Тогда второй блок: (17 35 35)
Также важным фактором для данного шифра является определитель матрицы ключа: он должен быть отличным от нуля, иначе расшифровку зашифрованного текста будет невозможно осуществить.
Итак, умножаем первый блок на ключ:
Умножаем второй блок на ключ:
Матричное умножение — это не сложная операция, поэтому расписывать его подробно я не стал.
Теперь нам нужно получившиеся матрицы разделить по модулю на 37, т.е. взять остаток от деления на 37.
Делим первую матрицу:
Делим вторую матрицу:
Почему делим на 37? Потому что это длина нашего алфавита, будь у вас алфавит другой длины, вы бы делили на другое число. Например, для английского алфавита делим на 26, или 29, если вы добавили какие-то символы.
Первая матрица: АЮН
Вторая матрица: ЧХЯ
Дешифрование
Теперь переходим к дешифрованию. Дешифрование производим по следующему алгоритму:
-
Обратно кодируем шифротекст в цифры и разбиваем на блоки.
Нахождение определителя тоже очень простая операция, так что я ее не расписывал.
Описание и сам алгоритм я расписывать не буду. Информацию об этом алгоритме легко можно найти в Интернете. На вход алгоритма подаем det K и длину нашего алфавита. На выходе мы получим d=1, x=-4, y=41. Нас интересует только x.
• Если детерминант отрицательный, а x – положительный, то обратный элемент детерминанта будет равен x.
• Если детерминант положительный, а x – отрицательный, то обратный элемент детерминанта будет равен 37+x.
• Если детерминант положительный, и x – положительный, то обратный детерминанту элемент будет равен x.
• Если детерминант и x – отрицательные, то обратный элемент будет равен -x.
Этот алгоритм поиска обратного элемента я подобрал экспериментальным путем, т.к. не мог найти ровным счетом ничего полезного по этой теме. В любом случае, даже если этот алгоритм примитивный, он работает.
Итак, наш детерминант равен 379, он положительный, а x равен -4 – отрицательный. Тогда обратный детерминанту элемент находим по формуле 37+x=37+(-4)=37-4=33.
Теперь эту матрицу делим по модулю на 37, это я уже расписывал в шифровании. Получаем такую матрицу, тут важно не терять знаки у элементов (некоторые выполняют деление по модулю с потерей минусов, в данном алгоритме это недопустимо):
Умножаем матрицу алгебраических дополнений на обратный детерминанту элемент. Получаем такую матрицу:
Делим данну матрицу по модулю на 37:
Транспонируем ее (меняем строки и столбцы местами):
Теперь если элемент матрицы отрицательный, меняем его на другой, вычисленный по формуле 37+<элемент>:
Последняя полученная матрица является обратной по модулю к матрице ключа. Если перемножить матрицу ключа и эту матрицу, а потом результат разделить по модулю на 37, мы получим единичную матрицу, т.е. матрицу вида:
Умножаем вторую строку:
Делим полученные строки на 37 по модулю:
Склеиваем матрицы (25 9 21 13 35 35) и декодируем с помощью нашего алфавита: ШИФР.