Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
9. Перехвачено сообщение «!IWGVIEXIZRADRYD», зашифрованное линейным шифрующим отображением биграмм-векторов при использовании 29-буквен-ного алфавита, причем буквы A-Z имеют числовые эквиваленты 0-25 соответственно, пробел = 26, ? = 27, ! = 28. Известно, что последние пять букв открытого текста — подпись отправителя «MARIA».
а) Найти дешифрующую матрицу и прочитать сообщение.
б) Найти шифрующую матрицу и, представившись другом Марии по имени Джо, зашифровать сообщение «DAMN FOG! JO».
10. В этом упражнении снова имеем дело с кириллицей (см. упражнение 12 предыдущего раздела). Мы используем 34-буквенный алфавит с традиционными числовыми эквивалентами для букв, пробел = 33. Предположим, что наиболее частыми биграммами в русском языке являются «НО» и «ET». Пусть известно, что в длинных отрезках шифртекста чаше всех встречаются биграммы «ЮТ» и «4M». Известно также, что шифрование производится линейным преобразованием биграмм-векторов для 34-буквенного алфавита. Прочитать перехваченное сообщение «СХНСЪШОНЩЗ».
11. Доказать, что композиция (см. упражнение 14 предыдущего раздела) криптосистемы с шифрующей матрицей А\ Є А/2 (Z/iVZ)* и криптосистемы с шифрующей матрицей Ai Є Ah(1ZfNZ)* также является криптосистемой с линейным шифрующим преобразованием.
12. Для того чтобы затруднить вскрытие криптосистемы, решено сначала зашифровать биграмму-вектор в 26-буквенном алфавите, используя матрицу
по модулю 26, а потом к результату применить матрицу
по модулю 29. (Заметим, что последовательное применение двух матриц по одному модулю, как показано в упражнении 11, эквивалентно применению одной матрицы,
88
ГЛ. III. КРИПТОГРАФИЯ
применение двух матриц по разным модулям дает более сложное преобразование.) Таким образом, открытый текст будет записан в 26-буквенном алфавите, а ши-фртекст — в 29-буквенном алфавите упражнения 9.
а) Зашифровать сообщение «SEND».
б) Описать, как производится дешифрование, и дешифровать сообщение «ZMOY».
13. Доказать, что если биграммы-векторы зашифровываются по формуле С = AP с необратимой матрицей .4 Є Ah(Z/NZ), то любой посланный шифртекст может быть дешифрован, по крайней мере, в два различных открытых текста.
14. Перехвачено сообщение «S GNLIKD7KOZQLLIOMKUL.VY» (пробел после S является частью сообщения). Предположим, что использовано линейное шифрующее преобразование С = AP в 30-буквенном алфавите, в котором A-Z имеют числовые эквиваленты 0-25, пробел = 26, . = 27, ,= 28, ? = 29. Известно также, что последние шесть букв открытого текста --- подпись KARLA и точка. Найти дешифрующую матрицу А~1 и весь открытый текст.
15. Перехвачено сообщение «КVW? TA!KJB?FVR». (Пробелы после ? и R входят в сообщение, а завершающая точка — нет). Известно, что использовано линейное шифрующее преобразование в 30-буквенном алфавите, в котором A-Z имеют числовые обозначения 0-25, пробел = 26, ? = 27, ! = 28, . = 29. Известно также, что первые шесть букв сообщения — это «С.I.A.». Найти дешифрующую матрицу Л-1 и весь открытый текст.
16. Предположим, что N = пт, где НОД (m, п) = 1. Любую матрицу .4 Є Mi(ZjNZ) можно вложить в Mi(ZJmZ) или Mi(ZJnZ) простым приведением элементов по модулю т или п. Пусть А и .4 обозначают соответствующие матрицы в M2(ZJmZ) или M2(ZJnZ).
а) Доказать, что отображение, сопоставляющее матрице А пару (А, А), является взаимно однозначным соответствием между Mi(Z/NZ) и множеством Ml(ZimZ) x Mi(ZinZ) всех пар матриц, одна из которых является матрицей по модулю т, а другая — по модулю п.
б) Доказать, что это отображение задает взаимно однозначное соответствие .между множеством Mi(Z/NZ)* обратимых матриц по модулю N и множеством M7(ZJmZ)* х M2(ZfnZ)*.
17. При простом р найти двумя разными способами число элементов множества Mi(ZipZ)* и убедиться в совпадении результатов:
а) подсчитать число решений в Fp уравнения ad — 6с = 0 и вычесть эту величину из числа элементов множества M2(ZJpZ);
б) любая А Є Mi(Z/pZ)* переводит векторы (J) и (°) в пару линейно независимых векторов, из которых первый — любой ненулевой вектор, а второй не пропорционален первому; подсчитать число вариантов.
18. Доказать, что матрица в Mi(Z/paZ) обратима тогда и только тогда, когда результат ее приведения по модулю р обратим в Mi(Z/pZ). Затем найти число элементов Mi(Z/pa Z)* .
19. Используя упражнения 16-18, найти формулу для числа элементов множества Mi(ZjNZ)*. Обозначим это число через ipi(N). Использовать формулу <p(N) = АгПр|п(1 — P-1) Для числа tfi(N) элементов множества (Z/ATZ)*. Записать формулу для <P2(N) в аналогичном виде. Сколько существует шифрующих 2 x 2-матриц при N = 26, 29, 30?
20. Пусть ^k(N) обозначает число обратимых к x fc-матриц с элементами из (ZjNZ). Угадайте формулу для tpk(N). Эту формулу нетрудно доказать методом упражнения 16 6).
§ 2. ШИФРУЮЩИЕ МАТРИЦЫ
89
Замечание. Прием, использованный в упражнениях 16-20, типичен для доказательств и вычислений в кольцах вычетов по модулю N. Сначала, исполь-з\я свойство мультипликативности, можно свести задачу к случаю, когда модуль является степенью простого числа. Затем при помощи процедуры «подъема» (другой пример этой процедуры см. в упражнении 20 к §11.2) задача приводится к случаю простого модуля. Теперь мы имеем дело с полем Fp. Работая в полях, можно в большей степени использовать геометрическую интуицию (как, например, в упражнении 17 6) выше). Все положения линейной алгебры, изученные нами в случае вещественных чисел, дословно переносятся на любое поле. Например, сравнение вида ах + by = с (mod р) может быть изображено как «прямая» в «плоскости» над полем Fp. Прямая, соответствующая второму сравнению, либо пересечется с первой прямой в единственной точке, либо будет параллельной первой прямой, либо совпадет с ней. В случае сравнений по составному модулю имеются и другие возможности, возникающие, когда определитель матрицы коэффициентов имеет нетривиальный общий множитель с N.
