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

3. Тематический план изучения дисциплины

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

1. Введение в математические основы криптографии.
2. Основы теории чисел. Делимость, простые числа, наибольший общий делитель. Алгоритм Евклида, расширенный алгоритм Евклида.
3. Цепные дроби. Асимптотический закон распределения простых чисел. Мультипликативные функции. Функция Эйлера.
4. Теория сравнений. Полная система вычетов, приведенная система вычетов. Z_n, Z_p.
5. Обратный элемент в Z_n Алгебраические структуры на целых числах - Z_n, Z_p.
6. Теорема Эйлера, теорема Ферма, тест Ферма на простоту. Криптосистема RSA. Понижение степени сравнения.
7. Сравнения первой степени и их решение. Системы сравнений первой степени и их решение. Китайская теорема об остатках и ее применения в криптографии (схема разделения секрета на ее основе и ее применение в RSA).
8. Квадратичные сравнения. Символ Лежандра. Закон взаимности. Существование решений квадратичного сравнения по простому модулю. Решение квадратичных сравнений по простому модулю.
9. Символ Якоби и его свойства. Тест Соловея-Штрассена на простоту. Существование и количество решений квадратичного сравнения по составному модулю. Решение квадратичных сравнений по составному модулю.
10. Квадраты и псевдоквадраты. Проблема различения квадратов и псевдоквадратов, ее связь с задачей факторизации. Числа Блюма. BBS-генератор. Криптосистемы Блюма-Гольдвассер, Гольдвассер-Микали.
11. Циклическая группа Z*_p (U_p). Порождающий элемент и дискретный логарифм. Задача дискретного логарифмирования. Криптосистемы Диффи-Хэллмана и Эль-Гамаля.
12. Теоремы Сэлфриджа и Поклингтона. (n-1) – тесты на простоту. Доказуемо простые числа общего вида.
13. Числа Ферма, теорема Пепина, тест Пепина. Числа Мерсенна и тест Лукаса-Лемера. Теорема Диемитко и процедура генерации простых чисел ГОСТ Р34.10-94.
14. Конечные группы и поля многочленов. Многочлены над Z_p, Z_n. Сложение многочленов, умножение многочленов, разложение многочлена на сомножители. Неприводимые многочлены.
15. Элементы теории сложности. Оценки сложности по времени, по объему требуемой памяти. Полиномиальная сложность, субэкспоненциальная сложность, экспоненциальная сложность алгоритмов. Сложность элементарных операций. Теоретико-числовые проблемы, лежащие в основе двухключевых криптосистем – факторизация, дискретное логарифмирование.
16. Алгоритмы факторизации. Метод пробных делений, метод Ферма, метод квадратичного решета, ро-метод Полларда, p—1 – метод Полларда, методы случайных квадратов. Примеры, оценки сложности указанных алгоритмов.
17. Алгоритмы дискретного логарифмирования. Метод прямого поиска, ро-метод Полларда, метод исчисления индексов, «шаг младенца-шаг великана». Примеры, оценки сложности указанных алгоритмов.

5. Практические занятия.

1. Операции над целыми числами. Нахождение наибольшего общего делителя при помощи алгоритма Евклида, наименьшего общего кратного. Построение таблицы первых простых чисел с помощью решета Эратосфена. Нахождение канонического разложения числа на простые сомножители.
2. Разложение дробей в цепные дроби при помощи алгоритма Евклида. Асимптотический закон распределения простых чисел – вычисление примерного количества простых чисел на заданном интервале. Вычисление функции Эйлера от числа. Теория сравнений. Построение приведенной системы вычетов от по заданному модулю. Проверка сравнений.
3. Вычисление обратного элемента в Z_n при помощи расширенного алгоритма Евклида. Тест Ферма на простоту. Понижение степени сравнения. При помощи теоремы Эйлера. Криптосистема RSA.
4. Сравнения первой степени и их решение. Системы сравнений первой степени и их решение по Китайской теореме об остатках.
5. Символ Лежандра. Существование решений квадратичного сравнения по простому модулю. Решение квадратичных сравнений по простому модулю. Символ Якоби. Существование и количество решений квадратичного сравнения по составному модулю. Решение квадратичных сравнений по составному модулю.
6. Квадраты и псевдоквадраты. Проблема различения квадратов и псевдоквадратов, ее связь с задачей факторизации. Числа Блюма. BBS-генератор. Криптосистемы Блюма-Гольдвассер, Гольдвассер-Микали. Циклическая группа Z*_p (U_p). Отыскание порождающего элемента.
7. (n-1) – тесты на простоту на основе теорем Сэлфриджа и Поклингтона. Числа Ферма, тест Пепина. Числа Мерсенна и тест Лукаса-Лемера. Процедура генерации простых чисел ГОСТ Р34.10-94.
8. Конечные группы и поля многочленов. Многочлены над Z_p, Z_n. Сложение многочленов, умножение многочленов, разложение многочлена на сомножители. Неприводимые многочлены. Нахождение НОД многочленов.
9. Алгоритмы факторизации. Метод пробных делений, метод Ферма, метод квадратичного решета, ро-метод Полларда, p—1 – метод Полларда, методы случайных квадратов. Примеры, оценки сложности указанных алгоритмов. Алгоритмы дискретного логарифмирования. Метод прямого поиска, ро-метод Полларда, метод исчисления индексов, «шаг младенца-шаг великана». Примеры, оценки сложности указанных алгоритмов.

