Документ взят из кэша поисковой машины. Адрес оригинального документа : http://mkma.math.msu.su/Sites/mkma/Uploads/Fw_%20programm%20of%20the%20criptospecialcourse.msword.docs1.doc Дата изменения: Fri Feb 12 19:26:48 2016 Дата индексирования: Sat Apr 9 21:23:08 2016 Кодировка: koi8-r

Московский государственный университет
имени М.В.Ломоносова

1


2 Механико-математический факультет


Кафедра математических и компьютерных методов анализа

Программа спецкурса
Арифметические вопросы криптографии

Для подготовки специалиста
по специальности «Математика»

Программу спецкурса подготовили
Минеев М.П. докт. физ.-мат. наук, профессор; Чубариков В.Н. докт. физ.-мат.
наук, профессор . chubarik1@mech.math.msu.su

Москва, весенний семестр 2016 года

Содержание программы


1.Основные задачи теории кодирования. Понятие информации и ее кодирование.

2. Алфавитное кодирование. Понятие алфавита и слова в алфавите.
Кодирование сообщения. Алфавит сообщений. Алфавит кодирования. Однозначное
кодирование.

3. Схема, задающая алфавитное кодирование. Примеры схем, задающих
однозначное и неоднозначное кодирование. Префикс слова и определение схемы,
обладающей свойством префикса. Достаточное условие взаимно однозначного
кодирования.

4. Помехоустойчивость. Многоразрядный код. Расстояние Хемминга.
Неравенство треугольника. Теорема об исправлении ошибок в кодах с любым
заданным расстоянием.
5. Помехоустойчивость. Пример двоичных кодов, в которых исправляется одна
возможная ошибка. Способ построения двоичных кодов, имеющих заданное
расстояние.

6. Передача сообщения по каналу без шума. Пример построения кода Фано в
случае 4-х буквенного алфавита сообщений и 2-х буквенного алфавита
кодирования. Средняя длина кодового слова. Общая схема построения кода
Фано, построение табдицы.

7. Бинарное дерево для двоичного кода Фано. Необходимое и достаточное
условия существования префиксного кода заданного объема и с заданным
набором длин слов. Неравенства Крафта - Мак-Миллана. Необходимое условие
существования однозначно декодируемого кода. Две теоремы об оценке средней
длины кодовых слов. Теорема о минимальной длине префиксного кода.

8. Построение оптимального кода Хафмена.

9. Способы защиты информации. Перестановки. Маршрутные перестановки. Шифры
вертикальной замены. Решетка Кардано.

10. Защита информации с помощью шифра замены. Система Цезаря и система
Цезаря с ключевым словом. Блочные и поточные шифры замены. Примеры блочных
шифров замены: шифры Плейфера и Хилла.

11. Конечные поля. Неприводимые многочлены над конечным полем. Циклические
коды. Порождающий и проверочный многочлены кода.

12. Рекуррентные соотношения. Последовательность Фибоначчи. Линейные
рекуррентные уравнения произвольного порядка. Рекуррентные соотношения
первого порядка в кольцах вычетов. Рекуррентные соотношения произвольного
порядка в конечных полях.

13. Симметричные шифры. Арифметический подход к искажению знаков в шифрах
простой замены и Виженера. Методы искажения знаков в шифре простой замены с
помощью извлечения квадратного корня и возведения в квадрат.
Комбинированный метод искажения частот появления знаков в шифре простой
замены. Анализ методов искажения знаков в шифре простой замены. Применение
китайской теоремы об остатках к шифру Виженера. Арифметический вариант
шифра Виженера.

14. Асимметричные шифры. Однонаправленная функция с секретом (с лазейкой).
Открытый и секретный ключи. Задача об укладке рюкзака. Система шифрования,
основанная на задаче о рюкзаке. Система Ривеста - Шамира - Адельмана
шифрования с открытым ключом.

15. Криптографические хеш-функции.
Функции хеширования и целостность данных. Ключевые функции хеширования.
Бесключевые функции хеширования. Целостность данных и аутентификация
сообщений. Возможные атаки на функции хеширования.

16. Цифровые подписи. Общие положения. Цифровые подписи на основе
шифрсистем с открытыми ключами. Цифровая подпись Фиата-Шамира. Цифровая
подпись Эль-Гамаля.

