Введение в криптографию: Теоретико-числовые основы защиты информации. Учебное пособие.

Description

Учебное пособие предназначено для изучения курсов «Методы и средства защиты информации», «Основы криптографии», других родственных дисциплин основных образовательных программ высшего образования, для изучения дисциплин по выбору, посвященных основам криптографии и прикладным вопросам теории чисел. Пособие включает в себя теоретические факты, упражнения и задачи различного уровня сложности по всем основным разделам криптографии и соответствующим разделам прикладной теории чисел. Помимо обширного списка упражнений и задач, в пособии представлены индивидуальные задания для проведения творческих и лабораторных работ, контрольные вопросы и типовые задания обязательного минимума по каждой теме. Пособие составлено в соответствии с требованиями федеральных государственных образовательных стандартов высшего образования и примерных основных образовательных программ высшего образования. Книга написана на базе многолетнего опыта практической работы авторов, ее материал построен по модульному принципу: выбор изучаемых разделов, порядок знакомства с ними и глубина освоения соответствующих теоретических и практических вопросов зависят от направления подготовки и профиля, в рамках которых проводится обучение. Пособие предназначено для преподавателей и студентов высших учебных заведений, прежде всего математических факультетов педвузов, учителей профильной школы, старшеклассников, интересующихся прикладными теоретико-числовыми проблемами, всех, кого привлекают история и современные тенденции развития криптографии. Материалы пособия могут быть полезны для организации индивидуальной учебно-исследовательской работы студентов в рамках подготовки курсовых работ, выпускных квалификационных работ бакалавра и магистерских диссертаций. Обозначения Введение Глава 1. Из истории криптографии 1.1. Исторические шифры 1.1.1. Простейшие подстановочные шифры (шифры простой замены) 1.1.2. Полиалфавитные подстановочные шифры 1.1.3. Простейшие шифры перестановки Упражнения Задачи 1.2. Криптоанализ классических шифров 1.2.1. Криптоанализ шифров перестановки 1.2.2. Криптоанализ шифров простой замены 1.2.3. Криптоанализ полиалфавитных криптосистем Упражнения Задачи 1.3. Задачи криптографических олимпиад Примеры решения задач Задачи Глава 2. Простейшие симметричные криптосистемы 2.1. Аффинные криптосистемы Упражнения Задачи 2.2. Криптоанализ аффинных криптосистем Упражнения Задачи Глава 3. Шифрующие матрицы 3.1. Алгебра матриц и аффинные матричные криптосистемы Упражнения Задачи 3.2. Криптоанализ аффинных матричных криптосистем Упражнения Задачи Глава 4. Система RSA. Дискретный логарифм 4.1. Система RSA и ее модификации 4.1.1. Криптосистема без передачи ключей 4.1.2. Криптосистема с открытым ключом 4.1.3. Электронная подпись Упражнения Задачи 4.2. Дискретный логарифм 4.2.1. Показатели, первообразные корни и индексы 4.2.2. Метод перебора 4.2.3. Метод согласования 4.2.4. Метод Сильвестра—Полита—Хеллмана 4.2.5. Алгоритм исчисления порядка Упражнения Задачи Глава 5. Вычислительные алгоритмы и их трудоемкость 5.1. Трудоемкость арифметических действий 5.1.1. Системы счисления 5.1.2. Символ «О»-болыиое 5.1.3. Анализ трудоемкости арифметических действий 5.1.4. Классификация алгоритмов по их трудоемкости Упражнения Задачи 5.2. Простейшие арифметические алгоритмы и их трудоемкость 5.2.1. Алгоритм Евклида 5.2.2. Расширенный алгоритм Евклида 5.2.3. Бинарный алгоритм Евклида 5.2.4. Расширенный бинарный алгоритм 5.2.5. Решение неопределенных уравнений первой степени 5.2.6. Алгоритм возведения в степень по модулю n Упражнения Задачи Глава 6. Простые и псевдопростые числа 6.1. Простые числа. Критерии простоты Упражнения Задачи 6.2. Вероятностные тесты простоты. Псевдопростые числа 6.2.1. Тест Ферма 6.2.2. Тест Соловея—Штрассена 6.2.3. Тест Миллера—Рабина Упражнения Задачи 6.3. Детерминированные тесты простоты. Генерация больших простых чисел 6.3.1. Проверка простоты с использованием числа n - 1 6.3.2. Проверка простоты с использованием числа n + 1 6.3.3. Генерация простых чисел Упражнения Задачи Глава 7. Факторизация натуральных чисел 7.1. Классические методы факторизации 7.1.1. Метод пробного деления 7.1.2. Метод Ферма Упражнения Задачи 7.2. Современные методы факторизации. Вскрытие системы RSA 7.2.1. Метод Полларда—Флойда 7.2.2. (Р - 1)-метод Полларда 7.2.3. Вскрытие системы RSA Упражнения Задачи Гпава 8. Псевдослучайные последовательности над конечным полем 8.1. Поля и кольца классов вычетов. Характеристика конечного поля 8.1.1. Кольца и поля. Примеры 8.1.2. Натуральные кратные элементов поля и характеристика поля 8.1.3. Расширения конечного поля. Существование конечного поля 8.1.4. Мультипликативная группа конечного поля Упражнения Задачи 8.2. Кольцо многочленов над полем F. Построение конечного поля 8.2.1. Неприводимые над полем многочлены 8.2.2. Сравнимость многочленов и построение конечного поля 8.2.3. Порядок многочлена над конечным полем 8.2.4. Примитивные многочлены над конечным полем Упражнения Задачи 8.3. Линейные рекуррентные последовательности над конечным полем 8.3.1. Псевдослучайные последовательности 8.3.2. Последовательности над конечным полем 8.3.3. Линейные рекуррентные последовательности 8.3.4. Аннулирующие многочлены Упражнения Задачи Глава 9. Задания для организации промежуточного и итогового контроля 9.1. Контрольные вопросы 9.2. Типовые задания обязательного минимума по основам криптографии 9.3. Задания для творческих лабораторных работ к разделу «Из истории криптографии» 9.3.1. Таблица Виженера 9.3.2. Шифр по книге 9.3.3. Частотный анализ 9.3.4. Решетки Кардано 9.3.5. Двойная перестановка 9.4. Задания для лабораторных работ к разделу «Простейшие симметричные криптосистемы. Шифрующие матрицы» 9.4.1. Аффинные криптосистемы 9.4.2. Шифрующие матрицы 9.4.3. Содержание отчета 9.5. Задания для лабораторных работ к разделу «Система RSA. Дискретный логарифм» 9.5.1. Система без передачи ключей 9.5.2. Система с открытым ключом 9.5.3. Электронная подпись 9.5.4. Дискретный логарифм 9.5.5. Содержание отчета 9.6. Задания для лабораторных работ к разделу «Вычислительные алгоритмы и их трудоемкость» 9.6.1. Алгоритм Евклида, его модификации и их трудоемкость 9.6.2. Применение алгоритма Евклида к решению неопределенных уравнений первой степени 9.6.3. Содержание отчета 9.7. Задания для лабораторных работ к разделу «Простые и псевдопростые числа» 9.7.1. Простейшие алгоритмы проверки чисел на простоту 9.7.2. Вероятностные алгоритмы проверки чисел на простоту 9.7.3. Содержание отчета 9.8. Задания для лабораторных работ к разделу «Факторизация натуральных чисел» 9.8.1. Классические методы факторизации 9.8.2. Методы факторизации Полларда 9.8.3. Содержание отчета 9.9. Задания для лабораторной работы к разделу «Псевдослучайные последовательности над конечным полем» 9.9.1. Содержание отчета Глава 10. Таблицы 10.1. Таблицы числовых эквивалентов символов русского и английского алфавитов 10.2. Таблицы Виженера 10.3. Таблицы частотности 10.4. Таблицы простых чисел 10.5. Таблицы неприводимых и примитивных многочленов 10.6. Таблицы индексов Ответы и решения Словарь терминов Литература