Вопросы к экзаменам

1. Основные понятия теории чисел. Теорема делимости.
2. Наибольший общий делитель и алгоритм Евклида.
3. Цепные дроби и алгоритм Евклида.
4. Наименьше общее кратное. Простые числа.
5. Теоремы Евклида о простых числах. Решето Эратосфена.
6. Основные свойства простых чисел. Теорема о единственности разложения на простые сомножители.
7. Теорема о делителях числа и ее следствия.
8. Асимптотический закон распределения простых чисел.
9. Функция Эйлера, ее свойства.
10. Сравнения. Свойства сравнений.
11. Полная система вычетов, приведенная система вычетов. Алгебраические свойства, обратный элемент.
12. Теорема Эйлера, теорема Ферма. Следствие.
13. Тест Ферма на простоту. Числа Кармайкла. Теорема Кармайкла.
14. Применение теоремы Ферма в криптосистеме RSA.
15. Сравнения с одним неизвестным 1-й степени.
16. Система сравнений 1-й степени. Китайская теорема об остатках.
17. Применение Китайской теоремы об остатках в RSA и схема разделения секрета на ее основе.
18. Квадратичные сравнения по простому модулю.
19. Символ Лежандра и его свойства.
20. Решение квадратичных сравнений по простому модулю.
21. Число решений квадратичного сравнения по составному модулю.
22. Символ Якоби, его свойства. Тест Соловея-Штрассена.
23. Квадратичные сравнения по модулю RSA. Связь задач извлечения корней и факторизации. Криптосистема Рабина.
24. Квадраты и псевдоквадраты. Числа Блюма.
25. BBS-генератор. Криптосистема Блюма-Гольдвассер, криптосистема Гольдвассер-Микали.
26. Тест Миллера-Рабина.
27. Порядок группы. Порядок элемента в группе. Порождающий элемент.
28. Существование порождающего элемента в Z*n
29. Критерий Люка.
30. Теорема Сэлфриджа и тест Миллера.
31. Теорема Поклнгтона и тест на простоту на ее основе.
32. Числа Ферма, теорема Пепина, тест Пепина.
33. Числа Мерсена. Тест Лукаса-Лемера.
34. Теорема Диемитко. Процедура генерации простых чисел ГОСТ Р 34.10-94.
35. Дискретный логарифм. Проблема Диффи-Хелмана. Криптосистема ЭльГамаля.
36. Кольца многочленов.
37. Поле многочленов GF(p^α).
38. Проблема факторизации. Метод проных делений.
39. Метод Ферма факторизации.
40. Метод квадратичного решета.
41. Ро-метод Полларда факторизации.
42. p—1 – метод факторизации.
43. Методы случайных квадратов.
44. Задача дискретного логарифмирования. Метод прямого поиска.
45. Ро-метод Полларда дискретного логарифмирования.
46. Алгоритм Полига-Хеллмана.
47. Метод «Шаг младенца-шаг великана».
48. Метод исчисления порядка.

Литература

ОСНОВНАЯ:

1. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии. Учебное пособие. — М.: Гелиос-АРВ, 2001.

2. Виноградов И. М. Основы теории чисел. – М.: Наука, 1972. – 402 с.

3. Столлингс В. Криптография и защита сетей. Принципы и практика. 2-е изд. — М: Вильямс, 2001.

