Котова лидия Владимировна

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

---

мето
сист
Р
стан
возн
мате
треб
пере
иссл
возн
во в
выч
крип
пост
знак
бурн
зада
М7. Ф
оды фак
темы RSA
Рис. 2.2.1. С
Изучен
новления 
никновени
ематическ
бования, 
еход от 
ледованию
никшими 
всех сфер
числитель
птографи
тоянному
комит с м
но развив
ач крипто
•
ФАКТОР
кторизаци
A. 
Содержате
ние дисци
криптогр
ия шиф
ких наук
предъявл
взлома
ю. Моду
в конце п
рах нашей
ьных ме
ических 
у поиску н
методами
вающими
оанализа 
• Задачи, в
кающие п
криптоан
• Историч
предпос
• Этапы 
становле
ИЗАЦИЯ
ии. Совр
ельные связ
иплины н
рафии как
фров, их
к. Модули
ляемые к 
а шифро
уль М4 з
прошлого
й жизни. 
етодов 
систем и
новых алг
и фактори
ися в наст
современ
озни-
при 
нализе
ческие 
сылки
ения
М
М
69
Я НАТУ
ременные
зи между б
начинаетс
к науки, 
х соверш
и М2, М3
классиче
ов к кр
знакомит 
о столетия
Быстрое
требуют
и методо
горитмов
изации, н
тоящее вр
нных сис
М1
М7
9 
УРАЛЬНЫ
е методы
базисными 
ся с исто
историю 
шенствов
3 позволя
еским ши
риптоанал
с совре
я и испол
е развитие
постоя
ов их в
в, что отр
начиная с
ремя мето
стем защ
М2,3
М4
ЫХ ЧИС
ы фактор
модулями 
рии вопр
термино
ание вс
яют оцен
ифрам, и 
лизу как
еменными
льзуемым
е вычисл
янного 
вскрытия.
ажено в м
с классич
одами, воз
щиты инф
•
• Соврем
крипто
• Матем
е осно
• Прост
крипт
СЕЛ. Кл
ризации. 
дисциплин
роса, осве
логии, пр
следствие
нить мате
тем сам
к матем
и крипто
и в насто
лительной
соверше
. Это п
модуле М
ческих и 
зникающи
формации
менные 
осистемы
матически
овы
тейшие 
тосистемы
лассическ
Вскрыт
ны МСЗИ
ещая этап
редпосыл
е развит
матическ
ым, поня
атическом
осистемам
оящее вре
й техники
енствован
приводит 
М7, которы
заканчив
ими в све
и. Нагляд
кие 
тие 
пы 
лки 
тия 
кие 
ять 
му 
ми, 
мя 
и и 
ния 
к 
ый 
вая 
ете 
дно 

---

70 
схема содержательных связей между базисными модулями представлена на 
рисунке 2.2.1.
2.2.2.
 
Первый модуль М1 не требует специальной математической 
подготовки и может выступать как самостоятельный раздел в рамках 
дисциплины по выбору; он может быть интересен студентам любого профиля 
направления 
подготовки 
Педагогическое 
образование, 
как 
естественнонаучного, так и гуманитарного. 
В рамках модуля изучаются: история терминологии; классификация 
шифров; шифры подстановки (простой замены); способ раскрытия шифра 
простой замены на основе частотного анализа; усовершенствованные: 
таблица Виженера, шифр аббата Тритемиуса, шифр «по книге»; шифры 
перестановки: скитала, маршрутная транспозиция, решетка Кардано; 
представление шифров замены и подстановки в виде функций; 
криптостойкость; использование классических шифров при составлении 
олимпиадных задач по математике, информатике и криптографии для 
школьников.
М1
Курсовые 
работы
Профессиональная 
деятельность
ОП
Познакомить с 
постановкой задачи 
защиты 
информации с 
историческими и 
эволюционными 
аспектами 
становления 
современных 
криптосистем
Требования к подготовке 
Школьные курсы математики и информатики, начала 
теории чисел
Т
Рассмотреть 
теоретические 
задачи, 
возникающие в 
связи с 
потребностью 
усовершенство-
вания
существующих 
криптосистем
Т
И
зучить теорию 
построения 
классических
криптосистем, 
методы 
криптоанализа
П
Продемонстриро
вать 
практическое 
применения 
разделов, 
изученных в 
курсах теории 
чисел и алгебры
ОП
Показать 
возможные 
направления для 
разработки курсов 
по выбору, 
факультативных и 
занятий по 
математике и 
информатике
ВКР
М2, М3, 
М4, М8
Рис. 2.2.2. Цели и перспективы изучения модуля М1

---

