Научная литература
booksshare.net -> Добавить материал -> Математика -> Коблиц Н. -> "Курс теории чисел и криптографии" -> 35

Курс теории чисел и криптографии - Коблиц Н.

Коблиц Н. Курс теории чисел и криптографии — Москва: Научное изд-во ТВП, 2001. — 254 c.
Скачать (прямая ссылка): theory-chisel-kriptographii.djvu
Предыдущая << 1 .. 29 30 31 32 33 34 < 35 > 36 37 38 39 40 41 .. 125 >> Следующая


729 = 437 + 292 437 = 292 + 145 292 = 2 • 145 + 2 145 = 72-2 +1

и затем

1 = 145 - 72 • 2 = 145 - 72(292 - 2 • 145) = 145 • 145 - 72 • 292 = 145(437 - 292) - 72•292 = 145-437 - 217-292 = 145-437 - 217(729 - 437) = 362 ¦ 437 (mod 729).

Итак, а = 362 • 142 = 374 (mod 729), и, следовательно, b' = 134 -675 • 374 = 647 (mod 729). Теперь применим преобразование дешифрования к биграммам «ND», «ХВ» и «НО» нашего сообщения (им соответствуют целые числа 354, 622 и 203 соответственно) и получим числа 365, 724 и 24. Записав 365 = 13 ¦ 27 + 14, 724 = 26 • 27 + 22, 24 = 0-27 + 2-1, мы соединим биграммы открытого текста в сообщение «NO WAY». Наконец, для нахождения ключа шифрования мы вычисляем а = а = 374 = 614 (mod 729) (снова используя алгоритм Евклида) и Ь = -а'~ V = -614 • 647 = 47 (mod 729).

Замечание. Хотя аффинные криптосистемы с биграммами (т.е. по модулю N ) лучше аналогичных однобуквенных систем (т.е. по модулю N), они также имеют недостатки. Заметим, что вторая буква каждой биграммы шифртекста зависит только от второй буквы биграммы открытого текста. Так получается из-за того^ что эта вторая буква определяется значением С = аР + b (mod N ) по модулю .V, а оно зависит только от P по модулю N, т.е. только от второй буквы биграммы открытого текста. Поэтому можно получить важную информацию (а именно, значения параметров а и & по модулю N) из частотного анализа четных букв шифртекста. Подобное замечание справедливо и для аффинных преобразований ^-буквенных блоков по

к

модулю TV .

70 ГЛ. III. КРИПТОГРАФИЯ

УПРАЖНЕНИЯ

1. В некоторых компьютерных сетях принято в том случае, если надо послать сообщение, которое может шокировать кого-либо (например, скабрезную шутку), шифровать буквы (но не пробелы или знаки препинания) применением преобразования С = P + 6 (mod 26). Тогда любой при желании сможет легко дешифровать текст, но никто не будет вынужден смотреть на сообщение, которое бьет по нервам. Используя частотный анализ для нахождения 6, дешифруйте заключительную фразу (она приводится на английском языке) в следующем анекдоте.

На международном конгрессе хирургов представители различных стран хвастались последними достижениями в области пересадки органов. Особенно гордились французы, американцы и русские. Французский хирург сказал: «Мы пришили оторванную ногу бегуну, а год спустя он принял участие в национальных соревнованиях по бегу на 1000 метров». «Используя новейшие достижения хирургии, — заявил русский хирург, — мы смогли пришить на место потерянную руку атлету, а через год он этой самой рукой установил мировой рекорд в толкании ядра». Но все они смущенно умолкли, когда американец, не желая отставать от других, объявил, что «Jr frjrq n fzvyr ba n ubefr'f nff', naq n lrne yngre vg jnf ryrpgrq Cerfvqrag!».

Примечание. В записи использован 26-буквенный алфавит, а пробелы и знаки препинания использованы для облегчения чтения.

2. Используя частотный метод, провести криптоанализ и дешифровать сообщение, зашифрованное применением преобразования сдвига букв 26-буквенного алфавита:

PXPXKXENYDRU XYTN LXHY MXGM AXYKX JN .YG\' RFX M AHWGX XW LEHGZX KY BIAX К M XQM

3. В 27-буквенном алфавите (пробел=26), используя аффинное шифрующее преобразование с ключом а = 13, 6 = 9, зашифровать сообщение «HELP ME».

4. В длинном отрезке шифртекста, полученного применением аффинного отображения букв 26-буквенного алфавита, чаще всех встречаются буквы «Y» и «Y» (в указанном порядке). Предполагая, что эти элементы шифртекста получены шифрованием букв «Е» и «Т» соответственно, прочитать сообщение «Q AOOYQQE YH EQV».

5. Вы анализируете аффинное шифрующее преобразование букв 37-буквенного алфавита, включающего в себя цифры 0-9, помеченные сами собой (т. е. целыми числами 0-9), буквы A-Z, имеющие числовые эквиваленты 10-35 соответственно, и пробел=36. Перехвачено сообщение «OH7F86BB46R36270266BB9» (здесь О обозначает букву, а не цифру). Вам известно, что открытый текст заканчивается подписью «007» (ноль-ноль-семь). Что это за сообщение?

6. Вы перехватили шифртекст «QFJDFOHFXOL», полученный применением аффинного преобразования букв 27-буквенного алфавита (пробел = 26). Вам известно, что первым словом является слово «I» (за / следует пробел!). Определить ключ шифрования и прочитать сообщение.

7. а) Сколько существует различных преобразований сдвига для yV-буквенного алфавита?

б) Найти формулу для числа различных аффинных шифрующих преобразований при W-OyKBeHHOM алфавите.

§ 1. НЕКОТОРЫЕ ПРОСТЫЕ КРИПТОСИСТЕМЫ

71

в) Сколько существует аффинных преобразований при N = 26, 27, 29, 30?

8. Говорят, что элемент P открытого текста неподвижен при данном шифрующем преобразовании /, если f(P) = P- Предположим, что используется аффинное шифрующее преобразование букв JV-букве иного алфавита. Будем считать также, что это отображение не является сдвигом, т.е. а ф 1.

а) Доказать, что если n — простое число, то всегда существует ровно одна неподвижная буква.

б) Доказать (для любого N), что если наше аффинное преобразование линейно, т.е. 6 = 0, то имеется, по крайней мере, одна неподвижная буква, и что если N четно, то линейное шифрующее преобразование имеет, по крайней мере, две неподвижных буквы.
Предыдущая << 1 .. 29 30 31 32 33 34 < 35 > 36 37 38 39 40 41 .. 125 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed