1. Цели и задачи дисциплины: Дисциплина "Теоретико-числовые методы в криптографии" реализует требования федерального государственного образовательного стандарта высшего профессионального образования по направлению подготовки 090301 «Компьютерная безопасность».

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

Дисциплина "Теоретико-числовые методы в криптографии" относится к числу прикладных математических дисциплин в силу отбора изучаемого материала и его важности для подготовки специалиста. Во всех разделах дисциплины большое внимание уделяется построению алгоритмов для решения практических задач.

Задачами дисциплины являются:

- четкое осознание необходимости и важности математической подготовки для специалиста по компьютерной безопасности,

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

- умение давать строгую с математической точки зрения оценку применяемых алгоритмов.

Таким образом, дисциплина "Теоретико-числовые методы в криптографии" является неотъемлемой составной частью профессиональной подготовки по направлению подготовки 090301 «Компьютерная безопасность». Вместе с другими дисциплинами цикла профессиональных дисциплин изучение данной дисциплины призвано формировать специалиста, и в частности, вырабатывать у него такие качества, как:

- строгость в суждениях,

- творческое мышление,

- организованность и работоспособность,

- дисциплинированность,

- самостоятельность и ответственность.

2. Место дисциплины в структуре ООП:

Дисциплина принадлежит циклу профессиональных дисциплин.

Дисциплина "Теоретико-числовые методы в криптографии" основывается на знаниях, полученных при изучении дисциплин

· «Математический анализ»,

· «Алгебра».

· «Теория вероятностей»

Знания, полученные при изучении дисциплины "Теоретико-числовые методы в криптографии", используются при изучении дисциплин

· Криптографические методы защиты информации,

· Криптографические протоколы.

3. Требования к результатам освоения дисциплины:

Процесс изучения дисциплины направлен на формирование следующих компетенций:

общекультурные компетенции:

способность понимать социальную значимость своей будущей профессии, цели и смысл государственной службы, обладать высокой мотивацией к выполнению профессиональной деятельности в области обеспечения информационной безопасности, защиты интересов личности, общества и государства, готовностью и способностью к активной состязательной деятельности в условиях информационного противоборства (ОК-5);

способность логически верно, аргументировано и ясно строить устную и письменную речь на русском языке, готовить и редактировать тексты профессионального назначения, публично представлять собственные и известные научные результаты, вести дискуссии (ОК-7);

способность к логически-правильному мышлению, обобщению, анализу, критическому осмыслению информации, систематизации, прогнозированию, постановке исследовательских задач и выбору путей их решения на основании принципов научного познания (ОК-9);

профессиональные компетенции:

способностью применять математический аппарат, в том числе с использованием вычислительной техники, для решения профессиональных задач (ПК-2);

способностью применять достижения современных информационных технологий для поиска и обработки больших объемов информации по профилю деятельности в глобальных компьютерных системах, сетях, в библиотечных фондах и в иных источниках информации (ПК-3)

способностью учитывать современные тенденции развития информатики и вычислительной техники, компьютерных технологий в своей профессиональной деятельности (ПК-7);

способностью к самостоятельному построению алгоритма, проведению его анализа и реализации в современных программных комплексах (ПК-12);

В результате изучения дисциплины студент должен:

Знать:

− строение мультипликативной группы колец вычетов;

− способы представления действительных чисел цепными дробями;

− основные свойства символов Лежандра и Якоби,

− критерии простоты и их использование для факторизации натуральных чисел;

− алгоритмы проверки чисел на простоту; построения больших простых чисел;

− алгоритмы разложения чисел и многочленов на множители,

− методы дискретного логарифмирования в конечных циклических группах;

− основные свойства групп точек эллиптических кривых.

Уметь:

− исследовать и решать системы сравнений по произвольному модулю;

− представлять действительные числа цепными дробями;

− строить большие простые числа,

− применять алгоритмы проверки чисел на простоту; построения больших простых чисел;

− применять алгоритмы разложения чисел и многочленов на множители,

Владеть:

− навыками применения теории чисел в криптографии и других дисциплинах;

− навыками применения основных вычислительных алгоритмов в кольцах вычетов и кольцах многочленов .

4. Объем дисциплины и виды учебной работы

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

Вид учебной работы	Всего часов / зачетных единиц	Семестры
Вид учебной работы	Всего часов / зачетных единиц	6
Аудиторные занятия (всего)	78	78
В том числе:
Лекции	40	40
Практические занятия (ПЗ)	34	34
Семинары (С)	-
Лабораторные работы (ЛР)	-
Контрольные работы (КР)	4	4
Самостоятельная работа (всего)	30	30
В том числе:	-	-
Курсовой проект (работа)	-
Расчетно-графические работы	-
Реферат	-
Другие виды самостоятельной работы	30	30
Вид итоговой аттестации (экзамен)	36	36
Общая трудоемкость часы зачетные единицы	108+36	108+36
Общая трудоемкость часы зачетные единицы	3+1	3+1

