КулЛиб - Классная библиотека! Скачать книги бесплатно
Всего книг - 706150 томов
Объем библиотеки - 1347 Гб.
Всего авторов - 272776
Пользователей - 124656

Последние комментарии

Новое на форуме

Новое в блогах

Впечатления

a3flex про Невзоров: Искусство оскорблять (Публицистика)

Да, тварь редкостная.

Рейтинг: 0 ( 1 за, 1 против).
DXBCKT про Гончарова: Крылья Руси (Героическая фантастика)

Обычно я стараюсь никогда не «копировать» одних впечатлений сразу о нескольких томах, однако в отношении части четвертой (и пятой) это похоже единственно правильное решение))

По сути — что четвертая, что пятая часть, это некий «финал пьесы», в котором слелись как многочисленные дворцовые интриги (тайны, заговоры, перевороты и пр), так и вся «геополитика» в целом...

В остальном же — единственная возможная претензия (субъективная

  подробнее ...

Рейтинг: 0 ( 0 за, 0 против).
medicus про Федотов: Ну, привет, медведь! (Попаданцы)

По аннотации сложилось впечатление, что это очередная писанина про аристократа, написанная рукой дегенерата.

cit anno: "...офигевшая в край родня [...] не будь я барон Буровин!".

Барон. "Офигевшая" родня. Не охамевшая, не обнаглевшая, не осмелевшая, не распустившаяся... Они же там, поди, имения, фабрики и миллионы делят, а не полторашку "Жигулёвского" на кухне "хрущёвки". Но хочется, хочется глянуть внутрь, вдруг всё не так плохо.

Итак: главный

  подробнее ...

Рейтинг: 0 ( 0 за, 0 против).
Dima1988 про Турчинов: Казка про Добромола (Юмористическая проза)

А продовження буде ?

Рейтинг: -1 ( 0 за, 1 против).
Colourban про Невзоров: Искусство оскорблять (Публицистика)

Автор просто восхитительная гнида. Даже слушая перлы Валерии Ильиничны Новодворской я такой мерзости и представить не мог. И дело, естественно, не в том, как автор определяет Путина, это личное мнение автора, на которое он, безусловно, имеет право. Дело в том, какие миазмы автор выдаёт о своей родине, то есть стране, где он родился, вырос, получил образование и благополучно прожил всё своё сытое, но, как вдруг выясняется, абсолютно

  подробнее ...

Рейтинг: +2 ( 3 за, 1 против).

Введение в криптографию. Теоретико-числовые основы защиты информации [Елена Ивановна Деза] (pdf) читать онлайн

Книга в формате pdf! Изображения и текст могут не отображаться!


 [Настройки текста]  [Cбросить фильтры]

Tlgm: @it_boooks

По-настоящему безопасной можно считать лишь
систему, которая выключена, замурована в бетонный
корпус, заперта в помещении со свинцовыми стенами
и охраняется вооруженным караулом, однако и в этом
случае сомнения не оставят меня.
_
Ю. Спаффорд

14

то Г11
о Q

09 Ы

шш

*

ОСНОВЫ
ЗАЩИТЫ
ИНФОРМАЦИИ
Е. И. Деза, Л. В. Котова

1 ВВЕДЕНИЕ
В КРИПТОГРАФИЮ
е
г

Теоретико-числовые основы
защиты информации

5 я
2 - s
&9 U 5

Около 1 5 0 разобранных примеров

X

* s s
3 £2
ев

URSS

различного уровня сложности
по всем основным разделам криптографии
и соответствующим разделам
прикладной теории чисел
URSS

Tlgm: @it_boooks

Основы защиты информации • №1 4

Е. И. Деза, JI. В. Котова

ВВЕДЕНИЕ
В КРИПТОГРАФИЮ
Теоретико-числовые
основы
защиты информации
Издание стереотипное

URSS

МОСКВА

Tlgm: @it_boooks

ББК 22.176 22.18 32.811 32.97

Редактор серии М А. Борисов
Деза Елена Ивановна, Котова Лидия Владимировна
Введение в криптографию: Теоретико-числовые основы защиты информации.
Учебное пособие. Изд. стереотип. — М.: ЛЕНАНД, 2022. — 376 с. (Основы защиты
информации. № 14.)
Учебное пособие предназначено для изучения курсов «Методы и средства защиты информа­
ции», «Основы криптографии», других родственных дисциплин основных образовательных про­
грамм высшего образования, для изучения дисциплин по выбору, посвященных основам крипто­
графии и прикладным вопросам теории чисел. Пособие включает в себя теоретические факты,
упражнения и задачи различного уровня сложности по всем основным разделам криптографии
и соответствующим разделам прикладной теории чисел. Помимо обширного списка упражнений
и задач, в пособии представлены индивидуальные задания для проведения творческих и лабора­
торных работ, контрольные вопросы и типовые задания обязательного минимума по каждой теме.
Пособие составлено в соответствии с требованиями федеральных государственных образо­
вательных стандартов высшего образования и примерных основных образовательных программ
высшего образования. Книга написана на базе многолетнего опыта практической работы авторов,
ее материал построен по модульному принципу: выбор изучаемых разделов, порядок знакомства
с ними и глубина освоения соответствующих теоретических и практических вопросов зависят от
направления подготовки и профиля, в рамках которых проводится обучение.
Пособие предназначено для преподавателей и студентов высших учебных заведений, прежде
всего математических факультетов педвузов, учителей профильной школы, старшеклассников,
интересующихся прикладными теоретико-числовыми проблемами, всех, кого привлекают история
и современные тенденции развития криптографии. Материалы пособия могут быть полезны для
организации индивидуальной учебно-исследовательской работы студентов в рамках подготовки
курсовых работ, выпускных квалификационных работ бакалавра и магистерских диссертаций.
Рецензенты:
д-р физ.-мат. наук, проф. кафедры теоретической информатики
и дискретной математики МШ'У И. И. Баврин;
д-р физ.-мат. наук, проф. кафедры математического анализа МГУ
имени М. В. Ломоносова В. Г. Чирский
Печатается по реш ению ученого совета М осковского педагогического
государст венного университета
Формат 60x90/16. Печ. л. 23,5. Доп. тираж. Зак. № АР-9586.
Отпечатано в ООО «ЛЕНАНД». 117312, Москва, проспект 60-летия Октября, 11А, стр. 11.

ISBN 978-5-9710-7833-3
978-5-9519-2849-8

© ЛЕНАНД, 2017, 2021

НАУЧНАЯ И УЧЕБНАЯ ЛИТЕРАТУРА

E-mail: URSS@URSS.ru

32798 ID 282571

Каталог изданий в Интернете:

httpy/URSS.ru
Тел./факс (многоканальный):

URSSі

+ 7 (499) 724 25 45

Все права защищены. Никакая часть настоящей книги не может быть воспроизведена или передана в
какой бы то ни было форме и какими бы то ни было средствами, будь то электронные или механические,
включая фотокопирование и запись на магнитный носитель, а также размещение в Интернете, если на то
нет письменного разрешения владельца.

Tlgm: @it_boooks

Содержание

Обозначения......................................................................................................

8

Введение ...........................................................................................................

14

Глава 1. Из истории криптографии..............................................................

17

1.1. Исторические шифры.........................................................................
1.1.1. Простейшие подстановочные шифры
(шифры простой зам ен ы )......................................................
1.1.2. Полиалфавитные подстановочные ш ифры ...........................
1.1.3. Простейшие шифры перестановки........................................
Упражнения..............................................................................
Задачи......................................................................................
1.2. Криптоанализ классических ш и ф р о в ..............................................
1.2.1. Криптоанализ шифров перестановки...................................
1.2.2. Криптоанализ шифров простой замены................................
1.2.3. Криптоанализ полиалфавитных криптосистем......................
Упражнения..............................................................................
Задачи......................................................................................
1.3. Задачи криптографических олимпиад..............................................
Примеры решения задач........................................................
Задачи......................................................................................

17
18
23
27
33
36
41
41
42
45
50
54
61
61
66

Глава 2. Простейшие симметричные криптосистемы................................

74

2.1. Аффинные криптосистемы ..............................................................
Упражнения......................................................' ......................
Задачи......................................................................................
2.2. Криптоанализ аффинных криптосистем ........................................
Упражнения..............................................................................
Задачи......................................................................................

74
80
83
85

Глава 3. Шифрующие матрицы ...................................................................

94

88

90

3.1. Алгебра матриц и аффинные
матричные криптосистемы................................................................. 94
Упражнения..............................................................................104
Задачи...................................................................................... 107

Tlgm: @it_boooks

4

Содержание

3.2. Криптоанализ аффинных матричных криптосистем..................... 111
Упражнения..............................................................................116
Задачи......................................................................................118
Глава 4. Система RSA. Дискретный логарифм...........................................123
4.1. Система RSA и ее модификации..................................................... 123
4.1.1. Криптосистема без передачи кл ю ч ей ...................................125
4.1.2. Криптосистема с открытым ключом..................................... 128
4.1.3. Электронная подпись..............................................................130
Упражнения..............................................................................133
Задачи......................................................................................135
4.2. Дискретный логарифм......................................................................138
4.2.1. Показатели, первообразные корни и индексы..................... 138
4.2.2. Метод перебора......................................................................140
4.2.3. Метод согласования................................................................ 142
4.2.4. Метод Сильвестра—Полита—Хеллмана................................ 144
4.2.5. Алгоритм исчисления п орядка............................................. 148
Упражнения..............................................................................151
Задачи......................................................................................152
Глава 5. Вычислительные алгоритмы и их трудоемкость........................ 156
5.1. Трудоемкость арифметических действий........................................ 156
5.1.1. Системы счисления................................................................ 157
5.1.2. Символ «0»-большое..............................................................160
5.1.3. Анализ трудоемкости арифметических действий................ 161
5.1.4. Классификация алгоритмов по их трудоемкости................167
Упражнения..............................................................................169
Задачи......................................................................................173
5.2. Простейшие арифметические алгоритмы
и их трудоемкость..............................................................................175
5.2.1. Алгоритм Евклида...................................................................175
5.2.2. Расширенный алгоритм Евклида...........................................179
5.2.3. Бинарный алгоритм Евклида................................................ 180
5.2.4. Расширенный бинарный алгоритм........................................ 184
5.2.5. Решение неопределенных уравнений
первой степени........................................................................ 185
5.2.6. Алгоритм возведения в степень по модулю п ..................... 188
Упражнения..............................................................................191
Задачи......................................................................................193

Tlgm: @it_boooks

Содержание

5

Глава 6 . Простые и псевдопростые ч и сл а................................................... 195
6.1. Простые числа. Критерии простоты................................................ 195
Упражнения.............................................................................. 200
Задачи...................................................................................... 202
6.2. Вероятностные тесты простоты.
Псевдопростые числа.........................................................................204
6.2.1. Тест Ф ерм а.............................................................................. 205
6.2.2. Тест Соловея—Штрассена......................................................209
6.2.3. Тест Миллера—Рабина.......................................................... 212
Упражнения.............................................................................. 215
Задачи...................................................................................... 217
6.3. Детерминированные тесты простоты.
Генерация больших простых чисел................................................... 219
6.3.1. Проверка простоты с использованием числа п — 1 ............. 220
6.3.2. Проверка простоты с использованием числа п + 1 ..............222
6.3.3. Генерация простых чисел.........................................................226
Упражнения.............................................................................. 227
Задачи...................................................................................... 228
Глава 7. Факторизация натуральных ч и сел ................................................ 232
7.1. Классические методы факторизации................................................ 232
7.1.1. Метод пробного деления.........................................................233
7.1.2. Метод Ферма........................................................................... 234
Упражнения.............................................................................. 238
Задачи...................................................................................... 238
7.2. Современные методы факторизации.
Вскрытие системы R SA ......................................................................240
7.2.1. Метод Полларда—Флойда......................................................240
7.2.2. (Р - 1)-метод Полларда.........................................................242
7.2.3. Вскрытие системы R SA ........................................................... 244
Упражнения.............................................................................. 258
Задачи...................................................................................... 259
Глава 8 . Псевдослучайные последовательности
над конечным полем.........................................................................261
8.1. Поля и кольца классов вычетов.
Характеристика конечного п о л я ......................................................262
8.1.1. Кольца и поля. Примеры ......................................................262
8.1.2. Натуральные кратные элементов поля
и характеристика п о л я ........................................................... 265
8.1.3. Расширения конечного поля.
Существование конечного поля..............................................266

Tlgm: @it_boooks

6

Содержание

8.1.4. Мультипликативная группа конечного п о л я ........................ 268
Упражнения................................................ .............................270
Задачи......................................................................................271
8.2. Кольцо многочленов над полем F.
Построение конечного поля..............................................................273
8.2.1. Неприводимые над полем многочлены................................ 275
8.2.2. Сравнимость многочленов
........................................ 278
и построение конечного поля
8.2.3. Порядок многочлена над конечным полем...........................283
8.2.4. Примитивные многочлены над конечным полем ................ 284
Упражнения..............................................................................285
Задачи......................................................................................287
8.3. Линейные рекуррентные последовательности
над конечным п о л е м ........................................................................ 290
8.3.1. Псевдослучайные последовательности...................................290
8.3.2. Последовательности над конечным п олем ...........................292
8.3.3. Линейные рекуррентные последовательности..................... 293
8.3.4. Аннулирующие многочлены...................................................296
Упражнения..............................................................................299
Задачи......................................................................................301
Глава 9. Задания для организации промежуточного
и итогового кон трол я......................................................................303
9.1. Контрольные вопросы ......................................................................303
9.2. Типовые задания обязательного минимума
по основам криптографии................................................................ 305
9.3. Задания для творческих лабораторных работ
к разделу «Из истории криптографии» ...........................................312
9.3.1. Таблица Виженера................................................................... 312
9.3.2. Шифр по к н и г е ......................................................................313
9.3.3. Частотный анализ...................................................................313
9.3.4. Решетки Кардано...................................................................317
9.3.5. Двойная перестановка...........................................................318
9.4. Задания для лабораторных работ к разделу
«Простейшие симметричные криптосистемы.
Шифрующие матрицы»......................................................................318
9.4.1. Аффинные криптосистемы ...................................................318
9.4.2. Шифрующие матрицы...........................................................319
9.4.3. Содержание о тч ета................................................................ 320
9.5. Задания для лабораторных работ к разделу
«Система RSA. Дискретный логарифм»...........................................320

Tlgm: @it_boooks

Содержание

9.6.

9.7.

9.8.

9.9.

1

9.5.1. Система без передачи ключей................................................ 320
9.5.2. Система с открытым ключом................................................ 321
9.5.3. Электронная подпись..............................................................321
9.5.4. Дискретный логарифм........................................................... 322
9.5.5. Содержание о тч ета.................................................................322
Задания для лабораторных работ к разделу
«Вычислительные алгоритмы и их трудоемкость»...........................323
9.6.1. Алгоритм Евклида, его модификации
и их трудоемкость................................................................... 323
9.6.2. Применение алгоритма Евклида
к решению неопределенных уравнений первой степени . . . 323
9.6.3. Содержание о тч ета.................................................................325
Задания для лабораторных работ к разделу
«Простые и псевдопростые числа»................................................... 326
9.7.1. Простейшие алгоритмы проверки чисел на простоту...........326
9.7.2. Вероятностные алгоритмы проверки чисел на простоту . . . 326
9.7.3. Содержание о тч ета.................................................................327
Задания для лабораторных работ к разделу
«Факторизация натуральных чисел»................................................ 328
9.8.1. Классические методы факторизации......................................328
9.8.2. Методы факторизации Полларда........................................... 328
9.8.3. Содержание о тч ета.................................................................328
Задания для лабораторной работы к разделу
«Псевдослучайные последовательности
над конечным полем».........................................................................330
9.9.1. Содержание отч ета.................................................................330

Глава 10. Таблицы........................................................................................... 332
10.1. Таблицы числовых эквивалентов
символов русского и английского алфавитов................................... 332
10.2. Таблицы Виженера ........................................................................... 333
10.3. Таблицы частотности.........................................................................334
10.4. Таблицы простых чисел...................................................................... 338
10.5. Таблицы неприводимых и примитивных многочленов...................346
10.6. Таблицы индексов.................................................................'.............348
Ответы и реш ения........................................................................................... 355
Словарь терминов.............................................................................................. 359
Литература.........................................................................................................363

Tlgm: @it_boooks

Обозначения

► N = {1, 2, 3, ...} — множество натуральных чисел;
Z = { . . . , —3, —2, —1, 0, 1, 2, 3, ...} — множество целых чисел.
► rest (а, Ъ) — остаток отделения целого числа а на натуральное число Ь:
a = bq + rest(a, Ь), где q, rest(a, Ь) G Z, и 0 < rest(a, b) < Ь.
► 6|a — целое число b, отличное от нуля, делит целое число а, то есть
а = Ьс, где с G Z.
► (а ь . . . an) — наибольший общий делитель целых чисел а ь . . . , а п,
хотя бы одно из которых не равно нулю, то есть наибольшее целое
число, делящее каждое из чисел а ь • • ., ап.
► [а\, . . . ап\ — наименьшее общее кратное целых чисел а \, . .. , а п , каж­
дое из которых не равно нулю, то есть наименьшее натуральное число,
делящееся на каждое из чисел а\ , . . . , а п .
► Р — {2, 3, 5, 7, 11, 13, 17, 19, ...} — множество простых чисел, то есть
натуральных чисел, имеющих ровно два натуральных делителя; р , q,
Р\, • •
Яь • • •, Qt — простые числа; п = р "1 • р "2 • • • • * > гДе
Р\9Р2 , • • • >Ps — различные простые числа, и а\,
..., a s G N каноническое представление натурального числа п > 1, то есть пред­
ставление п в виде произведения натуральных степеней различных
простых чисел.
► Р п — п - ъ простое число: р \ = 2, р 2 = 3, рз — 5 и т.д.
► р = a • q + 1 (где р, q G Р , и q велико) — сильное простое число, то есть
достаточно большое простое число р, такое что р — 1 имеет большие
простые делители, например q (причем q — 1 также имеет большие
простые делители), и р + 1 имеет большие простые делители.

► п —рі • р 2 • . . . • ps (где Р\,Р 2 , • • ., ps — различные простые числа) —
бесквадратное число.
► S = {4, 6 , 8 , 9, 10, 12, 14,15, 16, 18, ...} — множество составных чисел,
то есть натуральных чисел, имеющих не менее трех натуральных де­
лителей; N — P U 5 U {1}.
► п = 2аі • Заз ♦ ... • psPs (где 2 , 3, . . . , ps — последовательные простые
числа, а 2 > «з > . . . > а!рз, и
= 1 кроме п — 4; 36) — сильно
составное число, то есть натуральное число, которое имеет больше
делителей, чем любое предшествующее ему натуральное число.

Tlgm: @it_boooks

9

Обозначения

► В = {р\9рг, • • • , p s} — база разложения, то есть множество, состоя­
щее из нескольких различных простых чисел; п — р“] • . . . • p f 3 (где
^ 0) — В-гладкое число, то есть натуральное число, все простые
делители которого принадлежат базе В.
► п = (afc_iafc_2 . . . a i a 0)5 (где к ^ 0 , 0 ^ а* <
и afc_i Ф 0 ) —
запись натурального числа п в системе счисления с основанием д, то
есть представление п — а^-\дк~х + а>к-гдк
~2 + •.. + «і * д + Ооі ао,
аі, . . . , a,k- 1 — д-ичные цифры числа п.
► [ж] — целая часть действительного числа х , то есть наибольшее целое
число, не превосходящее ж; [ж] — наименьшее целое число, большее
или равное х.
► (р(п) — функция Эйлера, дающая число натуральных чисел, не превосхо­
дящих п и взаимно простых с ним:
^ (п ) — \{х £ N : х ^ п, (х, п) = 1}| = п • Ц
tр\п
t

(\ - -

V

Р

► /х(п) — функция Мебиуса: /х(1) = 1, /х(п) = (—l)s для бесквадратного
числа п = рі • . . . • ps , и /х(п) = 0 в остальных случаях.
► sign(a;) — знак действительного числа х: sign(a;) — 1 при х > 0 ,
sign(a;) = —1 при х < 0 , и sign(a;) = 0 при х = 0 .
► іг(х) = X) 1 — число простых чисел, не превосходящих действитель­
на;

ное число х.
сумма (произведение) значений комплекснозначной функции f ( x ), определенной для всех х £ N, по всем нату­
ральным делителям d натурального числа п.
► f (n) = 0(д(п)) (где f 9g — комплекснозначные функции натурального
аргумента) — функция f (n ) есть О-большое от функции д(п), то есть
существует такая положительная действительная константа С и такое
натуральное число щ , что для любого п ^ щ имеет место неравенство
► а = b(m odn) — целые числа а и Ь сравнимы по модулю n , n £ N,
то есть а и b имеют одинаковые остатки при делении на п, или, что
то же, п\(а — Ь).
► а ^ Ъ(m odn) — целые числа а и Ъ несравнимы по модулю n , п £ N,
то есть а и Ъ имеют различные остатки при делении на п, или, что
то же, п \ (а — Ь).

Tlgm: @it_boooks

Обозначения

10

► а„ — { x € Z : x = a (mod n)} = { . .. , a - 2n, a - n, a, a + n, a + 2n, ...} —
класс вычетов (числа а) по модулю п, то есть множество всех целых
чисел, сравнимых с числом а по модулю п.
► a m odn — один из вычетов, принадлежащих классу вычетов ап;
как правило, наименьший неотрицательный (наименьший по моду­
лю, наименьший натуральный) вычет класса ап, то есть наименьшее
неотрицательное (наименьшее по модулю, наименьшее натуральное)
число, сравнимое с а по модулю п.


— символ Лежандра:

= 1, если целое число а, взаим­

но простое с нечетным простым числом р, является квадратичным
вычетом по модулю р (то есть сравнение х 2 = a (mod р) разреши­
мо), и

= —1, если целое число а, взаимно простое с нечет­

ным простым числом р , является квадратичным невычетом по моду­
лю р (то есть сравнение х 2 = a(m odp) неразрешимо); если а\р, то



для нечетного п = р*1 • . . . • pss — символ Якоби.

► Рп(а) — показатель целого числа а (взаимно простого с п) по мо­
дулю п, то есть наименьшее натуральное число 7 , такое что а1 =
= 1 (m odn); если Рп(д) = «СООБЩЕНИЕ»)
и шестой («ПЕРЕСТА» -> «ПЕРЕСТАНОВКИ») строкам среди оставшихся
столбцов, находим исходное состояние таблицы.
Ы в

А

Е

Т

С

я

В Е

Е

р

Е

С Т

А

н

О В

И

к

О

В Н

Е м

Н О

э

Т

О Т Ш И

Ф

р

Н А

р

Т

и

К

А

Л

Ь

н

А

к

А

Е

С

Л

и

С

т

О Л

Б

г

О С О

О

Б

Щ

Е

Н и

Е м

О Ж Н О П

р

О ч

Е

С

Т

ь

д

А

Ж

Е

Н

3

н

А

Я

П

Р

А

в

И

л

А П

Е

р

Е

С

Т

А

Н О В

к

И

С

Т

О Л

Б

Ц

О

т

А

Б

Л

И

цЫ

Б

3

Я П

Е

Таким образом, исходное сообщение имело вид «ЭТОТ Ш ИФР НАЗЫ­
ВАЕТСЯ ВЕРТИКАЛЬНАЯ ПЕРЕСТАНОВКА ЕСЛИ СТОЛБИКОВ НЕМНОГО
СООБЩ ЕНИЕ МОЖНО ПРОЧЕСТЬ ДАЖЕ НЕ ЗНАЯ ПРАВИЛА ПЕРЕСТА­
НОВКИ СТОЛБЦОВ ТАБЛИЦЫ».

Замечание. При использовании шифров-перестановок пробелы и знаки
препинания обычно опускаются. Важным является также не оставлять
в таблицах и решетках пустые клетки. Если число символов сообщения
меньше размерности приготовленных решеток, то после сообщения можно
записать по порядку буквы используемого алфавита. Это позволяет получа­
телю понять, что сообщение окончено и затрудняет взлом.
1.2.2. Криптоанализ шифров простой замены

Для вскрытия шифров простой замены применяют частотный ана­
лиз — один из методов криптоанализа, основывающийся на предположе­
нии о том, что частота появления заданной буквы алфавита в достаточно
длинных текстах одна и та же для разных текстов одного языка.
Метод частотного анализа известен с IX в. Его родоначальником счи­
тают арабского философа и математика Аль Кинди (Abu Yusuf Ya’qub
ibn ’Ishaq as-Sabbah al-Kindi, около 801 - около 873), который составил
сочинение «О дешифровке криптографических сообщений». Раздел, по­
священный шифрам замены, включающий в себя описание способа их

Tlgm: @it_boooks

1.2. Криптоанализ классических шифров

43

вскрытия, основанного на частотном анализе встречаемых в шифре сим­
волов, включен в арабскую энциклопедию XV в. Наиболее известным
случаем применения частотного анализа в реальной жизни является де­
шифровка египетских иероглифов Ж.-Ф. Шампольоном в 1822 г.
Для вскрытия шифра Цезаря по элементу шифротекста надо про­
сто вычислить величину сдвига и выполнить обратный сдвиг: данный
вид шифрования очень прост, но, к сожалению, не является надежным.
Так, в русском языке наиболее часто встречается буква О (11 %). По­
этому разумно предположить, что наиболее часто встречающаяся буква
в шифротексте на русском языке будет результатом шифрования буквы О,
и найти величину используемого в шифре сдвига простым вычитанием
друг из друга соответствующих числовых эквивалентов букв. Впрочем, да­
же если в нашем распоряжении имеется лишь небольшое послание, не да­
ющее нам определить чаще всего встречающуюся букву, то для величины
сдвига к имеется всего 33 возможности, и можно просто попробовать их
все. Лишь одному значению к будет соответствовать осмысленное сооб­
щение, такое к и будет ключом шифрования.
[Пример 1.2,11) Для вскрытия шифротекста «ЗДЙЧ ОТФТЕД РТПТОТ»,

полученного с помощью шифра Цезаря со сдвигом fc, достаточно заме­
тить, что чаще других в шифротексте встречается буква Т. Это означает,
что сдвиг к преобразует наиболее часто встречающуюся букву русского
алфавита О = 15 в Т — 19, то есть к — 4. Чтобы дешифровать сообщение
«ЗДЙЧОТФТЕДРТПТОТ», остается вычесть 4 (mod 33) из числовых экви­
валентов букв послания, получив исходное сообщение «ДАЕТ КОРОВА
МОЛОКО».

Для повышения стойкости шифра Цезаря используют ключевое слово
для смещения и изменения порядка символов в алфавите подстановки.
Ключевое слово (буквы которого не должны повторяться) записывается
под буквами алфавита, начиная с буквы, числовым эквивалентом которой
является некоторое число к. Буквы алфавита подстановки, не вошед­
шие в ключевое слово, записываются после него циклически в алфавит­
ном порядке.
Так, для русского алфавита таблица шифрования в случае шифра Це­
заря с ключевым словом «ЧИСЛО» и сдвигом к = 5 выглядит следующим
образом.
Исходный алфавит А Б В Г
Алфавит замены

Ы Ь Э Ю

Исходный алфавит Р С Т У
Алфавит замены

Ж 3

Й

К

ж 3 И й
Ч И с л О А
ф X Ц ч ш щъ
м н п р т У ф
Д
я

Е Ё

м
в г
ь э
Цш

К Л
Б
Ы
X

н о п
Д Е Ё
ю Я
щъ

Tlgm: @it_boooks

44

Глава 1. Из истории криптографии

Несомненным достоинством системы Цезаря с ключевым словом яв­
ляется то, что количество возможных ключей практически неисчерпаемо.
Это делает частотный анализ затруднительным, но все же возможным,
поэтому надежность этого метода тоже не очень высока.
Квадрат Полибия тоже кажется на первый взгляд очень нестойким.
Однако для его реальной оценки следует учитывать два фактора: воз­
можность заполнить квадрат Полибия буквами произвольно, а не только
строго по алфавиту, и возможность периодически заменять используе­
мые для шифрования квадраты. Тогда анализ предыдущих сообщений
ничего не дает, так как к моменту раскрытия шифра он может быть
заменен.
Буквы могут вписываться в таблицу в произвольном порядке — за­
полнение таблицы в этом случае и является ключом. Максимальное ко­
личество ключей для шифра на таблице английского алфавита равно 25!.
В данном случае мы имеем дело с комбинацией шифров замены и пе­
рестановки.
В принципе, для любых одноалфавитных шифров процесс частотного
анализа для достаточно больших текстов не представляет особой труд­
ности. Об этом свидетельствуют и множество примеров из классической
литературы (рассказы «Пляшущие человечки» А. Конан Дойла и «Золотой
жук» Э. По, роман «Дети капитана Гранта» Ж. Верна и др.), в которых
приведено подробное описание соответствующих алгоритмов.
[Пример 1.2,12) Попробуем расшифровать представленную ниже крип­

тограмму, полученную простой заменой букв русского алфавита на числа
1-32 (буквы Е и Ё не различаются).
12 2 24 5 3 21 6 29 28 2 20 18 20 21 5 10 27 17 2 11 2 16
19 2 27 5 8 29 12 31 22 2 16, 19 2 19 5 17 29 8 29 6 29 16:
8 2 19 19 29 10 19 29 14 19 29 29 19 10 2 24 2 11 2 16
10 14.18 21 17 2 20 2 28 29 16 21 29 28 6 29 16
Один из вариантов решения состоит из следующих этапов.
• Анализируя двухбуквенные сочетания цифр, приходим на основании
изучения второй строки к выводу, что 19 = Н (из соединений «19, 2»
и «19, 5»).
• На основании анализа третьей строки получим, что 29 = 0 (из «29, Н, 10»),
а 10 = А или 10 = И.
• Аналогичным образом заключаем, что 14 = Щ (из «но 14 но»).
• Далее, дешифруем 8 =Д, 2 = Е, 10 = И (из «денно и нощно»).

Tlgm: @it_boooks

1.2. Криптоанализ классических шифров

45

• Осуществив выделенные замены, получим следующий текст.
12 е 24 5 3 21 6 о 28 е 20 18 20 21 5 и 27 17 е 11 е 16
н е 27 5 д о 12 31 22 е 16, н е н 5 17 о д о 6 о 16:
д е н н о и н о щ н о они е24е11е16
и щ 18 21 17 е 20 е 28 о 16 21 о 28 6 о 16
Продолжим анализ.

• Из второй строки следует, что 5 = А и 27 = 3.
• Кроме того, 17 = В, 6 = П, 16 = Й (последнее слово второй строки —
«водопой»).
• Теперь мы получаем такой текст:
12 е 24 а 3 21 п о 28 е 20 18 20 21 а и з в е 11 е й
н е з а д о 12 31 22 е й , н е н а
водопой:
д е н н о и н о щ н о они е24е11ей
и щ 18 21 в е 20 е 28 о й 21 о 28 п о й.

• Нетрудно видеть, что 21 = Т, 18 = У, 28 = Л, 20 = С (из последней строки
«ищут веселой толпой»).
• Аналогично, 11 = Р (из «з в е 11 е й» первой строки).
• Итак, текст принимает такой вид:
1 2 е 2 4 а З т по л е с у с т а и з в е р е й
н е з а д о 12 31 22 ей, н е н а в о д о п о й :
д е н н о и н о щ н о о н и е 24 е р е й
ищут веселой толпой.

Теперь мы можем закончить нашу работу.
• 24 = Г (из «егерей»).
в 12 = Б, 3 = Ю (из «бегают»).
• 31 =Ы, 22 = 4 (из «добычей»).

Таким образом, мы получили следующее четверостишие В. С. Высоцкого.
«Бегают по лесу стаи зверей
Не за добычей, не на водопой:
Денно и нощно они егерей
Ищут веселой толпой.»



1.2.3. Криптоанализ полиалфавитных криптосистем

Для затруднения частотного анализа подстановочных шифров исполь­
зуют разные методы, заменяя монобуквенные системы шифрования одно­
звучными, полиграммными или полиалфавтиными, комбинируя различ­
ные виды шифрования и т. д.

Tlgm: @it_boooks

46

Глава 1. Из истории криптографии

Наиболее известными полиалфавитными шифрами являются шифр
Тритемиуса и таблица Виженера. Преимущество этих методов шифрова­
ния состоит в том, что статистические характеристики исходного текста
практически не проявляются в зашифрованном сообщении. Стойкость
такой криптосистемы определяется произведением стойкости прямой за­
мены на число используемых алфавитов, т. е. число букв в ключе. Одним
из недостатков шифрования является то, что при небольшой длине ключа
надежность шифрования остается невысокой, а формирование длинных
ключей сопряжено с трудностями.
[Пример 1.2.13| Используя шифр Тритемиуса для русского алфавита раз­

мерности 30 (без Й, Ё и Ъ), была получена шифрограмма «РБЬНПТСИТСРРЕЗОХ». Попробуем прочитать исходное сообщение, если извест­
но, что шифрующая последовательность не содержала никаких букв,
кроме А, Б, В.
Для этого каждую букву шифрованного сообщения расшифруем в трех
вариантах, предполагая последовательно, что соответствующая буква шиф­
рующей последовательности есть буква А, Б или В.
шифрованное
сообщение

Р

Б

ь н п т с и т с

вариант 1

П

А

щм

О

с

р

3

с

вариант 2

О

Я

ш л н

р

п ж

р

вариант

3

н Ю ч к м п О

Е

р

Е

О

X

п п Дж н
п О О г Е м

ф

р

р

3

У

п О н н в Дл т

Выбирая из каждой колонки полученной таблицы ровно по одной
букве, находим осмысленное сообщение «НАШКОРРЕСПОНДЕНТ», кото­
рое и является искомым.

Замечание. Из полученной таблицы можно было найти и такое исход­
ное сообщение, как «НАШ МОРОЗ ПОПОВ ЕМУ», которое представляется
не менее осмысленным, чем приведенное выше. А если предположить, что
при передаче шифрованного сообщения произошло одно искажение — скажем,
в качестве 11-й буквы была принята не буква Р, а буква П, — то, наряду
с правильным вариантом, можно получить и такой: «НАШ МОРОЗ ПОМОГ
ЕМУ». При этом число различных вариантов исходного сообщения, полученных
по нашей схеме, без ограничений на осмысленность равно З16 или 43 046721,
т. е. более 40 миллионов!

Tlgm: @it_boooks

1.2. Криптоанализ классических шифров

47

Несмотря на недостатки практической реализации, полиалфавитные
шифры оказались достаточно криптостойкими для своего времени. На­
пример, шифр Виженера не могли взломать на протяжении 400 лет. Од­
нако, в 1863 г. Фридрих Вильгельм Касиски (Friedrich Wilhelm Kasiski, 1805-1881), немецкий шифровальщик и археолог, опубликовал свой
труд «Тайнопись и искусство дешифрования», в котором описал свое
крупное открытие в криптоанализе: алгоритм, известный сегодня как
тест Касиски.
Этот алгоритм позволил взламывать полиалфавитные шифры, в част­
ности, шифр Виженера. Открытие Касиски уступает по важности только
работе Аль-Кинди, который открыл метод частотного анализа.
Метод Касиски позволяет криптоаналитику найти длину ключевого
слова, используемого в полиалфавитном шифре. Как только длина клю­
чевого слова обнаружена, криптоаналитик выстраивает зашифрованный
текст в п колонках, где п — длина ключевого слова. Тогда каждую колон­
ку можно рассматривать как зашифрованный моноалфавитным шифром
текст, который можно подвергнуть частотному анализу.
Идея метода Касиски основана на том, что ключи являются пери­
одическими, а в естественном языке существуют часто встречающиеся
буквосочетания: биграммы и триграммы. Это наводит на мысль, что
повторяющиеся наборы символов в шифротексте — повторения попу­
лярных биграмм и триграмм исходного текста. Криптоаналитик ищет
в зашифрованном тексте повторные сегменты по крайней мере из трех
символов. Если найдено два таких сегмента и расстояние между ни­
ми равно d , то криптоаналитик предполагает, что n\d , где п — дли­
на ключа. Если удается найти несколько повторных сегментов с рас­
стояниями d \ , d 2 , . . . , d m между ними, то будет выполняться соотноше­
ние n|(di, с?2, . . . , dm), т. е. наибольший общий делитель всех найденных
таким образом расстояний будет кратен предполагаемой длине ключе­
вого слова.
Сложность метода Касиски состоит в необходимости поиска повто­
ряющихся сегментов. Это практически невозможно сделать вручную, од­
нако не составляет особой сложности на компьютере. Тем не менее метод
требует вмешательства человека, так как некоторые совпадения могут ока­
заться случайными, что приведет к тому, что наибольший общий делитель
всех расстояний будет равен 1. Криптоаналитик должен выяснить, какие
длины являются подходящими и, в конечном итоге, проверить правиль­
ность подобранного периода, исходя из осмысленности расшифрованно­
го текста [128].

Tlgm: @it_boooks

48

Глава 1. Из истории криптографии

|Пример 1.2.14| Попробуем применить метод Касиски к зашифрованно­

му с помощью некоторого полиалфавитного шифра периода к сообщению,
представленному ниже.
«СЪСШ Щ ГЖ ИСЮ БЩ ЫРО ФЧ РЛЫОУУПЦЛЫ ЦЙУБЭЫ Ф СЮ ДЯ ЛКЧААЮЦЩЦХИЯ Б ХЙЕУЖ ШЩ ЧЙХК ЯПУЩА УОРЧЙ ЧЬЩ ЬЙЬЩУЙЙЧ Е ПЛЖЮС ЧАХОИ ЩЦ ЛЩ ДФ СНБЮ СЛ Щ ЙККЦЖЦЛЩ эйснш т щчыовхюди
ЗЗН ЛЪЯД ЛЕЖОН ЕЮ ЧЪЛМСРТЖ ЦЬВЖ ЛГСЗЙЬЧШ НФЧЗ ЧЮАЮЕ ЛЖЙКУАХЙНАИЕЬВ ЙЦЛ ККФЩ УЮИЙЧ 3 ЫДСЙВГЫХ СОЗЖ ЪНШ Ш О ЛЪЯД
ЦСЗНКЕШ ЛГЫХ ЦЩ ЗШ О ЦСПЛЛТП С ЧАХЙВЩ Ю Й Ц СЗХФ С КЗСАХЦЩ
С Й Ф Ф З Ш О ЛЪЯД РЛЬНГЫХЪЖ ДПХЛЕЗ НФЧГХЛ ШЙ ШУЩ ЮОЕЛХЧУЛУ Щ КЯЙЛЩ НКЫЭА ЕЧРЮ ЗЫГЧЖ ФЖ ЩЦ ЧРШЙЛЩМ ДЛВОЖ ЫРО кйяЛЫОЖЧЖФПШЙЪНХ ХЙЕЩЖ С Ъ СШ СЬЛРНГ Ш ПРТЗПЗН ЧЕЧУЦЖЪЕЩУС
РЫСОНШ Й ЩЩТЖЛТЕЗ СЪСПХЛ СПРЬЛЕСЧШ ЙЪНХЩ ЪЙУЖЫЬЛ ЯЧВАЕЧИ Щ РЩ Т ОЕФЖ ЫХЪЖ ДХЩ Щ Щ ХОВХЮ ДФ Щ РЩ Т Щ ЗМ УВ ЫЩГЕПЫЛЖПЯЛЩ Е Ш УБЭЫЛЯЖ ЛЩ ДФ СНБЮ СЖ ШПБВЩ КЛЩА УОРЧЙ С ЛЪ­
ЯД Р Ю ЯЙЭЩ ИЙЯЩ ЭЧНЛЯДФ ДЙРЧБЩ ЫРО ЫФЖ НЖЫФМ ЕРУЛКФТЕЗ
У ЬЩУ ЧНШЙЪЖЧКИ ЧЩ Ы Й ЕЧЗАФ ДЭСФ Ю ЙНЭЩ СЦТА 3 СЪ СШ РГФПЛТ
3 ЙЪЬЛЕО ЛР ИОСЩ Х АФЧЭЧ ЩЮ ЯОЧАИОЬШ ЙО ЦСЙМУБУХЬЛЖ ЪЩНЖ Щ СБЮ СФ НЗНГЯХСЮ АКУЛА ЬЙЧБМС Л ГЖ ФФШ ПШ УБЕФФШ Ю ЧФ ЛЪЬЮ АЮ СФ НИИ ДЛЯЧЫЛ ЙЩ ЪБЮ СОЛЕЙЫ иЙТ СЩЬЦЛ НЖЫФМ Е НФЧКУЩЕ КЙЧК ЮОЩФЦЧЧЩУЧ УБЬЦЩ ЛЪЩ ГЖ ЗО ЛЪЯ ЫГЯ ЭЙЕ ЧЙФПЯЙ
ШУЩ ОЫЛР АЪВЛЕСЖ Р ЪЬЧАХ ЧААКШ ФЦЖЦГ НЖЫЖЕ ЕЧОЕЙПЬЛКЫП
Щ Ю ЫФСЖ ЪЬЛТ С РЛЫОУУПЫФТГЦЩМ ЫОЖЧЖ ФПШ ЙЪНЩ УЦЩ ЪЙЧАСПРЛА ХСЦЛЕ ЛЛНЙЛ ЗЛЯХ ЛЪЯ ЦФЩ ЬКФУЮ Ч ЕБЭ ЦФЩ ЬКФУЮ Ч ЯШЙМЩ ЛЪЩ ГЖЗО СЩ ЬЦЛ ЯЙЫ Щ САЗ Щ ШЗ ЧНСППГЫ ХУГЯ ЮОЛЖЪОСШЙ хьЛРЧЩ ФЯЙОЩ Ж ЦФДУЧНСД ЦГ ЗЮ ОЫШ Щ З РРЙ П Ф Д ХЕ ЛЪЯ ЧЧШЙМЩ
ЧЗШГ ЕЙНФТЗ.»

Поиск повторяющихся сегментов текста из трех букв дает такие ре­
зультаты.
• Группа «СЪС» встречается в позициях 1, 373, 417, 613. Соответствую­
щие расстояния равны
d\ = 373 — 1 = 372 = 4 -3 -3 1 ,
d 2 = 417 - 373 = 4 4 = 4-11,
d3 = 6 1 3 - 4 1 7 = 196 = 4-49.
Поскольку (d\, dj, d3) = 4, то предполагаем, что период к вскрывае­
мого полиалфавитного шифра делит 4.

Tlgm: @it_boooks

1.2. Криптоанализ классических шифров

49

• Группа «ЩГЖ» встречается в позициях 5, 781, 941. Соответствующие
расстояния равны
di — 781 —5 = 776 = 8-97,
d2 = 941 - 781 - 160 - 32-5.
Поскольку (d\9d2) — 8 , можно предположить, что период шифра делит
8. Это не противоречит выводу для предыдущей группы.
• Группа «ЫРО» встречается в позициях 13, 349, 557. Соответствующие
расстояния равны
d\ = 349 — 13 = 336 = 16- 3- 7,
d2 = 557 - 349 = 208 = 16-13.
Следовательно, (di, d2) = 16, что позволяет предполагать, что период
шифра делит 16. Это тоже не противоречит предыдущим результатам.
Таким образом, на основе проведенного теста Касиски можно сделать
правдоподобное предположение: период вскрываемого полиалфавитного
шифра равен 4.
Теперь, подвергая текст частотному анализу, нетрудно получить клю­
чевое слово «ЙГБП» и прочитать исходное сообщение:
«Игры различаются по содержанию характерным особенностям а также по то­
му какое место они занимают в жизни детей их воспитании и обучении Каждый
отдельный вид игры имеет многочисленные варианты Дети очень изобретательны
Они усложняют и упрощают известные игры придумывают новые правила и дета­
ли Например сюжетно-ролевые игры создаются самими детьми но при некотором
руководстве воспитателя Их основой является самодеятельность Такие игры иногда
называют творческими сюжетно-ролевыми играми Разновидностью сюжетно-роле­
вой игры являются строительные игры и игры драматизации В практике воспитания
нашли свое место и игры с правилами которые создаются для детей взрослыми
К ним относятся дидактические подвижные и игры забавы В основе их лежит четко
определенное программное содержание дидактические задачи и целенаправленное
обучение. Для хорошо организованной жизни детей в детском саду необходимо раз­
нообразие игр так как только при этих условиях будет обеспечена детям возможность
интересной и содержательной деятельности Многообразие типов видов форм игр не­
избежно как неизбежно многообразие жизни которую они отражают как неизбежно
многообразие несмотря на внешнюю схожесть игр одного типа модели».



Метод Касиски окажется бесполезным, если при работе полиалфа­
витного шифра будет использовано ключевое слово бесконечной длины.
Реализацией данной идеи является шифр Бернама (одноразовый шифроваль­
ный блокнот) — единственная система шифрования, для которой доказана
абсолютная криптографическая стойкость.

Tlgm: @it_boooks

Глава 1. Из истории криптографии

50

Шифр назван в честь американского инженера по телекоммуника­
циям Гильберта Вернама (Gilbert Sandford Vemam, 1890-1960), который
в 1917 г. построил телеграфный аппарат, выполнявший соответствующую
операцию шифрования автоматически — надо было только подать на него
ленту с ключом. Ключ, по мысли Вернама, должен был представлять со­
бой случайную последовательность букв. В 1945 г. американский ученый
и инжинер Клод Шеннон (Claude Elwood Shannon, 1916-2001) доказал
абсолютную стойкость шифра Вернама: перехват шифротекста не дает
никакой информации о сообщении и, с точки зрения криптографии, не­
возможно придумать более безопасную криптографическую систему.
Недостатком шифра Вернама является отсутствие подтверждения под­
линности и целостности сообщения. Шифр Вернама чувствителен к лю­
бому нарушению процедуры шифрования. Кроме того, под рукой всегда
необходимо иметь достаточное количество ключей, которые могут по­
надобиться в дальнейшем для шифрования больших объемов открытого
текста. Проблемой является защищенная передача последовательности
и сохранение ее в тайне. На практике можно один раз физически пе­
редать носитель информации с длинным истинно случайным ключом,
а потом по мере необходимости пересылать сообщения. На этом осно­
вана идея шифроблокнотов: шифровальщик по дипломатической почте
или при личной встрече снабжается блокнотом, каждая страница которо­
го содержит ключи. Такой же блокнот есть и у принимающей стороны.
Использованные страницы уничтожают [78].
Наконец, для работы шифра Вернама необходима истинно случайная
последовательность, а, по определению, последовательность, полученная
с использованием любого алгоритма, является не истинно случайной,
а псевдослучайной (см. главу 8).
В настоящее время шифрование Вернама используется достаточно
редко. Это связано с тем, что современные методы криптографии развиты
достаточно хорошо для того, чтобы удовлетворять потребностям поль­
зователей. Однако с развитием технологий и с увеличением доступных
компьютерных мощностей растет и вероятность успешной атаки. Совре­
менные носители данных могут хранить огромное количество случайных
ключей, а современные генераторы случайных чисел позволяют произво­
дить случайные ключи достаточного для использования в шифре Вернама
качества. Все это повышает актуальность использования современных мо­
дификаций этого криптографического метода.
Упражнения

( I ) Сообщение было зашифровано с помощью шифра простой переста­
новки столбцов. Найдите исходное сообщение, если известно число

Tlgm: @it_boooks

1.2. Криптоанализ классических шифров

51

строк m и число столбцов п использованной для шифрования
таблицы:
a) «ДНТНВОСЕАГЕШРОНАПЕЬР», m = 4 ,n = 5;
b) «ДЛТЕОЕВВШДЕЯЕНЛИЬЕМВП», m = 3 ,n = 7;
c) «ВЙГШАОСОИУАЕДНЯТШАМСПАМСИСТАЙЧИРЛАТ», т = 5, п = 7 .
(2) Сообщение было зашифровано с помощью шифра постолбцовая транс­
позиция. Пробелы в сообщении были опущены, а знаки препинания
заменены на условные комбинации: точка — «ТЧК», запятая — «ЗПТ».
Прочтите исходное сообщение, если после шифрования оно выглядело
так, как показано в таблице.
Я

