МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
РОССИЙСКОЙ ФЕДЕРАЦИИ
Саратовский государственный университет имени
Факультет компьютерных наук и информационных технологий
УТВЕРЖДАЮ
___________________________
"__" __________________20__ г.
Рабочая программа дисциплины
Введение в криптоанализ
Специальность
090301 Компьютерная безопасность
Специализация
Математические методы защиты информации
Квалификация выпускника
Специалист
Форма обучения
очная
Саратов,
2012
1. Цели освоения дисциплины
Целями освоения дисциплины «Введение в криптоанализ» являются:
- ознакомление студентов с основными задачами криптографического анализа;
- ознакомление с основными идеями и методами классического и современного криптографического анализа;
- овладение основными методами анализа криптосистем, основанных на перестановках и подстановках;
- овладение основными методами анализа линейных криптографических систем;
- овладение основными методами анализа систем с открытым ключом;
- ознакомление с основными идеями линейного и дифференциального криптоанализа современных стандартов шифрования.
Курс «Введение в криптоанализ» позволяет студентам овладеть фундаментальными понятиями и методами классической и современной теории криптографического анализа, без знания которых невозможна полноценная оценка современных систем защиты информации. При освоении данного курса у студентов формируются навыки грамотной оценки стойкости рассматриваемой криптографической системы, навыки решения практических задач с учётом этой оценки.
2.Место дисциплины в структуре ООП
Данная учебная дисциплина входит в раздел «Профессиональный цикл. Вариативная часть» ФГОС-3.
Для изучения дисциплины необходимы компетенции, знания, умения и готовности, сформированные у обучающихся в результате освоения курсов «Алгебра», «Геометрия», «Дискретная математика», «Теория вероятностей и математическая статистика», «Теория информации», «Математическая логика и теория алгоритмов», «Основы информационной безопасности», «Прикладная универсальная алгебра», «Криптографические методы защиты информации», «Методы программирования», «Алгоритмы алгебры и теории чисел», «Теоретико-числовые методы в криптографии».
3 Компетенции обучающегося, формируемые в результате освоения дисциплины «Введение в криптоанализ».
Выпускник должен обладать следующими общекультурными компетенциями
способностью действовать в соответствии с Конституцией Российской Федерации, исполнять свой гражданский и профессиональный долг, руководствуясь принципами законности и патриотизма (ОК-1);
способностью осуществлять свою деятельность в различных сферах общественной жизни с учетом принятых в обществе морально-нравственных и правовых норм, соблюдать принципы профессиональной этики (ОК-2);
способностью понимать социальную значимость своей будущей профессии, цели и смысл государственной службы, обладать высокой мотивацией к выполнению профессиональной деятельности в области обеспечения информационной безопасности и защиты интересов личности, общества и государства, готовностью и способностью к активной состязательной деятельности в условиях информационного противоборства (ОК-5);
спсобностью к работе в коллективе, кооперации с коллегами, способностью в качестве руководителя подразделения, лидера группы сотрудников формировать цели команды, принимать организационноуправленческие решения в ситуациях риска и нести за них ответственность, предупреждать и конструктивно разрешать конфликтные ситуации в процессе профессиональной деятельности (ОК-6);
способностью логически верно, аргументировано и ясно строить устную и письменную речь на русском языке, готовить и редактировать тексты профессионального назначения, публично представлять собственные и известные научные результаты, вести дискуссии (ОК-7);
способностью к письменной и устной деловой коммуникации, к чтению и переводу текстов по профессиональной тематике на одном из иностранных языков (ОК-8);
способностью к логически-правильному мышлению, обобщению, анализу, критическому осмыслению информации, систематизации, прогнозированию, постановке исследовательских задач и выбору путей их решения на основании принципов научного познания (ОК-9);
способностью самостоятельно применять методы и средства познания, обучения и самоконтроля для приобретения новых знаний и умений, в том числе в новых областях, непосредственно не связанных со сферой деятельности, развития социальных и профессиональных компетенций, изменения вида своей профессиональной деятельности (ОК-10);
Выпускник должен обладать следующими профессиональными компетенциями (ПК):
Общепрофессиональными:
способностью применять математический аппарат, в том числе с использованием вычислительной техники, для решения профессиональных задач (ПК-2);
способностью понимать сущность и значение информации в развитии современного общества, применять достижения современных информационных технологий для поиска и обработки больших объемов информации по профилю деятельности в глобальных компьютерных системах, сетях, в библиотечных фондах и в иных источниках информации (ПК-3)
способностью применять методологию научных исследований в профессиональной деятельности, в том числе в работе над междисциплинарными и инновационными проектами (ПК-4);
способностью учитывать современные тенденции развития информатики и вычислительной техники, компьютерных технологий в своей профессиональной деятельности (ПК-7);
способностью работать с программными средствами прикладного, системного и специального назначения (ПК-8);
способностью использовать языки и системы программирования, инструментальные средства для решения различных профессиональных, исследовательских и прикладных задач (ПК-9);
способностью формулировать результат проведенных исследований в виде конкретных рекомендаций, выраженных в терминах предметной области изучавшегося явления (ПК-10);
В результате изучения базовой части обучающийся должен
Знать:
основные понятия, задачи и алгоритмы криптографического анализа симметричных и ассиметричных криптосистем;
Уметь:
формулировать основные и промежуточные задачи по криптографическому анализу в конкретных условиях;
Владеть:
основными методами криптографического анализа.
4. Структура и содержание дисциплины
Общая трудоемкость дисциплины составляет 4 зачетных единиц 144 часов.
№ п/п | Раздел дисциплины | Семестр | Неделя семестра | Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах) | Формы текущего контроля успеваемости (по неделям семестра) Формы промежуточной аттестации (по семестрам) | |||
Лекции | Практика | Лаборатор. | Самостоятельные | |||||
1 | Основные задачи криптоанализа | 10 | 1-2 | 4 | 4 | 2 | опрос, проверка домашнего задания | |
2 | Анализ симметричных шифров | 10 | 3-9 | 14 | 14 | 16 | опрос, проверка домашнего задания | |
3 | Криптоанализ системы RSA | 10 | 10-16 | 12 | 12 | 9 | опрос, проверка домашнего задания | |
Промежуточная аттестация | Экзамен | |||||||
Итого: | 30 | 30 | 39 | 45 |
1. Основные задачи криптоанализа.
Оценка секретных систем. Основные виды криптоатак. Четыре основных задачи криптоанализа (по Фридману). Пять основных класса методов криптоанализа.
2. Анализ симметричных шифров
1) Анализ перестановки c периодом T.
Правило Казиски для вычисления длины ключа. Теорема о разложении подстановки на циклы. Число моноциклических перестановок из n символов. Анализ шифра перестановки при известной длине периода на основе вспомогательной таблицы.
2) Анализ шифров подстановки.
Частотный анализ простой подстановки.
Анализ шифра Виженера:
- Атака на основе открытого текста и шифротекста;
- Атака Фридмана, Индекс совпадения, Теорема 1 (об индексе совпадения), Теорема 2 (формула вычисления математического ожидания индекса совпадения). Теорема 3 (о среднем индексе совпадения). Теорема 4 (геометрическая оценка среднего индекса совпадения). Атака Фридмана на основе среднего индекса совпадения для вычисления периода шифра подстановки.
- Статистический метод вычисления длины периода гаммы в шифре гаммирования.
- Метод БШ.
Методы вычисления ключа при известной длине ключа:
- Метод чтения по колонкам;
- Метод протяжки вероятного слова;
- Атака по словарю;
- Метод Симпсона;
- Метод Томаса Якобсена.
Анализ шифра Хилла:
- Атака на основе выбранного открытого текста;
- Атака на основе известного открытого текста;
- Атака на основе только шифрограммы.
3. Криптоанализ системы RSA
Анализ на основе задачи разложения составного числа на множители:
- Метод пробного деления;
- ρ-метод Полларда;
- (p – 1)-метод Полларда;
- Метод квадратов (метод Ферма);
- Метод Диксона;
- Метод непрерывных дробей (в алгоритме Диксона);
- Метод квадратичного решета (в алгоритме Диксона);
Оценка безопасности системы RSA:
- Лемма о задаче разложения и вычисления функции Эйлера;
- Теорема о задаче вычисления секретного ключа в RSA;
- Алгоритм разложения на множители по известным показателям RSA.
Атаки на криптосистему RSA, не требующие разложения:
- Атака на основе теоремы Винера;
- Атака на основе Греко-китайской теоремы;
- Атака на основе «частично известных» открытых текстов:
a) Алгоритм нахождения линейно зависимых текстов для случая e = 3;
b) Алгоритм нахождения линейно зависимых текстов для произвольного e.
- Атака на RSA при малом порядке открытого показателя e по модулю j(n);
- Атака на RSA при малом порядке показателя e по модулю p – 1 или q – 1.
Задания по лабораторным работам
1. Изучить теоретический материал по выбранному заданию и предоставить подробное его описание.
2. Написать программу (пакет программ), с помощью которой можно решить поставленные задачи.
3. Подготовить и сдать полный отчёт о проделанной работе. В отчёт входят: 1) Теоретическое описание поставленных задач и их решений; 2) Программа (пакет программ), с помощью которой можно решить поставленные задачи; 3) При необходимости (в случае отсутствия понятного интерфейса программы) пользовательское описание программы (пакета программ).
4. Список заданий:
Задание 1:
1. Реализовать шифр простой перестановки.
2. Реализовать тест Казиски (программа выявления одинаковых участков криптограммы и вычисления наиболее часто встречаемого наименьшего расстояния между ними)
3. Разложение на простые множители небольших натуральных чисел.
4. Программа перебора ключей моноциклической перестановки.
Задание 2: Написать программы:
1) простая подстановка и сравнительный анализ частот двух сообщений с восстановлением простой подстановки,
2) атака на основе открытого текста и шифротекста (рус. алфавит),
3) шифр Виженера и программа, составляющую таблицу сдвигов.
4) Проанализировать зависимость значений таблицы сдвигов от отношения длины ключа к длине сообщения.
Задание 3: Написать программу, реализующую следующий алгоритм анализа простой замены:
1) подсчёт частот встречаемости шифробозначений, а также некоторых их сочетаний, например биграмм и триграмм подряд идущих знаков,
2) выявление шифробозначений, заменяющих гласные и согласные буквы,
3) выдвижение гипотез о значениях шифробозначений и их проверка, восстановление истинного значения шифробозначений.
4) предварительно написать программу реализующую шифр простой замены.
Задание 4: Написать программы, реализующие следующие методы анализа шифра замены при известной длине ключа:
1) метод чтения по колонкам,
2) метод протяжки вероятного слова,
3) атака по словарю.
4) предварительно написать программу, реализующую шифр многоалфавитной замены.
Задание 5: Написать программу, реализующие методы Якобсена для простой замены (см. [1] § 5.2, Алгоритм 2):
Задание 6: Написать программы:
1) линейная подстановка Хилла,
2) атака на шифр Хилла на основе выбранного открытого текста,
3) атака на шифр Хилла на основе известного открытого текста,
4) атака на шифр Хилла на основе только шифрограммы.
Задание 7 (анализ простой перестановки при известной длине ключа):
1) Написать программу по построению множества запретных биграмм языка открытых сообщений.
2) Написать программу по построению вспомогательной таблицы анализа шифра перестановки известного периода.
3) Написать программу, которая бы по заданной вспомогательной таблицы строила бы ориентированный лес возможных перестановок.
4) Написать программу по составлению словаря допустимых 3-х грамм, 4-грамм, 5-грамм, … для языка открытых сообщений.
5) Написать программу, которая бы по заданному ориентированному лесу и заданному словарю допустимых n-грамм из множества возможных перестановок отсеивала бы наиболее вероятные, или даже единственную возможную.
Задание 8:
1) Написать программу для шифра простой перестановки.
2) Написать программу, реализующие методы Якобсена для вычисления ключа шифра простой перестановки.
Задание 9 (Статистический метод вычисления длины периода гаммы в шифре гаммирования):
1) Программа по реализации шифра гаммирования.
2) Написать программу: расчёт Pc — вероятность символа c в языке открытых сообщений на основе частотного анализа, и на основе этих результатов вычисление P = (p1, p2, …, pm), где 
.
3) Написать программу по выбору гипотезы H(0) или H(1) на основе результатов предыдущих вычислений и вспомогательной последовательности шифртекста шифра гаммирования.
Задание 10:
1) Программа по реализации шифра гаммирования.
2) Написать программу, реализующую метод БШ для вычисления длины периода гаммы шифра гаммирования).
Задание 11 (метод Симпсона):
1) Программа по реализации шифра гаммирования.
2) На основе частотного анализа текста языка открытых сообщений программно вычислить MIср(P, P¢ ) = 
, учитывая следующее равенство:
MIср(Y, Z) = 
® (т. е. ») = MIср(P, P¢ ).
3) Полагая, что K является множеством циклических подстановок шифра Виженера программно осуществить подготовительный этап метода Симпсона.
4) При известном значении d и на основе решений заданий 1) и 2) программно реализовать промежуточный этап метода Симпсона, т. е. получить список наиболее вероятных ключей.
5) Программно реализовать опробование списка ключей из предыдущего задания.
Задание 12 (анализ системы RSA):
1) Программный комплекс для реализация RSA.
2) Запрограммировать метод пробных делений и указать границы возможности вашей программы.
3) Запрограммировать ρ-метод Полларда.
4) (p – 1)-метод Полларда.
Задание 13 (анализ системы RSA):
1. Программный комплекс для реализация RSA.
2. Запрограммировать метод Ферма.
3. Запрограммировать обобщённый метод Ферма.
Задание 14 (анализ системы RSA):
1) Программный комплекс для реализация RSA,
2) Запрограммировать алгоритм Диксона с методом квадратичного решета.
3) Запрограммировать алгоритм Диксона с методом непрерывных дробей.
Задание 15 (оценка безопасности системы RSA):
1) Программный комплекс для реализация RSA,
2) Запрограммировать алгоритм разложения на множители по известным показателям RSA..
Задание 16 (Атаки на криптосистему RSA, не требующие разложения):
1) Программный комплекс для реализация RSA,
2) Атака на основе теоремы Винера,
3) Атака на основе Греко-китайской теоремы,
4) Атака на основе «частично известных» открытых текстов,
5) Атака на RSA при малом порядке открытого показателя e по модулю j(n)
6) Атака на RSA при малом порядке показателя e по модулю p – 1 или q – 1
5. Образовательные технологии
В учебном процессе при реализации компетентностного подхода используются активные и интерактивные формы проведения занятий:
интерактивный опрос;
модельный метод обучения – моделирование в процессе обучения тех или иных ситуаций;
кейс-стади – имитация в учебном процессе реального события для демонстрации того или иного изучаемого явления, студентам предлагается рассмотреть случай, который требует решения тех или иных задач текущей темы;
метод проектов – распределение заданий между учащимися, предполагающий сбор и анализ информации, а также представление полученных результатов в виде реферата;
метод Делфи – метод поиска быстрых решений в группе;
эвристические технологии генерирования идей: «мозговой штурм», синектика, ассоциации;
тренинг – активное овладение и развитие знаний, умений и навыков.
6. Учебно-методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины.
7. Учебно-методическое и информационное обеспечение дисциплины «Криптографические протоколы»:
а) основная литература:
1. , Шанкин . Под редакцией , / , . . – М.: СОЛОН-ПРЕСС, 2007. . – 512 с, – (Серия книг «Аспекты защиты»). – ISBN -3.
б) дополнительная литература:
2. Основы криптографии [Текст]: учеб. пособие / ёров [и др.]. – 3-е изд., испр. и доп. – М.: Гелиос АРВ, 2005. – 479, [1] с. – Библиогр.: с. 469-475. – ISBN -0.
3. Василенко -числовые алгоритмы в криптографии [Текст] / . – М.: Изд-во Моск. Центра непрерыв. мат. образования, 2003. – 325, [3] с. – Библиогр. – ISBN -4.
4. Рябко современной криптографии для специалистов в информационных технологиях [Текст] / , . – М.: Науч. мир, 2004. – 172, [4] с. – Библиогр. – ISBN -1 (в пер.).
5. Криптография [Текст] / Н. Смарт; пер. с англ. ; под ред. . – М.: Техносфера, 2006. – 525, [3] с.: рис., табл. – (Мир программирования). – ISBN -1. – ISBN (англ.).
6. Салий методы и средства защиты информации. – 2010. – URL:
http://www. *****/files/nodes/11017/V. N._Saliy._Kriptograficheskie_metody_i_sredstva_zashchity_informacii. doc
7. Фомичев математика и криптология [Текст]: курс лекций / ; общ. ред. . – М.: ДИАЛОГ-МИФИ, 2003. – 397, [3] с. – Библиогр.: с. 386-назв.). – ISBN -8.
8. Виноградов теории чисел [Текст]: учеб. пособие / . – 10-е изд., стер. – СПб.; М.; Краснодар: Лань, 2004. – 176 с. – (Учебники для вузов. Специальная литература). – ISBN -9.
в) программное обеспечение и Интернет-ресурсы:
Стандартное программное обеспечение компьютерного класса, интегрированная среда разработки программного обеспечения Microsoft Visual Studio.
9. Материально-техническое обеспечение дисциплины
Лекционные занятия проводятся в аудиториях на 40-60 посадочных мест, в отведенных для занятий аудиториях имеются учебные доски (большого размера) для визуализации информации. Также в ходе лекционных занятий применяются учебно-демонстрационные мультимедийные презентации, которые обеспечиваются следующим техническим оснащением:
1. Компьютер (в комплекте с колонками)
2. Мультимедийный проектор
3. Экран.
Лабораторные занятия: дисплейные классы на 10-20 посадочных мест с установленным необходимым инструментальным программным обеспечением.
Программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и Примерной ООП ВПО по специальности 090301 «Компьютерная безопасность» и специализации «Математические методы защиты информации».
Автор
ст. преподаватель
Программа одобрена на заседании кафедры теоретических основ компьютерной безопасности и криптографии от «___» __________2012 года, протокол № ___
Зав. кафедрой
теоретических основ
компьютерной безопасности и криптографии
профессор
Декан факультета
компьютерных наук
и информационных технологий
доцент