17. Протоколы распределения ключей. Передача ключей с использованием
симметричного шифрования. Двусторонние протоколы. Передача ключей с
использованием асимметричного шифрования. Протоколы с использованием
цифровой подписи. Открытое распределение ключей. Схемы разделения секрета.
Возможные атаки на протоколы распределения ключей.

18. Управление ключами.

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

Литература


Основная литература:
Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы
криптографии. - М.: Изд-во «Гелиос Ассоциации российских вузов», 2001.

Бабаш А.В., Шанкин Г.П. Криптография. - М.: СОЛОМОН-Р, 2002.
Фомичев В.М. Дискретная математика и криптология. - М.: ДИАЛОГ МИФИ, 2003.

Минеев М.П., Чубариков В.Н. Лекции по арифметическим вопросам криптографии.
- М.: Изд. Дом «Луч», 2014.

Чмора А.Л. Современная прикладная криптография. - М.: «Гелиос АРВ», 2001.



Дополнительная литература:
Анохин М.И., Варновский Н.П., Сидельников В.М., Ященко В.В. Криптография в
банковском деле. - М.: Изд-во МИФИ, 1997.
Бабаш А.В., Глухов М.М., Шанкин Г.П. О преобразованиях множества слов в
конечном алфавите, не размножающих искажений // Дискретная математика.-
1997. - Т. 9. - ? 3.
Биллингслей П. Эргодическая теория и информация. - М.: Мир, 1969.
Варфоломеев А.А., Пеленицын М.Б. Методы криптографии и их применение в
банковских технологиях. - М.: Изд-во МИФИ, 1995.
Варфоломеев А.А., Домнина О.С., Пеленицын М.Б. Управление ключами в
системах криптографической защиты банковской информации. - М.: Изд-во МИФИ,
1996.
Варфоломеев А.А., Жуков А.Е., Пудовкина М.А. Поточные криптосистемы.
Основные свойства и методы анализа стойкости. - М.: Изд-во МИФИ, 2000.
Гнеденко Б.В. Курс теории вероятностей.- М.: Наука, 1988.
Диффи У., Хеллман М.Э. Защищенность и имитостойкость. Введение в
криптографию // ТИИЭР. - 1979.- Т. 67. - ?3.
Зубов А.Ю. Математика кодов аутентификации. - М.: «Гелиос АРВ», 2007.
Кнут Д. Искусство программирования для ЭВМ.- М.: Мир, - Т. 2. - 1977; Т. 3.
- 1978.
Лидл Р., Нидеррайтер Г. Конечные поля. Т 1, 2. - М.: Мир,1988.
Сборник задач по алгебре / Под ред. А.И. Кострыкина. - М.: Наука, 1987.
Саломаа А. Криптография с открытым ключом. - М.: Мир, 1996.
Симмонс Г. Дж. Обзор методов аутентификации информации // ТИИЭР. - 1988. -
Т. 76. - ? 5.
Неф М., Штройле П., Хартман В. Опасности в Интернете: Способы защиты для
пользователей. - М.: Редакция «ОПиПМ», Научное издательство «ТВП», 2006.
Перельман Я.И. Занимательная астрономия. - М.: Наука, 1966.
Проскурин В.Г. Защита программ и данных. - М.: Издательский центр
«Академия», 2011.
Смит Р.Э. Аутентификация: от паролей до открытых ключей. - Москва, Санкт-
Петербург, Киев: Вильямс, 2002.
Соболева Т.А. Тайнопись в истории России. - М.: «Международные отношения»,
1994.
Холл М. Комбинаторика.- М.: Наука, 1970.
Хоффман Л. Современные методы защиты информации. - М.: Радио и связь, 1980.
Шеннон К. Теория связи в секретных системах // В кн.: Работы по теории
информации и кибернетике.- М.: Наука, 1963.
Шнайер Б. Прикладная криптография. - М.: «Издательство ТРИУМФ», 2002.
Яглом А.М., Яглом И.М. Вероятность и информация. - М.: Наука, 1973.
Введение в криптографию / Под общ. ред. В.В.Ященко. - М.: МЦНМО, «ЧеРо»,
1998.
Becket B. Introduction to cryptology and PC security. - McGrow-Hill,
London, 1997.
Blom R. Nonpablic key distribution // Advances in Cryptology. - Proceedings
of EUROCRYPT'82. Plenum. New York. - 1983. - pp. 231-236.
Callas N.P. An application of computers in cryptography // Cryptologia,
October, 1978.
Diffie W., Hellman M.E. New directions in cryptography // IEEE Trans. on
Inf. Theory. - 1976. - IT-22.
Dyer M., Fenner T., Frieze A., Thomason A. On key storage in secure
networks // J. Cryptology. - 1995. - ? 8. - pp. 189-200.
Friedman W.F. The index of coincidence and its applications in
cryptanalysis. - Aegoen Park Press, Laguna Hills CA, 1920.
Friedman W.F., Callimahos D. Military cryptanalysis. Part I. Vol. 2. -
Aegoen Park Press, Laguna Hills CA, 1985.
El Gamal T. A public-key cryptosystem and a signature scheme based on
discrete logariphms // IEEE Trans. Inf. Theory. - 1985. - IT-31. - ? 4
Merkle R.C., Hellman M.E. On the security of multiple encryption //
Communications of the ACM. - 1981. - Vol. 24.
Jacobsen T. A Fast method for cryptanalysis of substitution cipher // J.
Cryptologia. - 1995. - XIX. - ? 3.
Kahn D. The codebreakers. The story of secret writing. - Macmillan, N.Y.,
1967.
Matsumoto T., Takashima Y., Imai H. On seeking smart public- key-
distribution system // Trans. of the IECE of Japan. - 1986. -E 69. - p. 99-
106.
Menezes A.J., van Oorschot P.C., Vanstone S.A. Hand book of applied
cryptography. - CRC Press, Boca Raton, New York, London, Tokyo, 1997.
Needham R.M., Schroeder M.D. Using encryption for authentication in large
networks of computers // Communications of the ACM. - 1978.- Vol. 21. -pp.
993-999.
Yardley H.O. The american black chamber. - Bobbs Merrill, Indianapolis, IN,
1931.
Shamir A. How to share a secret // Commun. ACM. - 1979. - V. 22. - ? 11. -
pp. 612-613.
Rivest R.L., Shamir A., Adleman L. A Method for obtaining didital
signatures and public key cryptosystems // Commun. ACM. - 1978. - V. 21. -
? 2
Stinson D.R. Cryptography: Theory and practice. - CRC Press, N.Y., 1995.

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



