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


2955

Последняя модификация

Кафедра информатики, т. 515418
Шевченко Игорь Иванович igor@tinro.ru
Занятия:
лекция - чт. 9:40 -11:10 338
лаб. - чт. 11:50-13:20 332
Консультация:
Экзамен

Вопросы

  1. Схема Шеннона. Симметричные криптосистемы. Перестановки и подстановки. Одноалфавитные и многоалфавитные криптосистемы. Потоковые и блочные шифры.
  2. Модулярные шифры. Шифры Виженера. Автоматический и бегущий выбор ключа.
  3. Шифры Вернама, Плейфейера, Хилла. Шифр одноразового блокнота. Абсолютно криптостойкие шифры.
  4. Шифр Файстеля. Структура шифра. Алгоритм дешифрования. Диффузия и конфузия.
  5. Осноы теории информации Шеннона. Применение к оценке криптостойкости. Совершенные криптостойкие системы.
  6. DES: шифрование и дешифрование. Лавинный эффект. Надежность. Криптоанализ.
  7. Режимы работы DES. Сцепление блоков. Шифрованная обратная связь. Двойной и тройной DES. Другие симметрично-блочные шифры.
  8. Криптосистемы, базирующиеся на задаче о рюкзаке.
  9. Группы, кольца, области целостности, поля. Классы вычетов по модулю.
  10. Простые числа. Основная теорема арифметики. Теорема Евклида о существовании бесконечного множества простых чисел. Теорема о промежутках между простыми числами.
  11. Малая теорема Ферма. Теорема Эйлера.
  12. RSA: основные элементы криптосистемы. Шифрование и дешифрование.
  13. Греко-китайская теорема об остатках и ее применения.
  14. Возведение в степень с использованием метода последовательного возведения в квадрат.
  15. Теорема о корнях x^2=1 mod p для нечетного простого p. Рандомизация проверки простоты (WITNESS). Числа Кармайкла.
  16. Алгоритм Евклида. Расширенный алгоритм Евклида для вычисления мультипликативного обратного.
  17. Первообразные корни и их свойства. Дискретные логарифмы.
  18. Протокол взаимной аутентификации. Схемы обмена ключами Диффи-Хеллмана и Эль Гамаля.
