Программа дисциплины Криптография с открытым ключом Для направления 231000. 62 «Программная инженерия» подготовки бакалавра



Скачать 148.68 Kb.
Дата18.02.2013
Размер148.68 Kb.
ТипПрограмма дисциплины
Правительство Российской Федерации
Государственный университет-

Высшая школа экономики

Факультет Бизнес-информатики

Отделение Программной Инженерии

Программа дисциплины

Криптография с открытым ключом

Для направления 231000.62 «Программная инженерия»

подготовки бакалавра

(2010 – 2011 учебный год)
Автор программы:

к.ф.-м.н, доцент А.А. Набебин

anabebin@hse.ru


Рекомендована секцией УМС
по Бизнес-информатике
Председатель

_________________ Г.А.Левочкина

"____" _________________ 2011 г.





Одобрена на заседании

кафедры Управление разработкой

программного обеспечения

Зав. кафедрой

________________ С.М.Авдошин

"____" _________________ 2011 г.

Утверждаю
Первый проректор ГУ-ВШЭ
__________________ В.В. Радаев
"____" _________________ 2011 г.








Москва 2010

  1. Пояснительная записка

Автор программы:

к.ф.-м.н, доцент А.А.Набебин
Общие сведения об учебном курсе.

Курс является общеуниверситетским факультативом. Курс читается в 3 – 4 модулях учебного года. Количество кредитов – 4.

Продолжительность курса составляет 64 аудиторных учебных часа, в том числе 32 часа лекций, 32 часа семинарских занятий и 80 часов самостоятельной работы, всего 144 часа. Рубежный контроль включает два домашних задания (3 и 4 модуль соответственно) и зачет по окончании 4 модуля.
Требования к студентам:

Освоение дисциплины требует знания курса алгебры.
Цель курса

Целью преподавания дисциплины “Криптография с открытым ключом” является изучение математических основ криптографии и основных криптографических протоколов с открытым ключом.
Аннотация

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

Для решения поставленных задач используется инструментальный язык программирования Mathcad.

Учебные задачи курса

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


В результате изучения курса студенты должны:

знать:

  • основные понятия модулярной арифметики (теории сравнений) целых чисел;

  • основные понятия абстрактной алгебры, теоремы и алгоритмы о конечных группах, (полиномиальных) кольцах и полях.

  • основные алгоритмы модулярной арифметики целых чисел и полиномов (НОД, НОК, модулярная степень, тесты на простоту натуральных чисел, неприводимость и примитивность полиномов в конечных полиномиальных полях).

  • основные криптографические системы и электронные цифровые подписи (ЭЦП) с открытым ключом (RSA, Эль-Гамаля, DSA), основанные на фактах модулярной алгебры целых чисел и конечных полиномиальных полей.


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

  • о современном состоянии, проблемах и основных направлениях развития криптографии.


уметь:

  • использовать криптографические протоколы;

  • решать и исследовать системы сравнений с неизвестными;

  • выбирать требуемую практическими обстоятельствами криптосистему;

  • осуществлять программирование используемых алгоритмов.




  1. Тематический план учебной дисциплины




№ п/п

Наименование темы

Всего часов

Аудиторные часы

Самостоя-тельная работа

Лекции

Семинары

3 модуль

1

Делимость. Деление с остатком. Позиционная система счисления. Факторизация целых чисел. НОД и НОК. Расширенный алгоритм Евклида вычисления НОД. Непрерывные и подходящие дроби.

17

3

4

10

2

Функции Мебиуса и формула обращения Мебиуса. Функция Эйлера.

8

2

1

5

3

Сравнения целых чисел по данному модулю. Вычеты и классы вычетов (классы сравнимости) по данному модулю. Теоремы Эйлера и Ферма.

16

3

3

10

4

Сравнения с переменными. Системы сравнений первой степени. Китайская теорема об остатках (доказательство Гаусса).

11

3