н

л

в

й

л

т

А л

ч

р

Д ч и

н

У л А

ы т Д О
и К с И

К

О

Е

т

Р

г

о

м

и

Ф Ы и

П

Е

У И О

о

г

Е

Е

С м

О Н

Д

и н

т

Д Б о Р
и к Е О

Р

Е

Р

Е

А

Д

Б Ы Ы Е

Е М П П Т
— т

Щ

Е

К X

3

я

Е

3 и О н н ы ч Д
н и п т я 3 с л

Е

В А

Ч Н О — — Е — л

У л

-

т

-

ж

(з ) Сообщение было зашифровано с помощью решетки Кардано. Про­
чтите исходное сообщение, если после шифрования оно приняло ни­
жеследующий вид.
р

п

т

Е

ш

А

в

Е

с

л

О

я

т

А

л



ь

3

т

-

-

У

к

Т

-

Я

А

ь



н

п



Ь

Е

У

-

ш

л

т

и

ь

3

Ы

я

Е

м



с
с
о

-

Е

ф





р

О



с

м

(3) При шифровании текста на русском языке каждую букву заменяют
парой цифр, опуская пробелы и знаки препинания. При этом разные
буквы текста заменяются разными парами цифр, а одинаковые —
одинаковыми. Найдите все возможные расположения слова «РАБОТА»
в исходном тексте по шифрованному тексту.
15 17 16 72 17 15 70 73 97 90 17 72 38 39 74 76 17 34 79 78 17 70 76 74
72 74 73 74 76 70 70 17 76 74 96 74 37 39 75 17 70 39 74 79 39 37 71 74
98 35 94 90 98 17 94 96 74 98 74 7617

