Главная » Просмотр файлов » А.В. Рожков, О.В. Ниссенбаум - Теоретико-числовые методы в криптографии

А.В. Рожков, О.В. Ниссенбаум - Теоретико-числовые методы в криптографии (1127102), страница 26

Файл №1127102 А.В. Рожков, О.В. Ниссенбаум - Теоретико-числовые методы в криптографии (А.В. Рожков, О.В. Ниссенбаум - Теоретико-числовые методы в криптографии) 26 страницаА.В. Рожков, О.В. Ниссенбаум - Теоретико-числовые методы в криптографии (1127102) страница 262019-05-11СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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. Содержание разделов дисциплины

  1. Введение в математические основы криптографии.

  2. Основы теории чисел. Делимость, простые числа, наибольший общий делитель. Алгоритм Евклида, расширенный алгоритм Евклида.

  3. Цепные дроби. Асимптотический закон распределения простых чисел. Мультипликативные функции. Функция Эйлера.

  4. Теория сравнений. Полная система вычетов, приведенная система вычетов. Zn, Zp.

  5. Обратный элемент в Zn Алгебраические структуры на целых числах - Zn, Zp.

  6. Теорема Эйлера, теорема Ферма, тест Ферма на простоту. Криптосистема RSA. Понижение степени сравнения.

  7. Сравнения первой степени и их решение. Системы сравнений первой степени и их решение. Китайская теорема об остатках и ее применения в криптографии (схема разделения секрета на ее основе и ее применение в RSA).

  8. Квадратичные сравнения. Символ Лежандра. Закон взаимности. Существование решений квадратичного сравнения по простому модулю. Решение квадратичных сравнений по простому модулю.

  9. Символ Якоби и его свойства. Тест Соловея-Штрассена на простоту. Существование и количество решений квадратичного сравнения по составному модулю. Решение квадратичных сравнений по составному модулю.

  10. Квадраты и псевдоквадраты. Проблема различения квадратов и псевдоквадратов, ее связь с задачей факторизации. Числа Блюма. BBS-генератор. Криптосистемы Блюма-Гольдвассер, Гольдвассер-Микали.

  11. Циклическая группа Z*p (Up). Порождающий элемент и дискретный логарифм. Задача дискретного логарифмирования. Криптосистемы Диффи-Хэллмана и Эль-Гамаля.

  12. Теоремы Сэлфриджа и Поклингтона. (n-1) – тесты на простоту. Доказуемо простые числа общего вида.

  13. Числа Ферма, теорема Пепина, тест Пепина. Числа Мерсенна и тест Лукаса-Лемера. Теорема Диемитко и процедура генерации простых чисел ГОСТ Р34.10-94.

  14. Конечные группы и поля многочленов. Многочлены над Zp, Zn. Сложение многочленов, умножение многочленов, разложение многочлена на сомножители. Неприводимые многочлены.

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

  16. Алгоритмы факторизации. Метод пробных делений, метод Ферма, метод квадратичного решета, ро-метод Полларда, p—1 – метод Полларда, методы случайных квадратов. Примеры, оценки сложности указанных алгоритмов.

  17. Алгоритмы дискретного логарифмирования. Метод прямого поиска, ро-метод Полларда, метод исчисления индексов, «шаг младенца-шаг великана». Примеры, оценки сложности указанных алгоритмов.

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

  1. Операции над целыми числами. Нахождение наибольшего общего делителя при помощи алгоритма Евклида, наименьшего общего кратного. Построение таблицы первых простых чисел с помощью решета Эратосфена. Нахождение канонического разложения числа на простые сомножители.

  2. Разложение дробей в цепные дроби при помощи алгоритма Евклида. Асимптотический закон распределения простых чисел – вычисление примерного количества простых чисел на заданном интервале. Вычисление функции Эйлера от числа. Теория сравнений. Построение приведенной системы вычетов от по заданному модулю. Проверка сравнений.

  3. Вычисление обратного элемента в Zn при помощи расширенного алгоритма Евклида. Тест Ферма на простоту. Понижение степени сравнения. При помощи теоремы Эйлера. Криптосистема RSA.

  4. Сравнения первой степени и их решение. Системы сравнений первой степени и их решение по Китайской теореме об остатках.

  5. Символ Лежандра. Существование решений квадратичного сравнения по простому модулю. Решение квадратичных сравнений по простому модулю. Символ Якоби. Существование и количество решений квадратичного сравнения по составному модулю. Решение квадратичных сравнений по составному модулю.

  6. Квадраты и псевдоквадраты. Проблема различения квадратов и псевдоквадратов, ее связь с задачей факторизации. Числа Блюма. BBS-генератор. Криптосистемы Блюма-Гольдвассер, Гольдвассер-Микали. Циклическая группа Z*p (Up). Отыскание порождающего элемента.

  7. (n-1) – тесты на простоту на основе теорем Сэлфриджа и Поклингтона. Числа Ферма, тест Пепина. Числа Мерсенна и тест Лукаса-Лемера. Процедура генерации простых чисел ГОСТ Р34.10-94.

  8. Конечные группы и поля многочленов. Многочлены над Zp, Zn. Сложение многочленов, умножение многочленов, разложение многочлена на сомножители. Неприводимые многочлены. Нахождение НОД многочленов.

  9. Алгоритмы факторизации. Метод пробных делений, метод Ферма, метод квадратичного решета, ро-метод Полларда, p—1 – метод Полларда, методы случайных квадратов. Примеры, оценки сложности указанных алгоритмов. Алгоритмы дискретного логарифмирования. Метод прямого поиска, ро-метод Полларда, метод исчисления индексов, «шаг младенца-шаг великана». Примеры, оценки сложности указанных алгоритмов.

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

  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. Метод исчисления порядка.

7.Литература

Характеристики

Тип файла
Документ
Размер
2,98 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6430
Авторов
на СтудИзбе
306
Средний доход
с одного платного файла
Обучение Подробнее