3

5

5

Сравнения второй степени. Вычеты и невычеты степени n. Дискретные корни степени n. Квадратичные вычеты. Символ Лежандра и символ Якоби

12

3

3

6

6

Примитивные корни и индексы. Экспонента данного числа по данному модулю. Примитивные корни из единицы. Индексы (дискретные логарифмы).

8

2

2

4




Итого в модуле 3

72

16

16

40

4 модуль

7

Группа, подгруппа, циклическая группа. Кольцо. Делители нуля.Поле. Характеристика поля.

16

3

3

10

8

Полиномиальные кольца R[x] и F[x]. Деление полиномов. Частное и остаток. Наибольший общий делитель. Приводимые и неприводимые полиномы. Сравнение полиномов по данному модулю. Кольца и поля равноостаточных классов. Примитивные полиномы. Тесты на неприводимость и примитивность полиномов.Универсальные алгебры.

25

5

5

15

9

Криптосистемы и электронные цифровые подписи RSA, Эль-Гамаля, DSA.

31

8

8

15




Итого в модуле 4

72

16

16

40




ВСЕГО

144

32

32

80




  1. Формы рубежного контроля и правила вывода оценок зачета и экзамена

Предусмотрено выполнение двух домашних заданий (3 и 4 модули). Выполнение домашнего задания оценивается по десятибалльной шкале. В четвертом модуле предусмотрен зачет.

Оценки выводятся по следующим формулам.

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

Оценка за зачет (4 модуль) выставляется как среднее арифметическое трех оценок: за выполнение домашних заданий в 3-м и 4-м модулях и за ответ на зачете по десятибалльной шкале (с учетом правил округления до целого числа баллов).
Оценки выставляются в ведомость и зачетную книжку. В экзаменационную ведомость и зачетную книжку студента выставляется также и оценка по данной дисциплине по пятибалльной шкале, получаемая из оценки по десятибалльной шкале в соответствии с приведенной ниже таблицей соответствия (см. Приложение № 2 к приказу Ректора ГУ-ВШЭ № 1002 от 17.06.2002).
Таблица соответствия оценок

по десятибалльной и пятибалльной системам.


По десятибалльной шкале

По пятибалльной шкале

1  неудовлетворительно

2  очень плохо

3  плохо


неудовлетворительно  2

4  удовлетворительно

5  весьма удовлетворительно


удовлетворительно  3

6  хорошо

7  очень хорошо


хорошо  4

8  почти отлично

9  отлично

10 блестяще


отлично  5



IV. Базовые учебники

  1. Набебин А.А. Сборник заданий по дискретной математике. М.: Научный мир 2009. – 280c. ISBN 978-5-91522-072-9.

  2. Набебин А.А. Дискретная математика. М.: Научный мир, 2010. – 512с. ISBN 978-5-91522-190-0

  3. Смарт Н. Криптография. М.: Техносфера, 2005.


Дополнительная литература

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

  2. Бабаш А.В. Криптографические и теоретико-автоматные аспекты современной защиты информации. М.: Издат. центр ЕАОИ, том 1, 2008; том 2, 2008; том 3, 2010.

  3. Болотов А.А., Гашков С.Б., Фролов А.Б. Часовских А.А. Элементарное введение в эллиптическую криптографию. Алгебраические и алгоритмические основы. М.: КомКнига, 2006.

  4. Болотов А.А., Гашков С.Б., Фролов А.Б. Элементарное введение в эллиптическую криптографию. Протоколы криптографии на эллиптических кривых. М.: КомКнига, 2006.

  5. Виноградов И.М. Основы теории чисел. СПБ.: Лань, 2004.

  6. Лидл Р., Нидеррайтер Г. Конечные поля. М.: Мир, 1988.

  7. Шнейер Б. Прикладная криптография. М.: Триумф, 2002.

  8. Menezes A., van Oorschot P., Vanstone S. Handbook of applied cryptography. CRC Press. 1996.

  1. Содержание программы