Tlgm: @it_boooks

52

Глава 1. Из истории криптографии

(? ) Шифрование сообщения состоит в замене букв известного текста
на русском языке на пары цифр в соответствии с некоторой табли­
цей, в которой разным буквам алфавита соответствуют разные пары
цифр. В каком случае будет легче восстановить текст: если известно,
что первое слово второй строки — «ПРАКТИКА»; если известно, что
первое слово пятой строки — «СЕМИНАР»?
(б) Для шифрования открытого текста каждую букву заменяют парой
цифр, при этом разные буквы текста заменяются разными пара­
ми цифр, а одинаковые — одинаковыми. Даны два зашифрованных
текста.
a) 79 15 38 98 95 91 34 95 73 77 96 15 78 95 73 98 1596 15 72 98 96 77
72 15 34 77 96 75 90 76 95 38 98 15 70 33 90 96 79 90 96 77 98 95
90 38 77 70 70 90 98 74 15 96 98 96 77 72 15 34 77 96 75 73 77 96
15 98 74 15 79 96 90 79 15 96 98 94 90 76 98 74 15 95 96 96 15 73
79 15 33 98 95 32 15 90 93 38 15 96 73 94 90 91 96 91 73 15 98 74
95 73 33 72 96 90 34 95 73 73 91 36 71 15 33 98 98 90 77 38 15 38
72 91 73 15 96 70 95 33 15 38 33 15;
b)

