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


1877

Последняя модификация 24 января 2008 г.

Кафедра информатики т. 515418
Шевченко Игорь Иванович igor@tinro.ru
Занятия:
лаб. - вт. 9:30 -10:50 332/209ц
лекция - вт. 11:00-12:20 338
Консультация:
Экзамен/зачет: 25 января 2008 г., 16:00 -- 17:30, ауд. 332

Вопросы

  1. Схема Шеннона. Симметричные криптосистемы. Перестановки и подстановки. Одноалфавитные и многоалфавитные криптосистемы. Потоковые и блочные шифры.
  2. Модулярные шифры. Шифры Вижинера. Автоматический и бегущий выбор ключа.
  3. Шифры Вернама, Плейфейера, Хилла. Шифр одноразового блокнота.
  4. Шифр Файстеля. Структура шифра. Алгоритм дешифрования. Диффузия и конфузия.
  5. DES. Лавинный эффект. Надежность. Криптоанализ.
  6. Режимы работы DES. Сцепление блоков. Шифрованная обратная связь. Двойной и тройной DES. Другие симметрично-блочные шифры.
  7. Криптосистемы, базирующиеся на задаче о рюкзаке.
  8. Группы, кольца, поля. Вычеты по модулю.
  9. Простые числа. Основная теорема арифметики. Теорема Евклида о существовании бесконечного множества простых чисел. Теорема о промежутках между простыми числами.
  10. Малая теорема Ферма. Теорема Эйлера.
  11. RSA: основные элементы криптосистемы. Шифрование и дешифрование.
  12. Греко-китайская теорема об остатках и ее применения.
  13. Возведение в степень с использованием метода последовательного возведения в квадрат.
  14. Теорема о корнях x^2=1 mod p для нечетного простого p. Рандомизация проверки простоты (WITNESS). Числа Кармайкла.
  15. Алгоритм Евклида. Расширенный влгоритм Евклида для вычисления мультипликативного обратного.
  16. Первообразные корни и их свойства. Дискретные логарифмы.
  17. Протокол взаимной аутентификации. Схема обмена ключами Диффи-Хеллмана.
Список рекомендуемой литературы
  1. Саломаа А. Криптография с открытым ключом. М.: Мир, 1996.
  2. Акритас. А. Основы компьютерной алгебры. М.: Мир, 1994
  3. Столлингс В. Криптография и защита сетей: принципы и практика. М.: Изд. дом Вильямс, 2001.
  4. Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography (Discrete Mathematics and Its Applications, Vol. 6). CRC Press, 2001.
  5. Скембрей Дж, Мак-Клар С., Курц Дж. Секреты хакеров. Безопасность сетей - готовые решения. М.: Изд. дом Вильямс, 2001.
  6. Ноден П., Китте К. Алгебраическая алгоритмика (с упражнениями и решениями). - М.: Мир, 1994
  7. Введение в криптографию /Под общ. ред. В.В. Ященко. - М.: МЦНМО: "ЧеРо", 1999.
  8. Молдовян Р.А., Молдовян Н.А., Советов Б.Я. Криптография. - СПб: Лань, 2001.
  9. Хопкрофт Дж., Ульман Дж., Мотвани Р. Введение в теорию автоматов, языков и вычислений. - М.: Изд. дом Вильямс, 2002.
  10. Математические и компьютерные основы криптологии. - Минск: ООО "Новое знание", 2003.
  11. Материалы, посвященные книге Столлингс В. Криптография и защита сетей: принципы и практика. М.: Изд. дом Вильямс, 2001, и не только http://williamstallings.com/Crypto3e.html
  12. Брассар Ж. Современная криптография. - М.: Полимед, 1999.
  13. Фергюсон Н., Шнайдер Б. Практическая криптография. -- М.: Вильямс, 2005.
  14. Computing Curricula 2001: Computer Science (РЕКОМЕНДАЦИИ ПО ПРЕПОДАВАНИЮ ИНФОРМАТИКИ В УНИВЕРСИТЕТАХ)
  15. 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.
  16. Building a Culture of Innovation Peter Denning talks about transforming practice in a community, cognitive blindness and finding dead cows
  17. Is Computer Science Science? Computer science meets every criterion for being a science, but it has a self-inflicted credibility problem.
  18. Терехов А.Н. КАК ГОТОВИТЬ СИСТЕМНЫХ ПРОГРАММИСТОВ
  19. А.В. Гиглавый "Болонский процесс" и содержание ИТ-образования
  20. Непейвода Н. Какая математика нужна информатикам? Сегодня многим ясно, что Россия не может конкурировать с Индией и Китаем в области кодирования и программирования простых систем. Для нашей страны характерны более высокие стоимость рабочей силы и затраты на поддержание определенного уровня жизни, а в результате отечественные фирмы сами привлекают индийских кодировщиков. России нужно занять свою нишу на уровне brainware, а для этого — пересмотреть систему подготовки аналитиков и постановщиков задач.
  21. MathWorld
  22. RSA-576 Factored
  23. RSA-200 Factored
  24. RSA-640 Factored
  25. 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.
  26. 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
  27. Александр Разборов Theoretical Computer Science: взгляд математика (Опубликовано в журнале "Компьютерра" №2 от 22 января 2001 года)
  28. Криптографические алгоритмы
  29. Назначение и структура алгоритмов шифрования
  30. Алгоритмы шифрования — финалисты конкурса AES. Часть 1.
  31. Алгоритмы шифрования — финалисты конкурса AES. Часть 2.
  32. Питер Норвиг Научитесь программировать за десять лет
  33. Авдошин С.М., Савельева А.А. Криптоанализ: современное состояние и перспективы развития