Модулярная арифметика целых чисел

  1. Делимость. Деление с остатком. Позиционная система счисления. Алгоритм вычисления h-ричной записи 10-тичного числа. Простые числа. Факторизация целых чисел. Наибольший общий делитель (НОД) и наименьшее общее кратное (НОК). Расширенный алгоритм Евклида нахождения d = НОД(a,b) и таких целых u,v, для которых d = au + bv. Непрерывные и подходящие дроби, алгоритм их вычисления.

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

1. Набебин А.А. Сборник заданий по дискретной математике. М.: Научный мир 2009.

2. Набебин А.А. Дискретная математика. М.: Научный мир, 2010.

Дополнительная литература:

1. Виноградов И.М. Основы теории чисел. СПБ.: Лань, 2004.

2. Лидл Р., Нидеррайтер Г. Конечные поля. М.: Мир, 1988.

3. Смарт Н. Криптография. М.: Техносфера, 2005.

4. Шнейер Б. Прикладная криптография. М.: Триумф, 2002.

5. Menezes A., van Oorschot P., Vanstone S. Handbook of applied cryptography. CRC Press. 1996.


  1. Функции Мебиуса. Формула обращения Мебиуса. Мультипликативные функции. Функция Эйлера и ее вычисление.

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

1. Набебин А.А. Сборник заданий по дискретной математике. М.: Научный мир 2009.

2. Набебин А.А. Дискретная математика. М.: Научный мир, 2010.

Дополнительная литература:

1. Виноградов И.М. Основы теории чисел. СПБ.: Лань, 2004.

2. Лидл Р., Нидеррайтер Г. Конечные поля. М.: Мир, 1988.

3. Смарт Н. Криптография. М.: Техносфера, 2005.

4. Шнейер Б. Прикладная криптография. М.: Триумф, 2002.

5. Menezes A., van Oorschot P., Vanstone S. Handbook of applied cryptography. CRC Press. 1996.


  1. Сравнения целых чисел по данному модулю. Свойства сравнений. Вычеты и классы вычетов (классы сравнимости) по данному модулю. Операции над классами. Полная и приведенная системы вычетов. Теоремы Эйлера и Ферма. Модулярные арифметические операции. Обратимые элементы. Порядок элемента. Генераторы. Алгоритмы вычисления мультипликативно обратного элемента, модулярной степени, генератора в циклической группе.

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

1. Набебин А.А. Сборник заданий по дискретной математике. М.: Научный мир 2009.

2. Набебин А.А. Дискретная математика. М.: Научный мир, 2010.

Дополнительная литература:

1. Виноградов И.М. Основы теории чисел. СПБ.: Лань, 2004.

2. Лидл Р., Нидеррайтер Г. Конечные поля. М.: Мир, 1988.

3. Смарт Н. Криптография. М.: Техносфера, 2005.

4. Шнейер Б. Прикладная криптография. М.: Триумф, 2002.

5. Menezes A., van Oorschot P., Vanstone S. Handbook of applied cryptography. CRC Press. 1996.


  1. Сравнения с переменными. Решение системы сравнений. Сравнения первой степени. Их решение с помощью непрерывных дробей. Системы сравнений первой степени. Китайская теорема об остатках (доказательство Гаусса). Набебин А.А. Сборник заданий по дискретной математике. М.: Научный мир 2009. Набебин А.А. Дискретная математика. М.: Научный мир, 2010.

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

1. Набебин А.А. Сборник заданий по дискретной математике. М.: Научный мир 2009.

2. Набебин А.А. Дискретная математика. М.: Научный мир, 2010.

Дополнительная литература:

1. Виноградов И.М. Основы теории чисел. СПБ.: Лань, 2004.

2. Лидл Р., Нидеррайтер Г. Конечные поля. М.: Мир, 1988.

