КРИПТОГРАФИЧЕСКИЕ МЕТОДЫ ЗАЩИТЫ ИНФОРМАЦИИ
(2006/07 уч. год, осенний семестр)


810

Кафедра информатики т. 515418
Шевченко Игорь Иванович igor@tinro.ru
Вторник
лаб. - вт. 8:00 209ц
лаб.- вт. 11:00 332
лекция - вт. 9:30 338
Консультация:
Экзамен/зачет:

Вопросы
(список будет модифицирован по факту)

  1. Основные принципы информатики (инфоратика как наука)
  2. Схема Шеннона. Симметричные криптосистемы. Перестановки и подстановки. Одноалфавитные и многоалфавитные криптосистемы. Потоковые и блочные шифры.
  3. Модулярные шифры. Шифры Вижинера. Автоматический и бегущий выбор ключа.
  4. Шифры Вернама, Плейфейера, Хилла. Шифр одноразового блокнота.
  5. Шифр Фейсталя. Диффузия и конфузия. Структура шифра. Алгоритм дешифрования.
  6. DES. Лавинный эффект. Надежность. Криптоанализ.
  7. Режимы работы DES. Сцепление блоков. Шифрованная обратная связь. Двойной и тройной DES. Другие симметрично-блочные шифры.
  8. Группы, кольца, поля. Вычеты по модулю.
  9. Простые числа. Основная теорема арифметики. Теорема Евклида о существовании бесконечного множества простых чисел. Теорема о промежутках между простыми числами.
  10. Малая теорема Ферма. Теорема Эйлера.
  11. RSA: основные элементы криптосистемы. Шифрование и дешифрование.
  12. Эффективный алгоритм возведения в степень. Рандомизация проверки простоты. Числа Кармайкла. Алгоритм Евклида. Вычисление мультипликативного обратного.
  13. Первообразные корни. Дискретные логарифмы. Схема обмена ключами Диффи-Хеллмана и ее модификация. Схема Эль Гамаля.
  14. Криптосистемы, базирующиеся на задаче о рюкзаке.
  15. Греко-китайская теорема об остатках и ее применения.
  16. Различные варианты машин Тьюринга и их вычислительные возможности. Имитация машин Тьюринга на реальных компьютерах.
  17. Классы языков. Временная сложность вычислений. Классы P и NP.
  18. Примеры NP-трудных проблем.
  19. Дополнения языков из NP.
  20. Классы RP и ZRP. Их соотношение с классами P и NP.
  21. Языки составных и простых чисел.
Список рекомендуемой литературы
  1. Саломаа А. Криптография с открытым ключом. М.: Мир, 1996.
  2. Акритас. А. Основы компьютерной алгебры. М.: Мир, 1994
  3. Столлингс В. Криптография и защита сетей: принципы и практика. М.: Изд. дом Вильямс, 2001.
  4. Скембрей Дж, Мак-Клар С., Курц Дж. Секреты хакеров. Безопасность сетей - готовые решения. М.: Изд. дом Вильямс, 2001.
  5. Ноден П., Китте К. Алгебраическая алгоритмика (с упражнениями и решениями). - М.: Мир, 1994
  6. Введение в криптографию /Под общ. ред. В.В. Ященко. - М.: МЦНМО: "ЧеРо", 1999.
  7. Молдовян Р.А., Молдовян Н.А., Советов Б.Я. Криптография. - СПб: Лань, 2001.
  8. Хопкрофт Дж., Ульман Дж., Мотвани Р. Введение в теорию автоматов, языков и вычислений. - М.: Изд. дом Вильямс, 2002.
  9. Математические и компьютерные основы криптологии. - Минск: ООО "Новое знание", 2003.
  10. Материалы, посвященные книге Столлингс В. Криптография и защита сетей: принципы и практика. М.: Изд. дом Вильямс, 2001, и не только http://williamstallings.com/Crypto3e.html
  11. Брассар Ж. Современная криптография. - М.: Полимед, 1999.
  12. Фергюсон Н., Шнайдер Б. Практическая криптография. -- М.: Вильямс, 2005.
  13. Computing Curricula 2001: Computer Science (РЕКОМЕНДАЦИИ ПО ПРЕПОДАВАНИЮ ИНФОРМАТИКИ В УНИВЕРСИТЕТАХ)
  14. The Great Principles of Computing Peter Denning teaches students at the Naval Postgraduate School how to develop strategic, big-picture thinking about the field of computing.
  15. Building a Culture of Innovation Peter Denning talks about transforming practice in a community, cognitive blindness and finding dead cows
  16. Is Computer Science Science? Computer science meets every criterion for being a science, but it has a self-inflicted credibility problem.
  17. Терехов А.Н. КАК ГОТОВИТЬ СИСТЕМНЫХ ПРОГРАММИСТОВ
  18. А.В. Гиглавый "Болонский процесс" и содержание ИТ-образования
  19. Непейвода Н. Какая математика нужна информатикам? Сегодня многим ясно, что Россия не может конкурировать с Индией и Китаем в области кодирования и программирования простых систем. Для нашей страны характерны более высокие стоимость рабочей силы и затраты на поддержание определенного уровня жизни, а в результате отечественные фирмы сами привлекают индийских кодировщиков. России нужно занять свою нишу на уровне brainware, а для этого — пересмотреть систему подготовки аналитиков и постановщиков задач.
  20. MathWorld
  21. RSA-576 Factored
  22. RSA-200 Factored
  23. RSA-640 Factored
  24. MysteryTwister 2005 is an international crypto competition. During the year 2005, different tasks will be set, altogether 13 CryptoChallenges, CC1 to CC13, of increasing difficulty, such as, for example, decrypting an encrypted message or forging a digital signature. The variety of topics, which will be covered by the collection of challenges, is intended to provide a survey of modern cryptology.
  25. Millennium Problems: In order to celebrate mathematics in the new millennium, The Clay Mathematics Institute of Cambridge, Massachusetts (CMI) has named seven Prize Problems. P vs NP Problem
  26. Александр Разборов Theoretical Computer Science: взгляд математика (Опубликовано в журнале "Компьютерра" №2 от 22 января 2001 года)
  27. Криптографические алгоритмы
  28. Назначение и структура алгоритмов шифрования
  29. Алгоритмы шифрования — финалисты конкурса AES. Часть 1.
  30. Алгоритмы шифрования — финалисты конкурса AES. Часть 2.