5. Содержание дисциплины

5.1. Содержание разделов дисциплины

Раздел 1. Основы теории чисел

Тема 1. Введение.

1.1. Место теории чисел среди других математических дисциплин. Приложения теории чисел. Краткая история развития теории чисел. Литература по дисциплине.

Тема 2. Арифметика колец вычетов

2.1. Вычисления в кольце целых чисел. Алгоритм Евклида и его сложность.

2.2. Вычисления в кольцах вычетов. Китайская теорема об остатках. Алгоритм Монтгомери.

2.3. Строение мультипликативной группы кольца вычетов. Критерий цикличности. Первообразные корни.

2.4. Квадратичные вычеты и невычеты. Квадратичный закон взаимности. Символы Лежандра и Якоби, их свойства. Алгоритмы вычисления символа Лежандра.

2.5. Решение степенных и показательных сравнений.

Тема 3. Цепные дроби

3.1. Понятие конечной и бесконечной цепной дроби. Подходящие дроби и их свойства.

3.2. Представление действительных чисел цепными дробями. Теорема Лагранжа о представлении квадратичных иррациональностей периодическими цепными дробями.

3.3. Цепные дроби как наилучшие рациональные приближения действительных чисел.

Тема 4. Простые числа

4.1. Частные виды простых чисел: простые числа Ферма и Мерсенна, их свойства.

4.2. Критерии простоты. Необходимые условия простоты.

4.3. Вопросы распределения простых чисел в натуральном ряду. Теорема Чебышева и асимптотический закон распределения простых чисел.

4.4. Алгоритмы проверки чисел на простоту. Тесты Соловея-Штрассена и Миллера-Рабина. Методы построения больших простых чисел.

Раздел 2. Прикладные вопросы теории чисел

Тема 5. Методы разложения чисел на множители

5.1. Алгоритмы экспоненциальной сложности. Метод Ферма и его модификации. Вероятностный алгоритм факторизации Полларда. Алгоритм факторизации Полларда-Штрассена.

5.2. Субэкспоненциальные алгоритмы, основанные на идее метода Ферма. Алгоритм Диксона. Оценка сложности алгоритма Диксона. Алгоритм Брилхарта-Моррисона. Метод квадратичного решета Померанца.

5.3. "р-1" и "р+1" - методы разложения.

5.4. Криптографическая система RSA и основы ее анализа.

Тема 6. Вычисления в кольцах многочленов

6.1. Алгоритмы нахождения значений многочленов, произведения многочленов.

6.2. Использование быстрых преобразований Фурье для нахождения произведения многочленов.

Тема 7. Методы дискретного логарифмирования.

7.1. Методы логарифмирования в произвольной циклической полугруппе. Алгоритмы Полларда, А.О.Гельфонда, В.И.Нечаева.

7.2. Индекс-метод Вестерна-Миллера для логарифмирования в простом поле и поле малой характеристики.

7. 3. Метод Копперсмита логарифмирования в поле малой характеристики.

7.4. Криптографические системы, построенные на основе задачи дискретного логарифмирования: ключевой обмен Диффи и Хеллмана, системы открытого шифрования и цифровой подписи Эль-Гамаля и их анализ.

Тема 8. Элементы криптографии на эллиптических кривых

8.1. Эллиптические кривые. Группа точек эллиптической кривой. Применение эллиптических кривых при построении криптосистем.

8.2. Применение аппарата теории эллиптических кривых к проверке простоты и факторизации целых чисел.

5.2 Разделы дисциплины и междисциплинарные связи с обеспечиваемыми

(последующими) дисциплинами

№ п/п	Наименование обеспечиваемых (последующих) дисциплин	№ разделов данной дисциплины, необходимых для изучения обеспечиваемых (последующих) дисциплин
№ п/п	Наименование обеспечиваемых (последующих) дисциплин	1	2
1.	Криптографические методы защиты информации	+	+
2.	Криптографические протоколы	+	+

5.3. Разделы дисциплин и виды занятий

№ п/п	Раздел дисциплины	Лекции	ПЗ	КР	С	СРС	Всего час.
1.	Основы теории чисел	20	18	2	¾	15	55
2.	Прикладные вопросы теории чисел	20	16	2	¾	15	53

6. Лабораторный практикум

№ п/п

№ раздела дисциплины

Наименование лабораторных работ

Трудо-емкость

(часы/зачетные единицы)

Не предусмотрен

…

7. Практические занятия (семинары)