4. Шеннон К. Работы по теории информации и кибернетике. — М.: ИЛ, 1963.

5. Введение в криптографию / Под общей ред. Ященко В.В. — М: МЦИМО, «ЧеРо», 1998.

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

7. Варфоломеев А.А., Домнина О.С, Пеленицын М.Б. Управление ключами в системах криптографической зашиты банковской информации. — М: МИФИ, 1996.

8. Варфоломеев А.А., Пеленицын М.Б. Методы криптографии и их применение в банковских технологиях. — М.: МИФИ, 1995.

9. Фомичев В.М. Симметричные криптосхемы. Краткий обзор основ криптологии для шифрсистем с открытым ключом. — М.: МИФИ, 1995.

10. История криптографии. А.В. Бабаш, Г.П. Шанкин. Учебное пособие. - М.: "ГелиосАРВ",2001 г.

11. Рябко Б.Я., Фионов А.Н., Основы современной криптографии для специалистов в информационных технологиях, М.: Научный мир, 2004.

12. Шнайер Б., Прикладная криптография

13. Черемушкин А.В. Вычисления в алгебре и теории чисел. Курс лекций. — М.: 2002.

ДОПОЛНИТЕЛЬНАЯ:

1. Агибалов Г.П. Избранные теоремы начального курса криптографии: Учебное пособие. – Томск: Изд-во НТЛ, 2005. – 116 с.

2. Диффи У., Хеллман М.Э. Защищенность и имитостойкость. Введение в криптографию. - ТИИЭР, т.67, №3, 1979.

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

4. Брассар Ж. Современная криптология. — М.: ПОЛИМЕД, 1999.

5. Мэсси Дж.Л. Современная криптология: введение. - ТИИЭР, Т.76, №5, 1988.

6. Нечаев В.И. Элементы криптографии. Основы теории защиты информации. — М.: Высшая школа, 1999.

7. Проскурин Г.В. Принципы и методы зашиты информации. — М.: МИЭМ, 1997

8. A. Menezes, P. van Oorschort, S. Vanstone, Handbook of Applied Cryptography – CRC Press, Inc., 1997

Программа составлена

д.ф.-м.н., профессором

А.В.Рожковым и

ст. преподавателем

О.В. Ниссенбаум

СПИСОК ЛИТЕРАТУРЫ

1. Агибалов Г.П. Избранные теоремы начального курса криптографии: Учебное пособие. – Томск: Изд-во НТЛ, 2005. – 116 с.

2. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии: Учебное пособие. – М.: Гелиос АРВ, 2002. – 480 с.

3. Александров П. С. Введение в теорию групп. - 2-е изд., стер. - М.: Едиториал УРСС, 2004. - 128 с.

4. Введение в криптографию/Под общей ред. В.В. Ященко. – М.: МЦНМО, 1998. – 272 с.

5. Виноградов И. М. Основы теории чисел. – М.: Наука, 1972. – 402 с.

6. Дегтев А.Н. Алгебра и логика: Учебное пособие для студентов вузов, обучающихся по специальности "Математика". - Тюмень: Изд-во ТюмГУ, 2000. - 88 с.

7. Молдовян Н.А., Молдовян А.А. Введение в криптосистемы с открытым ключом. – СПб.: БХВ-Петербург, 2005. 288 с.: ил.

8. Молдовян А.А., Молдовян Н.А., Советов Б.Я. Криптография. – СПб.: Изд-во «Лань», 2001. – 224с.

9. Рябко Б.Я., Фионов А.Н. Криптографические методы защиты информации: учебное пособие для вузов. – М.: Горячая линия–Телеком, 2005. – 229 с.: ил.

10. Черемушкин А.В. Вычисления в алгебре и теории чисел. Курс лекций. — М.: 2002.

11. Шнайер Б. Прикладная криптография: Протоколы, алгоритмы, исходные тексты на языке Cи. – М.: Издательство ТРИУМФ, 2003 – 816 с., ил.

12. Diffie W., Hellman M.E. New directions in cryptography // IEEE Transactions on Information Theory. – 1976. – V. 22. – P.644-654.

13. Goldwasser S., Bellare M. Lecture notes on cryptography. – Cambridge, Massachusetts, 2001. – 283 p.

14. Grundbegriffe der Kryptographie/ Vorlesungsscript von Eike Best - Oldenburg, 2005.

15. Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. – CRC Press, 1996. – 661 p.