Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
А = APP"1 = CP'1.
Аналогично, из уравнения P = A 1C находится A l: А 1 = PC
Пример 6. Пусть известно, что противник использует при шифровании 2 x 2-матрицу с элементами из 29-буквенного алфавита, где A-Z имеют обычные числовые эквиваленты, пробел=26, 1=21, !=28. Принято сообщение
«GFPYJP X7UYXSTLADPLW»,
82
ГЛ. III. КРИПТОГРАФИЯ
причем предполагается, что последние пять букв открытого текста — подпись «KARLA». Этих букв хватает для построения лишь двух биграмм. Итак, биграммам «DP» и «LW» шифртекста в открытом тексте отвечают биграммы «AR» и «LA» соответственно. Значит, матрица Р, составленная из «AR» и «LA», получается как результат умножения неизвестной матрицы дешифрования А на матрицу С. составленную из «DP» и «LW»:
/о іЛ і(з її Л
I4 17 0 у 15 22 J ¦
Таким образом,
.-1_/0 П\(3 UV' /О 1Л / 3 13^ /21 19 Л
V17 °/\ 15 22 У "V17 0 / V23 7 / V22 18Z
и все открытое сообщение имеет вид
/21 19 Л /6 15 9 26 27 24 18 11 3 11 \ I4 22 18 у V4 5 24 15 23 20 23 19 0 15 22 У
_ / 18 17 10 26 19 13 14 28 0 ll\ _ Vn 19 8 4 0 26 14 13 10 17 0 у
= «STRIKE AT NOON1KARLA».
Замечание. Чтобы описанный метод работал, нужна обратимость матрицы Р, образованной из двух известных биграмм открытого текста, т. е. определитель D не должен иметь общих множителей с числом букв N. Что же делать, если нам не повезет? Если известна еще одна пара биграмм открытого и шифрованного текстов, можно попробовать использовать ее в матрицах P и С вместо первых или вторых столбцов в надежде получить обратимую матрицу. Пусть у нас нет такой возможности или ни одна известная пара не дает обратимой матрицы Р. Тогда мы не можем определить матрицу А точно. Однако имеющейся у нас информации достаточно для того, чтобы значительно сократить число возможных вариантов для дешифрующей матрицы. Проиллюстрируем это на примере. (См. также упражнения в конце раздела.)
Пример 7. Известно, что противник использует шифрующую матрицу А с элементами из 26-буквенного алфавита. Перехвачено сообщение «WKNCCHSSJH». Известно также, что первое слово — это «GIVE». Мы хотим найти матрицу дешифрования А 1 и прочитать сообщение.
Решение. Воспользовавшись процедурой примера 6 и записав P= «GIVE»=^ ^1),
§ 2. ШИФРУЮЩИЕ МАТРИЦЫ 83
2 4
3 2
+ 13A1
вместо A1B уравнение
А~
22 13 \ _ / 6 21 10 2 j ~ І 8 4
(последнее равенство имеет смысл поэлементного сравнения по модулю 26), мы исключим все возможности, кроме двух следующих:
(I о\ (\ 1
A1 = ( л 1 ) или
т. е.
11/ VIl
,-1 /15 4 \ /15 17
А = I „ , I или
16 15 J V 16 15
C = «WKNC»=(^ Л-1= PC"1,
мы сразу столкнемся с трудностями, так как det С = 18 и НОД (18, 26) = 2. Мы можем продолжить следующим образом. Пусть А обозначает приведенную по модулю 13 матрицу А. Аналогичный смысл имеют обозначения P и С. Рассматривая эти матрицы в M2(Z/13Z), можно
найти С 1 (точнее, С ), так как НОД (det С, 13) = 1. Поэтому из
равенства P = A С получим
3-1^=(S *) G» s)"-(з t
Таким образом, элементы матрицы А 1, являющиеся целыми по модулю 26, должны приводится по модулю 13 к элементам матрицы
2 4
3 2
Следовательно, для каждого элемента этой матрицы есть по две возможности. Точнее,
л" = (з а) + 13*.
где А\ Є M2(Z/2Z) есть 2 X 2-матрица из нулей и единиц. Поэтому остается 2 = 16 возможных вариантов. Однако, что самое главное, так как матрица А 1 обратима, ее определитель должен быть взаимно прост с 26 и, в частности, быть нечетным. Это соображение оставляет возможными всего шесть вариантов для А\. Далее, когда мы подставим
84
ГЛ. III. КРИПТОГРАФИЯ
Попытка дешифрования с первой матрицей приводит к заведомо сомнительному варианту «GIVEGHEMHP». Дешифрование с матрицей
А ~\16 15
дает ответ «GIVETHEMUP». Значит, последний вариант — правильный. Этот метод предполагает некоторое количество проб и ошибок, но в любом случае это лучше проверки всех 157 248 вариантов матрицы дешифрования А Є M2(Z/26Z) .
Замечание. В примере 7, возможно, удобнее было бы подправить элементы матрицы А 1, прибавив к ним кратные 13 так, чтобы все они делились на два, т.е. определить матрицу А\ равенством
A-I = (i26 !I) + I3*.
Тогда можно искать матрицу А\, оперируя по модулю 2, так как AxC = P (mod 2).
Шифрующие аффинные преобразования. Более общий способ шифрования биграммы-вектора P = (*) состоит в умножении его
на 2 X 2-матрицу А = (" Є M2(ZfNZ) и прибавлении к результату вектора констант В = Q) :
С = AP+ В,
т. е.
X \ fa b\ (х\ f е\ (ах + by + е
у') Vе dJ KvJ + KfJ \сх + dy + f Это преобразование называется аффинным отображением. Оно аналогично шифрующей функции С = аР + b из §1, где рассматривались однобуквенные элементы сообщений. Разумеется, как и раньше, знак равенства понимается как сравнимость элементов по модулю N.
Обратное преобразование, выражающее P через С, может быть получено вычитанием вектора В из обеих частей и последующим применением к ним А :
