Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
в) Привести пример (при некотором N) аффинного преобразования, не имеющего неподвижных букв.
9. Пусть элементами сообщения являются биграммы -буквенного алфавита. Найти формулу для числа различных аффинных шифрующих преобразований. Сколько их при N = 26, 27, 29, 30?
10. Перехвачено шифрованное сообщение «PWULPZTQAWHF», полученное применением аффинного отображения биграмм 26-буквенного алфавита, где, как и ранее, биграмме из букв с числовыми эквивалентами х и у соответствует целое число 26х + у. Статистический анализ предшествующих шифртекстов, полученных применением того же отображения, показал, что в шифртексте чаще всего встречаются биграммы «IX» и «TQ» (в указанном порядке). Известно, что наиболее часто встречающимися биграммами английского текста являются «ТН» и «НЕ» (в указанном порядке).
а) Найти ключ дешифрования и прочитать сообщение.
б) Вы решили захватить получателя сообщения, но так, чтобы отправитель не заподозрил неладное. Поэтому вы хотите выдать себя за сообщника отправителя и отвечаете «GOODWORK» («отлично»). Найти ключ шифрования и соответствующий шифртекст.
11. Вы перехватили сообщение «DXM SCE DCCUVGX », зашифрованное применением аффинного отображения биграмм 30-буквенного алфавита, в котором буквы A-Z имеют числовые эквиваленты 0-25, пробел= 26, ? = 27, ! = 28, ' = 29. Частотный анализ показывает, что в предыдущих шифртекстах чаще всех встречались биграммы «М », «U » и «Ш» (в указанном порядке). Допустим, что в английском языке (для данного алфавита) самыми частыми являются биграммы «Е », «S » и « Т» (в указанном порядке).
а) Определить ключ дешифрования и прочитать сообщение.
б) Найти ключ шифрования и зашифровать сообщение «YES ГМ JOKING!».
12. Описанные приемы, разумеется, можно использовать при любых алфавитах. Рассмотрим пример для русского алфавита. Используем следующие числовые эквиваленты для букв кириллицы
А
Б
В
Г
Д
E
Ё
Ж
3
и
й
0
1
2
3
4
5
6
7
8
9
10
К
Л
M
H
О
П
P
С
T
У
ф
11
12
13
14
15
16
17
18
19
20
21
X
Ц
ч
Ш
Щ
Ъ
Ы
Ь
Э
ю
Я
22
23
24
25
26
27
28
29
30
31
32
72
ГЛ. III. КРИПТОГРАФИЯ
Предположим, что перехвачено кодированное сообщение «ЦНТИ», зашифрованное применением аффинного отображения биграмм 33-буквенного русского алфавита. Частотный анализ предыдущих шифртекстов показал, что чаще всего в нем встречаются биграммы «ЦА» и «ЫТ» (в указанном порядке). Допустим, что двумя самыми часто встречающимися биграммами в русском языке являются «НО» и «ET» (в указанном порядке). Найти ключ дешифрования и выписать открытый текст сообщения.
13. Пусть, как и в упражнении 8, неподвижным элементом открытого текста называется элемент, не изменяющийся при данном шифрующем преобразовании. Найти все неподвижные биграммы для шифрующего преобразования примера 11.
1-1. Под композицией (или произведением) двух криптосистем понимается криптосистема, в которой открытый текст шифруется первой криптосистемой, а полученный шифртекст рассматривается как открытый текст для второй криптосистемы, т.е. шифруется еще раз с помощью второй криптосистемы. При более строгом изложении следует потребовать, чтобы множество Ci элементов шифртекста первой криптосистемы содержалось в множестве элементов открытого текста второй криптосистемы. Пусть /і и /г — шифрующие функции, тогда композиция криптосистем задается шифрующей функцией / = /г о f\. Если обозначить через / («intermediate text» — промежуточный текст) элемент шифртекста первой системы, а через 1 = Ci обозначить множество элементов промежуточного текста, то композицию криптосистем можно схематически изобразить диаграммой
Доказать, что:
а) композиция двух шифрующих преобразований сдвига также является шифрующим преобразованием сдвига;
б) композиция двух шифрующих линейных преобразований является шифрующим линейным преобразованием;
в) композиция двух аффинных шифрующих преобразований является аффинным шифрующим преобразованием.
15. Рассмотрим немного более сложную криптосистему, в которой открытый и шифрованный тексты записываются в разных алфавитах. Мы возьмем для открытого текста Л^-буквенный алфавит, а для шифртекста — М-буквенный, Л/ > N. Как обычно, мы рассматриваем биграммы в iV-буквенном алфавите как двузначные числа в системе счисления с основанием N1 т.е. как целые числа между 0 и N2 — 1. Аналогично, биграммы в М-буквенном алфавите рассматриваются как целые числа между 0 и M2 — 1. Теперь выберем любое целое L между Л'2 и M2: N2 $С L < M2. Выберем также целые числа а и Ь с НОД (a, L) = 1. Биграмма P открытого текста шифруется по правилу С = аР-\-Ъ (mod L) (где С — наименьший неотрицательный вычет по модулю L, удовлетворяющий этому сравнению). Здесь V — множество всех возможных биграмм P — состоит из всех целых чисел из диапазона от 0 до Л'2 — 1. Множество С всех возможных биграмм С шифртекста (т. е. биграмм в большем алфавите) составляет лишь часть множества всех целых из диапазона от 0 до M2 —1 и на самом деле представляет собой подмножество множества тех целых чисел, Меньших L, которые получаются применением шифрующего преобразования ко всем возможным биграммам открытого текста. Пусть открытый текст записан в 27-буквенном алфавите упражнения 3, а шифртекст — в 30-буквенном алфавите упражнения 11. Предположим, что L = 853. Предположим также, что самые часто встречающиеся биграммы открытого текста
