Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
Нас особенно будет интересовать случай R = Z/NZ. Следующее предложение формулируется именно для этого случая, хотя аналогичное утверждение верно для любого R.
Предложение III. 2.1. Пусть
Л=(с є ^(Z/.VZ) и D = ad-be.
Следующие утверждения эквивалентны:
a) НОД (D,N)= 1;
b) матрица А имеет обратную;
c) если хотя бы один из элементов х, у Є Z/NZ отличен от нуля, то -4(р/(0°).
d) матрица А задает взаимно однозначное отображение мно-жества (Z/NZ) на себя.
Доказательство. Мы уже видели, что а) ==> Ь). Поэтому достаточно показать, что b) => d) => с) => а).
Предположим, что выполнено Ь). Тогда выполнено и утверждение d), так как А 1 задает обратное отображение в Далее, если выполнено d), то (р ф (°) влечет за собой, что А(х) ф Л(°) = (°), и, следовательно, с) выполнено. Наконец, докажем, что с) => а),
§ 2. ШИФРУЮЩИЕ МАТРИЦЫ
79
рассуждением от противного. Итак, пусть а) неверно. Положим т = НОД (D,N) > 1 и т = N/m. Возможны три случая.
Случай 1. Если все четыре элемента матрицы А делятся на т, то возьмем (jj) = (™,), что приведет к противоречию со свойством с).
Случай 2. Если хотя бы один из элементов а и о не делится на т, то возьмем g) = ("6^ ). Тогда
fa Ь\ f-bm'\ _ ґ-abm + bam'\ _ f О \ _ ЛЛ \с d)\am')~ \-cbm + dam'J ~ \Drri') ~ \о) '
так как m\D и, следовательно, N = mm'\Dm .
Случай 3. Если хотя бы один из элементов с и d не делится на т, то возьмем = (_cm,J и продолжим рассуждения, как в предыдущем случае.
Рассмотренные случаи исчерпывают все возможности. Таким образом, нарушение а) влечет за собой нарушение с). Это завершает доказательство предложения.
Пример 2. Решить следующие системы сравнений:
а)
2х + Зу = 1 (mod 26), Ix + 8у = 2 (mod 26);
Ъ)
х + 3у=1 (mod 26), Ix + 9у ее 2 (mod 26);
с)
ж + Зу EEE 1 (mod 26), Ix + 9у ее 1 (mod 26).
Решение. В матричной форме система а) имеет вид AX ее В (mod 26), где А — матрица из примера 1, X= (Jj), В = Q)• Получаем единственное решение
Матрица систем Ь) и с) не имеет обратной по модулю 26, так как ее определитель равен 14 и имеет с модулем 26 общий множитель 2. Однако можно перейти к модулю 13, найти решение системы по этому модулю и проверить, не дает ли оно решений по модулю 26. По модулю 13 получаем
о-a 1OO
80
ГЛ. III. КРИПТОГРАФИЯ
(где (ef) = (*) для системы Ь) и (J) для системы с)). Это дает (ху) = (3J
и (^) (mod 13) соответственно. Проверяя варианты, возникающие при переходе к модулю 26, убеждаемся, что система Ь) решений не имеет, а система с) имеет два решения х = 6, у = 7 и х = 19, у = 20.
Другой способ решения систем уравнений (иногда более предпочтительный, особенно при необратимой матрице) состоит в исключении одного из неизвестных (так, в системах Ь) и с) можно было вычесть семь раз первое сравнение из второго).
Возвращаясь к криптографии, видим, что согласно предложению III. 2.1 можно построить преобразование шифрования наших биграмм-векторов, используя матрицы .4 Є M2(ZfNZ), у которых определитель не имеет общих множителей с N:
Л=(ас bd) , D = ad -be, HOR(D,N)=I.
А именно, элемент открытого текста P = преобразуется в элемент шифртекста C= (*,) по правилу
- (;И°;)(;
Чтобы дешифровать сообщение, просто применяем обратную матрицу: P = Л"1 AP = Л"1C, т.е.
А ( D~ld -D~lb\ fx
VJ \~D 1C D la ) \y
П p и M e p 3. В 26-буквенном алфавите, используя матрицу Л примера 1, зашифровать элемент «NO». Решение. Имеем
и С = AP есть «QV».
Замечание. Чтобы зашифровать последовательность P = Р1Р2Р3 ¦ ¦ ¦Pk из к биграмм открытого текста, можно построить 2 X /:-ма.трицу из к век торов-столбцов (обозначим ее также через P) и, умножив 2 X 2-матрицу Л на 2 X /с-матрицу Р, получить 2 х /г-матрицу С = AP из шифрованных биграмм-векторов.
Пример 4. Продолжая пример 3, зашифровать открытый текст «NOANSWER».
§ 2. ШИФРУЮЩИЕ МАТРИЦЫ
81
Решение. Числовым эквивалентом для «NOANSWER» является последовательность векторов (!4)(^3)(22)(17)- Имеем
С = AP
2 3\ / 13 0 18 4 Л _ / 68 39 102 59 7 8у I4 14 13 22 17 / V 203 104 302 164
16 13 24 21 0 16
т.е. шифрованное сообщение имеет вид «QVNAYQHI».
Пример 5. В ситуации примеров 3 и 4 дешифровать сообщение «FWMDIQ».
Решение. Имеем
_ -і /14 П\(Ь 12 8 ґ - л ° " 1 17 10Д22 3 16
19 о9 Xo)=^TTACK..
Как и в § 1. будем считать, что у нас имеется некоторая ограниченная информация, которую мы хотим использовать для дешифрования отрезка шифртекста. Нам известно, что «противник» использует биграммы-векторы и линейное шифрующее преобразование С = AP в TV-буквенном алфавите. Однако мы не знаем ни ключа шифрования (матрицы А), ни ключа дешифрования (матрицы А Но предположим, что у нас есть возможность найти две пары биграмм открытого и шифрованного текстов С\ = APx и C2 = AP2. Возможно, эти сведения нам удалось получить частотным анализом биграмм в длинном отрезке шифртекста или каким-либо образом стало известно, во что шифруется некоторый четырехбуквенный отрезок текста. В этом случае для определения матриц А и А 1 мы можем сделать следующее. Объединим два столбца P1 и P2 в 2 x 2-матрицу P и таким же образом поступим со столбцами шифртекста. Мы получим уравнение для 2x2-матриц: С = АР, где С и P нам известны, а А является неизвестной. Можно решить это уравнение, домножив обе части на P :