Список рекомендуемой литературы и интернет-источники
    Информационная среда по некоторым разделам алгебры и ее приложениям
  1. Саломаа А. Криптография с открытым ключом. М.: Мир, 1996.
  2. Акритас А. Основы компьютерной алгебры. М.: Мир, 1994
  3. Столлингс В. Криптография и защита сетей: принципы и практика. М.: Изд. дом Вильямс, 2003.
  4. Материалы, посвященные книге Столлингс В. Криптография и защита сетей: принципы и практика и не только http://williamstallings.com/Crypto3e.html
  5. Смарт Н. Криптография. - Москва: Техносфера, 2005.
  6. Брассар Ж. Современная криптология. - М.: Полимед, 1999.
  7. Осипян В. О., Осипян К. В. Криптография в упражнениях и задачах Издательство: Гелиос АРВ, 2004.
  8. Панасенко С. Алгоритмы шифрования. Специальный справочник. -- СПб.:БХВ-Петербург, 2009.
  9. Baigneres T., Junod P., Lu Yi, Monnerat J., Vaudenay S. A CLASSICAL INTRODUCTION TO CRYPTOGRAPHY EXERCISE BOOK. - Springer Science+Business Media, Inc., 2006.
  10. Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography (Discrete Mathematics and Its Applications, Vol. 6). CRC Press, 2001.
  11. Скембрей Дж, Мак-Клар С., Курц Дж. Секреты хакеров. Безопасность сетей - готовые решения. М.: Изд. дом Вильямс, 2001.
  12. Ноден П., Китте К. Алгебраическая алгоритмика (с упражнениями и решениями). - М.: Мир, 1994
  13. Введение в криптографию /Под общ. ред. В.В. Ященко. - М.: МЦНМО: "ЧеРо", 1999.
  14. Молдовян Р.А., Молдовян Н.А., Советов Б.Я. Криптография. - СПб: Лань, 2001.
  15. Хопкрофт Дж., Ульман Дж., Мотвани Р. Введение в теорию автоматов, языков и вычислений. - М.: Изд. дом Вильямс, 2002.
  16. Математические и компьютерные основы криптологии. - Минск: ООО "Новое знание", 2003.
  17. Фергюсон Н., Шнайдер Б. Практическая криптография. -- М.: Вильямс, 2005.
  18. Computing Curricula 2001: Computer Science (РЕКОМЕНДАЦИИ ПО ПРЕПОДАВАНИЮ ИНФОРМАТИКИ В УНИВЕРСИТЕТАХ)
  19. 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.
  20. Building a Culture of Innovation Peter Denning talks about transforming practice in a community, cognitive blindness and finding dead cows
  21. Is Computer Science Science? Computer science meets every criterion for being a science, but it has a self-inflicted credibility problem.
  22. Терехов А.Н. КАК ГОТОВИТЬ СИСТЕМНЫХ ПРОГРАММИСТОВ
  23. А.В. Гиглавый "Болонский процесс" и содержание ИТ-образования
  24. Непейвода Н. Какая математика нужна информатикам? Сегодня многим ясно, что Россия не может конкурировать с Индией и Китаем в области кодирования и программирования простых систем. Для нашей страны характерны более высокие стоимость рабочей силы и затраты на поддержание определенного уровня жизни, а в результате отечественные фирмы сами привлекают индийских кодировщиков. России нужно занять свою нишу на уровне brainware, а для этого — пересмотреть систему подготовки аналитиков и постановщиков задач.
  25. MathWorld
  26. RSA-576 Factored
  27. RSA-200 Factored
  28. RSA-640 Factored
  29. 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.
  30. 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
  31. Александр Разборов Theoretical Computer Science: взгляд математика (Опубликовано в журнале "Компьютерра" №2 от 22 января 2001 года)
  32. Криптографические алгоритмы
  33. Назначение и структура алгоритмов шифрования
  34. Алгоритмы шифрования — финалисты конкурса AES. Часть 1.
  35. Алгоритмы шифрования — финалисты конкурса AES. Часть 2.
  36. Питер Норвиг Научитесь программировать за десять лет
  37. Авдошин С.М., Савельева А.А. Криптоанализ: современное состояние и перспективы развития
  38. В Вене запущена квантовая криптографическая система
  39. Подтвердилось открытие самого большого известного простого числа.
  40. Quantum cryptography by Nicolas Gisin, Grґegoire Ribordy, Wolfgang Tittel and Hugo Zbinden
  41. The Security of Practical Quantum Key Distribution by Valerio Scarani, Helle Bechmann-Pasquinucci, Nicolas J. Cerf, Miloslav DuЎsek, Norbert LЁutkenhaus, Momtchil Peev
  42. Quantum Cryptography by Hoi-Kwong Lo and Yi Zhao
  43. Введение в квантовую криптографию
  44. An introduction to the Rijndael cipher, by Straubin
Этические принципы,
которые следует соблюдать при выполнении заданий (см., например,
Code of Academic Integrity)
  1. Все идеи, аргументация и изложение материала, которые встречаются в тексте без ссылки на оригинал, должны быть результатом творческой деятельности самого студента. Все заимствования из работ других авторов должны быть соответствующим образом обозначены. Это также относится к использованию результатов творческой деятельности других: перефразированному тексту, заимствованным выводам, данным, примерам, иллюстрациям и т.д. Нарушение этих стандартов является плагиатом.
  2. Все экспериментальные данные, результаты наблюдений, статистические сведения и любая другая используемая в работе в качестве исходной информация должна быть подлинной. Любая модификация используемой информации должна быть четко обозначена. Данные не должны фальсифицироваться ни в коем случае. Нарушение квалифицируется как подлог.
  3. Студенты могут сотрудничать при выполнении академических заданий только в пределах, оговоренных преподавателем. Студентам запрешается полностью или частично выполнять задания и готовить ответы на зачетах/экзаменах за других. Студентам запрещается использовать полностью или частично то, что было подготовлено другим студентом как задание или ответ на экзамене/зачете даже в случае, когда этот другой студент информирован и согласен на заимствование. Студентам запрещается разглашать детали экзамена/зачета без разрешения преподавателя. Студентам запрещено использовать информацию, предоставленную другими студентами о деталях экзамена/зачета без разрешения преподавателя. Нарушение этих стандартов представляет собой сговор.
