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

Кафедра информатики т. 515-418
Шевченко Игорь Иванович igor@tinro.ru
Пятница
лаб. 9:30-10:50 (ауд. 332)

лекция 11:00-12:20 (ауд. 332)

лаб. 13:30-14:50 (ауд. 332)
Консультация:
Экзамен/зачет:

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

  1. Схема Шеннона. Симметричные криптосистемы. Перестановки и подстановки. Одноалфавитные и многоалфавитные криптосистемы. Потоковые и блочные шифры.
  2. Модулярные шифры. Шифры Вижинера. Автоматический и бегущий выбор ключа.
  3. Шифры Вернама, Плейфейера, Хилла. Шифр одноразового блокнота.
  4. Шифр Фейсталя. Диффузия и конфузия. Структура шифра. Алгоритм дешифрования.
  5. DES. Лавинный эффект. Надежность. Криптоанализ.
  6. Режимы работы DES. Сцепление блоков. Шифрованная обратная связь. Двойной и тройной DES. Другие симметрично-блочные шифры.
  7. Простые числа. Основная теорема арифметики. Теорема Евклида о существовании бесконечного множества простых чисел. Теорема о промежутках между простыми числами.
  8. Малая теорема Ферма. Теорема Эйлера.
  9. RSA: основные элементы криптосистемы. Шифрование и дешифрование.
  10. Проверка на простоту заданного числа. Алгоритм Евклида. Вычисление мультипликативного обратного.
  11. Дискретные логарифмы. Схема обмена ключами Диффи-Хеллмана и ее модификация. Схема Эль Гамаля.
  12. Криптосистемы, базирующиеся на задаче о рюкзаке.
  13. Греко-китайская теорема об остатках и ее применения.
  14. Различные варианты машин Тьюринга и их вычислительные возможности. Имитация машин Тьюринга на реальных компьютерах.
  15. Классы языков (рекурсивные, рекурсивно перечислимые). Временная сложность вычислений. Классы P и NP.
  16. Примеры NP-трудных проблем.
  17. Дополнения языков из NP.
  18. Классы RP и ZRP. Их соотношение с классами P и NP.
  19. Сложность проверки простоты. Рандомизация проверки простоты. Числа Кармайкла.
  20. Протокол с нулевым разглашением, базирующийся на изоморфизме графов. Аутентификация.
  21. Разделение секрета.
  22. Неотслеживаемость и затеняющая подпись.
  23. Квантовая криптография.
Список рекомендуемой литературы
  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.
Задачи
(заключительная версия 20.12.2004)
  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. Доказать, что перестановка П(m): 0, 2, … , 2^n-1 (взаимно однозначное отображение n-битовых целых чисел в себя) в более, чем 60% случаев имеет неподвижную точку.
  11. Доказать, что дешифрование в DES - это обращение шифрования (ключи в обратном порядке).
  12. Показать, что в DES первые 24 бита любого подключа выбираются из одного 28-битного множества исходного ключа, а другие - из непересекающегося с ним 28-битного подмножества этого ключа.
  13. Зашифровать слово, используя схему, базирующюся на задаче о рюкзаке.
  14. Доказать, что n_i^s=2^i
    - является минимальной супервозрастающей,
    - может использоваться для кодирования любого числа,
    - никакая другая не обладает этим свойством.
  15. нод(a,b)=1. Выразить \phi(a*b) через \phi(a) и \phi(b).
  16. RSA:
    - если нод(a,b)=1 => c^d mod n=w,
    - e по d единственное,
    - если нод(a,b)\not =1 => c^d mod n=w,
    - найти неизвестные параметры через известные.
  17. Предположим, что найден эффективный способ решения задачи e по d. Означает ли это, что можно решать эффективно задачу факторизации (p и q по n).
  18. Доказать, что решение системы из греко-китайской теоремы об остатках.
  19. Найти (73*1651)mod 1813 (с использованием греко-китайской теоремы).
  20. Описать машину Тьюринга, складывающую числа, записанные на ленту.
  21. Задачи по разделению секрета.

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

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

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

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