Задачи
  1. Описать методику криптоанализа модулярного шифра с n/=1.
  2. Символ a называется неподвижным, если
    a->a*n+k=a (mod m), n\=1.
    Показать, что
    a) Если m -- простое, то всегда существует неподвижный символ.
    b) Если k=0, то существует по крайней мере неподвижный символ.
    с) Если k=0 и m -- четное, то существует по крайней мере два неподвижных символа.
  3. Расшифровать заданное сообщение
    ymjkw jvzjs hdrjy mtisj jixqt
    slhnu mjwyj cyxyt btwp
    с использованием частотной таблицы (модулярный шифр с n=1).
  4. Сколько всего различных модулярных шифров в m-буквенном алфавите (в английском языке, m=26)?
  5. Показать, что нод(m,n)=1 н. и д. для однозначности дешифрования модулярного шифра.
  6. Реализовать в системе Mathematica схему шифрования-дешифрования Плейфейера, подготовить тесты по методу белого ящика, продемонстрировать его работу и методику криптоанализа на достаточно длинном тексте на естественном языке.
  7. Зашифровать слово с использованием шифра Виженера.
  8. Какова методика криптоанализа шифра Виженера?
  9. Сколько возможных ключей позволяет использовать шифр Плейфейра? (Представить в виде степени двойки.)
  10. Какие из докомпьютерных шифров являются групповыми, а какие нет (с доказательством)?
  11. Показать, что шифр перестановки является линейным преобразованием в B^n, B={0,1}.
  12. Сколько существует нелинейных криптопреобразований B^3->B^3?
  13. Каковы необходимые и достаточные условия взаимной однозначности преобразования Хилла?
  14. Какова методика криптоанализа шифра Хилла с избранным открытым текстом?
  15. Используя понятие энтропии и информации по Шеннону, оценить минимальное число вопросов, которое необходимо задать, чтобы гарантированно определить задуманное собеседником число (\leq N), если он дает только двоичные ответы на вопросы (да/нет).
  16. Имеется N монет одного достоинства. Одна из них, фальшивая, либо легче, либо тяжелее остальных. Используя понятие энтропии и информации по Шеннону, оценить минимальное число взвешиваний на чашечных весах без гирь, необходимых для гарантированного нахождения фальшивой монеты и определения, является ли она легче или тяжелее остальных.
  17. Продемонстрировать лавинный эффект в DES: написать программу в системе Mathematica, которая вычисляет расстояние Хемминга для изменений в тексте и в ключе. Сгенерировать сообщение и ключ, а затем, последовательно изменяя в сообщении по одному биту, рассчитать расстояние Хемминга с исходным при неизменном ключе. Вычислить также среднее расстояние по всем вариантам. Аналогичные действия проделать для фиксированного сообщения, изменяя ключ.
  18. Продемонстрировать различные режимы использования DES с использованием системы Mathematica.
  19. Доказать свойство дополнительности DES: если C=DES(M,K), то C'=DES(M',K') (Z' - обозначает слово, составленное из дополнений соответствующих битов бинарного слова Z). (Используйте следующее равенство для логических переменных (x+y)'=x'+y.) На первый взгляд, для анализа DES с помощью простого перебора ключей необходимо исследовать 2^56 вариантов. Не меняет ли приведенный результат эту оценку?
  20. Доказать, что перестановка П: 0, 1, 2, … , 2^n-1 (взаимно однозначное отображение n-битовых целых чисел в себя) в более, чем 60% случаев имеет неподвижную точку, n \geq 2.
  21. Показать, что в DES первые 24 бита любого подключа выбираются из одного 28-битного множества исходного ключа, а другие - из непересекающегося с ним 28-битного подмножества этого ключа.
  22. Зашифровать слово computer, используя схему, базирующюся на задаче о рюкзаке.
  23. Доказать, что n_i^s=2^i, i=1,...,k:
    - является минимальной супервозрастающей последовательностью,
    - может использоваться для кодирования любого числа (при достаточно большом k),
    - никакая другая не обладает этим свойством.
  24. нод(a,b)=1. Выразить \phi(a*b) через \phi(a) и \phi(b).
  25. RSA:
    - если нод(a,b)=1 => c^d mod n=w,
    - e по d единственное,
    - если нод(m,n)\not =1, m^e mod n=c => c^d mod n=m (сколько таких чисел?),
    - найти неизвестные параметры p, q через известные n и \phi(n).
  26. Предположим, что найден эффективный способ решения задачи нахождения d по e. Означает ли это, что можно решать эффективно задачу факторизации (нахождения p и q по n).
  27. Доказать, что a^{-1} mod m существует тогда и только тогда, когда нод(a,m)=1.
  28. Z_m - поле тогда и только тогда, когда m - простое.
  29. Показать, что заданный алгоритм осуществляет возведение в степень с использованием метода последовательного возведения в квадрат.
  30. Исполнить WITNESS при a=7, p=561.
  31. Пусть p=P[нод(a,b)=1, где a,b - два выбранные наугад числа].
    - Доказать, что P[нод(a,b)=d, где a,b - два выбранные наугад числа]=p/d^2.
    - Доказать, что сумма P[нод(a,b)=d, где a,b - два выбранные наугад числа] по d>=1 равна 1.
    - Определить p из последнего соотношения и доказать, что вероятность того, что два выбранные наугад числа окажутся взаимнопростыми примерно равна 0.6.
  32. Найти количество составных натуральных чисел a, не превосходящих 561 таких, что a^560=1 mod 561.
  33. Инвариант цикла в EXTENDED EUCLID.
  34. нод(n,n+1)=?
  35. Доказать, что если n - простое (>2), то n делит 2^n-2. Доказать, что составное число 341 делит 2^341-2.
  36. Найти все первообразные корни по модулю 25 (с использованием критерия).
  37. Решить систему x=2 mod 3, x=3 mod 5, x= 2 mod 7.
  38. Шесть профессоров начинают читать лекции по своим курсам в ПН, ВТ, СР, ЧТ, ПТ, СБ и читают их далее через 2, 3, 4, 1, 6, 5 дней соответственно. Лекции не читаются по ВС (отменяются). Когда в первый раз все лекции выпадут на ВС и будут отменены.
  39. Найти (73*1651)mod 1813 (с использованием греко-китайской теоремы).
  40. Доказать, что \phi(n) -- четное, n > 2.
  41. Найти нод(560,1769) с использованием расширенного алгоритма Евклида.
Для получения положительной оценки требуется
  1. Реферат на 2 стр. (до экзамена/зачета) по согласованной (темы для согласования нужно присылать по почте) теме (до экзамена/зачета) и его защита. Основное направление - криптоанализ и отдельные составляющие изученных систем (DES, рюкзак, RSA), а также криптографические протоколы, современные криптографические системы и т.п.
  2. Решение всех задач (до экзамена/зачета).
  3. Знание алгоритмов и умение решать элементарные задачи (см. Темы для дополнительных вопросов).

Алгоритмы

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

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

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

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

  1. Олейников Игорь Анализ криптосистем типа Меркле-Хеллмана (рюкзачные криптосистемы)