3. Смарт Н. Криптография. М.: Техносфера, 2005.

4. Шнейер Б. Прикладная криптография. М.: Триумф, 2002.

5. Menezes A., van Oorschot P., Vanstone S. Handbook of applied cryptography. CRC Press. 1996.


  1. Сравнения второй степени. Вычеты и невычеты степени n. Дискретные корни степени n. Квадратичные вычеты. Символ Лежандра и символ Якоби. Алгоритм вычисления символа Якоби.

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

1. Набебин А.А. Сборник заданий по дискретной математике. М.: Научный мир 2009.

2. Набебин А.А. Дискретная математика. М.: Научный мир, 2010.

Дополнительная литература:

1. Виноградов И.М. Основы теории чисел. СПБ.: Лань, 2004.

2. Лидл Р., Нидеррайтер Г. Конечные поля. М.: Мир, 1988.

3. Смарт Н. Криптография. М.: Техносфера, 2005.

4. Шнейер Б. Прикладная криптография. М.: Триумф, 2002.

5. Menezes A., van Oorschot P., Vanstone S. Handbook of applied cryptography. CRC Press. 1996.


  1. Примитивные корни и индексы. Экспонента данного числа по данному модулю. Примитивные корни из единицы. Индексы (дискретные логарифмы) данного числа по данному основанию по данному модулю. Теорема о существовании примитивных корней.

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

1. Набебин А.А. Сборник заданий по дискретной математике. М.: Научный мир 2009.

2. Набебин А.А. Дискретная математика. М.: Научный мир, 2010.

Дополнительная литература:

1. Виноградов И.М. Основы теории чисел. СПБ.: Лань, 2004.

2. Лидл Р., Нидеррайтер Г. Конечные поля. М.: Мир, 1988.

3. Смарт Н. Криптография. М.: Техносфера, 2005.

4. Шнейер Б. Прикладная криптография. М.: Триумф, 2002.

5. Menezes A., van Oorschot P., Vanstone S. Handbook of applied cryptography. CRC Press. 1996.
Группа, кольцо, поле

  1. Группа, подгруппа, циклическая группа. Порядок группы. Порядок элемента. Кольцо. Делители нуля. Группа обратимых элементов кольца Zn. Поле. Характеристика поля.

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

1. Набебин А.А. Сборник заданий по дискретной математике. М.: Научный мир 2009.

2. Набебин А.А. Дискретная математика. М.: Научный мир, 2010.

Дополнительная литература:

1. Виноградов И.М. Основы теории чисел. СПБ.: Лань, 2004.

2. Лидл Р., Нидеррайтер Г. Конечные поля. М.: Мир, 1988.

3. Смарт Н. Криптография. М.: Техносфера, 2005.

4. Шнейер Б. Прикладная криптография. М.: Триумф, 2002.

5. Menezes A., van Oorschot P., Vanstone S. Handbook of applied cryptography. CRC Press. 1996.


  1. Полиномиальные кольца R[x] и F[x]. Деление полиномов. Частное и остаток. Наибольший общий делитель (НОД) двух полиномов из Zp[x]. Расширенный алгоритм Евклида вычисления НОД. Приводимые и неприводимые полиномы из Zn[x]. Деление полиномов. Частное и остаток. Сравнение полиномов по данному модулю. Классы эквивалентности. Кольца и поля равноостаточных классов Zp[x]/(f(x)) по модулю полинома f(x), приводимого для кольца и неприводимого для поля. Примитивные полиномы. Мультипликативный обратный элемент в Zp[x]/(f(x)). Модулярная степень в Zp[x]/(f(x)). Тесты на неприводимость и примитивность полиномов над Zp. Универсальные алгебры.

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

1. Набебин А.А. Сборник заданий по дискретной математике. М.: Научный мир 2009.

2. Набебин А.А. Дискретная математика. М.: Научный мир, 2010.

Дополнительная литература:

1. Виноградов И.М. Основы теории чисел. СПБ.: Лань, 2004.

2. Лидл Р., Нидеррайтер Г. Конечные поля. М.: Мир, 1988.

3. Смарт Н. Криптография. М.: Техносфера, 2005.

4. Шнейер Б. Прикладная криптография. М.: Триумф, 2002.

5. Menezes A., van Oorschot P., Vanstone S. Handbook of applied cryptography. CRC Press. 1996.
Применение модулярной арифметики в криптографии

  1. Криптография и ее цели. Шифры блочные, потоковые и шифры с открытым ключом. Хэш-функция. Электронная цифровая подпись. Проблема факторизации целых чисел и полиномов. Некоторые частные алгоритмы факторизации. Проблемы дискретного квадратного корня и дискретного алгоритма. Криптосистемы и электронные цифровые подписи RSA, Эль-Гамаля, DSA, Голдвассера-Микали, Блюма-Голдвассера, Фейге-Фиат-Шамира, GQ, Шнорра, Ниберга-Рюппеля.

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

1. Набебин А.А. Сборник заданий по дискретной математике. М.: Научный мир 2009.

2. Набебин А.А. Дискретная математика. М.: Научный мир, 2010.

Дополнительная литература:

1. Виноградов И.М. Основы теории чисел. СПБ.: Лань, 2004.

2. Лидл Р., Нидеррайтер Г. Конечные поля. М.: Мир, 1988.

3. Смарт Н. Криптография. М.: Техносфера, 2005.

4. Шнейер Б. Прикладная криптография. М.: Триумф, 2002.

5. Menezes A., van Oorschot P., Vanstone S. Handbook of applied cryptography. CRC Press. 1996.
Домашнее задание по дисциплине «Криптография с открытым ключом»

Индивидуальные домашние задания выдается из книги: Набебин А.А. Сборник заданий по дискретной математике. М.: Научный мир 2009.
Оценка качества освоения дисциплины

Зачет проводится в форме компьютерного тестирования (60 мин) по тематике пройденного материала.

Вопросы для подготовки к зачету в форме компьютерного тестирования

  1. Делимость и ее свойства. Представление числа по делителю, частному, остатку. Представление числа в системе счисления по основанию h.

  2. Простые числа. Бесконечность множества простых чисел. Решето Эратосфена для простых чисел.

  3. Теорема о факторизации и ее свойства.

  4. Наибольший общий делитель (НОД) и его свойства. Вычисление НОД с помощью теоремы о факторизации. Алгоритм Евклида вычисления НОД. Расширенный алгоритм Евклида.

  5. Наименьшее общее кратное (НОК) и его свойства. Вычисление НОК с помощью теоремы о факторизации. Связь между НОД и НОК.

  6. Непрерывные и подходящие дроби и их вычисление.

  7. Целая и дробная часть вещественного числа. Мультипликативная функция. Сумма мультипликативной функции от числа по всем делителям этого числа.

  8. Функция Мебиуса. Преобразование Мебиуса.

  9. Функция Эйлера и ее вычисление.

  10. Сравнение целых чисел. Три определения сравнений и их эквивалентность. Свойства сравнений.

  11. Полная система вычетов. Наименьшая неотрицательная, абсолютно наименьшая, приведенная система вычетов. Классы вычетов. Операции над классами.

  12. Теоремы Эйлера и Ферма.

  13. Сравнения с одним неизвестным произвольной степени. Решение сравнения. Система сравнений произвольных степеней и ее решение.

  14. Сравнения и их системы с несколькими переменными и их решение.

  15. Сравнения первой степени и их решение.

  16. Система сравнений первой степени. Теорема Гаусса о ее решении.

  17. Сравнения любой степени по простому модулю и их решение. Теорема Вильсона.

  18. Сравнения любой степени по составному модулю и их решение.

  19. Вычеты (корни) степени n. Квадратичные вычеты (квадратные корни) и их свойства. Квадратичные вычеты по простому модулю.

  20. Символ Лежандра и его свойства.

  21. Символ Якоби и его свойства.

  22. Квадратичные вычеты (квадратные корни) по составному модулю.

  23. Числа и их экспоненты (показатели) по данному модулю. Связь между сравнением степеней и их экспонент.

  24. Примитивные (первообразные) корни и их свойства. Теорема о существовании примитивных корней.

  25. Универсальные алгебры. Гомоморфизм и изоморфизм алгебр. Теорема о гомоморфизме.

  26. Полугруппы, подполугруппы, циклические полугруппы.

  27. Кольца и поля. Характеристика поля. Конечные поля.


