А.В. Рожков, О.В. Ниссенбаум - Теоретико-числовые методы в криптографии (1127102), страница 26
Текст из файла (страница 26)
Приложение 2.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
. |
ТЕОРЕТИКО - ЧИСЛОВЫЕ МЕТОДЫ В КРИПТОГРАФИИ |
Рабочая программа для специальности |
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. Содержание разделов дисциплины
-
Введение в математические основы криптографии.
-
Основы теории чисел. Делимость, простые числа, наибольший общий делитель. Алгоритм Евклида, расширенный алгоритм Евклида.
-
Цепные дроби. Асимптотический закон распределения простых чисел. Мультипликативные функции. Функция Эйлера.
-
Теория сравнений. Полная система вычетов, приведенная система вычетов. Zn, Zp.
-
Обратный элемент в Zn Алгебраические структуры на целых числах - Zn, Zp.
-
Теорема Эйлера, теорема Ферма, тест Ферма на простоту. Криптосистема RSA. Понижение степени сравнения.
-
Сравнения первой степени и их решение. Системы сравнений первой степени и их решение. Китайская теорема об остатках и ее применения в криптографии (схема разделения секрета на ее основе и ее применение в RSA).
-
Квадратичные сравнения. Символ Лежандра. Закон взаимности. Существование решений квадратичного сравнения по простому модулю. Решение квадратичных сравнений по простому модулю.
-
Символ Якоби и его свойства. Тест Соловея-Штрассена на простоту. Существование и количество решений квадратичного сравнения по составному модулю. Решение квадратичных сравнений по составному модулю.
-
Квадраты и псевдоквадраты. Проблема различения квадратов и псевдоквадратов, ее связь с задачей факторизации. Числа Блюма. BBS-генератор. Криптосистемы Блюма-Гольдвассер, Гольдвассер-Микали.
-
Циклическая группа Z*p (Up). Порождающий элемент и дискретный логарифм. Задача дискретного логарифмирования. Криптосистемы Диффи-Хэллмана и Эль-Гамаля.
-
Теоремы Сэлфриджа и Поклингтона. (n-1) – тесты на простоту. Доказуемо простые числа общего вида.
-
Числа Ферма, теорема Пепина, тест Пепина. Числа Мерсенна и тест Лукаса-Лемера. Теорема Диемитко и процедура генерации простых чисел ГОСТ Р34.10-94.
-
Конечные группы и поля многочленов. Многочлены над Zp, Zn. Сложение многочленов, умножение многочленов, разложение многочлена на сомножители. Неприводимые многочлены.
-
Элементы теории сложности. Оценки сложности по времени, по объему требуемой памяти. Полиномиальная сложность, субэкспоненциальная сложность, экспоненциальная сложность алгоритмов. Сложность элементарных операций. Теоретико-числовые проблемы, лежащие в основе двухключевых криптосистем – факторизация, дискретное логарифмирование.
-
Алгоритмы факторизации. Метод пробных делений, метод Ферма, метод квадратичного решета, ро-метод Полларда, p—1 – метод Полларда, методы случайных квадратов. Примеры, оценки сложности указанных алгоритмов.
-
Алгоритмы дискретного логарифмирования. Метод прямого поиска, ро-метод Полларда, метод исчисления индексов, «шаг младенца-шаг великана». Примеры, оценки сложности указанных алгоритмов.
5. Практические занятия.
-
Операции над целыми числами. Нахождение наибольшего общего делителя при помощи алгоритма Евклида, наименьшего общего кратного. Построение таблицы первых простых чисел с помощью решета Эратосфена. Нахождение канонического разложения числа на простые сомножители.
-
Разложение дробей в цепные дроби при помощи алгоритма Евклида. Асимптотический закон распределения простых чисел – вычисление примерного количества простых чисел на заданном интервале. Вычисление функции Эйлера от числа. Теория сравнений. Построение приведенной системы вычетов от по заданному модулю. Проверка сравнений.
-
Вычисление обратного элемента в Zn при помощи расширенного алгоритма Евклида. Тест Ферма на простоту. Понижение степени сравнения. При помощи теоремы Эйлера. Криптосистема RSA.
-
Сравнения первой степени и их решение. Системы сравнений первой степени и их решение по Китайской теореме об остатках.
-
Символ Лежандра. Существование решений квадратичного сравнения по простому модулю. Решение квадратичных сравнений по простому модулю. Символ Якоби. Существование и количество решений квадратичного сравнения по составному модулю. Решение квадратичных сравнений по составному модулю.
-
Квадраты и псевдоквадраты. Проблема различения квадратов и псевдоквадратов, ее связь с задачей факторизации. Числа Блюма. BBS-генератор. Криптосистемы Блюма-Гольдвассер, Гольдвассер-Микали. Циклическая группа Z*p (Up). Отыскание порождающего элемента.
-
(n-1) – тесты на простоту на основе теорем Сэлфриджа и Поклингтона. Числа Ферма, тест Пепина. Числа Мерсенна и тест Лукаса-Лемера. Процедура генерации простых чисел ГОСТ Р34.10-94.
-
Конечные группы и поля многочленов. Многочлены над Zp, Zn. Сложение многочленов, умножение многочленов, разложение многочлена на сомножители. Неприводимые многочлены. Нахождение НОД многочленов.
-
Алгоритмы факторизации. Метод пробных делений, метод Ферма, метод квадратичного решета, ро-метод Полларда, p—1 – метод Полларда, методы случайных квадратов. Примеры, оценки сложности указанных алгоритмов. Алгоритмы дискретного логарифмирования. Метод прямого поиска, ро-метод Полларда, метод исчисления индексов, «шаг младенца-шаг великана». Примеры, оценки сложности указанных алгоритмов.
6. Вопросы к экзаменам
-
Основные понятия теории чисел. Теорема делимости.
-
Наибольший общий делитель и алгоритм Евклида.
-
Цепные дроби и алгоритм Евклида.
-
Наименьше общее кратное. Простые числа.
-
Теоремы Евклида о простых числах. Решето Эратосфена.
-
Основные свойства простых чисел. Теорема о единственности разложения на простые сомножители.
-
Теорема о делителях числа и ее следствия.
-
Асимптотический закон распределения простых чисел.
-
Функция Эйлера, ее свойства.
-
Сравнения. Свойства сравнений.
-
Полная система вычетов, приведенная система вычетов. Алгебраические свойства, обратный элемент.
-
Теорема Эйлера, теорема Ферма. Следствие.
-
Тест Ферма на простоту. Числа Кармайкла. Теорема Кармайкла.
-
Применение теоремы Ферма в криптосистеме RSA.
-
Сравнения с одним неизвестным 1-й степени.
-
Система сравнений 1-й степени. Китайская теорема об остатках.
-
Применение Китайской теоремы об остатках в RSA и схема разделения секрета на ее основе.
-
Квадратичные сравнения по простому модулю.
-
Символ Лежандра и его свойства.
-
Решение квадратичных сравнений по простому модулю.
-
Число решений квадратичного сравнения по составному модулю.
-
Символ Якоби, его свойства. Тест Соловея-Штрассена.
-
Квадратичные сравнения по модулю RSA. Связь задач извлечения корней и факторизации. Криптосистема Рабина.
-
Квадраты и псевдоквадраты. Числа Блюма.
-
BBS-генератор. Криптосистема Блюма-Гольдвассер, криптосистема Гольдвассер-Микали.
-
Тест Миллера-Рабина.
-
Порядок группы. Порядок элемента в группе. Порождающий элемент.
-
Существование порождающего элемента в Z*n
-
Критерий Люка.
-
Теорема Сэлфриджа и тест Миллера.
-
Теорема Поклнгтона и тест на простоту на ее основе.
-
Числа Ферма, теорема Пепина, тест Пепина.
-
Числа Мерсена. Тест Лукаса-Лемера.
-
Теорема Диемитко. Процедура генерации простых чисел ГОСТ Р 34.10-94.
-
Дискретный логарифм. Проблема Диффи-Хелмана. Криптосистема ЭльГамаля.
-
Кольца многочленов.
-
Поле многочленов GF(pα).
-
Проблема факторизации. Метод проных делений.
-
Метод Ферма факторизации.
-
Метод квадратичного решета.
-
Ро-метод Полларда факторизации.
-
p—1 – метод факторизации.
-
Методы случайных квадратов.
-
Задача дискретного логарифмирования. Метод прямого поиска.
-
Ро-метод Полларда дискретного логарифмирования.
-
Алгоритм Полига-Хеллмана.
-
Метод «Шаг младенца-шаг великана».
-
Метод исчисления порядка.
7.Литература