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

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

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

  1. Схема Шеннона. Симметричные криптосистемы. Перестановки и подстановки. Одноалфавитные и многоалфавитные криптосистемы. Потоковые и блочные шифры.
  2. Модулярные шифры. Шифры Вижинера. Автоматический и бегущий выбор ключа. Шифры Плейфейера, Хилла, одноразового блокнота. Барабанные шифры. Типы криптоанализа.
  3. Шифр Фейсталя. Диффузия и конфузия. Структура шифра. Алгоритм дешифрования.
  4. DES. Лавинный эффект. Надежность. Криптоанализ.
  5. Режимы работы DES. Сцепление блоков. Шифрованная обратная связь. Двойной и тройной DES. Другие симметрично-блочные шифры.
  6. Канальное и сквозное шифрование в сетях передачи данных. Распределение ключей.
  7. Генерирование случайных чисел. Алгоритм Лемера.
  8. Простые числа. Основная теорема арифметики. Теорема Евклида о существовании бесконечного множества простых чисел. Теорема о промежутках между простыми числами.
  9. Малая теорема Ферма. Теорема Эйлера.
  10. RSA: основные элементы криптосистемы. Шифрование и дешифрование.
  11. Цифровая подпись.
  12. Дискретные логарифмы. Схема обмена ключами Диффи-Хеллмана и ее модификация. Схема Эль Гамаля.
  13. Криптосистемы, базирующиеся на задаче о рюкзаке.
  14. Греко-китайская теорема об остатках и ее применения.
  15. Сложность вычислений. Гипотеза P=NP и стойкость криптосистем.
  16. Односторонние функции. Гипотеза о существовании односторонних функций и стойкость криптосистем.
  17. Псевдослучайные генераторы.
  18. Интерактивные системы доказательств с нулевым разглашением. Модель протокола с нулевым разглашением.
  19. Протокол, базирующийся на изоморфизме графов. Аутентификация.
  20. Неотслеживаемость и затеняющая подпись.
Список рекомендуемой литературы
  1. Саломаа А. Криптография с открытым ключом. М.: Мир, 1996.
  2. Акритас. А. Основы компьютерной алгебры. М.: Мир, 1994
  3. Столлингс В. Криптография и защита сетей: принципы и практика. М.: Изд. дом Вильямс, 2001.
  4. Скембрей Дж, Мак-Клар С., Курц Дж. Секреты хакеров. Безопасность сетей - готовые решения. М.: Изд. дом Вильямс, 2001.
  5. Ноден П., Китте К. Алгебраическая алгоритмика (с упражнениями и решениями). - М.: Мир, 1994
  6. Введение в криптографию. /Под общ. ред. В.В. Ященко. - М.: МЦНМО: "ЧеРо", 1999.
  7. Молдовян Р.А., Молдовян Н.А., Советов Б.Я. Криптография. - СПб: Лань, 2001.
  8. Разнообразные материалы, посвященные книге Столлингс В. Криптография и защита сетей: принципы и практика. М.: Изд. дом Вильямс, 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. Почему в алгоритме Лемера 2^31-1 выбирается в качестве m, хотя для 2^31, например, операция сравнения реализуется проще?
  9. Показать, что в алгоритме Лемера обеспечение полного периода не гарантирует качества генерируемой псевдослучайной последовательности. (Сравнить, например, х_{n+1}=6x_n mod 13 и х_{n+1}=7x_n mod 13.)
  10. Какой максимальный период можно получить для генератора: х_{n+1}=а x_n mod 24 (чему равно а, какие ограничения на х_0?)
  11. Доказать, что если m - простое и алгоритм Лемера с параметром a порождает последовательности максимального периода, то при использовании параметра а^k также будут порождаться последовательности максимального периода, если k меньше m, а m-1 не делится на k. (Проверить для х_0=1, m=1, а=3, 3^2, 3^3, 3^4.)
  12. Чему равен НОД (n, n+1)?
  13. Показать, что утверждение n - простое т. и т.т., когда n |2^n-2 неверно. (Доказать, что для n=341=11*31, правая часть удовлетворяется.)

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

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

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

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