- •Теоретико-числовые методы в криптографии
- •Аннотация.
- •Предисловие
- •Введение
- •Глава 1. Основы теории чисел. §1. Теория делимости.
- •1.1. Основные понятия и теоремы.
- •1.2. Наибольший общий делитель.
- •1.3 Нок (наименьшее общее кратное)
- •1.4. Простые числа
- •Решето Эратосфена
- •1.5. Единственность разложения на простые сомножители.
- •1.6. Асимптотический закон распределения простых чисел.
- •§2. Функция Эйлера.
- •2.1. Мультипликативные функции.
- •2.2. Функция Эйлера.
- •§3. Теория сравнений
- •3.1. Свойства сравнений:
- •3.2. Полная система вычетов.
- •3.3. Приведенная система вычетов
- •3.4. Обратный элемент.
- •3.5. Алгебраические структуры на целых числах.
- •3.6. Теоремы Эйлера и Ферма. Тест Ферма на простоту.
- •Тест Ферма на простоту
- •3.7. Применение теоремы Эйлера в rsa:
- •§4. Сравнения с одним неизвестным
- •4.1. Сравнения первой степени.
- •4.2. Система сравнений первой степени. Китайская теорема об остатках.
- •4.3. Применения китайской теоремы об остатках.
- •4.4. Сравнения любой степени по простому модулю.
- •4.5. Сравнения любой степени по составному модулю.
- •§5. Теория квадратичных вычетов
- •5.1. Квадратичные вычеты по простому модулю.
- •5.2. Символ Лежандра. Символ Якоби.
- •Свойства символа Лежандра:
- •Свойства символа Якоби:
- •5.3. Тест на простоту Соловея-Штрассена.
- •Тест Соловея-Штрассена:
- •5.4. Решение квадратичных сравнений по простому модулю.
- •5.5. Квадратичные сравнения по составному модулю.
- •5.6. Тест на простоту Миллера-Рабина.
- •5.7. Связь задач извлечения квадратных корней и факторизации по модулю rsa. Криптосистема Рабина.
- •5.8. Квадраты и псевдоквадраты.
- •5.9. Числа Блюма.
- •§6. Первообразные корни и индексы. Порождающий элемент и дискретный логарифм.
- •6.1. Основные понятия и теоремы.
- •6.2. Существование первообразных корней по модулю p.
- •6.3. Первообразные корни по модулям pα, 2pα.
- •6.4. Нахождение первообразных корней по простому модулю.
- •6.5. Существование и количество первообразных корней.
- •6.6. Дискретные логарифмы.
- •6.7. Проблема Диффи-Хеллмана.
- •6.8. Условная стойкость шифра Эль Гамаля.
- •§7. Построение доказуемо простых чисел общего и специального вида.
- •7.1. Теорема Сэлфриджа и доказуемо простые числа общего вида на основании полного разложения (n—1).
- •7.2. Теорема Поклингтона и доказуемо простые числа общего вида на основании частичного разложения (n—1).
- •7.3. Числа Ферма. Теорема Пепина.
- •7.4. Числа Мерсенна.
- •7.5. Теорема Диемитко и процедура генерации простых чисел заданной длины гост р 34.10-94.
- •Глава 2. Алгебраические основы теории чисел.
- •§1. Основные понятия алгебры.
- •1.1. Начальные понятия.
- •1.2. Делимость в кольцах.
- •1.3. Деление с остатком.
- •1.4. Основная теорема арифметики.
- •§2. Конечные поля и неприводимые многочлены.
- •§3. Кольца многочленов.
- •3.1. Кольца многочленов.
- •3.2. Кольцо многочленов Zp[X].
- •3.3. Конечные поля многочленов.
- •Глава 3. Алгоритмы в криптографии и криптоанализе. §1. Элементы теории сложности.
- •§2. Алгоритмы факторизации.
- •2.1. Метод пробных делений.
- •2.2. Метод Ферма.
- •2.3. Метод квадратичного решета.
- •2.6. Методы случайных квадратов.
- •§3. Алгоритмы дискретного логарифмирования.
- •3.1. Метод прямого поиска.
- •3.2. Шаг младенца – шаг великана.
- •3.4. Алгоритм Полига-Хеллмана.
- •3.5. Алгоритм исчисления порядка (index-calculus algorithm).
- •Задачи и упражнения.
- •Упражнения к Главе 2.
- •Ответы к упражнениям.
- •1. Пояснительная записка
- •1.1. Цели и задачи дисциплины
- •1.2. Требования к уровню освоения содержания дисциплины
- •2. Объем дисциплины и виды учебной работы
- •3. Тематический план изучения дисциплины
- •4. Содержание разделов дисциплины
- •6. Вопросы к экзаменам
- •7.Литература основная:
- •Дополнительная:
- •Оглавление
А.В. Рожков
О.В. Ниссенбаум
Теоретико-числовые методы в криптографии
Учебное пособие
Тюмень 2007
Аннотация.
Рассмотрены теоретико-числовые и алгебраические основы криптографии, криптографические алгоритмы, построенные на теоретико-числовых и теоретико-сложностных проблемах, такие как RSA, Диффи-Хеллмана, Эль-Гамаля. Рассмотрена проблема генерации простых чисел, приведены вероятностные тесты на простоту и алгоритмы генерации доказуемо простых чисел с математическим обоснованием. В третьей главе приведены алгоритмы, криптоанализа асимметричных криптосистем – алгоритмы факторизации и дискретного логарифмирования – с оценками сложности. Изложение сопровождается примерами. В пособие включены также рабочая программа по дисциплине «Теоретико-числовые методы в криптографии» для студентов специальности «Компьютерная безопасность» ТюмГУ, и задания для самостоятельного выполнения с ответами к ним.
Предисловие
Современная криптография в значительной мере использует результаты таких дисциплин как алгебра, теория чисел, теория сложности. Студентам, изучающим криптографию всерьез, необходимо знание ее математических основ, поскольку ничто так не помогает знанию как понимание, а понимание алгоритмов криптографии и криптоанализа невозможно без понимания идей, которые в них заложены.
Предлагаемое учебное пособие базируется на курсе лекций, читаемом авторами в Тюменском государственном университете студентам специальности «Компьютерная безопасность». По окончании обучения студенты этой специальности получают квалификацию «математик», поэтому в этой книге математические факты даются последовательно, с доказательствами настолько строгими и подробными, насколько это позволяет семестровый курс. Однако для того, чтобы читать и понимать это пособие, достаточно знаний математики в объеме, даваемом в технических вузах.
В первой главе содержатся основы теории чисел и криптографические алгоритмы, базирующиеся на теоретико-числовых принципах. Читателю, знакомому с теорией чисел, можно ограничиться чтением шестого и седьмого пунктов из §3, и продолжить чтение начиная с §5. Указанные разделы содержат описания вероятностных тестов на простоту, криптосистем, основанных на теоретико-числовых принципах (таких как RSA, Диффи-Хеллмана), методы построения доказуемо простых чисел. Описания криптосистем сопровождаются доказательствами их стойкости.
Вторая глава посвящена алгебраическим основам теории чисел и таким алгебраическим структурам как кольца многочленов. На кольцах и полях многочленов построены некоторые криптосистемы, в частности AES.
В третьей главе описываются алгоритмы криптоанализа двухключевых криптосистем – алгоритмы факторизации и дискретного логарифмирования. Глава предваряется параграфом, информирующем об основах теории сложности, и для каждого алгоритма из третьей главы приведена оценка сложности. Для всех описанных алгоритмов приведены примеры.
В разделе «Задачи и упражнения» приведены задачи, решение которых поможет закрепить изученный теоретический материал. Примеры решения подобных задач читатель может найти в тексте пособия в соответствующем разделе. Ответы к задачам приведены в конце раздела.
В Приложении 1 приведена таблица простых чисел и порождающих элементов циклических групп целых чисел, им соответствующих.
Приложение 2 представляет собой рабочую программу курса «Теоретико-числовые методы в криптографии», читаемого студентам специальности 090102 «Компьютерная безопасность» в Тюменском государственном университете и включает в себя в том числе вопросы к экзамену.