71 
Основные характеристики модуля представлены на рисунке 2.2.2. Цели 
изучения модуля имеют ярко выраженные теоретические, прикладные и 
общепрофессиональные аспекты. 
Таким образом, внешними ППК изучения модуля являются знания 
школьного курса математики и, возможно, основ теории чисел (достаточно в 
объеме школьного факультативного курса). 
Актуальными внутренними ППК дисциплины являются для данного 
модуля ТППК-1, ТППК-2, ТППК-3, ПППК-1, ПППК-5, ПППК-6, ОПППК-4, 
ОПППК-5.
Уточняя их, мы получаем следующие ТППКМ1, ПППКМ1 и 
ОПППКМ1 модуля М1: 
- знает теорию построения классических криптосистем, методы 
криптоанализа (
ТППКМ1-1
);
- способен рассматривать теоретические задачи, возникающие в связи с 
потребностью усовершенствования существующих криптосистем (
ТППКМ1-
2
);
- знает практическое применение разделов, изученных в курсах теории чисел 
и алгебры (
ПППКМ1-1
); 
- знаком с постановкой задачи защиты информации с историческими и 
эволюционными аспектами становления современных криптосистем 
(
ОПППКМ1-1
);
- знает возможные направления для разработки школьных факультативных и 
внеклассных занятий по математике и информатике (
ОПППКМ1-2
).
Примеры заданий, предлагаемых в рамках изучения М1. 
• 
Найдите число различных ключей для решетки Кардано n×n для 
любого четного n. 
• 
Можно ли соединить телефонными проводами 993 абонента так, 
чтобы каждый имел связь ровно с 99 другими абонентами? 
• 
В каком случае будет легче восстановить текст зашифрованного 
сообщения, полученного простой заменой: если угадано второе слово второй 

---

72 
строки – ТРАЕКТОРИЯ; или если угадано третье слово третьей строки – 
КАРИКАТУРА? 
• 
Определите, какой из сейфов надежнее, если 1-ый имеет 80 
переключателей по 3 положения каждый; 2-ой имеет 6 переключателей с 60 
положениями у каждого? 
В качестве основной литературы студентам могут быть предложены 
разработанные на кафедре теории чисел математического факультета МПГУ 
пособия: Нечаев В.И. «Элементы криптографии. Основы теории защиты 
информации» [129]; Деза Е.И., Котова Л.В. «Теоретико-числовые основы 
защиты информации» [84].
Широчайший спектр дополнительной литературы может быть 
представлен работами [8], [10], [11], [20], [29], [32], [33], [42], [52], [57], [58], 
[65], [82], [97], [98], [131], [151]. 
Модуль М2 формирует математическую базу, необходимую для 
построения простейших криптосистем.
Для изучения данного модуля требуется знание основных разделов 
теории чисел; (внешние ППК). Внутренними ППК дисциплины являются для 
данного модуля ТППК-1, ТППК-2, ТППК-4, ПППК-1, ПППК-5, ПППК-6, 
ОПППК-2, ОПППК-3, ОПППК-4, ОПППК-5. 
Уточняя их, мы получаем следующие ТППКМ2, ПППКМ2 и ОПППКМ2 
модуля М2: 
- знает принцип работы симметричных криптосистем (ТППКМ2); 
- способен использовать приложения изученных в теории чисел разделов 
(ПППКМ2);
- способен использовать новые знания для организации проектной 
деятельности школьников, для их подготовки к тематическим олимпиадам 
(ОПППКМ2).
В теоретических заданиях модуля уточняются возможные параметры 
систем шифрования. В прикладных заданиях требуется применение 
теоретических знаний к решению конкретных задач. В качестве заданий 

---

73 
общепрофессионального 
направления 
могут 
использоваться 
задачи 
школьных олимпиад по криптографии и математике. При этом в решении 
таких задач школьникам (как и студентам) могли бы очень пригодиться 
сведения из теории сравнений. Таким образом, перед будущими учителями 
возникает возможность проанализировать дополнительный материал, 
который может быть предложен школьникам для помощи в подготовке к 
олимпиадам. 
В рамках модуля М2 изучаются: основные элементы криптосистемы 
(алфавит, элементы шифротекста (биграммы, k-граммы), шифрующее 
преобразование); 
аффинные 
отображения; 
условие 
однозначности 
отображения; 
частные 
случаи 
(сдвиг, 
линейное 
преобразование); 
дешифрование аффинных криптосистем; взаимосвязь шифрующих и 
дешифрующих ключей; принцип Керкгоффса; криптоанализ аффинных 
криптосистем. 
Для изучения модуля необходимы знания в области начал теории 
чисел. Однако возможно использование теоретического введения, не 
требующего больших временных затрат. Содержание модуля опирается на 
теорию сравнений, изученную студентами в рамках курса теории чисел. Для 
решения задач по дешифрованию аффинных криптосистем с биграммами 
необходимо вспомнить основные методы решения сравнений и систем 
сравнений первой степени, научиться решать системы сравнений первой 
степени от двух переменных по составному модулю. 
Отметим, что здесь и далее мы приводим примеры только 
теоретических 
и 
прикладных 
заданий, 
в 
то 
время 
как 
общепрофессиональным заданиям уделим отдельное внимание в третьей 
главе. 
Примеры Т-заданий. 
• 
Сколько можно составить различных линейных преобразований 
для алфавита, содержащего N символов? 

---

