- •Теоретико-числовые методы в криптографии
- •Аннотация.
- •Предисловие
- •Введение
- •Глава 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.Литература основная:
- •Дополнительная:
- •Оглавление
5.6. Тест на простоту Миллера-Рабина.
Теперь, наконец, мы располагаем достаточной информацией для того, чтобы привести тест Миллера-Рабина. Этот тест, как и тесты Ферма и Соловея-Штрассена, строит вероятно простые числа, то есть число, опознанное этим тестом как простое, может с некоторой малой вероятностью оказаться составным, однако вероятность ошибки у теста Миллера-Рабина гораздо ниже, чем у первых двух тестов. Как правило, для опознания простого числа достаточно одной итерации теста, но все же рекомендуемое количество итераций – пять.
Тест Миллера-Рабина основан на двух важных фактах:
1) Согласно теореме Ферма, если n – простое число, то для любого a: 0<a<n выполняется an—1≡1(mod n);
2) Если n – простое число, то сравнение x2≡1(mod n) имеет только тривиальные корни x≡±1(mod n), а если n – составное, то такое сравнение имеет несколько корней помимо тривиальных.
Тест Миллера-Рабина:
Вход: n=2sr+1 – нечетное число, проверяемое на простоту, s≥0, r – нечетное.
t - количество итераций, параметр надежности.
1. Повторить t раз следующие шаги:
1.1. Случайным образом выбрать a: 1<a<n—1.
1.2. Строим последовательность b0, b1,…,bs, где bj=mod n, j=0,1,…,s.
1.3. Если в построенной последовательности не встретилась «1», то идти на Выход с сообщением «n - составное число».
1.4. Если перед первой единицей в последовательности стоит не «-1», то идти на Выход с сообщением «n - составное число».
2. Идти на Выход с сообщением «n – простое число с вероятностью εt».
Выход.
Обратим внимание на то, что в последовательности b0, b1,…,bs каждый последующий член является квадратом предыдущего по модулю n, а последний член есть ни что иное как an—1 mod n.
Вероятность ошибки ε ≤ φ(n)/4n, то есть верхняя граница ошибки на одной итерации для теста Миллера-Рабина в 2 раза меньше аналогичной для теста Соловея-Штрассена и в 4 раза – для теста Ферма.
Пример 1.
n=65=64+1=26+1. r=1, s=6.
t=5.
1. 1-я итерация:
1.1. a=8.
1.2. Составляем последовательность: 8, 64=—1, 1, 1, 1, 1.
1.3. В последовательности встретилась «1».
1.4. Перед первой единицей стоит —1.
1. 2-я итерация:
1.1. a=11.
1.2. Составляем последовательность: 11, 56, 16, 61, 16, 61.
1.3. В последовательности не встретилась «1».
Выход: « n - составное число».
В том случае, когда тест Миллера-Рабина определяет составность числа n на шаге 1.4, появляется возможность частично факторизовать n.
Действительно, пусть в последовательности b0, b1,…,bs, где bj=mod n, нашлось такое i, что bi≠±1, bi+1=1. Обозначим для краткости bi=b. Тогда bi+1=b2≡1(mod n). Тогда n\(b2—1) n\(b+1)(b—1). Но в силу того, что b±1(mod n), n не делит (b+1), n не делит (b—1). Следовательно,
1<НОД(n, b—1)<n, 1<НОД(n, b+1)<n.
Значит, НОД(n,b—1) и НОД(n,b+1) являются нетривиальными делителями числа n.
Пример 2
n=161=160+1=25·5+1. r=5, s=5.
1. 1-я итерация:
1.1. a=22. a5 mod 161 = 225 mod 161=22.
1.2. Составляем последовательность: 22, 1, 1, 1, 1, 1.
1.3. В последовательности встретилась «1».
1.4. Перед первой единицей стоит 22.
Выход: « n - составное число».
Факторизуем 161: b=22. b+1=23, b—1=21.
Вычислим НОД(161, 23): 161=23·7+0.
НОД(161,21): 161=21·7+14
21=14·1+7
14=7·2+0.
Итак, нашли два нетривиальных делителя 161, и получили 161=23·7.
Надо заметить, что на самом деле случай, когда в тесте Миллера-Рабина возникает возможность факторизации, происходит весьма редко. Гораздо чаще сообщение о составности мы получаем на шаге 1.3.