71 75 74 39 74 73 74 72 30 73 74 78 33 79 98 94 78 36 79 97 72 29 78 74
96 74 92 30 38 79 70 72 94 78 79 22 92 92 79 98 37 70 92 74 94 77 74
93 31 78 74 70 39 79 71 75 94 98 70 39 97 92 72 22 23 39 78 94 70 74 76
78 94 78 78 30 77 39 94 74 75 94 39 79 38 94 70 73 79 77 79 78 39 94
75 94 70 73 75 74 76 94 39 74 96 74 76 78 74 96 79 94 39 79 71 30 27 39
79 32 71 75 74 39 74 73 74 72 74 92 71 75 94 98 35 22 92 72 22 23 39.

Известно, что один из них соответствует сообщению на русском язы­
ке, а другой — на английском (пробелы и знаки препинания опуще­
ны). Определите, какой шифрованный текст соответствует сообщению
на русском языке.
( j ) Зная, что сообщение зашифровано с помощью шифра Цезаря, найдите
величину к примененного сдвига и расшифруйте сообщение:
a) «ФОЫИЫШОЩОФОЫДЦОШЬСАД»;
b)

«ТИМСЖУТПЙСЙЖТМС»;

c) «БШЬАШЭЕЖВЧДЗЫШЭУЬАШЭЕЖВДЗФЯШЭ».
(§) Перехвачена криптограмма, которая была получена при использова­
нии шифра Тритемиуса для русского алфавита размерности 30 (без
Й, Ё и Ъ). Попробуйте прочитать исходное сообщение, если шифротекст имеет вид «ФФЧСЙИФНЧЧИНЩЩЩЧФРСИЩД» и известны
буквы, формирующие ключ: Ж, 3, И.

Tlgm: @it_boooks

1.2. Криптоанализ классических шифров

53

(5) Используя частотный анализ букв русского языка, вскройте сообще­
ние (стихотворение Р. Киплинга), если известно, что различным бук­
вам соответствуют различные двузначные числа. Знаки препинания
сохранены для удобства вскрытия.
29 15 10 17 29 22 25 31 15 33 35 41 43 45 35 57 45 25 17 59 15 10 25 41
25 69, 59 78 29 82 25 78 25 17 15 10 88 90 78 25 62 25 22 10 57 73 79
35 67 78 90 88 29 45 35 29, 54 57 90 31 90 73 22 88 15 88 29 15 17 69 41
25 15, 70 17 90 57 43 59 15 78 15 62 22 25 17 57 25 69 88 15 82 17 25 88
29 45 35
(Й) Криптограмма получена при использовании шифра простой замены
букв 32-буквеного русского алфавита (буквы Е и Ё идентифицирова­
ны). Используя метод частотного анализа, прочтите четверостишия:
a) «Гьюь Фюббшн эй яюэовл,

b)

©

с) «Щм умэс яи сс щс нарф,

Пфзшэюь юришь эй шчьйфшвл:

Щм умэс ыдм ючмрць ямц юыфя;

Г эйщ юбюрйээо бвпвл —

Аяэь риефя а щсх щм пэарф,

С Фюббшн ьюцэю вюылъю сйфшвл.»

Лэць ыиеся щм лшцмв чмщэя.»

«Йхпм кмлся цйег тердсйц

d) «Исжжу спзы обе збслпк ойгпк,

Сй уйыдпяхг, ей хйфимхя!

Й пу ойгэ й еп ойгэ

Ж ийся чсасмг хрмфмхя:

Дпойу гжужс рейцпумйгэк

Ийся жйхйпяг, жйфя, едхищейц.»

Ипмпуэж ржежмйгэ.»

Задан некоторый текст, зашифрованный шифром Виженера. Опреде­
лите ключевое слово и прочитайте текст:
Влцдутжбюцхъяррмшбрхцэооэцгбрьцмйфктъъюьмшэсяцпунуящэйтаьэдк
цибрьцгбрпачкъуцпъбьеэгкцъгуущарцеэвърюуоюэкааэбрняфукабъарпяъ
афкъиьжяффнйояфывбнэнфуюгбрьешьжэтбэечюъюръегофкбьчябашвеэу
ъъюаднчжчужцеэвлрнчулбюпцуруньъшсэюъзкцхъяррнрювяспэмасчкпэужь
жыатуфуярюравртубурьпэщлафоуфбюацмнубсюкйтаьэдйюнооэгюожбгкб
рънцэпотчмеодзцвбцшщвидепчдчдръюьскасэгъппэгюкдойрсрэвоопчщшо
казръббнэугнялекьсрбеуыэбдэулбюасшоуэтъшкрсдугэфлбубуъчнчтртпэг
юкиугюэмэгюккъъпэгяапуфуэзьрадзьжчюрмфцхраююанчечюъыхьъцомэф
ъцпоирькнщпэтэузуябащущбаыэйчдфрпэцъьрьцъцпоилуфэдцойэдятррач
кубуфнйтаьэдкцкрннцюабугюуубурьпйюэъжтгюркующоъуфъэгясуоичщщч
дцефырэдщэъуяфшечцюйрщвяхвмкршрпгюопэуцчйтаьэдкцибрьцыяжтюр
буэтэбдуящэубъибрювъежагибрбагбрымпуноцшяжцечкфодщоъчжшйуъц
хчщвуэбдлдъэгясуахзцэбдэулькнъщбжяцэьредъьвювлрнуяфуоухфекьгцч
ччгэъжтанопчынажпачкъуъмэнкйрэфщэъьбудэндадъярьеюэлэтчоубъцэф
эвлнеэгфдеэвэекбечоукгаутэыпуббцчкпэгючеаъбэнэфъркацхеваетуфяепь
рювържадфежбьфутощоявьъгупчршуитеачйчирамчюфчоуяюонкяжыкгецб
рясшчйотъъжрсщчл.

Tlgm: @it_boooks

Глава 1. Из истории криптографии

54

Задачи

[Tj Известно, что каждому из трех шифрованных текстов
«ЙМЫВОТСЬЛКЪГВЦАЯЯ»,«УКМАПОЧСРКЩВЗАХ»,«ШМФЭОГЧСЙЪКФЬВЫЕАКК»

соответствовало исходное сообщение «МОСКВА». Расшифруйте три
текста
«ПЕОИРВНТМОЛАРГЕИАНВИЛЕДНМТААГТДЫКУБЧКГЕИШНЕИАЯРЯ»,
«ЛСИЕМГОРТКРОМИТВАВКНОПКРАСЕОГНАЬЕП»,
«РТПАИОМВСВТИЕОБПРОЕННИГЬКЕЕАМТАЛВТДЬСОУМЧШСЕОНШЬИАЯК»

при условии, что двум из них соответствует одно и тоже сообщение.
[2] Расшифруйте фразу, зашифрованную постолбцовой транспозицией,
если символ ^ используется как знак пробела:
a) «-ОНКА-БНЫЕЦВЛЕ-К-ТГОАНЕИР»;
b) «НЗМАЕЕАА-Г-НОТВОССОТЬЯАЛС»;
c) «РППОЕААДТВЛ-ЕБЬЛНЫЕ-ПА-ВР»;
d) «ОПЗДЕП-ИХРДОТ-И-ВРИТЧ-САА»;
e) «ВКЫОСИРЙУ-ОЬВНЕ-СОАПНИОТС».
[3] Расшифруйте фразу, зашифрованную двойной перестановкой (сначала
были переставлены столбцы, затем строки), если символ ^ использу­
ется как знак пробела:
a) «-ЙЕСТОВО-НИИНЛАЕТИЖДСОПВ-»;
b) «НДИАЕОЫЛПНЕ- -НВЕАНГТ-ИЗЛА»;
c) «П-БИРДЛЬНЕВ-ОП-ОПЗДЕВЫГЕА»;
d) «МДООИТЕЬ-СМТ-НАДТЕСУБЕХНО»;
e) «АИНАЛЖНОЛЕШФ-ЗИ-УАРОЬСНЕ-».
[4І Шифр Bid , имеющий простое правило шифрования, использует в ка­
честве ключа квадратную таблицу, в которую в некотором порядке
записаны буквы английского алфавита (буквы I и J отождествлены).
С

О

D

Е

А

в

F

G

Н

I

к

L

М

N

Р

Q

R

S

Т

и

V

W

X

Y

Z

Результатом шифрования фразы «SIXTY EIGHT MILES» на приведенном
ключе является фраза «RYXXT OFTXT LKSWS». Зашифруйте на том же
ключе фразу «ENTER OTHER LEVEL».

Tlgm: @it_boooks

55

1.2. Криптоанализ классических шифров

[5] Получателю было отправлено три письма. В первом письме содержал­
ся листочек с квадратной таблицей (а).

э
р
в
А

р
А

п

я т
Е
т ы
в О ш
и т Е
О т т
я н

А

О
ш
р
к
н

3
О

0

X

X

X

0

X

X

0

X

0

X

X

Е

X

X

X

X

0

X

Ф

X

X

0

X

X

0

С

0

X

X

X

X

X

А

X

X

X

0

X

X

В третьем — листочек с таблицей (Ь). Второе письмо, содержащее
пояснения по использованию этих таблиц, потерялось. Помогите по­
лучателю прочитать зашифрованное сообщение.
[б] Для зашифровывания текста шифром поворотная решетка из бумаж­
ного квадрата размером 8 x 8 клеток изготовили трафарет. Первые
16 букв текста сообщения вписали в прорези трафарета (по одной
в каждую), потом трафарет повернули на 90 градусов и вписали сле­
дующие 16 букв и т.д. Для повышения сложности шифра процедуру
шифрования провели дважды. Найдите текст исходного сообщения
по шифрованному тексту.
А

Л

А

п

А

л

Н

Р

И

Е

ь

и

Р

Е

Е

Ы П ы

О

С Н

Л

X

А

Ы Н Ф и

В

3

ц

И

н

С

О

А

ш

О Н Ф Ю 3

Е

Л

и

К И Н

И

Е

Е

Н

О

О

п

Т

X

ь

и

Н

И

Т

Р

Г

ь

р

Д

г

ц

Ж

Д

У

О

Е

Н

Д
м

Н

Е

Р

Е

Ф й

и

к

п

н

А

и

ь

О И

Й

ф

Е

Ю ц
Н р

А

О Й

В

А

Р

А

Э

Р

Л

Л

А

ь

л

А

В

Е

О Ж Н

И

т

и

с

ж

Н

О Л

и

X

р

Е

Д
и

А

т

Е

И

Л

я

о

т

Л

О А

Б

с

ь

Л

Р

Е

с

А

А

к

Й

ы

О О

3

И

У ю

р

А

Й

Е

Б

X

Л

Е

Р

т

3

О

Т

Ы

я

и

С

О

Ш

В

Г

Ы

Ь

П

с

О

О

м

Ж

Л

В

О

т

3

Л

ь

О

Е

Е

И

м

А

р

н

Д Д

И Е

Т

Л

X

d)

и

в

и

С

К

я

и

ч

И

и

с

В

3

Б

Ы с

и

р

К

ю

Е

м

ь

Е

В

С

Б

т

с

Р

Г

р

ы

Д

в

П

А

с

X

К

Т

Д

Д

Tlgm: @it_boooks

Глава 1. Из истории криптографии

56

И

Ь

М н

О

т
ж
Д Д
У с с в Д
ж О О Д в
п ы т я т
У О п ж т
Е Е О о К
и

В

О

С

В

ж

А

Е

Е

Л

Ь

В

3

Е

И

м

р

X

К

Ы А Ф Н

А

С

К

Е

н

Е

Н

К

С Т

А

Т

С

Ч

Л

м

И

Р

Ы С

Ь

Я

Е

Т

У

Д

Е

Т

И

Н

р

И

ч

Ю Н

С

Е

3

О С

Е

А

О Б

А

П

О Ш Ы

н

С

ч

Н

Т

Е

А

Е

Р

Е

А

я

Я

О

А

Я

О

О

И

Л

Т

Т

[У] Для использования шифра прямоугольная решетка был изготовлен тра­
фарет размером 6 x 1 0 клеток. При наложении трафарета на лист бу­
маги того же размера вписали первые 15 букв текста сообщения в
прорези трафарета (по одной в каждую), потом трафарет повернули
на 180 градусов и вписали следующие 15 букв, после чего трафарет
перевернули «наизнанку» и т.д. Результат шифрования выгладит так.
Е

Е

И

К

О Р

Б

К

Б

О Ч

К

Ы
Н

3

с
т
р
и

А
Л
А

С

Т
М
И
Т

Ш

О
н
У

Е

О

О

с

У

ы