№ п/п	№ раздела дисциплины	Тематика практических занятий (семинаров)	Трудо-емкость (час.)
1.	1	Свойства функций оценки сложности. Сложность арифметических операций в кольце целых чисел	2
2.	1	Вычисления в кольце целых чисел и в кольце матриц	2
3	1	Вычисления в кольцах вычетов, китайская теорема об остатках	2
4	1	Применения алгоритма быстрого преобразование Фурье. Вычисление в конечных полях	2
5	1	Исследование разрешимости и решение квадратичных сравнений	2
6	1	Непрерывные (цепные) дроби	2
7	1	Приближение действительных чисел цепными дробями	2
8	1	Распределение простых чисел. Теорема Чебышева.	2
9	1	Изучение свойств мультипликативной группы кольца вычетов.	2
10	2	Вероятностные алгоритмы проверки чисел на простоту. Применение достаточных условий простоты к построению больших простых чисел.	2
11	2	Экспоненциальные алгоритмы разложения целых чисел на множители	2
12	2	Субэкспоненциальные алгоритмы разложения целых чисел на множители.	2
13	2	Алгоритмы нахождения значений многочленов, произведения многочленов. Использование быстрых преобразований Фурье для нахождения произведения многочленов	2
14	2	Экспоненциальные алгоритмы дискретного логарифмирования	2
15	2	Субэкспоненциальные алгоритмы дискретного логарифмирования	2
16	2	Изучение свойств группы точек эллиптической кривой.	2
17	2	Алгоритмы проверки простоты и факторизации целых чисел, использующие эллиптические кривые.	2

8. Примерная тематика курсовых проектов (работ)

Курсовые работы не предусмотрены.

9. Учебно-методическое и информационное обеспечение дисциплины:

а) основная литература

1. Глухов М. М., Круглов И. А., Пичкур А. Б., Черемушкин А. В. Введение в теоретико-числовые методы криптографии. – СПб:»Лань», 2010

2. Коблиц Н. Курс теории чисел и криптографии. – М.: ТВП, 2001. – 262 с.

3. Виноградов И.М. Основы теории чисел. – СПб.: «Лань», 2004. – 176 с.

4. Черемушкин А. В. Лекции по арифметическим алгоритмам в криптографии. – М.: МЦНМО, 2002. – 104 с.

б) дополнительная литература

1. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. – Москва – Санкт-Петербург – Киев: Издательский дом «Вильямс», 2001. – 384 с.

2. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. – М.: МЦНМО, 2007.

3. Ростовцев А. Г. Алгебраические основы криптографии. – СПб.: НПО «Мир и семья», ООО «Интерлайн», 2000. – 354 с.

5. Нестеренко Ю.В. Теория чисел: учебник для студентов высших учебных заведений. – М.: Издат. центр «Академия», 2008. – 272 с.

6. Гашков С.Б., Чубариков В.Н. Арифметика, алгоритмы, сложность вычислений. Учебное пособие. — М.: Высшая школа, 2000.

7. Ноден П., Китте К. Алгебраическая алгоритмика. С упражнениями и решениями. — М.: Мир, 1999.

8. Акритас А. Основы компьютерной алгебры с приложениями. — М.: Мир, 1994

9. Саломаа А. Криптография с открытым ключом. — М.: Мир, 1996.

в) программное обеспечение

не предусмотрено

г) базы данных, информационно-справочные и поисковые системы

· вузовские электронно-библиотечные системы учебной литературы.

· база научно-технической информации ВИНИТИ РАН

Электронно-библиотечная система должна обеспечивать возможность индивидуального доступа для каждого обучающегося из любой точки, в которой имеется доступ к сети Интернет.

10. Материально-техническое обеспечение дисциплины:

компьютерный класс для выполнения домашних заданий с использованием пакетов прикладных программ

11. Методические рекомендации по организации изучения дисциплины:

Примерным учебным планом на изучение дисциплины отводятся один семестр. В конце семестра в качестве итогового контроля предусмотрен экзамен. На подготовку и сдачу экзамена в соответствии с ФГОС ВПО и примерным учебным планом выделяется 36 часов.

Методические указания для преподавателя по проведению основных видов занятий по дисциплине.

Лекция является одним из важнейших видов учебных занятий. Ее основное назначение – дать систематизированные основы научных знаний по дисциплине, раскрыть содержание, закономерности и тенденции развития изучаемого предмета, рекомендовать методику применения теоретических знаний на практике, сконцентрировать внимание слушателей на наиболее сложных и узловых вопросах, стимулировать их активную познавательную деятельность, формировать творческое мышление и потребность в самообразовании.

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

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

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

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

В качестве средств для текущего контроля успеваемости и промежуточной аттестации студентов рекомендуются:

− Индивидуальные долгосрочные задания. Студенту предлагается самостоятельно решить некоторые задачи, которые не задавались в виде домашнего задания. По итогам выполнения индивидуального долгосрочного задания преподаватель выставляет студенту дополнительную оценку.

− Проведение на практических занятиях письменных 10 минутных контрольных опросов для всех студентов.

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

В соответствии со спецификой ВУЗа в процессе преподавания дисциплины методически целесообразно в каждом разделе выделить наиболее важные темы и акцентировать на них внимание обучаемых.