Документ взят из кэша поисковой машины. Адрес оригинального документа : http://new.math.msu.su/content_root/programs/kaf/special/matstat/matvop-zub.doc Дата изменения: Mon Nov 10 08:55:20 2008 Дата индексирования: Sun Apr 10 03:24:12 2016 Кодировка: koi8-r

МАТЕМАТИЧЕСКИЕ ВОПРОСЫ КРИПТОГРАФИИ

проф. А.М. Зубков
1/2 года, 4 курс
1. Шифр простой замены и шифр Виженера. Метод вскрытия шифра простой
замены.
2. Определение совершенного шифра. Теорема о числе ключей в совершенном
шифре. Совершенное шифрование длинных текстов, его достоинства и
недостатки.
3. Теорема о числе высоковероятных цепочек в последовательности
независимых испытаний.
4. Энтропия распределения на конечном алфавите. Свойства энтропии.
Максимальное значение энтропии. Оценки энтропии совместного распределения и
энтропии условного распределения.
5. Префиксные коды. Неравенства Крафта-МакМиллана.
6. Теорема о минимальной длине кода.
7. Понятие о псевдослучайных числах. Рекуррентные датчики псевдослучайных
чисел как отображения конечного множества. Распределение длины отрезка
апериодичности случайного отображения.
8. Свойства периодов рекуррентной последовательности. Минимальный период
линейной рекуррентной последовательности по составному модулю. Китайская
теорема об остатках.
9. Функция Эйлера. Теорема Эйлера.
10. Определение первообразного корня. Существование первообразного корня
по простому модулю. Для каких модулей существуют первообразные корни?
Максимальный возможный период рекуррентной мультипликативной
последовательности.
11. Линейные рекуррентные последовательности над конечным полем.
Матричное и полиномиальное представления последовательностей и связь между
ними.
12. Импульсные последовательности. Характеристический многочлен и
производящая функция рекуррентной последовательности.
13. Порядки многочлена и характеристической матрицы. Условия
максимальности периода линейной рекуррентной последовательности над
конечным полем.
14. Свойства решетчатости мультипликативной рекуррентной
последовательности. Спектральный тест и его геометрический смысл.
15. Теорема Колмогорова об оптимальных отображениях. Формализация понятия
случайности.
16. Применения алгоритмов сортировки: композиция шифрующих отображений,
шифрование без обмена ключами, простой алгоритм дискретного
логарифмирования.
17. Простейший алгоритм сортировки, цифровая сортировка, сортировка
слиянием.
18. Нижняя оценка среднего числа сравнений в алгоритмах сортировки,
основанных на попарных сравнениях элементов.
19. Быстрая сортировка. Алгоритм поиска члена вариационного ряда с
заданным номером.
20. Современные блочные шифраторы. Стандарт шифрования данных США.
21. Криптография с открытым ключом. Общая схема системы шифрования с
открытым ключом. Схема обмена ключами. Схема электронной подписи. Схема
аутентикации.
22. Системы шифрования Райвеста-Шамира-Адлемана и Эль-Гамаля.
23. Метод построения больших простых чисел.
24. Алгоритмы умножения многоразрядных чисел и больших матриц.
25. Поиск делителя натурального числа методом Полларда.
26. Метод нахождения делителя натурального числа, основанный на поиске
сравнений второй степени.
27. Описание алгоритма дискретного логарифмирования.
28. Пороговые схемы разделения секрета. Построение пороговых схем с
помощью линейных соотношений.
29. Построение схемы разделения секрета с произвольной системой доступа.

Литература
1. Введение в криптографию (под общей ред. В.В. Ященко). М., МЦНМО-ЧеРо,
1998.
2. Ященко В.В. Основные понятия криптографии / Варновский Н.П. Криптография
и теория сложности / Нестеренко Ю.В. Алгоритмические проблемы теории чисел
/ Кабатянский Г.А. Математика разделения секрета. Математическое
просвещение (третья серия), 1998, вып. 2.
3. Соболева Т.А. Тайнопись в истории России. М., Международные отношения,
1994.
4. Шеннон К.Э. Теория связи в секретных системах. В кн. Шеннон К.Э. Работы
по теории информации и кибернетике. М., ИЛ, 1963.
5. Файнстейн А. Основы теории информации. М., ИЛ, 1960.
6. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных
алгоритмов. М., Мир, 1979.
7. Кнут Д. Искусство программирования для ЭВМ. Т. 2. М., Мир, 1977.
8. Лидл Р., Нидеррайтер Г. Конечные поля. М., Мир, 1988.
9. Саломаа А. Криптография с открытым ключом. М., Мир, 1996.
10. Диффи У., Хеллмэн М.Э. Защищенность и имитостойкость. Введение в
криптографию.// ТИИЭР (Труды института инженеров по электронике и
радиотехнике), 1979, т. 67, ? 3.
11. Труды института инженеров по электронике и радиотехнике, 1988, т. 76, ?
5.