1. Атаки в криптографическом анализе.
2. Отличие понятий теоретической и практической стойкости шифров.
3. Основные недостатки алгоритма DES, пути их устранения.
4. Сравнение систем поточного и блочного шифрования.
5. Описание шифрующего блока поточного шифра.
6. Преимущества шифрсистем с открытыми ключами перед симметричными
шифрсистемами.
7. Возможные схемы использования одноразовых паролей.
8. Атаки при нападении на протоколы идентификации.
9. Основные требования к хеш-функциям.
10. Области применения хеш-функции в цифровой подписи.
11. Структура сертификата открытого ключа.
12. Конечные поля. Неприводимые многочлены.


2 Вопросы для проработки спецкурса

1. Описать ключ в шифре Виженера.
2. Множество всех ключей в шифре Цезаря.
3. Примеры шифров, не являющихся ни шифрами замены и ни шифрами
перестановки.
4. Примеры шифров перестановки, которые можно рассматривать как
блочный шифр замены.
5. Свойства открытого текста необходимые для вскрытия шифра
вертикальной перестановки.
6. Ключ шифра простой замены. Максимально возможное число ключей
шифра простой замены.
7. Почему в криптографических системах, основанных на открытых
ключах, нельзя использовать одинаковые ключи для шифрования и
цифровой подписи?
8. Каковы преимущества централизованного распределения ключей?
9. Как можно использовать цифровую подпись для защиты протоколов
передачи ключей?
10. Код Шеннона является префиксным.

11. Код Гилберта - Мура является префиксным.

12. В чем состоит задача обеспечения помехоустойчивости при передаче
сигнала по каналу связи?

13. Почему азбука Морзе обеспечивает сжатие информации и увеличение
скорости передачи сообщений?

14. Количество неприводимых многочленов заданной степени в конечном поле.

15. Описать все неприводимые многочлены 4-й степени над полем из двух
элементов.

16. Алгоритм проверки неприводимости многочлена произвольной степени над
конечным полем.

17. Описать коды Хэмминга размерности 7 над полем из двух элементов.