Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
P = А~1С - А~1В.
Оно также является аффинным преобразованием P = А'С + В' с А' = А и В' = -А В. Заметим, что для однозначности дешифрования требуется обратимость матрицы А.
Пусть известно, что противник использует аффинное шифрующее преобразование биграмм-векторов из iV-буквенного алфавита. Для нахождения А и В (или A=A и В = -А В) теперь нужны, по
§ 2. ШИФРУЮЩИЕ МАТРИЦЫ
85
крайней мере, три пары биграмм. Пусть, например, известно, что биграммы C1, C2, C3 шифртекста отвечают биграммам открытого текста P1, P2, P3:
P1 = Л'С, + P', P2 = Л'С2 + Р', P3 = Л'Сз + Я'.
Для нахождения Л' и Р' мы можем сделать следующее. Вычтем последнее уравнение из первых двух и образуем 2 X 2-матрицу P из столбцов P1 — P3 и P2 - P3, а 2 X 2-матрицу С — из столбцов C1 - C3 и C2 — C3. Получим матричное уравнение P = AC, которое, как и в случае линейных преобразований, может быть разрешено относительно А' (при условии, что матрица С обратима). Наконец, определив А' = А 1, находим из любого из приведенных выше уравнений В1, например. В = P1 — A C1.
УПРАЖНЕНИЯ
1. Используя частотный метод, дешифровать сообщение в 26-буквенном алфавите, закодированное шифром Виженера с трехбуквенным ключевым словом. Сделать это следующим образом. Для определения первой буквы ключевого слова использовать последовательность из каждой третьей буквы сообщения, начиная с первой. Не надо предполагать, что самой частой буквой сообщения обязательно является буква «Е». Следует просмотреть в качестве варианта шифра для буквы «К» четыре наиболее часто встречающихся буквы. Если при выборе варианта для «Е» оказывается, что хотя бы одна из трех других часто встречающихся букв отвечает сравнительно редкой букве, скажем, «Q» или «Z», то это свидетельствует о неправильном выборе шифра для «Е». Исключая такие варианты, найти шифр для «Е», затем букву ключевого слова, использованного при шифровании. Таким способом определить ключевое слово и дешифровать сообщение
AW Y\'PQCTB LW Y L PASQ J WU PG В USH FAC ELDLL DLWLB WA FAHSEBY JXXACELWC JTQM ARKUDLWCSXBUDLKDPLXSEQC JT X WPRWSRGBCLWPG JEZIFWIM JDLLDAGCQM AYLTGLPP JXTWS GFRMVTLGUYUXJAIGWHCPXQLTBXDPVTAGSGFVRZTWTGM M VFLXRLDK WP RLWCSXPHDPL PKSHQG ULM BZ WGQAPQCTB А URZTWSHQMBCYXAGJJVGCSSGLIFWNQSXBFDGSHIWSFGLRZ T WEPLS VC VIF WX QSXBOWCFH M ETRZXLYPP JXTWSGFRM VTR ZT WH WM FTBOPQZXLYIM FP LV W YVIF WDPAVGFP J ETQKPE WG CSSRGIFWB
86
ГЛ. III. КРИПТОГРАФИЯ
2. Найти обратные к следующим матрицам по модулю N. Записать элементы обратных матриц как неотрицательные целые, меньшие N.
а))1 3) (mod 5), 6)(1 3 ) (mod 29), в)( 5 17J (mod 26),
.4 3 J 4 \4 З
./40 0 \ , / 197 62 \ ,
г)(0 21) (mod 841), д)(6оз 2П )(mod 841).
В упражнениях 3-5 найдите все решения (*) по модулю Л', рассматривая х и у как неотрицательные целые числа, меньшие N. 3.
а) X + Ay = 1 (mod 9) б) х + Ay = 1 (mod 9) Ъх + Iy = 1 (mod 9) 5х + 8у = 1 (mod 9)
в) X + 4у = 1 (mod 9) г) х + Ay = 0 (mod 9) Ъх -\- 8у = 2 (mod 9) 5х + 8у = 0 (mod 9)
4.
a) 17z + Hy = 7 (mod 29) б) 17z + Hy = 0 (mod 29) 13х + 10jf = 8 (mod 29) 13х + 1Oy = 0 (mod 29)
в) 9x + 2Oy = 0 (mod 29) г) 9x + 2Oy S 10 (mod 29) 16z + 13y = 0 (mod 29) 16x + 13y = 21 (mod 29)
д) 9x + 2Oy = 1 (mod 29) 16z + 13y = 2 (mod 29)
a)
48Ox +
971y
416 (mod 1111)
297z +
398y
=
319 (mod 1111)
6)
48Or +
971y
=
109 (mod 1111)
297x +
398y
=
906 (mod 1111)
в)
48Oz +
971y
=
0 (mod 1111)
297z +
398y
=
0 (mod 1111)
г)
48Ox +
971y
=
0 (mod 1111)
298z +
398y
0 (mod 1111)
д)
48Ox +
971y
=
648 (mod 1111)
298z +
398y
=
1004 (mod 1111)
6. Числа Фибоначчи определяются правилами f\ = 1, /2 = 1, /3 = 2, fn + i = fn + fn-l при и > 1, или, в эквивалентной форме, матричным уравнением
/п + 1 fn \ /1 1 fn fn-l) U 0
(см. упражнение 10 к §1.2). Используя определение в матричной форме, доказать, что fn четно тогда и только тогда, когда п делится на 3. Обобщить этот результат, доказав, что /„ делится на а тогда и только тогда, когда п делится на 6, при
§ 2. ШИФРУЮЩИЕ МАТРИЦЫ
87
следующих а и b: а) а = 2, 6 = 3; б) а = 3, b = 4; в) а = 5, 6 = 5; г) а = 7, 6 = 8; д) а = 8, 6 = 6; е) а = 11, b = 10.
7. Перехвачено сообщение «SONAFQCHMWPTVEVY», зашифрованное линейным отображением биграмм-векторов, причем известно, что отправитель использовал обычный 26-буквенный алфавит A-Z с числовыми эквивалентами 0-25 соответственно. Предварительный статистический анализ длинного отрезка перехваченного шифртекста показал, что самыми частыми биграммами в шифртексте являются «КН» и «XW» (в указанном порядке). Предположим, что эти биграммы отвечают биграммам «ТН» и «НЕ» соответственно, как самым частым биграм-мам в большинстве длинных открытых текстов, относящихся к предполагаемому предмету переписки. Найти дешифрующую матрицу и прочитать сообщение.
8. Перехвачено сообщение «ZRIXXYVBMNPO», зашифрованное линейным отображением биграмм-векторов при использовании 27-буквенного алфавита, причем буквы A-Z имеют числовые эквиваленты 0-25 соответственно, пробел = 26. Обнаружено, что чаще всего в шифртексте встречаются биграммы «PK» и «RZ». Предположим, что они отвечают самым частым биграммам 27-буквенного алфавита «Е » (E и пробел) и «S » соответственно. Найти дешифрующую матрицу и прочитать сообщение.