Задачи
(список будет модифицирован по факту)
  1. Расшифровать заданное сообщение с использованием частотной таблицы.
  2. Сколько всего различных модулярных шифров в английском языке?
  3. Показать, что нод(m,n)=1 н. и д. для однозначности дешифрования модулярного шифра.
  4. Сколько возможных ключей позволяет использовать шифр Плейфейра? (Представить в виде степени двойки.)
  5. Реализовать схему шифрования-дешифрования Плейфейера в виде программы.
  6. Какие из изученных классических шифров являются групповыми?
  7. Какова методика криптоанализа шифра Хилла с избранным открытым текстом?
  8. Продемонстрировать лавинный эффект в DES: написать программу, которая вычисляет расстояние Хемминга для изменений в тексте и в ключе на каждом шаге шифрования и выводит результаты в виде таблицы или графика.
  9. Вариант 1 (Саломаа). Доказать, что если при использовании DES заменить все биты на их дополнения одновременно в открытом тексте и ключе, то произойдет аналогичная замена в закрытом тексте.
    Вариант 2 (Столлингс). Докажите, что если Y=DES(X,K), то Y'=DES(X',K') (Z' - обозначает слово, составленное из дополнений соответствующих битов бинарноо слова Z).
    a) Используйте следующее равенство для логических переменных (x+y)'=x'+y.
    b) Для анализа DES с помощью простого перебора ключей необходимо исследовать 2^56 вариантов. Не меняет ли приведенный результат приведенную оценку?
  10. Доказать, что перестановка П: 0, 1, 2, … , 2^n-1 (взаимно однозначное отображение n-битовых целых чисел в себя) в более, чем 60% случаев имеет неподвижную точкуб n \geq 2.
  11. Показать, что в DES первые 24 бита любого подключа выбираются из одного 28-битного множества исходного ключа, а другие - из непересекающегося с ним 28-битного подмножества этого ключа.
  12. Зашифровать слово computer, используя схему, базирующюся на задаче о рюкзаке.
  13. Доказать, что n_i^s=2^i, i=1,...,k:
    - является минимальной супервозрастающей последовательностью,
    - может использоваться для кодирования любого числа (при достаточно большом k),
    - никакая другая не обладает этим свойством.
  14. нод(a,b)=1. Выразить \phi(a*b) через \phi(a) и \phi(b).
  15. RSA:
    - если нод(a,b)=1 => c^d mod n=w,
    - e по d единственное,
    - если нод(a,b)\not =1 => c^d mod n=w,
    - найти неизвестные параметры через известные.
  16. Предположим, что найден эффективный способ решения задачи нахождения d по e. Означает ли это, что можно решать эффективно задачу факторизации (нахождения p и q по n).
  17. Исполнить WITNESS при a=7, p=561.
  18. Инвариант цикла в EXTENDED EUCLID.
  19. нод(n,n+1)=?
  20. Доказать, что если n - простое (>2), то n делит 2^n-2. Доказать, что составное число 341 делит 2^341-2.
  21. Найти все первообразные корни по модулю 25 (с использованием критерия).
  22. Решить систему x=2 mod 3, x=3 mod 5, x= 2 mod 7.
  23. Шесть профессоров начинают читать свои курсы в ПН, ВТ, СР, ЧТ, ПТ, СБ каждый 2, 3, 4, 1, 6, 5 дни соответственно. Лекции не читаются по ВС (отменяются). Когда в первый раз все лекции выпадут на ВС и будут отменены.
  24. Найти (73*1651)mod 1813 (с использованием греко-китайской теоремы).
  25. Описать машину Тьюринга, проверяющую, делится ли одно заданное натуральное число на другое.
  26. Разработать алгоритм, который решает проблему 2ВЫП за полиномиальное время.

    Для получения положительной оценки требуется

    1. Реферат на 2 стр. по согласованной (темы для согласования нужно присылать по почте) теме (до экзамена/зачета) и его защита. Основное направление - криптоанализ и отдельные составляющие изученных систем (DES, рюкзак, RSA), а также доказательство принадлежности проблем к некоторому классу сложности, криптографические протоколы, современные криптографические системы и т.п.
    2. Решение всех задач (до экзамена/зачета).
    3. Знание алгоритмов и умение решать элементарные задачи (см. Темы для дополнительных вопросов).

    Темы для дополнительных вопросов

    1. Классическое шифрование;
    2. DES;
    3. RSA;
    4. теория сложности;
    5. криптографические протоколы;
    6. современные проблемы криптографии и др.

    Темы рефератов