Ю

К

с
р
и
п
р

я
г

и

У

А

т

Р

л

Е

Ь
И

Какой текст был зашифрован?
Шифрование фразы на русском языке проходит в два этапа. На пер­
вом этапе каждая буква текста заменяется на следующую в алфавитном
порядке (последняя заменяется на первую), используется алфавит без
Ъ и Ё. На втором этапе применяется шифр простой замены с неиз­
вестным ключом (его применение заключается в замене каждой буквы
шифруемого текста буквой того же алфавита, при этом разные буквы
заменяются разными буквами). После шифрования фразы был полу­
чен следующий шифротекст (пробелы разделяют слова):
a) «ГНПНВТ НРЗКЗС ЗГТШЗИ»;
b ) «АЯРЙДСАНК ЗВПЯ ЛЗККЗНМНБ»;
c) «ЛКЬФПЭЛШХ ТНЫК ЦТХХТШЧШМ»;
d) «ОШЫШНЮ ШЫХТЭ ТОЮДТУ».
По данному шифротексту восстановите открытое сообщение, если
известно, что результат шифрования любого открытого сообщения не
зависит от порядка выполнения его этапов.

Tlgm: @it_boooks

1.2. Криптоанализ классических шифров

57

[9] Расшифруйте текст, если известно, что каждой букве алфавита соот­
ветствует двузначное число.
• 39 25 20 34 82 63 66 46 35 20 25 82 86 39 51 74 35 51 66 20 44 37
25 27 51 35 44 20 90 37 51 25 25 51 63 91 20 11 37 46 48 25 20 37
61 51 14 82 82 66 82 35 29 82 91 25 51 74 51 24 78 51 24 59 46 86 51
44 74 20 25 37 37 37 44 82 31 11 37 82 51 46 25 51 34 82 25 37 82 86
37 25 27 51 35 44 20 90 37 51 25 25 48 44 46 82 78 25 51 14 51 18 37
59 44 51 74 82 35 20 90 37 59 44 66 90 82 25 25 48 44 37 61 10 44
20 18 20 44 37 86 61 20 25 86 51 39 66 86 51 44 10 66 82 86 46 51
35 10 37 66 51 46 51 39 51 63 66 39 59 91 37 56 46 51 86 20 66 20
82 46 66 59 24 35 10 18 37 78 51 35 18 20 25 37 91 20 90 37 63 46
51 66 51 18 14 20 66 25 51 35 82 91 10 14 29 46 20 46 20 44 35 20 91
14 37 56 25 48 78 37 66 66 14 82 24 51 39 20 25 37 63 35 10 86 51
39 51 24 37 46 82 14 37 44 25 51 18 37 78 37 91 25 37 78 91 25 20
31 46 51 61 51 66 25 51 39 25 48 78 39 37 24 20 78 10 18 35 51 91 25
51 25 82 10 24 82 14 59 31 46 24 51 14 42 25 51 18 51 39 25 37 44 20
25 37 59 24 20 25 25 48 44 39 51 74 35 51 66 20 44 66 56 37 46 20
59 56 46 51 51 61 82 66 74 82 56 82 25 37 82 37 25 27 51 35 44 20
90 37 51 25 25 51 63 61 82 91 51 74 20 66 25 51 66 46 37 25 82 37
44 82 82 46 66 44 48 66 14 20 82 66 14 37 51 46 66 10 46 66 46 39
10 82 46 39 37 24 37 44 20 59 10 18 35 51 91 20
• 74
95
50
29
82
32
29
32
25
53
50
95
89
49
34
62
49
99
17
95

29 23 27 17 99 71 25 49 32 29 34 27 63 32 25 17 99 60 62 25 34
29 53 59 82 27 71 29 77 99 34 27 91 17 99 71 49 99 27 15 60 32 25
27 17 62 27 95 27 50 25 91 32 59 77 95 29 50 25 99 59 25 99 74
53 25 59 17 99 25 91 23 49 71 25 17 99 60 49 25 34 32 25 71 95 27
27 32 32 25 29 50 17 25 15 77 99 32 59 77 62 95 25 53 95 29 23
25 17 99 60 34 15 35 17 27 99 27 71 25 12 25 99 95 29 45 49 74
62 95 27 63 34 27 71 17 27 12 25 50 27 17 62 27 95 27 50 25 91
29 35 95 29 50 25 99 29 17 29 82 49 83 62 25 17 27 50 27 62 95
34 59 74 99 25 71 50 27 53 25 62 29 17 32 25 17 99 49 17 71 35
29 32 29 17 32 29 15 49 23 49 27 82 32 29 34 27 63 32 25 95 29
25 99 29 77 10 27 12 25 25 50 25 95 59 34 25 71 29 32 49 35 49
27 53 27 95 71 49 95 25 71 29 32 49 27 82 74 95 49 99 49 23 32
83 74 25 99 74 29 53 59 50 15 25 74 25 71 62 49 99 29 32 49 35
53 29 62 25 82 49 32 29 77 10 49 83 59 17 99 95 25 91 17 99 71
15 35 62 25 17 15 27 34 32 49 83 25 62 99 49 82 29 15 60 32 25
95 49 82 27 32 27 32 49 27 34 49 17 74 25 71 89 83 82 29 17 17
71 25 71 12 25 95 35 23 27 91 53 29 82 27 32 89 74 29 23 27 17
71 25 49 32 29 34 27 63 32 25 17 99 60 95 29 50 25 99 89 34 25
99 49 12 29 27 99 17 35 25 62 99 49 82 49 53 29 67 49 27 91 62
25 12 95 29 82 82 32 25 12 25 25 50 27 17 62 27 23 27 32 49 35

Tlgm: @it_boooks

58

Глава 1. Из истории криптографии

10 Используя частотный анализ букв русского языка, вскройте сообще­
ние, если известно, что различным буквам соответствуют различные
двузначные числа. Знаки препинания и некоторые пробелы сохране­
ны для удобства вскрытия.
56 27 54 54 27 56 51 32 82 16 63 49 27 63 11 30 73 35 23 54 89 70 27
63 27 49 32 70 35 16 97 82 1 6 67 73 27 51 30 56 32 63 70 29 63 27
49 32 73 29 54 73 27 48 29 13 29 82 56 82 27 95 54 27 35 27 18 51 29,
97 56 27 70 29 63 30 51 51 35 15 63 89 48 16. 16 63 15 11 51 30 82 29 49
65 27 54 32 63 30 49 29 61 27 63 32 48 3 0 - 2 7 56 51 35 15 56 30 23
32 27 11 70 27 35 27 18 32 56 29 63 89 82 30 23, 27 82 30 51 30 51 11
15 73 35 29 54 70 27 49 65 32 38 30 63 30 73 35 32 23 56 82 16 67 70
49 56 35 29 97 16. 82 27 49 51 27 13 51 29 54 30 27 82 27 73 16 49 56
32 63 70 29 63 27 49 32 73 29 54 82 15 95 16 73 27 35 32 70 15 56 30
38 32 63 32 92-73 27 54 11 30 61 30 18 82 32 51 30 49 63 27 18 29 82 82
16 67 61 30 92 29 56 16. 27 82 49 16 82 16 63 61 30 92 29 56 16 73 27 54
13 15 24 51 16 32 70 92 27 24 29 63 73 27 49 56 16 73 29 82 89 51 30 13.

11 Шифрование сообщений состоит в замене букв исходного текста в со­
ответствии с некоторой (известной только отправителю и получателю)
таблицей, в первой строке которой выписаны все буквы используемо­
го алфавита в естественном (алфавитном) порядке, а во второй — все
буквы того же алфавита в произвольном порядке. Перед шифровани­
ем из текста сообщения удалили все пробелы и знаки препинания.
Восстановите исходное сообщение по имеющемуся зашифрованному
тексту (для удобства чтения его разбили на группы по пять букв).
ЙЛЙСЭ ВНЛЦЩ ТНАРТ ЦСКЕЛ ХИЦЭК ЦЫЦИП МОНКЕ
ЖКГЁК ЗКДЁК ТЦЩЯР КСАНИ ЦЩТЮЗ НКРЛС ФМТКС
АНШАЁ ЁКЁАЗ КЁИЖЛ ЮЁЛУА ЖКТЁК СЛЁЭА ОККВА
ХЛЁИЮ КВАТЗ АУИЦЩ СЛЖОЛ НЛЁЦИ НКСЛЁ ЁМЯЕЛ
ХИЦМИ ДИЖКГ ЁКТРА ДЛЦЩТ ЛЖКТЦ КЮЦАТ ЩЁЭБК
ТКЕЁЛ ЁЁЭБС ЭВКНС КСЦКН КЖТДМ УЛАСЛ ЖЁАКВ
КБЦИТ ЩВАЕЕ ЁЛЁИБ ЁЛМУЁ ЭПКТЁ КСЙНИ ЗЦКОН
КЛЦИИ

12 Для шифрования сообщения используют неизвестную последователь­
ность целых чисел. Каждую букву сообщения заменяют ее порядковым
номером в алфавите: А — на 1, ..., Я — на 33, затем прибавляют к
полученному номеру очередной член последовательности и, наконец,
выписывают остаток от деления этой суммы на 33. При реализации
указанного алгоритма получилось вот такое шифрованное сообщение:
22 24 23 27 2 3 3 9 18 25 1 18 18 8 12 32 6 32 23.

Tlgm: @it_boooks

1.2. Криптоанализ классических шифров

59

Если бы при шифровании того же самого сообщения вместо сложения
с членами заданной последовательности мы производили вычитание,
то был бы получен такой результат:
14 11 15 7 1 9 7 3 8 20 29 2 27 16 14 32 11 13 32.
Найдите исходное сообщение.
13 1 При шифровании исходного сообщения каждую его букву заменили
одной либо двумя цифрами, причем одинаковые буквы всегда заме­
няли одной и той же цифрой или парой цифр. Полученную после­
довательность разбили на группы по пять цифр для удобства записи.
Найдите исходное сообщение по данному шифрованному тексту.
40745 21618 52412 92008 62528 72621 41386
44415 44214 34922 41612 21322 43150 85412
14341 64725 40212 11328 68541 93552 38321
40222 18141 52854 02144 40540 21417 28213
02298 72625 54347 32243 15047 52540 52940
74440 53645 53417 12241 92872 84787 02223
52347 28147 53417 44223 05415 02120 28545
21621 24221 22022 74822 46651 74040 54347
35523 83214 22829 22292 34728 12202 24422
32103 41544 02287 96214 02286 28622 45415
20674 65122 28222 92951 74022 21672 90224
44085 49305 34550 54932 24315 05140 21473
05264 08621 26408 24667
1141 При зашифровывании исходного сообщения каждый его символ (бук­
ву или пробел) заменяли одной либо двумя цифрами, причем одина­
ковые символы всегда заменяли одинаково. Для удобства записи по­
лученную последовательность сгруппировали по пять цифр. Найдите
исходное сообщение по данному шифрованному тексту.
14939 21803 25872 18125 86808 62163 49258 62581 21432
42921 29325 43204 08781 32545 81127 81208 56212 57270
32508 74986 21478 04349 32547 49874 92128 25866 43246
21472 98325 81443 64725 74947 47293 80254 46125 45246
72749 24802 16202 84781 23812 54381 47214 94321 49254
26125 27149 80347 81832 54524 81276 24438 02580 25446
12545 24672 74924 80216 20284 78123 81258 14436 47492
54349 43818 32520 80448 12580 47268 12434 95806 83252
78685 25476 81442 28178 03498 52572 08525 45818 62920
43802 54180 26248 12749 47478 12381 25868 18144 42647
80852 58047 26812 43495 80852 58144 42678 18621 04547

Tlgm: @it_boooks

60

Глава 1. Из истории криптографии

