Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
над Z (ключ) и у = (ух9...,уп) — «-грамма шифртекста, то
у^ = Ek (х) = к • Jt ^. Соответственно X^ = Dk (у) = к~1 • у^,
где к~] — матрица, обратная к матрице для к.
Подчеркнем, что матричные операции здесь производятся над кольцом Z .
Проиллюстрируем введенное определение примером.
Пример (шифра Хилла)
Положим п = 4 и зашифруем фразу:
без труда не вынешь рыбку из пруда
записанную в 30-буквенном русском алфавите. Условимся о числовом кодировании букв в соответствии с таблицей:
116
Шифры замены
А Б В Г д E Ж 3 И К Л M H о П
1 18 11 6 0 15 20 5 21 23 13 4 16 8 25
P С T У Ф X ц Ч Ш щ Ь ы Э Ю Я
24 10 19 26 12 2 28 7 17 22 3 29 27 14 9
В качестве ключа выберем матрицу
'1 2 3 4"
12 3 5
к = *
13 3 5
J 3 4 5 J
являющуюся обратимой над кольцом Z30. Несложно убедиться в том, что
ґ 5 2S 1 27л
, _ 0 29 I О
О 0 29 1
^29 1 0 Oj
Запишем открытый текст по столбцам матрицы T :
'18 241616 24 26 24^ 15 261515 29 2126
T =
5 0 11 1718 5 О ч 19 1 29 3 23 25 1 ,
и получим шифртекст в виде столбцов матрицы к • T:
117
fлава 5
Ґ\ 2 3 4^ /
1 2 3 5
1 3 3 5
3 4 5, ч
18 241616 24 26 24ч 15 261515 29 2126 5 O 11 1718 5 O
19 1 29 3 23 25 1
? х
^19 2015 19 18 З 20 л 8 21 14 221128 21 2317 29 7 101917 28 17 10 24 28 24 17
Теперь осталось воспользоваться числовым кодом, чтобы выписать шифртекст в буквенном виде:
токцжишшеюыстщчрбвсцъцтржигиги
Замечание. Из соображений удобства в применении получили широкое распространение шифры, для которых правила зашифрования и расшифрования идентичны. Такие шифры называются обратимыми. Шифр Хилла является обратимым в том и только том случае, когда к~х — к, или иначе: к2 = E, где E — единичная матрица. Матрица, удовлетворяющая этому свойству, называется инволютивной.
Из курса алгебры известен критерий обратимости квадратной матрицы над кольцом Zm.
Теорема. Квадратная матрица M над кольцом Zm обратима тогда и только тогда, когда (jА/j, т) = \, то есть определитель \М\ взаимно прост с т.
Заметим, что правило зашифрования Em (с матрицей Mnxn) в шифрсистеме Хилла является обратимым линейным
118
Шифры замены
преобразованием «-мерного модуля Znm . Такая функция является лишь одним из примеров простого задания обратимого преобразования Znm -> Z" , являющегося, очевидно, биекцией
на Znm. Любая же такая биекция потенциально может рассматриваться как правило зашифрования блочного шифра простой замены (если п — размер блока), выбираемого некоторым ключом. Поскольку число обратимых линейных преобразований модуля Znm составляет (при п>2,т>2) лишь
незначительную часть общего числа рассматриваемых биекций, то же самое можно сказать и о доле, которую составляют (при данном п) шифрсистемы Хилла в множестве возможных блочных шифров простой замены.
Замечание. Можно проверить, что имеется всего 24 обратимых преобразования f '.Z12 —» Z2, причем все они являются аффинными, то есть для любого х є Z2 они имеют вид
f(x) = x-A + b,
где А — некоторая обратимая 2x2 -матрица над Z2, и SeZ22.
Естественным обобщением шифра Хилла является аффинный блочный шифр, правило зашифрования E ^ (х)
которого определяется формулой (1). При этом А является обратимой п х п матрицей, а Ь — фиксированным п-мерным вектором над Zm.
Как и при рассмотрении предыдущих шифров, приведем некоторые соображения о криптоанализе аффинного блочного шифра и, в частности, шифра Хилла.
Увеличение значности шифрвеличин резко усложняет попытки вскрытия открытого текста по известному тексту криптограммы. Однако свойство линейности, присущее рас-
119
І лава Ь
сматриваемым шифрам, конечно, является их криптографической слабостью. Чтобы показать это, рассмотрим следующую криптоатаку на аффинный шифр.
Предположим, что известны л +1 пар блоков открытого текста и соответствующих им блоков шифртекста: (х0,у0(х„,у„), X1,уJ є Znm, полученных на одном ключе
(А,Ь). Требуется этот ключ найти.
Для решения поставленной задачи положим:
х(,) =X,-X0, у0) =у, -у0, і = I,п.
Тогда х(,) и у{,) оказываются связанными линейным соотношением у(/) = х(,) • А .
Аналогичное соотношение имеет место и для матриц
X =
и Y =
х(Л) v("’
V J J
из которого находим матрицу А в виде произведения A = XY.
Наконец, вектор Ъ находится, например, по формуле Ь = yQ - X0 • А. Естественно, что такое решение корректно
лишь в том случае, когда матрица X обратима.
Поскольку обращение матрицы и вычисление произведения матриц являются не слишком трудоемкими операциями, то таковой же является и поставленная задача.
Более детальное рассмотрение блочных шифров простой замены будет продолжено в гл. 8.
120
Шифры замены
§ 5.4. Многоалфавитные шифры замены
Напомним, что правило зашифрования многоалфавитного шифра однозначной замены определяется следующим образом. Пусть х = (JC1 ,...,JC,) —открытый текст, представленный
последовательностью шифрвеличин X1GU9 Z = I,/, и к — произвольный ключ. Тогда