74 
• 
Найдите обратное аффинное преобразование для преобразования 
f (P) ≡ А·Р + b(mod N) при N=33, А=7 , b=20. 
• 
Пусть элементами сообщения являются биграммы N-буквенного 
алфавита. Найдите формулу для числа различных аффинных шифрующих 
преобразований. Сколько их при N = 26, 27, 33?
Примеры П-заданий. 
• 
Зашифруйте фразу «аффинные криптосистемы», используя 
аффинное преобразование для 34-буквенного алфавита ([А; Я] = [0; 32], 
пробел = 33) с ключами A=13, b=10. 
• 
Расшифруйте сообщение 
«ЯКОХЖУМВКАЩ?-ХЩ»
, если известно, 
что первым словом является «Я», за ним следует пробел, при шифровании 
использовали алфавит из 41 символа (буквы A – Я (0-32), пробел (33), знаки 
препинания: «
.
», «
,
»,
«
-
»,«
;
»,
«
:
», «
!
».
«
?
» (34 - 40))
.
Модуль М2 может выступать в качестве прикладного раздела при 
изучении теории чисел. Решение теоретических задач модуля может не 
только продемонстрировать применимость различных разделов теории 
чисел, но и помочь глубже в них разобраться. Приведем примеры таких 
задач. 
• 
Докажите, что для одного алфавита композиция двух 
шифрующих сдвигов является сдвигом. 
• 
Элемент P называют неподвижным для шифрующего 
преобразования, если выполняется сравнение f (P) ≡ P (mod N). Докажите, 
что если N –
простое и преобразование не является сдвигом, то существует 
неподвижный символ и при этом только один. 
• 
При каких целых а сравнение 
)
30
(mod
3
≡
ax
разрешимо?
• 
Определите все целые значения параметра а, при которых 
разрешима система сравнений 
⎩
⎨
⎧
≡
+
≡
)
36
(mod
0
30
75
)
36
mod
(
20
8
a
x
x
. 
В качестве основной литературы студентам могут быть предложены 

---

75 
пособия: Деза Е.И., Котова Л.В. «Теоретико-числовые основы защиты 
информации» [84]; Коблиц Н. «Криптография и теория чисел» [74]. 
Дополнительная литература может быть представлена работами [3], 
[20], [24], [29], [30], [33], [36], [40], [42], [58], [61], [65], [97], [98], [99], [122], 
[142], [143].
В рамках модуля М3 изучаются: представление k-грамм в виде 
векторов; линейная алгебра по модулю N; существование обратной матрицы 
по модулю N; способы решений сравнений с биграммами; матричные 
аффинные преобразования; криптоанализ матричных криптосистем.
Для изучения данного модуля требуется знание основных разделов 
алгебры матриц и теории чисел (внешние ППК). Внутренними ППК 
дисциплины являются для данных модулей ТППК-1, ТППК-2, ТППК-4, 
ПППК-1, ПППК-5, ПППК-6, ОПППК-2, ОПППК-3, ОПППК-4, ОПППК-5. 
Уточняя их, мы получаем следующие ТППКМ3, ПППКМ3 и ОПППКМ3 
модуля М3: 
- знает принцип работы матричных криптосистем (ТППКМ3); 
- способен использовать приложения изученных в алгебре и теории чисел 
разделов (ПППКМ3);
- способен использовать полученные сведения для организации проектной 
деятельности школьников (ОПППКМ3).
Модуль демонстрирует междисциплинарные связи линейной алгебры и 
теории чисел. Для изучения необходимы знания из линейной алгебры: 
матрица, определитель, обратная матрица, матрица дополнений, вычисление 
обратной матрицы. Матричные криптосистемы показывают, как можно 
совершенствовать аффинные преобразования, увеличивая взаимосвязь 
элементов и сохраняя «малые вычисления». Задачи, решаемые в рамках 
модуля, часто имеют формулировки, аналогичные задачам модуля М2, что 
позволяет сравнить их, проанализировать значимость внесенных изменений. 
Примеры Т-заданий. 

---

76 
• Сколько различных квадратных матриц по модулю 2N дает матрица по 
модулю N? 
• Докажите, что композиция линейных матричных шифрований по 
одному модулю также является линейным матричным шифрованием по 
данному модулю. 
Примеры П-заданий. 
• Матричное линейное шифрующее преобразование включает 33 буквы 
русского алфавита, занумерованные соответственно положению в алфавите 
(0-32). Вам известно, что при данном шифровании биграммы «ИВ» и «ЕТ» 
переходят соответственно в биграммы «РЧ» и «ОБ». Вскройте сообщение
«З П Д З Ч О».
В качестве основной литературы студентам могут быть предложены 
пособия: Деза Е.И., Котова Л.В. «Теоретико-числовые основы защиты 
информации» [84];
Коблиц Н. «Курс теории чисел и криптографии» [74]. 
Дополнительная литература может быть представлена работами [3], 
[29], [30], [36], [40], [58], [61], [83], [97], [98], [99], [122].
В случае, если у студентов отсутствовала необходимая подготовка по 
теории чисел или алгебре, им может быть предложен дополнительный 
модуль М0, содержащий необходимые теоретические сведения (рис. 2.2.3).