15| Шифротекст
АМИМОПРАСТЕТИРАСИСПД
ИСАФЕИИБОЕТКЖРГ ЛЕОЛО
ИШИСАННСЙСАООЛТЛЕЯТУ
ИЦВЫИПИЯДПИЩПЬПСЕЮЯЯ
получен из исходного сообщения перестановкой его букв. Текст
У Щ.ф М Ш П Д Р Е Ц Ч Е Ш Ю Ш Ч Д А К Е
ЧМДВКШБЕЕЧДФЭПЙЩГШФЩ
ЦЕЮЩФПМЕЧПМЕРЩМЕОФЧЩ
ХЕ ШР Т Г Д И Ф Р С Я Ы Л К Д Ф Ф Е Е
получен из того же исходного сообщения однозначной заменой каж­
дой буквы на другую. Восстановите исходное сообщение.
161 Для проверки телетайпа, печатающего буквами русского алфавита
«АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ», передан набор из
9 слов, содержащий все 33 буквы алфавита. В результате неисправ­
ности телетайпа на приемном конце получены слова «ГЪЙ АЭЕ БПРК
ЕЖЩЮ НМЬЧ СЫЛЗ ШДУ ЦХОТ ЯФВИ». Восстановите исходный текст,
если известно, что характер неисправности таков, что каждая буква
заменяется буквой, отстоящей от нее в указанном алфавите не дальше,
чем на две буквы (например, буква Б может перейти в одну из букв
А, Б, В, Г).
1171 В результате перестановки букв сообщения получена криптограмма
«БТИПЧЬЛОЯЧЫЫОТПУНТНОНЗЛЖАЧОЬОТУНИУХНИППОЛОЬЧОЕЛОЛС».
Прочтите исходное сообщение, если известно, что оно было разбито на
отрезки одинаковой длины г, в каждом из которых буквы были пере­
ставлены по следующему правилу: буква отрезка, имеющая порядковый
номер х (х = 1, 2 , . . . , г ) , в соответствующем отрезке криптограммы
имеет порядковый номер f ( x) = R E S T (ax + b9г), где а и b — некото­
рые натуральные числа, а величина R E S T (ax + b, г) равна остатку от
деления суммы ax + b на г, если этот остаток не равен нулю, и г, если
остаток равен нулю.
Одноразовый блокнот — ключ шифра Вернама, обладающий тремя
критически важными свойствами: генерироваться с помощью слу­
чайных чисел (то есть иметь случайное равномерное распределение:
Рк{Щ =

где к — ключ, а N — количество бинарных симво­

лов в ключе); совпадать по размеру с заданным открытым текстом;
применяться только один раз. Какие из рассмотренных нами шифров
наиболее близки шифру Вернама? Как нужно модифицировать ис­
пользование тех или иных изученных шифров, чтобы приблизить их
свойства к свойству шифра Вернама? В чем преимущества и недостатки
практического использования одноразового блокнота в шифровании?

Tlgm: @it_boooks

1.3. Задачи криптографических олимпиад

61

1.3. Задачи криптографических олимпиад
Примеры решения задач
[Пример 1.3.15) Формулировка некоторого геометрического утверждения

была вписана в клетки таблицы 10 х 10 построчно слева направо, начиная
с верхней левой клетки. Знак переноса на следующую строку не ставился,
но между соседними словами одной строки помещалась пустая клетка.
Решили переставлять буквы в отдельных столбцах, сдвигая их все на одну
позицию вверх и перенося самую верхнюю букву вниз (при этом пустую
клетку также считая буквой). Иногда меняли местами сразу все строки,
симметричные относительно средней линии, а именно 1-ю с 10-й, 2 -ю с
9-й и т.д., после чего снова брались за передвижение букв в столбцах. В
результате таблица приняла представленный на рисунке вид. Прочитайте
исходное геометрическое утверждение.
А

л

п

Н

в

И

В

т

Р

Е

о

с

н

л

Я

О

л

Т

я

л

ы

Е

О

ы т

У

О

А

о

щ

Д

р

р

А

Е

Н

р

У

и

О

н

с

т

В

П

к

и

м

Е

ь

Е

в

О

т

С

с
к
ж

и

Ь
С

т

ы

X X н
и Е О
Ь п
п

А

д

ю
X

Е

Н

с

Е

л

О

О

П
Е

О

с

Е

р

О

Я

[Решение] Будем решать эту задачу перебором, вырезав из бумаги три

полосы, соответствующие первым трем строкам таблицы. Используем
попытки «увидеть» в зашифрованном тексте какое-либо слово, имею­
щее отношение к геометрической тематике, например, «прямая», «точка»
и т.п., учитывая естественное соображение: круг слов, используемых в
геометрических текстах, существенно ограничен. Сузим набор операций
сдвига букв в столбцах и отражения столбца относительно средней ли­
нии: сдвинуть столбец на одну позицию вверх и затем отразить — это
все равно, что столбец сначала отразить, а затем сдвинуть вверх на девять
позиций, поэтому можно считать, что сначала мы передвигали буквы в
столбцах, а затем, может быть, один раз отразили таблицу относительно
средней линии.

Tlgm: @it_boooks

Глава 1. Из истории криптографии

62

Рассмотрим букву «Я» в предпоследнем столбце. Перед ней могут сто­
ять буквы «О», «П», «Н», «Р», «С», «Ы», «В». Сочетание «ОЯ» встречается в
математических текстах в слове «постоянная», но необходимой буквы «Т»
в седьмом столбце нет. Сочетание «РЯ» может быть частью слова «прямая»,
но в седьмом столбце нет «Р». Сочетания «касающихся», «пересекающихся»
представляются наиболее вероятным, и присутствие буквы «Щ» в пятом
столбце тому подтверждение. После того как столбцы с пятого по девятый
выстроены так, чтоб прочитывалось «ЩИХСЯ», получение ответа стано­
вится совсем простым делом.
п

О

с

Л

Е

д

Е

Л

ь

ы

А

Ж

Е

н
н
с

и

С

к

О

О

с

И

д

в

У

Е

к

А

П

р
О

Я

Н

А

Т

Е

О

Т

Р

Я

п

Л

О

О

т

Н

И

н о
X
р Е
П Е
ю Щ И X с Я
р А
м Ы X
ь н ы
и
Л
в
О р О Т
О
Е

т

С

Е

т

в

О

П

Л

ь

С

В

Е
У

[Пример 1,3,16] Для шифровании текста ѵь ѵг, . . . , ѵ* на русском языке

каждую его букву ѵ* заменили числом ^ согласно таблице.

Ѵі

А

Б

В

Г

д

Е

Ё

Ж

3

И

Й

К

Л

М

н

О

п

и

00

01

02 03

04

05

06

07

08

09

10

11

12

13

14

15

16

Ѵі

Р

С

Т

У

Ф

X

ц

Ч

Ш

Щ

ь

ы

Ъ

э ю

Я

и

17

18

19 20

21

22

23

24

25

26

27 28 29 30

31

32

К каждому числу U последовательности t \ , t 2 >. . . ,tk прибавили чис­
ло аі последовательности а \9
. . . , а^, заданной соотношениями а\ = 1 ,
а п+1 = 3ап + 4 при п > 0. Затем остаток от деления каждой суммы t{ + а*
на 33 вновь заменили буквой по той же таблице. При переписывании
зашифрованного текста несколько букв были пропущены. В результате
получилось вот что: «РЧЖЬЭТСЪЙЛЖЪЯОШКС». Найдите исходный текст.

Tlgm: @it_boooks

1.3. Задачи криптографических олимпиад

63

[Решение! Заменяя каждый член последовательности а\ = 1, ап+і =

= За„+ 4 остатком от его деления на 33, получим последовательность 1, 7,
25, 13, 10, 1, 7, 25,13, 10, .... Так как каждый член этой последовательности
остатков однозначно находится из предыдущего, заключаем, что ее период
равен пяти.
Будем вычитать из чисел, соответствующих буквам зашифрованного
текста, числа этой периодической последовательности, а результаты заме­
нять буквами согласно данной в условии задачи таблице.
р

Ч

Ж

Ь

Э

Т

С

ъ

й

л

17

24

7

29

30

19

18

27

10

12

1

7

25

13

10

1

7

25

13

10

16

17

15

16

20

18

11

2

30

2

П

Р

О

К

В

э

В

П

У

С

После слова «ПРОПУСК» идет нечитаемый текст. Значит, или непо­
средственно после этого слова, или после буквы «В» пропущены буквы.
(Перебор различных вариантов тривиален и поэтому здесь не приводится.)
Сдвигая нашу периодическую последовательность относительно зашиф­
рованного текста, находим такой вариант.
17

24

7

Р

Ч

Ж

Ь

1

7

25

13

16

17

15

16

П

Р

О

п

29

30

19

18

э

Т

С

10

12

7

20

18

У

С

27

10

12

7

27

32

15

25

11

18

Ъ

й

Л

Ж

Ъ

Я

О

Ш

К

С

13

10

1

7

25

13

10

1

7

25

11

14

0

11

0

2

19

5

24

4

26

К

Н

А

К

А

В

Т

Е

Ч

Д щ

25

Естественно предположить, что на месте пропущенного знака в ис­
ходном тексте находилась буква «3». Действуя далее аналогично, восста­
навливаем весь текст
17

24

7

Р

Ч

Ж

Ь

1

7

25

13

16

17

15

П

Р

О

30

19

18

э

Т

С

10

12

7

16 20

18

п

С

29

У

27

10

12

7

Ъ

й

Л

Ж

13

10

1

7

11

14

0

11

0

К

Н

А

К

А

25

ПРОПУСК ЗНАКА В ТЕКСТЕ

27

32

15

25

11

18

Ъ

Я

О

Ш

К

С

25

13

10

7

25

13

2

19

5

18

19

5

В

Т

Е

С

Т

Е

1



Tlgm: @it_boooks

64

Глава 1. Из истории криптографии

[Пример 1,3.17| Каждую букву исходного сообщения заменили ее дву­

значным порядковым номером в русском алфавите согласно таблице.
А

Б

В

Г

д

Е

Ё

Ж

3

И

Й

К

Л

м

н

О

п

01

02

03

04

05

06

07

08

09

10

11

12

13

14

15

16

17

Р

С

Т

У

Ф

X

Ц

Ч

Ш

щ

ъ

Ы

ь

э

ю

я

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

Полученную числовую последовательность разбили на трехзначные
цифровые группы без пересечений и пропусков. Каждое из получен­
ных трехзначных чисел умножили на 77 и оставили только три послед­
ние цифры произведения. В результате получилась последовательность
«317564404970017677550547850355». Восстановите исходное сообщение.
[Решение] Для нахождения последней буквы исходного сообщения необ­
ходимо решить сравнение 11п = 355 (mod 1000): здесь п пока неизвестное

трехзначное число.
Пусть п = 100а + 106 + с, где а, Ь, с — цифры его десятичной записи.
Тогда 77(100а + 106 + с) = 355 (mod 1000) & 7000а + 7006 + 70с 4- 700а +
+ 70Ь+7с ее 355 (mod 1000)
700(а +Ь)+70(Ь+с)+7с = 355 (mod 1000).
Значит, с = 5. Далее, 700(а +6)4-706+30 = 0 (mod 1000). Отсюда Ъ=
= 1. Тогда 700а + 800 = 0 (mod 1000). Значит, а = 6 , и поэтому п = 615.
Сравнение 77п = 355 (mod 1000) могло быть решено иначе. Умножив
обе части его на 13, получим ЮОІп = 13 • 355 (mod 1000). Ясно, что
последние три цифры числа, стоящего в левой части равенства, совпадают
с тремя последними цифрами самого числа п. Вычислив 13 • 355 — 4615,
найдем п — 615.
Теперь аналогично решаем сравнение, в правой части которого сто­
ят другие трехзначные цифровые группы шифросообщения (850, 547,
550 и т.д.).
Искомая цифровая последовательность имеет вид «121332252610221801150111050615», что позволяет получить исходное сообщение «КЛЮЧШИФРАНАЙДЕН».

[Пример 1,3,18] Для доступа к управлению параметрами своего счета

клиенту банка необходимо связаться по телефону с банком и набрать
семизначный пароль. После первой же неправильно набранной цифры
пароля банк прерывает телефонное соединение. Как надо действовать,
чтобы за наименьшее число попыток подобрать пароль?

Tlgm: @it_boooks

1.3. Задачи криптографических олимпиад

65

[Решение! Цифры пароля будем подбирать последовательно. Свяжемся с

банком и наберем цифру 0. Если связь не оборвалась, то первая цифра
пароля — ноль. Если связь прервана, то первая цифра отлична от 0 и,
связываясь заново с банком, пробуем набрать 1, и т.д. Не позднее чем через
девять звонков мы будем точно знать, какая цифра стоит на первом месте в
пароле, и сможем перейти к подбору второй цифры. Общее число звонков,
которое понадобится для выяснения пароля, не превосходит 7*9 = 63. Еще
один звонок может понадобиться для получения доступа после полного
выяснения пароля.

Замечание. Если бы решение о доступе или отказе принималось только
после ввода всего пароля, то система защиты была бы гораздо надежнее —
последовательный подбор был бы невозможен, и потенциально пришлось бы
перебирать все 107 = 10000000 вариантов пароля.

[Пример 1.3.19] Центральный замок автомобиля открывается и закрыва­
ется с помощью брелка. При получении сигнала брелка замок открывается
(если был закрыт) или закрывается (если был открыт). В брелке и замке
имеются счетчики (назовем их СБ и СЗ ), на которых изначально бы­
ло выставлено одно и то же число. Пусть N — текущее значение СБ.
При нажатии на кнопку брелка СБ меняет значение на N + 1, старое же
значение N в зашифрованном виде передается замку. Микрокомпьютер
замка расшифровывает полученный сигнал и находит число, переданное
брелком. Если это число равно или превосходит значение СЗ , то замок
срабатывает, а СЗ принимает значение N + 1. Если это число оказыва­
ется меньше или при расшифровании обнаруживается ошибка, то замок
остается в прежнем состоянии. Злоумышленник способен запоминать сиг­
налы брелка; поставив помеху, искажать сигналы брелка (при этом сам
злоумышленник получает сигнал без искажений); посылать замку ранее
запомненные сигналы. Как злоумышленнику открыть замок, если алго­
ритмы шифрования и дешифрования ему неизвестны?
[Решениеі Приведенный в задаче протокол работы брелка и замка был

изобретен в ЮАР и практически без изменения использовался во многих
известных противоугонных системах. Достаточно продолжительное время
уязвимость этого протокола не была замечена. Перейдем собственно к
решению, пояснив предварительно одно из условий задачи: если СБ = к
и СЗ — 771, где к ^ 771, то при нажатии на кнопку брелка и срабаты­
вании замка счетчик замка принимает значение не т п + 1, a
1. Это
сделано для того, чтобы один и тот же сигнал брелка не мог быть исполь­
зован дважды.

Tlgm: @it_boooks

Глава 1. Из истории криптографии

66

Запишем теперь по пунктам действия злоумышленника.
• Пусть замок открыт. Владелец хочет запереть машину и уйти. Пусть
СБ = к и СЗ = 771, где к ^ т . Владелец нажимает кнопку брелка.
Злоумышленник запоминает посланный сигнал к и ставит помеху. В
результате получаем, что СБ = к + 1 и по-прежнему СЗ — т , т.е. замок
не закрылся.
• Заметив, что машина не заперта, владелец повторно нажимает кнопку
брелка. Злоумышленник снова запоминает сигнал к Л-1 брелка и опять
ставит помеху. В этот момент СБ — к + 2, а замок так и остается
открытым, т. е. СЗ — т .
• Выполнив действия предыдущего пункта, злоумышленник немедлен­
но посылает замку ранее запомненный сигнал к. Замок закрывается,
и СЗ = к + 1. Владелец уходит, полагая, что машину запер он сам.
• Злоумышленник посылает замку ранее запомненный сигнал к + 1, и
замок открывается.

Задачи
[Т| Можно ли создать проводную телефонную сеть связи, состоящую из

993 абонентов, каждый из которых был бы связан ровно с 99 другими?
[2] Кодовая комбинация сейфа устанавливается на внутренней стороне
дверцы с помощью трех дисков. Каждый из них может быть уста­
новлен в одно из 20 положений, пронумерованных числами от 0 до
19, поворотом по часовой стрелке. В начальный момент диски уста­
новлены в положение (0, 0, 0). За положение с номером 19 диск не
поворачивается. При повороте каждого диска на одно положение раз­
дается щелчок. Сравните число возможных ходовых комбинаций, при
установке которых раздается 33, 32, 25 щелчков.
[ЗІ Два криптографа выясняют, чей шифр содержит больше ключей. Пер­
вый говорит, что ключ его шифра состоит из 50 упорядоченных сим­
волов, каждый из которых принимает 7 значений. Второй говорит, что
ключ его шифра состоит всего из 43 упорядоченных символов, зато
каждый из них принимает 10 значений. Чей шифр содержит больше
ключей?
[41 В первую строку таблицы размером 3 x 1 0 вписали 10 различных букв
30-буквенного русского алфавита (Е и Ё, И и Й, Ь и Ъ отождествле­
ны). Затем все оставшиеся буквы в естественном порядке (построчно
сверху вниз, слева направо) вписали в свободные клетки таблицы.
Алгоритм шифрования по заданной таблице следующий: из номеров

Tlgm: @it_boooks

67

1.3. Задачи криптографических олимпиад

столбцов таблицы с буквами открытого сообщения составим нату­
ральное число и умножим его на 9. Первую, вторую, третью и т.д.
цифры полученного числа будем рассматривать как последовательные
номера столбцов таблицы, в которых находятся первая, вторая, третья
и т.д. буквы шифротекста. Последовательные номера строк таблицы,
в которых находятся буквы шифротекста, определяются набором со­
ответствующих номеров строк с буквами исходного слова, к которому
слева приписывается 1, если число цифр произведения больше числа
букв исходного слова. Можно ли слово «АСТРАХАНЬ» зашифровать с
помощью такой таблицы в слово «БУТЕРБРОД»?
І5І Исходное сообщение, состоящее из букв русского алфавита и знака ^
пробела между словами, преобразуется в цифровое сообщение заменой
каждого его символа парой цифр согласно следующей таблице.
А

Б

В

Г

д

Е

Ж

3

И

К

Л

М

Н

О

п

р

01

02

03

04

05

06

07

08

09

10

И

12

13

14

15

16

С

Т

У

Ф

X

ц

Ч

Ш

Щ

ь

ы

Э

ю

Я

-

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

Для шифрования используется отрезок последовательности А{ = 3,
Ak+ 1 = Ak + 3(fc2 + к + 1) для любого натурального к , начинающийся
с некоторого фиксированного члена Ат. При шифровании каждая
цифра сообщения складывается с соответствующей цифрой отрезка
и заменяется последней цифрой полученной суммы. Восстановите
сообщение «2339867216458160670617315588».
\б\ Преобразование цифрового текста заключается в том, что каждая его
цифра заменяется остатком от деления значения многочлена f ( x) —
= a( x 3 + 4х 2 + 4х + b) на число 10, где а и Ъ — фиксированные
натуральные числа. Выясните, при каких значениях а и b указанное

преобразование допускает однозначное дешифрование.
[У] Пусть Х\ и Ж2 — корни трехчлена х 2 + Зх + 1. Для шифрования от­
крытого текста, записанного в 31-буквенном русском алфавите (не
используются буквы Ё и Ъ), к порядковому номеру каждой его буквы
прибавим значение многочлена f ( x) = х в + 3х5 + х 4 + х 3 + 4 х 2 + 4х + 3,
вычисленное либо при х = х \ , либо при х = х ^, а затем заменим полу­
ченное число соответствующей ему буквой. Зашифруйте этим методом
сообщение «НАС УТРО ВСТРЕЧАЕТ ПРОХЛАДОЙ». Расшифруйте со­
общение «ДЮСРНПЗПР».

Tlgm: @it_boooks

Глава 1. Из истории криптографии

68

[8 ] Цифры 0 , 1 , . . . , 9 разбиты на несколько непересекающихся групп.
Из цифр каждой группы составлены всевозможные числа, для записи
каждого из которых все цифры группы используются ровно один раз
(учитываются и записи, начинающиеся с нуля). Все полученные числа
расположены в порядке возрастания, и fc-му числу поставлена в соот­
ветствие k -я буква алфавита АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ При реализации данного алгоритма оказалось, что
каждой букве соответствует число и каждому числу соответствует неко­
торая буква. Шифрование сообщения осуществляется заменой каждой
буквы соответствующим ей числом. Если ненулевое число начинается
с нуля, то при шифровании этот нуль не выписывается. Восстановите
сообщение «873146507381» и укажите таблицу замены букв числами.
[9І Дана криптограмма.
ФН

х

+

Ы

ФАФ

х

ЕЕ

+

Е

ИША

+

МР

=

НЗ

ИМН

Восстановите цифровые значения букв, при которых справедливы все
указанные равенства, если разным буквам соответствуют разные циф­
ры. Расставьте буквы в порядке возрастания их цифровых значений и
получите исходный текст.
1101 В нашем распоряжении имеется два сейфа. Первый содержит 100 пе­
реключателей по два положения каждый, второй — 8 переключателей
по 100 положений каждый. Сейф открывается только при полном сов­
падении. Какой сейф надежнее и почему?
[ГГ| Клетки магического квадрата размера 4 х 4 с единицей в правом ниж­
нем углу заполнили буквами некоторого сообщения так, что его первая
буква попала в клетку с номером 1, вторая — в клетку с номером 2 и т.
д. В результате построчного выписывания букв заполненного квадра­
та (слева направо и сверху вниз) получилась последовательность букв
«ЫРЕУСТЕ ВЫАБЕВКП». Зная, что существует ровно четыре таких ма­
гических квадрата, расшифруйте данное шифрованное сообщение.
12 1 Клетку таблицы размера 8 x 8 назовем «хорошей», если все остальные
клетки таблицы можно замостить прямоугольниками 3 x 1 .

Tlgm: @it_boooks

1.3. Задачи криптографических олимпиад

69

Укажите все «хорошие» клетки таблицы.
Сообщение, записанное в 33-буквенном русском алфавите, числовы­
ми аналогами символов которого являются числа 0-32, зашифровано
шифром Тритемиуса по правилу, определяемому некоторым ключевым
словом. Во все клетки таблицы, за исключением «хороших», построч­
но вписаны буквы шифрованного текста, а в «хорошие» клетки —
буквы ключевого слова. Найдите ключевое слово и восстановите ис­
ходное сообщение по приведенной таблице.
Е

Ю

У

Я

Б

В

Д
ш

А

Р

Ш

Н

П

Ь

р

Щ

Е

У

Д
в

Ъ

Й

л

Ё

И

Ж

Щ

Е

Д
с

Е

ю

У

В

К

ч

Ч

Б

с

Г

Е

Ь

р

Е

ш

В

й

Е

С

В

ь

О

3

Ю

ь

Ь

А

Ь

3

Ь

щ

Е

Б

Ё

1131 В банке работают девять директоров, причем они не очень-то дове­
ряют друг другу. Главный сейф банка открывается в том и только том
случае, когда все его замки открыты. Для каждого замка можно из­
готовить необходимое число копий ключа. Какое наименьшее число
замков должно быть у сейфа и как надо распределить ключи между
директорами, чтобы сейф мог быть открыт, только если вместе собе­
рутся не менее 5 директоров?
1141 Один из девяти директоров банка (см. предыдущую задачу) был из­
бран председателем, в связи с чем потребовалось внести изменения
в конструкцию сейфа: нужно, чтобы сейф могли открыть не только
любые пять собравшихся вместе директоров, но и любой директор
вместе с председателем. При этом группа из менее чем пяти директо­
ров, среди которых нет председателя, либо председатель в одиночку
не должны иметь возможность открыть сейф. Какое наименьшее чис­
ло замков надо установить на двери сейфа и каким образом раздать
ключи директорам для реализации указанных правил доступа к содер­
жимому сейфа?

Tlgm: @it_boooks

Глава 1. Из истории криптографии

70

1151 Числа, расположенные в клетках таблицы, указывают, сколько сосед­
них по горизонтали, вертикали и диагонали клеток (включая ту, в
которой находится само число) должны быть окрашены. Восстанови­
те картину, которой соответствуют эти числа.
5

2

0

5
3

0

2

1

3

3

5

4

6
5

2

3

3

2

3

3

3

2

3

5

3

0
1

3

0

7

9

8

2

6

6
3
0

1
0

3
1

4
5

2
0

1

6

0

5

6

1161 В центральном компьютере сети пейджинговой связи имеется вирус.
Он преобразует сообщения так, что все буквы передаются без иска­
жений, а каждая цифра несколько раз шифруется, причем количе­
ство шифрований равно абонентскому номеру получателя сообщения.
Кроме того, раз в день таблица шифрования меняется на другую. Как
выбрать абонентский номер так, чтобы не зависеть от действий вируса?
Найдите все такие номера.
1171 Чтобы не забыть секретную комбинацию цифр, открывающую сейф,
зашифруем ее и запишем результат в ежедневник. Для шифрования
выпишем цифры в таблицу, после чего несколько раз наугад переста­
вим столбцы этой таблицы, запомнив при этом способ перестановки.
Переставим столбцы тем же способом еще раз и запишем окончатель­
ный результат. Полученная таблица выглядит так.
4

5

6

2

2

0

2

9

0

1

9

9

Во сколько раз знание таблицы из ежедневника упростит вскры­
тие сейфа?

Tlgm: @it_boooks

1.3. Задачи криптографических олимпиад

71

ГІ8 І Перед шифрованием сообщения каждую его букву заменили двумя
цифрами в соответствии с ее порядковым номером в алфавите, под
полученной строкой цифр выписали еще одну строку, в которой встре­
чаются только цифры 1 и 2 , а затем сложили цифры в каждом столб­
це и записали остатки этих сумм при делении на 10. При реализа­
ции указанного алгоритма получилась цифровая последовательность
«29173018132839332553371832». Найдите исходное сообщение.
191 В первую строку таблицы размером 3 x 1 0 вписали 10 различных букв
30-буквенного русского алфавита (Е и Ё, И и Й, Ь и Ъ отождествле­
ны). Затем все оставшиеся буквы в естественном порядке (построчно
сверху вниз, слева направо) вписали в свободные клетки таблицы.
Алгоритм шифрования по заданной таблице следующий: из номеров
столбцов таблицы с буквами открытого сообщения составим нату­
ральное число и умножим его на 9. Первую, вторую, третью и т.д.
цифры полученного числа будем рассматривать как последовательные
номера столбцов таблицы, в которых находятся первая, вторая, третья
и т.д. буквы шифротекста. Последовательные номера строк таблицы,
в которых находятся буквы шифротекста, определяются набором со­
ответствующих номеров строк с буквами исходного слова, к которому
слева приписывается 1, если число цифр произведения больше чис­
ла букв исходного слова. Постройте шифрующую таблицу указанного
вида и зашифруйте с помощью указанного криптографического алго­
ритма слово «РУСЬ»; сообщение «МАТЕМАТИКА ЦАРИЦА НАУК».
При установкекодового замка каждой из 26 английских букв, располо­
женных на его клавиатуре, сопоставляется произвольное натуральное
число, известное лишь обладателю замка. Условие сопоставления раз­
ным буквам разных чисел не обязательно. После набора произвольной
комбинации попарно различных букв происходит суммирование чис­
ловых значений, соответствующих набранным буквам. Замок откры­
вается, если сумма делится на 26. Докажите, что для любых числовых
значений букв существует комбинация, открывающая замок.
Для изображения Моны Лизы в квадратной таблице размера 15 х 15
каждую ее клетку покрасили белой или черной краской. Назовем под­
ряд идущие клетки одного цвета строки или столбца таблицы поло­
сой, а число клеток в полосе — ее длиной. Восстановите изображение
по известным длинам полос черного цвета в каждой строке и в каждом
столбце (следующих соответственно сверху вниз и слева направо).
Информация по строкам: 9; 11; 1, 1; 2, 3, 3, 2; 2, 2; 2, 1, 1, 1, 2; 2, 1,2;
2, 2; 1, 5, 1; 2, 3, 2; 2, 2; 7; 1, 1; 6 , 6 ; 1, 4, 1, 4, 1.
Информация по столбцам: 1; 5, 1; 9, 2; 2, 2, 2; 2, 1, 2, 2; 2, 1, 1, 1, 1,
2; 2, 1, 2, 3; 2, 2, 2, 1, 1; 2, 1, 2, 3; 2, 1, 1, 1, 1, 2; 2, 1, 2, 2; 2, 2, 2;
9, 2 ; 5, 1; 1.

Tlgm: @it_boooks

72

Глава 1. Из истории криптографии

22 Знаменитый математик Леонард Эйлер в 1759 г. нашел замкнутый

маршрут обхода всех клеток шахматной доски ходом коня ровно по од­
ному разу. Прочтите текст, вписанный в клетки шахматной доски
по такому маршруту, если начало текста расположено в клетке А4.

Д

Л

Р

И

Л

п

н

Б

У

К

А

О

т

У

с

Т

О

О

О

А

н

О

и

Р

т

Б

Г

К

т

т

У

К

к

О

Е

О

р

А

в

О

к

Д

Г

П

в

л

Е

Т

т

А

Н

Р

А

Г

О

Е

А

О

В

м
и

Д

У

Л

1231 Пользователи сети связи для обеспечения секретности сообщений вы­
бирают (независимо друг от друга) пары преобразований (Е ; D ) , одно
из которых, Е (открытый ключ), публикуют в справочнике, а вто­
рое, D (личный ключ), держат в секрете. Известно, что значения
Е( т) и D(n) легко вычислить для любых сообщений т и п , причем
из равенства Е( т) = п следует, что D(n) — т. В то же время нахо­
ждение т по Е( т) является сложной задачей, которую невозможно
решить (любыми средствами) за реальное время, если неизвестно D.
Если пользователь А хочет послать пользователю В сообщение т >
он берет из справочника открытый ключ Е В пользователя В, вы­
числяет п = ЕВ( т) и посылает п к В. Получив п, В вычисляет
DB( n) = т. Злоумышленник, перехвативший п, не сможет вычис­
лить т. Это гарантирует секретность информации. Вкладчик предло­
жил банкиру способ передачи секретных сообщений с уведомлением
о получении: А передает В сообщение (А; ЕВ( т) ) \ В, получив сооб­
щение, вычисляет т и направляет А уведомление (В; ЕА( т) ) . Бан­
кир возразил вкладчику, что этот способ не обеспечивает секретности
информации от любого пользователя, который может перехватывать
сообщения и как угодно их изменять. Дополнительно потребовав,
чтобы для каждого преобразования Е было сложно подобрать пару
(т; п), для которой Е( т) = Е(п), банкир предложил вкладчику свой
способ: А передает В сообщение ЕВ( А; т) ; В, получив сообщение,
находит т и направляет А уведомление ЕА(В; т). Объясните, поче­
му способ банкира лучше способа вкладчика.

Tlgm: @it_boooks

1.3. Задачи криптографических олимпиад

73

Литература к главе 1
При подготовке текста главы 1 были использованы следующие источ­
ники [3], [6-12], [18], [24], [25], [27], [30], [35], [39-42], [44-47], [53-55],
[57], [62], [78-81], [83-85], [87], [89], [96], [119], [128].

Tlgm: @it_boooks

Глава 2

Простейшие симметричные криптосистемы

Рассмотрев исторические аспекты развития криптографии, в этой гла­
ве мы переходим к систематическому изложению математических основ
теории защиты информации.
Как и ранее, будем называть предназначенное для пересылки сообще­
ние открытым текстом, а замаскированное сообщение — шифротекстом,
процесс преобразования открытого текста в шифротекст — шифрованием,
а обратную процедуру — дешифрованием.
Открытый текст и шифротекст записываются в некоторых алфавитах;
обычно, но не всегда, эти алфавиты совпадают. Открытый и шифрован­
ный тексты разбиваются на элементы. Элементами могут служить как
отдельная буква, так и пара {биграмма), и тройка {триграмма) букв или
даже блок из, например, 64 букв.
Шифрующее преобразование является функцией, которая преобразует
элемент открытого текста в элемент шифротекста. Другими словами, это
отображение / из множества X всех возможных элементов открытого
текста в множество Y всех возможных элементов шифротекста:
f : X -+Y.
Дешифрующее преобразование действует в обратном направлении, восста­

навливая открытый текст по шифротексту. Это функция / _1, обратная
к функции / :

г 1:Y-¥X.

Описанный способ шифрования называется симметричной крипто­
системой, поскольку для шифрования и расшифровывания применяется
один и тот же криптографический ключ (точнее, ключ шифрования может
быть рассчитан по ключу дешифрирования, и наоборот).

2.1. Аффинные криптосистемы
К числу простейших симметричных криптосистем принадлежат аф­
финные криптосистемы, основанные на использовании так называемых
аффинных преобразований.

Tlgm: @it_boooks

2.1. Аффинные криптосистемы

75

Пусть і Е І - элемент открытого текста, а и Ь — некоторые целые
числа, по модулю не превосходящие N — мощность используемого алфа­
вита. Тогда отображение / : X —> Y , осуществляемое по закону
f ( x) = ах + b (mod N),

называется аффинным преобразованием с ключами а и Ъ [53].
Важными частными случаями аффинного преобразования являются
линейное преобразование
f( x) = ах (mod N),

соответствующее случаю b = 0 , и сдвиг
/(* ) = х + Ь (mod N ),
соответствующий случаю а — 1. Нетрудно видеть, что сдвиг является
ничем иным, как математическим выражением шифра Цезаря.
[Пример 2.1.1) Зашифруем сообщение «КРИПТОГРАФИЯ», записанное

в 33-буквенном русском алфавите, используя аффинное отображение с клю­
чами шифрования а = 7, b — 4.
Первая буква слова К имеет в алфавите порядковый номер 11 (нуме­
рация букв начинается с нуля). Выполним преобразование
7- 1 1 + 4 = 81 = 15 (m od33)
и убедимся, что 15-я буква в алфавите — это О. Таким образом, буква К
переходит в ходе преобразования в букву О.
Аналогичным образом получим, что
Р (7 • 17 + 4 = 123 = 24 (mod 33)) перейдет в Ч;
И (7 • 9 + 4 = 67 = 1 (mod 33)) перейдет в Б;
П (7 • 16 + 4 = 116 = 17 (mod 33)) перейдет в Р;
Т (7 • 19 + 4 = 137 = 5 (mod 33)) перейдет в Е;
О (7 • 15 + 4 = 109 = 1 0 (mod 33)) перейдет в Й;
Г (7 • 3 + 4 = 25 = 25 (mod 33)) перейдет в Ш;
А( 7- 0 + 4 = 4 = 4 (m od33)) перейдет в Д;
Ф (7 • 21 + 4 = 151 = 19 (mod 33)) перейдет в Т;
Я (7 • 32 + 4 = 228 = 30 (mod 33)) перейдет в Э.
Другими словами, заменяя символы слова «КРИПТОГРАФИЯ» их чис­
ловыми эквивалентами, мы получим последовательность «11 17 9 16 19 15
3 17 0 21 9 32», переходящую в ходе аффинного преобразования в после­
довательность «15 24 1 17 5 10 25 24 4 19 1 30» числовых эквивалентов
шифротекста «ОЧБРЕЙШЧДТБЭ».

Tlgm: @it_boooks

76

Глава 2. Простейшие симметричные криптосистемы

Аффинные криптосистемы относятся к симметричным криптосисте­
мам, т. е. обладают обратным преобразованием. Для того чтобы найти
такое преобразование, надо выразить у = f ( x) через х:
у = ах + Ъ(mod N), у —Ъ ~ а х (mod N), х = а~1(у —b) (mod N).

Для поиска а~1 необходимо решить сравнение at = 1 (modiV), кото­
рое имеет ровно одно решение в случае (a, N) = 1.
Этот результат следует из теоремы о линейных сравнениях [36], кото­
рая утверждает, что линейное сравнение ах = Ь (mod п) имеет ровно одно
решение, если (а, п) — 1 , ровно d решений, если (а ,п ) — d, d\b, и не имеет
решений в остальных случаях.
Таким образом, мы получаем условие существования дешифрующего {об­
ратного аффинного) преобразования: если (a, N ) — 1, то обратное аффинное
отображение существует и имеет вид
х = а • f ( x) + b' (mod ІѴ), где а — а -1, Ь! = - а ~ 1 • Ъ.



[Пример 2.1.2] Найдем обратное преобразование для аффинного отобра­
жения
у = 4х + 3 (mod 7).
Сначала найдем а' = а -1 из сравнения At = 1 (mod 7). Поскольку
(4, 7) = 1, то сравнение имеет единственное решение по модулю 7. Рас­
смотрим несколько способов его нахождения.
1. Последовательно перебирая числа 0, 1, 2, ..., 6 , являющиеся пред­
ставителями всех классов вычетов по модулю 7, мы получим, что
4*2 = 8 = 1 (mod 7), то есть решением сравнения 4t = 1 (mod 7) яв­
ляется класс вычетов t = 2 (mod 7).
2. Последовательно добавляя к правой части первоначального сравне­
ния модуль 7, мы получим сравнения 4t = 1 (mod 7), At = 8 (mod 7).
Получив в правой части число, делящееся на 4, сократим обе части
сравнения на 4 и получим t = 2 (mod 7).
3. Теорема Эйлера [36] утверждает, что для любого натурального числа п
и любого целого а, взаимно простого с п , имеет место сравнение
а'

Получив вектор X — I(4\
1, перейдем к исходному сообщению «ДА».

W



На практике мы можем столкнуться при дешифровке сообщений с раз­
личными «нештатными» ситуациями, поскольку при использовании не­
обратимой матрицы описанный выше алгоритм дает сбои и требуются
специальные методы для его корректировки. Рассмотрим различные слу­
чаи, которые могут произойти при дешифровании.
[Пример 3.1-5|

1. Используя 33-буквенный русский алфавит и шифрующее отображе-

(

ние f ( X ) = А • X с матрицей А — I

\3

1

2\}, была получена биграмма «ББ»
4/

шифротекста. Найдем соответствующую ей биграмму открытого текста.
Для этого заметим, что биграмма «ББ» имеет числовой эквивалент

(I ЛI .

Таким образом, для нахождения числового эквивалента соответ­

ствующей биграммы открытого текста необходимо решить сравнение

соем :)—
Поскольку А = 1 -4 —2 -3 — 4 —6 — —2 и (—2, 33) = 1, то данное
сравнение разрешимо и имеет ровно одно решение — биграмму по моду­
лю 33. Найдем его двумя способами.
Первый способ. В матричной форме сравнение имеет вид
Y = А - X (mod 33).

Перейдем к сравнению X = А ~1 • Y (mod 33) и найдем

Tlgm: @it_boooks

3.1. Алгебра матриц и аффинные матричные криптосистемы

101

Прежде всего найдем А 1. Поскольку А • А 1 = 1 (mod 33), то есть
-2 • А -1 = 1 (mod 33), то А -1 = 16. Тогда
А~1 = 16 •

Отсюда следует, что

\ —15 1 6 /

\ 1 /

Ѵ -15+16

Таким образом, числовой эквивалент биграммы открытого текста X /з2 \

= I
I , а сама биграмма имеет вид «ЯБ».
V 1/
Второй способ. Запишем наше преобразование в виде системы срав­
нений:
х + 2у = 1 (mod 33)

(

Зх + 4у = 1 (mod 33).

Домножим левую и правую части первого сравнения на 2 и вычтем
из второго сравнения первое. Получим х = —1 (mod 33), откуда сле­
дует, что у = 1 (mod 33). Поскольку х = —1 = 32 (mod 33), то получаем
/32\

окончательный ответ X = \

I , дающий, как и в предыдущем случае,

биграмму «ЯБ».
2.
Если при шифровании по той или иной причине была использована
«плохая» шифрующая матрица А , ситуация может осложниться. Рассмот­
рим, например, задачу дешифрования биграммы «АД», полученной при
использовании 33-буквенного русского алфавита и шифрующего.отобрас матрицей А = I( 1 5 \1.
V2 1}
Попробуем, как и ранее, найти биграмму из сравнения

жения f ( X) =

Tlgm: @it_boooks

Глава 3. Шифрующие матрицы

102

Поскольку А = 1 -1 —2 - 5 = 1 — 10 = - 9 , и (-9 , 33) ^ 1, то для
( 1 5\
матрицы I
I обратной матрицы не существует, и решить сравнение
\2 1 )
первым способом не представляется возможным.
Что даст второй способ? Запишем сравнение в виде системы сравнений:

{

х + 5у = 1 (mod 33),
2х + у = 5 (mod 33).

Проведя несложные преобразования, получим сравнение - 9 у = 3 (mod 33).
Поскольку (—9,33) = 3, то данное сравнение имеет три решения:
у = 7,18, 29 (mod 33). Находя соответствующие х = 1 —5?/(mod 33), по­
лучим следующие возможности:
у = 7, 18, 29 (mod 33),
х = 32, 10, 21 (mod 33).
( 32 \

Это дает нам три вектора

V 7/

( 10 \

1,

\ 18/

/2 1
1,

\29,

J , и, следовательно, три

возможных варианта «ЯЖ», «ЙС», «ФЬ» расшифровки имеющегося в на­
шем распоряжении шифротекста.
3. Если же при использовании 33-буквенного русского алфавита и то-

5\

го же шифрующего отображения f ( X) = А • X с матрицей А = (I 1 1
\2 1 /
бьша получена биграмма «БД», то попытка ее дешифровки будет выгля­
деть следующим образом.
Как и ранее, попытка найти биграмму из сравнения

С

1 ) ■С

Н

У

(mod зз>

заставит нас убедиться в том, что обратной матрицы не существует и ре­
шить задачу первым способом не представляется возможным. При реше­
нии задачи вторым способом, записав сравнение в виде системы срав­
нений
х + 5у = 1 (mod 33),

{

2х + у = 4 (mod 33),

Tlgm: @it_boooks

3.1. Алгебра матриц и аффинные матричные криптосистемы

103

получим, после несложных преобразований, сравнение —9у = 2 (mod 33).
Поскольку (—9, 33) = 3, и 3 | 2 , то данное сравнение решений не имеет,
и дешифровать имеющуюся в нашем распоряжении биграмму не пред­
ставляется возможным. Видимо, в ходе шифрования произошел какойто сбой.

Чтобы с помощью аффинных матричных преобразований дешифро­
вать некоторое шифрованное сообщение, его следует разбить на биграммы
и построить последовательность Zi Z2Z i . .. Zm, состоящую из m числовых

( * Л1, . . . ,

( z™\
Zm = I
I биграмм шифротекста. Эту

t j

\ t mJ

последовательность можно рассматривать как 2 х ш матрицу Z , состоящую
из m векторов-столбцов, которые представляют биграммы шифротекста.
Таким образом, для дешифровки сообщения достаточно умножить
2 x 2 матрицу А~1 на 2 х m матрицу Z и, получив при этом 2 х ш матрицу
X = А~1 • Z, состоящую из числовых эквивалентов биграмм-векторов
открытого текста, перейти с ее помощью к исходному сообщению.
[Пример 3.1.6] Дешифруем сообщение «БЯЕБФХ», полученное при ис­

пользовании 33-буквенного русского алфавита и шифрующего преобра/2

3\

зования Z — А Х с матрицей А — I
). Для этого представим шиф\4 8 /
рованное сообщение «БЯЕБФХ» в виде последовательности трех векторов
/ 1\

I

(ъ \
I, I

(

/21 \

I, I

і 5 2і\

1. Составим из них 2 x 3 матрицу Z = I

\32/ V1/ V22/

)

V32122/

и осуществим нужное преобразование:

770 34

570
(mod 33).

,576 177 1046/

V 15 12 23 /

Рассматривая вектора-столбцы I/ 11 \I , I/ М 1 ,1I 9 \I полученной мат\ 15 /

\n j

\23)

рицы как числовые эквиваленты биграмм открытого текста, без труда
получим исходное сообщение «КОБЛИЦ».


Tlgm: @it_boooks

104

Глава 3. Шифрующие матрицы

Упражнения

(2Л

ЛЛ Используя 33-буквенный алфавит и матрицу А = I
Qlj
I , зашифруйV 5 8)
те слова «ЗАДАЧА»; «ПРИМЕР».

(5)

В 26-буквенном алфавите, используя матрицу А —

[

V? 8 )
руйте фразу «NOANSWER»; дешифруйте фразу «FWMDIQ».

] , зашиф-

( з ) В 26-буквенном алфавите, используя матрицу А — [
] и вектор
/ \
\3 8 /
/із\

4

7

констант В = I
I , зашифруйте следующие латинские фразы:
\2 /
a) «Alter ego» («Второе Я»);
b) «Caesarem decet stantem тогі» («Цезарю подобает умереть стоя»);
c) «Carmina morte carent» («Стихи лишены смерти»).

Проверьте результат, произведя расшифровку полученных шифротекстов.
(3) В 27-буквенном алфавите, используя матрицу А = і
/

\

V 7

Л з\

констант В = I

V 2/

4

) и вектор
8 /

7

I , зашифруйте следующие латинские фразы:

a) «АЬ aqua silente саѵе» («Остерегайся тихой воды»);
b) «Abeunt studia in mores» («Занятия накладывают отпечаток
на характер»);
c) «Alma mater» («Мать-кормилица»);
d) «Bis dat, qui cito dat» («Вдвойне дает, кто дает скоро»).

Проверьте результат, произведя расшифровку полученных шифротекстов.
(5) Зашифруйте в 33-буквенном алфавите, используя матрицу А = [
( Л

и вектор констант В = I

]

I , русские переводы латинских фраз, ис­

пользованных в предыдущих упражнениях. Проверьте результат, про­
изведя расшифровку полученных шифротекстов.

Tlgm: @it_boooks

3.1. Алгебра матриц и аффинные матричные криптосистемы

105

(б) Для шифрующего преобразования f ( X ) = А • X (mod N) постройте
обратное шифрующее преобразование, если


a) N = 29 н А = [

3\



;

d) N = 25 и А = [

\4 3 /
/15

;

\ 4 Ъ)

17\

( \

b) N = 26 и А = [
V4

9 /

/4 0

0 \

\0

21У

c) N = 4\ и А = I

3\

);

;

\ \

е) N = 16 и А = [
);
VI 2 /
(\
f) N = 29 и А = [

Ъ\

\4 3 /

Выбрав подходящий алфавит, зашифруйте и расшифруйте в каждом
из случаев сообщение, числовой эквивалент которого имеет вид « 11
10 12 8 12 15 14 10 10 13». Зашифруйте и расшифруйте собственную
фразу, записанную в соответствующем алфавите.
( і ) Найдите биграмму [
\У/

j открытого текста из сравнения:

Tlgm: @it_boooks

Глава 3. Шифрующие матрицы

106

е) С -и =(!)'

В каждом из случаев, выбрав подходящий алфавит, расшифруйте со­
общение «ABCDEFG». Зашифруйте и расшифруйте придуманное вами
сообщение.
(§) Пользуясь 30-буквенным русским алфавитом (И и Й, Е и Ё, Ь и Ъ
отождествлены), дешифруйте биграмму f ( X ) , которая была получена
с помощью аффинного матричного преобразования
f ( X ) = А - Х + В (mod 30), если
a ) Л = ^ 2 4

В =

> f (x ) = «МА»;

b) Л = ^ * 3 ^ , Б = ^ 7 ^ , f ( X ) = «ПЫ»;

с> (Г1)’ (о)’/(х)=

«л и »;

^ А=( 5 §) ’В= (о) ’/(Х)=:
е>А= (і9 іо) ’В =(4 ) ’/(Х)=;
f ) A = ( 9 2 ),B=l

g) А = ^

),В=[

-

I , f ( X ) — «КО»;

0

) , / ( * ) = «ЗЫ».

Получили ли вы дешифровку; однозначную дешифровку? Почему?
В каждом из случаев придумайте пример сообщения, допускающего
однозначную расшифровку; сообщения, которое не может быть рас­
шифровано в указанных условиях.

Tlgm: @it_boooks

3.1. Алгебра матриц и аффинные матричные криптосистемы

107

Задачи

ПП Докажите, что для множества аффинных матричных преобразований
над одним и тем же алфавитом выполняются следующие утверждения:
a) композиция матричных сдвигов является матричным сдвигом;
b) композиция линейных матричных преобразований является ли­
нейным матричным преобразованием;
c) композиция аффинных матричных преобразований является аф­
финным матричным преобразованием.

(а ь\

Пусть А = I
I £ M2(Ztv) и А = ad — be — определитель этой
\с dj
матрицы. Докажите, что следующие утверждения эквивалентны:

a) (A , N )

= I;

b) Матрица А имеет обратную;
c) Если хотя бы один из элементов х, у £

отличен от нуля, то

d) Матрица А задает взаимно-однозначное отображение множества
ZN х
на себя.
[з] Найдите биграмму