Перед проведением зачета публикуется открытый вариант теста.
Автор программы к.ф.-м.н., доцент А.А.Набебин





Похожие:

Программа дисциплины Криптография с открытым ключом Для направления 231000. 62 «Программная инженерия» подготовки бакалавра iconПрограмма дисциплины иностранный язык (английский) для направления 231000. 62 "Программная инженерия"
Программа дисциплины иностранный язык (английский) для направления 231000. 62 "Программная инженерия" подготовки бакалавра
Программа дисциплины Криптография с открытым ключом Для направления 231000. 62 «Программная инженерия» подготовки бакалавра iconПрограмма дисциплины Алгебра Для направления 231000. 62 «Программная инженерия» подготовки бакалавра (2011 2012 учебный год)
Федеральное государственное автономное образовательное учреждение высшего профессионального образования
Программа дисциплины Криптография с открытым ключом Для направления 231000. 62 «Программная инженерия» подготовки бакалавра iconПрограмма дисциплины Алгебра Для направления 231000. 62 «Программная инженерия» подготовки бакалавра (2010 2011 учебный год)
...
Программа дисциплины Криптография с открытым ключом Для направления 231000. 62 «Программная инженерия» подготовки бакалавра iconНаправление подготовки 231000 «Программная инженерия»
Главной задачей направления подготовки «Программная инженерия» является формирование и подготовка ит-профессионалов, готовых к работе...
Программа дисциплины Криптография с открытым ключом Для направления 231000. 62 «Программная инженерия» подготовки бакалавра iconПрограмма дисциплины Формальные методы программной инженерии для направления 231000. 68 «Программная инженерия»

Программа дисциплины Криптография с открытым ключом Для направления 231000. 62 «Программная инженерия» подготовки бакалавра iconПрограмма дисциплины Оптимизация и математические методы в принятии решений Для направления 231000. 62 «Программная инженерия»

Программа дисциплины Криптография с открытым ключом Для направления 231000. 62 «Программная инженерия» подготовки бакалавра iconПрограмма подготовки бакалавров 231000 «Программная инженерия»
Направление «Программная инженерия» реализуется на математико-механическом факультете (мат-мех) Санкт-Петербургского государственного...
Программа дисциплины Криптография с открытым ключом Для направления 231000. 62 «Программная инженерия» подготовки бакалавра iconРабочая программа дисциплины «Физика» Направление подготовки 231000 Программная инженерия Профиль подготовки
Целью освоения дисциплины является ознакомление студентов с теоретическими и практическими основами базовых разделов физики
Программа дисциплины Криптография с открытым ключом Для направления 231000. 62 «Программная инженерия» подготовки бакалавра iconКод и наименование направления подготовки: 231000. 62 «Программная инженерия»
Инженер-проектировщик программных систем
Программа дисциплины Криптография с открытым ключом Для направления 231000. 62 «Программная инженерия» подготовки бакалавра iconПрограмма дисциплины Свободно-распространяемое программное обеспечение в современном бизнесе для направления 231000. 68 «Программная инженерия»
Ниу вшэ. Она входит в вариативную часть профессионального цикла, определяющего магистерскую программу, и читается во втором семестре...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org