Наименование дисциплины: Теоретико-числовые методы в криптографии

Направление подготовки (специальность): 090301 Компьютерная безопасность

Специализация: Математические методы защиты информации

Квалификация (степень) выпускника: специалист

Форма обучения: очная

Автор: к. ф.-м. н., доцент, доцент кафедры алгебры и математической логики .

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

1) подготовка в области компьютерной безопасности;

2) овладение методами решения основных задач в области современной криптографии;

3) овладение современным математическим аппаратом, используемым в криптографии и теории кодирования для дальнейшего использования в приложениях.

2. Дисциплина " Теоретико-числовые методы в криптографии" входит в цикл С3.профессиональных дисциплин в базовую часть. Дисциплина "Теоретико-числовые методы в криптографии" является основополагающей в списке обучения методам криптографической защиты информации, базирующейся на результатах теории чисел. Изучение дисциплины основывается на курсах: "Алгебра", "Теория вероятностей и математическая статистика", "Математическая логика" и "Теория чисел".

3. В результате освоения дисциплины обучающийся должен:

НЕ нашли? Не то? Что вы ищете?

иметь представление:

а) об основных понятиях теории чисел, используемых в криптографии;

б) о способах получения оценок сложности в используемых теоретико-числовых

алгоритмах;

в) теоретических и эвристических соображениях, лежащих в основе конструируемых

теоретико-числовых алгоритмов;

г) о теоретико-вероятностных и детерминистических схемах, используемых в теории

чисел;

д) о связи теории чисел с математическoй логикой;

знать и уметь использовать:

a) принципы построения основных теоретико-числовых алгоритмов, используемых

в криптографии;

б) принципы конструирования быстрых теоретико-числовых алгоритмов;

в) системы модульной арифметики;

г) случаи быстрого дискретного логарифмирования;

д) сложности основных теоретико-числовых алгоритмов;

е) основные сведения о распределении простых чисел.

владеть:

а) терминологией, используемой в теории чисел;

б) навыками использования основных теоретико-числовых алгоритмов,

используемых в криптографии;

в) навыками моделирования и анализа теоретико-числовых алгоритмов;

г) современной научной литературой в области теоретико-числовых

алгоритмов.

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

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

№ п/п

Раздел дисциплины

1

ВВЕДЕНИЕ Применение теоретико-числовых методов в криптографии

2

ЭЛЕМЕНТЫ ТЕОРИИ ЧИСЕЛ Непрерывные дроби и их свойства. Применение непрерывных дробей к решению сравнений. Квадратичные вычеты. Символы Лежандра и Якоби. Квадратные корни: метод Цассенхауза-Кантора. Теорема Чебышева о распределении простых чисел. Классы вычетов, вычисления в кольцах вычетов. Китайская теорема об остатках и ее использование при решении теоретико-числовых задач. Строение мультипликативной группы кольца Теорема Гаусса.

3

СЛОЖНОСТЬ АРИФМЕТИЧЕСКИХ ОПЕРАЦИЙ Сложность операций в кольце вычетов. Сложность алгоритма Евклида. Модульная арифметика и ее использование. Вычисления с многочленами. Дискретное преобразование Фурье.

4

АЛГОРИТМЫ ПРОВЕРКИ ЧИСЕЛ НА ПРОСТОТУ

Решето Эратосфена. Критерий Вильсона. Тест на основе малой теоремы Ферма. Псевдопростые числа и числа Кармайкла. Построение чисел Кармайкла и псевдопростых чтисел. Тест Соловея-Штрассена. Эйлеровы псевдопростые числа по данному основанию. Сильно псевдопростые числа. Тест Рабина-Миллера. Полиномиальный тест распознавания простоты.

5

АЛГОРИТМЫ ПОСТРОЕНИЯ БОЛЬШИХ ПРОСТЫХ ЧИСЕЛ

Критерий Люка. Теорема Селфриджа. Числа Ферма, критерий их простоты. Теорема Поклингтона. Теорема Диемитко. Метод Маурера. Метод Михалеску. Обзор методов. Числа Мерсенна. Тест Люка-Лемера.

6

АЛГОРИТМЫ ФАКТОРИЗАЦИИ ЦЕЛЫХ ЧИСЕЛ. Метод Полларда. Алгоритм Полларда-Штрассена. Факторизация Ферма. Алгоритм Диксона. Алгоритм Брилхарта-Моррисона. Метод квадратичного решета. метод Полларда. Алгоритм Шенкса.

7

ДИСКРЕТНОЕ ЛОГАРИФМИРОВАНИЕ

Криптографическая система RSA. Выбор параметров системы RSA. Детерминированные методы. метод Полларда. Дискретное логарифмирование в конечном поле. Частные Ферма в различных кольцах.

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

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

1.  Маховенко, Е. Б., Теоретико-числовые методы в криптографии : учеб. пособие для вузов / , М., Гелиос АРВ, 2006, 319c

2.  , , Теория чисел. Часть 2: учебное пособие для вузов, Ярославль, ЯрГУ, 2004, 108c

3.  Ростовцев, А. Г., Алгебраические основы криптографии, СПб., Мир и семья, 2000, 354c

4.  Гашков, С. Б., Арифметика. Алгоритмы. Сложность вычислений : учеб. пособие для вузов / , . - 2-е изд., перераб., М., Высшая школа, 2000, 320c

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

1.  Алгебраическая алгоритмика. М.: "Мир", 1999 г.

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

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

4.  Василенко - числовые алгоритмы в криптографии. - М.: МЦНМО, 2003.-- 328 с.

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

6.  Маховенко. Введение в криптографию с открытым ключом.-- Санкт - Петербург.: НПО "Мир и Семья", 2001.

7.  , , Черемушкин криптографии. Учебное пособие. М: “Гелиос АРВ”, 2001.

8.  Криптография и защита сетей. Принципы и практика.-- 2-е изд. М.: Гелиос АРВ, 2001.

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

10. Торокин -техническая защита информации, М: “Гелиос АРВ”, 2005

11. Введение в криптографию/Под редакцией М: МЦНМО, «ЧеРо» , 1998.

12. , , Криптография в упражнениях и задачах, М.: “Гелиос АРВ”, 2004.

в) программное обеспечение и Интернет-ресурсы:

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