открытого текста из сравнения:

Tlgm: @it_boooks

Глава 3. Шифрующие матрицы

108

(mod 25);

(mod 25).
[4] Числа Фибоначчи определяются правилами u\ = Ui — 1, un+\ = u n + un-\
при n > 1. Докажите, что в матричной форме это правило может быть
записано в виде

( ^П+І

\
Щ і-1 /

( 1 1\

\ 1 0 /,

Используя определение чисел Фибоначчи в матричной форме, до­
кажите, что ип четно тогда и только тогда, когда п делится на 3;
докажите, что ип делится на а тогда и только тогда, когда п делится
на Ь, если a = 2, Ъ — 3; a = 3, b — 4; a = 5, b = 5; a = 7, b = 8;
a = 8, 6 = 6; а = 11, Ь — 10.
[5| Постройте первые двадцать чисел Фибоначчи. Постройте матрицы
^п+І

.. ,

для п — 1, 2,..., 19, пользуясь уже известными значе-

ниями чисел Фибоначчи. Осуществите построение указанных матриц
последовательным умножением уже имеющейся матрицы на матрицу

Tlgm: @it_boooks

3.1. Алгебра матриц и аффинные матричные криптосистемы

109

(I 1 М 1. Какой способ удобнее? Можно ли использовать полученные
\1 О/
матрицы для построения аффинных матричных отображений? Можно

(

Ѣі+l Un

\I

при произволь-

un Un—
iJ
ном задании параметра п? Почему?
[б] Осуществите шифрование биграммы «ОХ», записанной в 33-буквенном
русском алфавите, с помощью аффинного матричного отображения
г/ ѵ \
( un+1 un \
да) —I
I А, где п — ваш номер в списке группы, a un —
\ Un Un—\ )
n-e число Фибоначчи.
0 Пусть N, М G N, и (ІѴ, М) = 1. Убедитесь в том, что любую матрицу
A G M 2(Zn) м о ж н о вложить в множество М 2(Ъм) простым приведе­
нием элементов по модулю М. Приведите примеры таких вложений.
\Й\ Пусть N = m n, где (т ,гі) — 1. Пусть Ат G М2(Zm) — матрица,
полученная путем приведения элементов матрицы Л по модулю т ,
и і „ G M2(Zn) — матрица, полученная путем приведения элементов
матрицы А по модулю п.
a) Докажите, что отображение, сопоставляющее матрице А пару
(Ат,А п), является взаимно-однозначным соответствием между
множеством M 2(ZN) и декартовым произведением M2(Zm)x M 2(Zn)
множеств M2(Zm) и M2(Zn). Приведите примеры.
b) Докажите, что это отображение задает взаимно-однозначное со­
ответствие между множеством М^{Ъ^) обратимых 2 x 2 матриц с
элементами из ZN и декартовым произведением М \(Zm) х М^С^п)
множества M |(Z m) обратимых 2 x 2 матриц с элементами из Zm
на множество М\ (Zn) обратимых 2 x 2 матриц с элементами из Zn.
Приведите примеры.
[9] Найдите число элементов множества M2(ZP), где р — простое число.
Подсчитайте число решений в Ъѵ уравнения ad —be — 0. Докажите,
что число