МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
. |
ТЕОРЕТИКО - ЧИСЛОВЫЕ МЕТОДЫ В КРИПТОГРАФИИ |
Рабочая программа для специальности |
075200 – Компьютерная безопасность |
Тюмень 2007
1. Пояснительная записка
1.1. Цели и задачи дисциплины
Дисциплина «Теоретико – числовые методы в криптографии» обеспечивает приобретение знаний по математическим основам криптографической защиты информации. Целью преподавания дисциплины «Теоретико – числовые методы в криптографии» является изложение базовых принципов построения и математического обоснования криптографических систем.
Задачи изложить:
• теоретико-числвые, алгебраические, аналитические и вероятностные подходы к построению и анализу криптосистем;
• математические основы криптографии;
• математические методы, используемые в криптоанализе
1.2. Требования к уровню освоения содержания дисциплины
В результате изучения дисциплины студенты должны
иметь представление:
• об основных задачах и понятиях криптографии;
• о теоретико-числовых основах двухключевой криптографии;
• об основных алгоритмических проблемах криптографии и способах их решения;
• о специальных математических структурах, применяемых в криптографии.
знать:
• основы дискретной алгебры и теории чисел;
• применение конечных автоматов в криптографии;
• характеристики языков, распознаваемых конечными автоматами ( P, NP, BPP и т. д.)
• применение теории вероятности в криптографии и криптоанализе;
• применение теоретико-числового аппарата для решения задач криптографии;
• основные двухключевые криптосистемы и доказательство их стойкости.
уметь:
• формализовать поставленную задачу;
• выполнить постановку задач криптоанализа и указать подходы к их решению;
• использовать основные математические методы, применяемые в синтезе и анализе типовых криптографических алгоритмов.
• применять полученные знания к различным предметным областям.
иметь навыки:
• владения криптографической терминологией;
• применения алгоритмов, основанных на теоретико-числовых принципах, к вопросам построения криптосистем и их анализу;
• использования современной научно-технической литературы в области криптографической защиты.
2. Объем дисциплины и виды учебной работы
Вид занятий | Всего часов | Семестры |
8 | ||
Общая трудоемкость | 90 | 90 |
Аудиторные занятия | 51 | 51 |
Лекции | 34 | 34 |
Практические занятия | 17 | 17 |
Индивидуальная работа | 6 | 6 |
Самостоятельная работа | 33 | 33 |
Контрольные работы + | + | |
Вид итогового контроля экзамен | экзамен |
3. Тематический план изучения дисциплины
№ п/п | Наименование темы | Лекции | Практические | Самост. | Формы контроля |
1 | Введение в математические проблемы криптографии. | 2 | 1 | 2 | к/р |
2 | Основы теории чисел. Делимость, простые числа, наибольший общий делитель. Алгоритм Евклида, расширенный алгоритм Евклида. Цепные дроби. Асимптотический закон распределения простых чисел. | 3 | 1 | 4 | |
3 | Мультипликативные функции. Функция Эйлера. | 1 | 1 | ||
4 | Теория сравнений. Полная система вычетов, приведенная система вычетов. Zn, Zp. | 2 | 1 | ||
5 | Обратный элемент в Zn Алгебраические структуры на целых числах - Zn, Zp. | 2 | 1 | ||
6 | Теорема Эйлера, теорема Ферма, тест Ферма на простоту. Криптосистема RSA. | 2 | 1 | ||
7 | Сравнения первой степени. Системы сравнений первой степени. Китайская теорема об остатках и ее применения в криптографии (схема разделения секрета на ее основе и ее применение в RSA). | 2 | 2 | 3 | |
8 | Квадратичные сравнения. Символ Лежандра. Закон взаимности. Решение квадратичных сравнений по простому модулю. | 2 | 1 | к/р | |
9 | Символ Якоби и его свойства. Тест Соловея-Штрассена на простоту. Решение квадратичных сравнений по составному модулю. | 2 | 1 | 4 | |
10 | Квадраты и псевдоквадраты. Числа Блюма. BBS-генератор. Криптосистемы Блюма-Гольдвассер, Гольдвассер-Микали. | 2 | 1 | ||
11 | Циклическая группа Z*p (Up). Порождающий элемент и дискретный логарифм. | 2 | 1 | к/р | |
12 | Теоремы Сэлфриджа и Поклингтона. Доказуемо простые числа общего вида. | 2 | 1 | 2 | |
13 | Числа Ферма и тест Пепина. Числа Мерсенна и тест Лукаса-Лемера. Теорема Диемитко и процедура генерации простых чисел ГОСТ Р34.10-94 | 2 | 1 | 3 | |
14 | Конечные поля многочленов. | 2 | 1 | 10 | Домашняя к/р |
15 | Элементы теории сложности. Теоретико-числовые проблемы, лежащие в основе двухключевых криптосистем. | 2 | 1 | Расчетная работа | |
16 | Алгоритмы факторизации | 2 | 1 | 2 | |
17 | Алгоритмы дискретного логарифмирования. | 2 | 1 | 2 | |
4. Содержание разделов дисциплины
5. Практические занятия.
6. Вопросы к экзаменам
Основные понятия теории чисел. Теорема делимости. Наибольший общий делитель и алгоритм Евклида. Цепные дроби и алгоритм Евклида. Наименьше общее кратное. Простые числа. Теоремы Евклида о простых числах. Решето Эратосфена. Основные свойства простых чисел. Теорема о единственности разложения на простые сомножители. Теорема о делителях числа и ее следствия. Асимптотический закон распределения простых чисел. Функция Эйлера, ее свойства. Сравнения. Свойства сравнений. Полная система вычетов, приведенная система вычетов. Алгебраические свойства, обратный элемент. Теорема Эйлера, теорема Ферма. Следствие. Тест Ферма на простоту. Числа Кармайкла. Теорема Кармайкла. Применение теоремы Ферма в криптосистеме RSA. Сравнения с одним неизвестным 1-й степени. Система сравнений 1-й степени. Китайская теорема об остатках. Применение Китайской теоремы об остатках в RSA и схема разделения секрета на ее основе. Квадратичные сравнения по простому модулю. Символ Лежандра и его свойства. Решение квадратичных сравнений по простому модулю. Число решений квадратичного сравнения по составному модулю. Символ Якоби, его свойства. Тест Соловея-Штрассена. Квадратичные сравнения по модулю RSA. Связь задач извлечения корней и факторизации. Криптосистема Рабина. Квадраты и псевдоквадраты. Числа Блюма. BBS-генератор. Криптосистема Блюма-Гольдвассер, криптосистема Гольдвассер-Микали. Тест Миллера-Рабина. Порядок группы. Порядок элемента в группе. Порождающий элемент. Существование порождающего элемента в Z*n Критерий Люка. Теорема Сэлфриджа и тест Миллера. Теорема Поклнгтона и тест на простоту на ее основе. Числа Ферма, теорема Пепина, тест Пепина. Числа Мерсена. Тест Лукаса-Лемера. Теорема Диемитко. Процедура генерации простых чисел ГОСТ Р 34.10-94. Дискретный логарифм. Проблема Диффи-Хелмана. Криптосистема ЭльГамаля. Кольца многочленов. Поле многочленов GF(pα). Проблема факторизации. Метод проных делений. Метод Ферма факторизации. Метод квадратичного решета. Ро-метод Полларда факторизации. p—1 – метод факторизации. Методы случайных квадратов. Задача дискретного логарифмирования. Метод прямого поиска. Ро-метод Полларда дискретного логарифмирования. Алгоритм Полига-Хеллмана. Метод «Шаг младенца-шаг великана». Метод исчисления порядка.7.Литература
ОСНОВНАЯ:
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-е изд., стер. - М.: Едиториал УРСС, 20с.
4. Введение в криптографию/Под общей ред. . – М.: МЦНМО, 1998. – 272 с.
5. Основы теории чисел. – М.: Наука, 1972. – 402 с.
6. Алгебра и логика: Учебное пособие для студентов вузов, обучающихся по специальности "Математика". - Тюмень: Изд-во ТюмГУ, 20с.
7. , Введение в криптосистемы с открытым ключом. – СПб.: БХВ-Петербург, 20с.: ил.
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.
ОГЛАВЛЕНИЕ
Аннотация. 2
ПРЕДИСЛОВИЕ.. 3
ВВЕДЕНИЕ.. 5
ГЛАВА 1. Основы теории чисел. 8
§1. Теория делимости. 8
1.1. Основные понятия и теоремы. 9
1.2. Наибольший общий делитель. 11
1.3 НОК (наименьшее общее кратное) 17
1.4. Простые числа. 17
1.5. Единственность разложения на простые сомножители. 20
1.6. Асимптотический закон распределения простых чисел. 23
§2. Функция Эйлера. 26
2.1. Мультипликативные функции. 26
2.2. Функция Эйлера. 27
§3. Теория сравнений. 29
3.1. Свойства сравнений: 29
3.2. Полная система вычетов. 30
3.3. Приведенная система вычетов. 32
3.4. Обратный элемент. 32
3.5. Алгебраические структуры на целых числах. 34
3.6. Теоремы Эйлера и Ферма. Тест Ферма на простоту. 37
3.7. Применение теоремы Эйлера в RSA: 39
§4. Сравнения с одним неизвестным.. 43
4.1. Сравнения первой степени. 43
4.2. Система сравнений первой степени. Китайская теорема об остатках. 45
4.3. Применения китайской теоремы об остатках. 47
4.4. Сравнения любой степени по простому модулю. 49
4.5. Сравнения любой степени по составному модулю. 51
§5. Теория квадратичных вычетов. 55
5.1. Квадратичные вычеты по простому модулю. 55
5.2. Символ Лежандра. Символ Якоби. 56
5.3. Тест на простоту Соловея-Штрассена. 61
5.4. Решение квадратичных сравнений по простому модулю. 62
5.5. Квадратичные сравнения по составному модулю. 66
5.6. Тест на простоту Миллера-Рабина. 69
5.7. Связь задач извлечения квадратных корней и факторизации по модулю RSA. Криптосистема Рабина. 72
5.8. Квадраты и псевдоквадраты. 74
5.9. Числа Блюма. 75
§6. Первообразные корни и индексы. Порождающий элемент и дискретный логарифм. 79
6.1. Основные понятия и теоремы. 79
6.2. Существование первообразных корней по модулю p. 81
6.3. Первообразные корни по модулям pα, 2pα. 82
6.4. Нахождение первообразных корней по простому модулю. 85
6.5. Существование и количество первообразных корней. 86
6.6. Дискретные логарифмы. 87
6.7. Проблема Диффи-Хеллмана. 88
6.8. Условная стойкость шифра Эль Гамаля. 88
§7. Построение доказуемо простых чисел общего и специального вида. 90
7.1. Теорема Сэлфриджа и доказуемо простые числа общего вида на основании полного разложения (n—1). 90
7.2. Теорема Поклингтона и доказуемо простые числа общего вида на основании частичного разложения (n—1). 92
7.3. Числа Ферма. Теорема Пепина. 93
7.4. Числа Мерсенна. 95
7.5. Теорема Диемитко и процедура генерации простых чисел заданной длины ГОСТ Р 34.10-94. 96
ГЛАВА 2. Алгебраические основы теории чисел. 99
§1. Основные понятия алгебры. 100
1.1. Начальные понятия. 100
1.2. Делимость в кольцах. 107
1.3. Деление с остатком. 110
1.4. Основная теорема арифметики. 114
§2. Конечные поля и неприводимые многочлены. 119
§3. Кольца многочленов. 129
3.1. Кольца многочленов. 129
3.2. Кольцо многочленов Zp[x]. 131
3.3. Конечные поля многочленов. 131
ГЛАВА 3. Алгоритмы в криптографии и криптоанализе. 134
§1. Элементы теории сложности. 134
§2. Алгоритмы факторизации. 139
2.1. Метод пробных делений. 140
2.2. Метод Ферма. 141
2.3. Метод квадратичного решета. 142
2.4. Ро-метод Полларда. 144
2.5. p—1 – метод Полларда. 146
2.6. Методы случайных квадратов. 147
§3. Алгоритмы дискретного логарифмирования. 149
3.1. Метод прямого поиска. 149
3.2. Шаг младенца – шаг великана. 150
3.3. Ро-метод Полларда для дискретного логарифмирования. 152
3.4. Алгоритм Полига-Хеллмана. 154
3.5. Алгоритм исчисления порядка (index-calculus algorithm). 156
Задачи и упражнения. 160
Упражнения к Главе
Упражнения к Главе 2: 163
Упражнения к Главе 3: 164
Ответы к упражнениям. 165
Приложение
СПИСОК ЛИТЕРАТУРЫ
ОГЛАВЛЕНИЕ.. 178
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 |