Задачи

Решения присылать в pdf-файлах, подготовленных в текстовых редакторах. Имена файлов д. содержать информацию о номерах задач и решателе. Текст должен включать данные о решателе, номер и условие задачи. Запрещается любое копирование материалов без ссылки на первоисточник (плагиат), а также нарушения обычных этических норм (подлог, сговор и пр.); см., например, Code of Academic Integrity. Сотрудничество при решении задач приветствуется, но его результатом могут быть только идеи, а изложение должно быть полностью самостоятельным для каждого участника. В файле с решением обязательно перечисляются все те, кто участвовал в процессе поиска решения задачи.
  1. Cхема шифрования-дешифрования Плейфейера
    1. Сколько возможных ключей позволяет использовать шифр Плейфейра? (Представить в виде степени двойки.) Землянникова, Кевролетин В.В.
    2. Реализовать (Mathematica, Scheme, Sage, ...) схему шифрования-дешифрования Плейфейера, подготовить тесты по методу белого ящика, продемонстрировать его работу и методику криптоанализа на достаточно длинном шифрованном тексте. Кевролетин В.В., Подольский
  2. Модулярные шифры
    1. Расшифровать заданное сообщение
      ymjkw jvzjs hdrjy mtisj jixqt
      slhnu mjwyj cyxyt btwp
      с использованием частотной таблицы (модулярный шифр с n=1). , Подольский
    2. Показать, что нод(m,n)=1 н. и д. для однозначности дешифрования модулярного шифра. - Землянникова, Кевролетин В.В., , Подольский
    3. Описать обратное преобразование для модулярного шифра с n/=1. Будет ли оно модулярным шифром. Землянникова, Кевролетин В.В.
    4. Реализовать программу (Mathematica, Scheme, Sage, ...) для подсчета частоты встречаемости отдельных символов, пар, троек и т.д. Подготовить тесты. Продемонстрировать работу на достаточно длинном тексте. Сравнить результаты с известными. Кевролетин В.В., Подольский
    5. Описать и реализовать (Mathematica, Scheme, Sage, ...) методику криптоанализа модулярного шифра с n/=1 (продемонстрировать методику криптоанализа на достаточно длинном шифрованном тексте). Подольский
    6. Сколько всего различных модулярных шифров в m-буквенном алфавите (в английском языке, m=26)? Землянникова, Кевролетин В.В., Подольский
  3. Шифр Виженера
    1. Какова методика криптоанализа шифра Виженера (реализовать (Mathematica, Scheme, Sage, ...) и продемонстрировать методику криптоанализа на достаточно длинном шифрованном тексте.)? Землянникова, Кевролетин В.В.
    2. Шифр Хилла
      1. Каковы необходимые и достаточные условия взаимной однозначности преобразования Хилла? Васильева, Подольский
      2. Если det A= -1 mod 26, то A -- 2*2 матрица инволюций т. и т. т., когда a_{11}+ a_{22}=0 mod 26. Построить матрицу инволюций при a_{11}=2. Васильева, Подольский, Кевролетин В.В.
      3. Какова методика криптоанализа шифра Хилла с избранным открытым текстом? Васильева, Подольский
    3. Докомпьютерные шифры
      1. Какие из докомпьютерных шифров являются групповыми, а какие нет (с доказательством)? Васильева
      2. Показать, что шифр перестановки является линейным преобразованием в B^n, B={0,1}. Васильева, Подольский
      3. Сколько существует нелинейных криптопреобразований B^3->B^3?
      4. Доказать, что перестановка П: 0, 1, 2, … , 2^n-1 (взаимно однозначное отображение n-битовых целых чисел в себя) в более, чем 60% случаев имеет неподвижную точку, n \geq 2. Васильева, Подольский
    4. Применение теории информации
      1. В алфавите исходного и зашифрованного сообщения имеется 6 гласных и 6 согласных букв. Все согласные передаются без искажения. Гласная в 50% случаев передается без искажений, а в 50% равновероятно появление любой гласной буквы. Сколько информации содержится в полученном символе о переданном?
      2. Используя понятие энтропии и информации по Шеннону, оценить минимальное число вопросов, которое необходимо задать, чтобы гарантированно определить задуманное собеседником число (\leq N), если он дает только двоичные ответы на вопросы (да/нет).
      3. Имеется N монет одного достоинства. Одна из них, фальшивая, либо легче, либо тяжелее остальных. Используя понятие энтропии и информации по Шеннону, оценить минимальное число взвешиваний на чашечных весах без гирь, необходимых для гарантированного нахождения фальшивой монеты и определения, является ли она легче или тяжелее остальных.
      4. Какая информация будет получена в результате проведения зачета, если студент получает зачет с вероятностью 0.9, если он готовился, и 0.3, если нет, и известно, что 90% студентов готовились к зачету.
    5. DES
      1. Продемонстрировать лавинный эффект в DES: написать программу (Mathematica, Scheme, Sage), которая вычисляет расстояние Хемминга для изменений в тексте и в ключе. Сгенерировать сообщение и ключ, а затем, последовательно изменяя в сообщении по одному биту, рассчитать расстояние Хемминга с исходным при неизменном ключе. Вычислить также среднее расстояние по всем вариантам. Аналогичные действия проделать для фиксированного сообщения, изменяя ключ. Программу предварительно протестировать, см., например, Ronald L. Rivest TESTING IMPLEMENTATIONS OF DES Подольский
      2. Продемонстрировать различные режимы использования DES (Mathematica, Scheme, Sage, ...). - Васильева, Подольский
      3. Доказать свойство дополнительности DES (1): если C=DES(M,K), то C'=DES(M',K') (Z' - обозначает слово, составленное из дополнений соответствующих битов бинарного слова Z). (Используйте следующее равенство для логических переменных (x+y)'=x'+y.) На первый взгляд, для анализа DES с помощью простого перебора ключей необходимо исследовать 2^56 вариантов. Как меняет приведенный результат эту оценку? - Васильева, Подольский, Землянникова
      4. Пусть \phi_q -- подстановка, которая реализуется цикловой функцией шифра Файстеля, T^n -- циклический сдвиг вправо, 2n -- длина блока. Доказать, что T^n, T^n \phi_q, \phi_q T^n -- инволюции. Васильева, Подольский
    6. Теория сложности вычислений
      1. Разработать алгоритм с полиномиальным (от размерности) временем работы для решения проблемы выполнимости булевой функции, заданной КНФ (конъюнкция дизъюнкций), в которой любая дизъюнкция содержит ровно два литерала (литерал - переменная или ее отрицание). Использовать тот факт, что если один из литералов имеет значение "ложь", то второй должен иметь значение "истина" для того, чтобы КНФ приняла значение "истина" на соответствующем наборе логических значений.
    7. Системы, базирующиеся на задаче о рюкзаке
      1. Зашифровать слово computer, используя схему, базирующуюся на задаче о рюкзаке. - Землянникова, Васильева, Подольский
      2. Доказать, что n_i^s=2^i, i=1,...,k:
        - является минимальной супервозрастающей последовательностью,
        - может использоваться для кодирования любого числа (при достаточно большом k),
        - никакая другая не обладает этим свойством.
      - Землянникова, Васильева
    8. RSA:
      1. Доказать, что a^{-1} mod m существует тогда и только тогда, когда нод(a,m)=1.
      2. Кольцо классов вычетов по mod m (Z_m) является полем тогда и только тогда, когда m - простое. Землянникова, Васильева
      3. Предположим, что найден эффективный способ решения задачи нахождения d по e. Означает ли это, что можно решать эффективно задачу факторизации (нахождения p и q по n).
      4. Показать, что заданный алгоритм осуществляет возведение в степень с использованием метода последовательного возведения в квадрат.
      5. Исполнить WITNESS при a=7, p=561 (Подольский).
      6. Найти количество составных натуральных чисел a, не превосходящих 561 таких, что a^560=1 mod 561.
      7. Инвариант цикла в EXTENDED EUCLID (Подольский).
      8. Найти нод(560,1769) с использованием расширенного алгоритма Евклида. Васильева, Подольский
      9. Доказать, что если n - простое (>2), то n делит 2^n-2. Доказать, что составное число 341 делит 2^341-2.
      10. Уравнение ax=b mod m, нод(a,m)=d>1, имеет решение тогда и только тогда, когда d|b. Если условие выполняется, то имеется ровно d решений по mod m.
      11. Решить систему x=2 mod 3, x=3 mod 5, x= 2 mod 7. (Подольский)
      12. Шесть профессоров начинают читать лекции по своим курсам в ПН, ВТ, СР, ЧТ, ПТ, СБ и читают их далее через 2, 3, 4, 1, 6, 5 дней соответственно. Лекции не читаются по ВС (отменяются). Когда в первый раз все лекции выпадут на ВС и будут отменены.
      13. Найти (678*973)mod 1813 (с использованием греко-китайской теоремы).
      14. Вычислить первые 20 простых чисел Мерсенна. Землянникова, Подольский
      15. Как повлияет на работу RSA тот факт, что одно из чисел (например, p) не является простым, а представляется в виде произведения двух простых: p=p_1*p_2. Васильева, Подольский
      16. Как повлияет на работу RSA тот факт, что шифруемое число не является взаимно простым, например, с p. Васильева
      17. Сгенерировать RSA и провести шифрование/дешифрование (Mathematica, Scheme, Sage). Васильева, Подольский
      18. Пусть n(=pq) и \phi(n) известны, а p и q -- неизвестны. Выразить p и q через n и \phi(n). Рассмотреть случай n=2993 и \phi(n)=2880. Землянникова, Васильева, Подольский
      19. $p,q,e,d,n$ -- параметры RSA.
        Доказать, что имеется $r+s+rs$ неподвижных точек $x$, $1\leq x\leq n-1$, где $r=gcd(p-1,e-1), s=gcd(q-1,e-1)$. (Из-за этого выбираются $p$ и $q$, для которых $r$ и $s$ малы.)
    9. Дискретные логарифмы
      1. Найти наименьший первообразный корень по модулю 25 (с использованием критерия). Подольский
    Для получения положительной оценки требуется
    1. Реферат на 2 стр. (до экзамена/зачета) по согласованной (темы для согласования нужно присылать по почте) теме (до экзамена/зачета) и его защита. Основное направление - криптоанализ и отдельные составляющие изученных систем (докомпьютерные системы, DES, рюкзак, RSA), а также криптографические протоколы, современные криптографические системы, elliptic curve cryptography и т.п. Требуется изучить несколько источников и попытаться самостоятельно изложить материал. Приложить библиографические описания использованных источников. Любое заимствование д.б. явно обозначено см. Этические принципы.
    2. Решение всех задач (до экзамена/зачета).
    3. Знание алгоритмов и умение решать элементарные задачи (см. Темы для дополнительных вопросов).

    Алгоритмы

    1. нахождение обратного;
    2. умножение по mod с использованием греко-китайской теоремы;
    3. возведение в степень по mod с использованием метода последовательного возведения в квадрат;
    4. WITNESS;
    5. EUCLID;
    6. EXTENDED EUCLID и т.д.

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

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

    Материалы для экзамена

    Закрепленные темы рефератов

    1. SSL, Васильева Елена
    2. cast-256, Землянникова
    3. Алгоритм RC5 Подольский Л.А.