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

Теоретико-числовые алгоритмы в криптографии и 
их трудоемкость. 
Сравнение трудоемкости арифметических операций, 
используемых в криптосистемах. Полиномиальные 
алгоритмы, вероятностные алгоритмы. Распознавание 
простоты числа. Псевдопростые числа. Факторизация 
натуральных чисел. Вскрытие системы RSA.
2 8 6 16 
Проведенный выше обзор был призван продемонстрировать 
возможности разработанной нами модульной структуры дисциплины МСЗИ.

---

122 
3.2. Опытно-экспериментальное обучение студентов основам защиты 
информации 
При реализации дидактической модели профессионально направленной 
профессионально направленной математической подготовки учителей 
информатики при обучении методам и средствам защиты информации нами 
проводились лекции, семинары, ЛИР, осуществлялся поэтапный контроль 
уровня сформированности ППК дисциплины МСЗИ. Остановимся на 
вопросах практической реализации этих видов деятельности в процессе 
изучения дисциплины МСЗИ. 
3.2.1. Лекционные занятия проводились в классической форме. 
Отметим лишь тот факт, что в случае изучения базовой математической 
дисциплины (например, теории чисел) обычно реализуется схема, условно 
называемая «от теории к практике».
Теория чисел 
МСЗИ 
Рис. 3.2.1. Сравнительные схемы представления лекционного материала 
В нашем случае выраженный прикладной характер дисциплины 
обуславливает реализацию иной схемы, в которой сначала мы ставим 
практическую задачу, далее приводим необходимые сведения из различных 
Теория 
Практи
ческая 
задача
Практи
ческая 
задача
••• 
Прило
жение
теории 
Прило
жение 
теории 
Практическая 
задача 
Теория 1 
Теория 2 
Прило
жение 
теории 
1
Прило
жение 
теории
2 
Прило
жение
теорий 
1 и 2 
••• 

---

123 
теорий, а затем говорим, как отдельно каждую из теорий или их комбинацию 
можно применить к решению поставленной задачи (рис. 3.2.1). 
Наиболее яркими примерами реализации данной схемы являются 
лекции в рамках модулей М4, М6 и М7. Так, изучая модуль М4, мы 
формулируем задачу вскрытия системы RSA. Существуют различные 
направления поиска решения поставленной задачи (дискретный логарифм, 
факторизация модуля). Для решения задачи дискретного логарифмирования 
ученые также расходятся в разные стороны (теория индексов, алгоритмы 
согласования). В конечном результате, объединяют успехи различных 
направлений, создавая комбинированные методы, более эффективные для 
решения исходной задачи. Факторизация большого натурального числа, 
которая изучается в модуле М7, также вынуждает нас знакомить сначала с 
независимыми друг от друга теориями Ферма, Эйлера, теорией цепных 
дробей и теорией квадратичных форм, каждая из них предлагает свои 
интересные решения. Однако к вскрытию системы привело именно 
объединение этих идей в сложный вероятностный алгоритм, результат 
которого не является гарантированным.
При изложении этого материала на лекциях мы ставим задачу, затем 
отдельно излагаются теории и их успехи; на семинарах и ЛИР 
отрабатывается реализация этих подходов к решению задачи, оценка их 
эффективности. Только потом целесообразно знакомить студентов с 
результатом совместных усилий этих теорий. Отметим, что демонстрация 
именно этапов решения проблемы, взаимопроникновения идей из разных 
теорий является основной целью нашей дисциплины, как уже отмечалось 
ранее. Дело в том, что большинство рассматриваемых в курсе задач являются 
решенными только в некоторой степени (что существенно отличает 
дисциплину 
МСЗИ 
от 
давно 
сформировавшихся 
классических 
математических дисциплин), поиски новых эффективных решений ведутся в 
реальном времени, и наша задача - познакомить с основными 
направлениями, разрабатываемыми в этой области. 

---

124 
Исключение из представленной схемы составляет только изложение 
модуля М1, где нет необходимости знакомить со специальными теориями, а 
логика изложения выглядит как «задача → решение = новая задача → 
решение = новая задача→…», где каждое решение предыдущей задачи 
ставит задачу новую, например «есть шифр, нужен метод вскрытия → 
найден метод вскрытия, нужен новый шифр → и т.д». При этом модуль М1 
задает направление всей последующей содержательной линии «от задачи к 
решению». 
3.2.2. Как уже отмечалось, мы рассматриваем семинарские занятия как 
промежуточную форму между лекциями и ЛИР. Рассматривая некоторые 
теории, мы нуждаемся в возможности на практике увидеть реализацию 
изученного материала, чтобы в последующем студенты могли:
- рассмотреть возможные исходы применения теории; 
- спрогнозировать результат; 
- выбрать необходимое приложение; 
- скомбинировать действия из различных теорий. 
Для модуля М1 потребность в таких занятиях совсем отсутствует. 
Остальные модули содержат серьезную фундаментальную математическую 
составляющую, требующую отработки на семинарах. В таблице 3.2.1 
представлены темы, которые необходимо отработать в рамках каждого 
модуля, и примеры соответствующих заданий. 
Таблица 3.2.1. 
Темы и задачи для семинаров по дисциплине МСЗИ 
Модуль Тема 
Надо отработать 
Примеры заданий 
М2 
Линейные 
сравнения 
и 
системы линейных 
сравнений. 
Решение систем 
сравнений, 
теорема 
о 
разрешимости 
линейных 
сравнений.
1) Решите систему сравнений: 
⎩
⎨
⎧
≡
−
−
≡
−
+
)
9
(mod
0
2
8
5
)
9
mod
(
0
1
4
y
x
y
x
.
2) Для любого натурального а решите 
сравнение:
)
1
3
(mod
1
)
2
(
2
2
+
+
≡
+
a
a
x
a
a
М3 
Матрицы 
над 
кольцом классов 
вычетов. 
Нахождение 
обратных матриц. 
Решение 
сравнений 
с 
1)Найдите обратную матрицу по модулю 
26 для А=
⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
9
4
17
15
. 

---

М4 
М5 
М6 
М7 
М8 
учеб
теор
обус
коне
Теор
Теор
Врем
слож
алго
Псев
числ
Мет
факт
Коне
Мно
коне