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

Кафедра информатики т. 515-418
Шевченко Игорь Иванович shevch@dvgu.ru
Пятница 12:30-15:00 (ауд. 332)
Консультация: 9 января 2004 г. в 16:00 в ауд. 332
Экзамен: 10 января 2004 г. 9:00 - 11:00
Повторный прием: 30 января 2004 г. 15:00 - 17:00 в ауд. 332

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

  1. Схема Шеннона. Симметричные криптосистемы. Перестановки и подстановки. Одноалфавитные и многоалфавитные криптосистемы. Потоковые и блочные шифры.
  2. Модулярные шифры. Шифры Вижинера. Автоматический и бегущий выбор ключа.
  3. Шифры Вернама.
  4. Шифры Плейфейера.
  5. Шифры Хилла.
  6. Шифры одноразового блокнота.
  7. Типы криптоанализа.
  8. Шифр Фейсталя. Диффузия и конфузия. Структура шифра. Алгоритм дешифрования.
  9. DES. Лавинный эффект. Надежность. Криптоанализ.
  10. Режимы работы DES. Сцепление блоков. Шифрованная обратная связь. Двойной и тройной DES. Другие симметрично-блочные шифры.
  11. Простые числа. Основная теорема арифметики.
  12. Теорема Евклида о существовании бесконечного множества простых чисел.
  13. Теорема о промежутках между простыми числами.
  14. Свойства арифметики в классах вычетов.
  15. Малая теорема Ферма. Теорема Эйлера.
  16. RSA: основные элементы криптосистемы. Шифрование и дешифрование.
  17. Проверка на простоту заданного числа.
  18. Алгоритм Евклида.
  19. Вычисление мультипликативного обратного.
  20. Цифровая подпись.
  21. Дискретные логарифмы. Схема обмена ключами Диффи-Хеллмана и ее модификация. Схема Эль Гамаля.
  22. Криптосистемы, базирующиеся на задаче о рюкзаке.
  23. Греко-китайская теорема об остатках и ее применения.
  24. Различные варианты машин Тьюринга и их вычислительные возможности. Имитация машин Тьюринга на реальных компьютерах.
  25. Классы языков (рекурсивные, рекурсивно перечислимые). Временная сложность вычислений. Классы P и NP.
  26. Примеры NP-трудных проблем.
  27. Дополнения языков из NP.
  28. Поблемы, разрешимые в полиномиальном пространстве (PS).
  29. Классы RP и ZRP. Их сотношение с классами P и NP.
  30. Сложность проверки простоты. Рандомизация проверки простоты. Числа Кармайкла.
  31. Неклассические задачи криптографии. Протокол, базирующийся на изоморфизме графов. Общая схема процедуры аутентификации с нулевым разглашением.
Список рекомендуемой литературы
  1. Саломаа А. Криптография с открытым ключом. М.: Мир, 1996.
  2. Акритас. А. Основы компьютерной алгебры. М.: Мир, 1994
  3. Столлингс В. Криптография и защита сетей: принципы и практика. М.: Изд. дом Вильямс, 2001.
  4. Скембрей Дж, Мак-Клар С., Курц Дж. Секреты хакеров. Безопасность сетей - готовые решения. М.: Изд. дом Вильямс, 2001.
  5. Ноден П., Китте К. Алгебраическая алгоритмика (с упражнениями и решениями). - М.: Мир, 1994
  6. Введение в криптографию. /Под общ. ред. В.В. Ященко. - М.: МЦНМО: "ЧеРо", 1999.
  7. Молдовян Р.А., Молдовян Н.А., Советов Б.Я. Криптография. - СПб: Лань, 2001.
  8. Хопкрофт Дж., Ульман Дж., Мотвани Р. Введение в теорию автоматов, языков и вычислений. - М.: Изд. дом Вильямс, 2002.
  9. Разнообразные материалы, посвященные книге Столлингс В. Криптография и защита сетей: принципы и практика. М.: Изд. дом Вильямс, 2001, и не только http://williamstallings.com/Crypto3e.html
Задачи
  1. Продемонстрировать лавинный эффект в DES: написать программу, которая вычисляет расстояние Хемминга для изменений в тексте и в ключе на каждом шаге шифрования и выводит результаты в виде таблицы или графика.
  2. Вариант 1 (Саломаа). Доказать, что если при использовании DES заменить все биты на их дополнения одновременно в открытом тексте и ключе, то произойдет аналогичная замена в закрытом тексте.
    Вариант 2 (Столлингс). Докажите, что если Y=DES(X,K), то Y'=DES(X',K') (Z' - обозначает слово, составленное из дополнений соответствующих битов бинарноо слова Z).
    a) Используйте следующее равенство для логических переменных (x+y)'=x'+y.
    b) Для анализа DES с помощью простого перебора ключей необходимо исследовать 2^56 вариантов. Не меняет ли приведенный результат приведенную оценку?
  3. Доказать, что перестановка П(m): 0, 2, … , 2^n-1 (взаимно однозначное отображение n-битовых целых чисел в себя) в более, чем 60% случаев имеет неподвижную точку.
  4. Доказать, что дешифрование в DES - это обращение шифрования (ключи в обратном порядке).
  5. Показать, что в DES первые 24 бита любого подключа выбираются из одного 28-битного множества исходного ключа, а другие - из непересекающегося с ним 28-битного подмножества этого ключа.
  6. Сколько возможных ключей позволяет использовать шифр Плейфейра? (Представить в виде степени двойки.)
  7. Какова методика криптоанализа шифра Хилла с избранным открытым текстом?
  8. Чему равен НОД (n, n+1)?
  9. Показать, что утверждение n - простое т. и т.т., когда n |2^n-2 неверно. (Доказать, что для n=341=11*31, правая часть удовлетворяется.)
  10. Алгоритм Стайна (анализ). Сравнение с алгоритмом Евклида (на примере вычисления нод(2152,764)).
  11. Решить систему x=2 mod 3, x=3 mod 5, x= 2 mod 7.
  12. Шесть профессоров начинают читать свои курсы в ПН, ВТ, СР, ЧТ, ПТ, СБ через 2, 3, 4, 1, 6, 5 дней соответственно. Лекции не читаются по ВС (отменяются). Когда в первый раз все лекции выпадут на ВС и будут отменены.

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

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

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

    1. Классическое шифрование;
    2. DES;
    3. Криптосистема RSA и связанные с ней вопросы;
    4. Теория сложности.