Методические указания к самостоятельной работе студентов к спецкурсу "Теоретико-числовые методы в криптографии"



страница1/6
Дата31.03.2018
Размер1,87 Mb.
ТипМетодические указания
  1   2   3   4   5   6
Методические указания к самостоятельной работе студентов

к спецкурсу “Теоретико-числовые методы в криптографии”

Гамова А.Н.
I. Элементарная теория чисел.


  1. Основные понятия [2]: 2.1




  1. Отношение сравнимости и его свойства; полная система вычетов по mod m, система наименьших неотрицательных вычетов; функция Эйлера.

  2. Теорема Эйлера: m>1, натуральное, a-целое, (a,m) =1, то a(m)1 (mod m).

  3. Теорема Ферма: ap-11 (mod p), где p- простое и p не делит a.

2. Сравнения 1-й степени 2.2

ax b(mod m) (2.2)

1) Теорема. Сравнение ax b(mod m) имеет решение, если b делит d = (a.m).

2) Теорема. Если (2.2) разрешимо, x0 его решение, то x0, x0+m1, …, x0+(d-1)m1

все решения (2.2), где m1=m/d.



Самостоятельная работа: [2]: 2, упр.4.

3. Китайская теорема об остатках: Система сравнений

x a1(mod m1), x a2(mod m2),…, x ar(mod mr), (3.2)

где m1, m2, ,mr –попарно взаимно просты, имеет решение

x0 =  ai Mi Ni (mod m1m2 … mr), где Mi = m1m2 … mi-1mi+1 …mr, Ni=Mi-1 (mod mi)

Самостоятельная работа: [2]: 2, упр.6.


  1. Теорема: Сравнение n-й степени по mod p не может иметь более n корней.

  2. Сравнения 2-й степени:

x2 a (mod m), (5.1)

где m>1, (a,m) = 1.

Если сравнение разрешимо, a называется квадратичным вычетом по mod m,

В противном случае – квадратичным невычетом по mod m.

1) Символы Лежандра и Якоби; их свойства: 2.3.1

2) Методы решения сравнений (5.1) для m = p, где p не делит a.

Если символ Лежандра ( a / p) =1, то сравнение (5.1) разрешимо и имеет точно два решения.

а) Пусть p = 3 (mod 4), то есть p = 4m + 3, то 1= (a / p) = a p-1 /2 = a 2m+1 (mod p), откуда

x1 = am+1 (mod p), x2 = - am+1 (mod p).

б) Пусть p = 5 (mod 8), то есть p = 8m + 5, то 1= (a / p) = a p-1 /2 = a 4m+2 (mod p), откуда

a 2m+1 =1 (mod p) или a 2m+1 = -1 (mod p). В первом случае имеем решение

x1 = am+1 (mod p) и x2 = - am+1 (mod p). Во втором случае, заметим, что число 2 является квадратичным невычетом при p = 5 (mod 8), тогда по свойству 3 символа Лежандра ( 2 / p) = 2 p -1 / 2 = 2 4m + 2 = -1 (mod p). Тогда a 2m+1 2 4m + 2 = 1 (mod p).

Получаем решения x1 = a m+1 2 2m + 1 (mod p) и x2 = - a m+1 2 2m + 1 (mod p).

Самостоятельная работа: [2]: 2 упр.7, 8,13, 14.

3) Случаи составного модуля: 2.3.3

a) Теорема: p  2, простое, p не делит a, n  1. Сравнение

x2 a (mod pn) (3.1)

разрешимо тогда и только тогда, когда



x2 a (mod p), (3.2)

разрешимо.

b) Порядком числа a, 1  a < m, (a, m) = 1, по mod m называется наименьшее натуральное число d, для которого a d 1 (mod m). Если порядок d = (m), число a называется первообразным корнем по mod m.

c) Теорема: Для любого простого p  2 существует первообразный корень по

mod p2.

d) Теорема: Если сравнение (3.1) разрешимо, то оно имеет ровно два решения.

e) Теорема: Пусть число a нечетное, то

1. Сравнение x2 a (mod 2) разрешимо при любом a.

2. Сравнение x2 a (mod 22 ) разрешимо тогда и только тогда, когда a 1 (mod 4).

3. Сравнение x2 a (mod 2n ), где n  3. разрешимо тогда и только тогда, когда

a 1 (mod 8).

ж) Теорема: Пусть m = m1 m2…mr, где числа m1, m2,…,mr попарно взаимно просты.

Сравнение (5.1) разрешимо тогда и только тогда, когда разрешимы все сравнения

x2 a(mod m1), x2 a(mod m2),…, x2 a(mod mr).

Следствие 1. Пусть (m, a) = 1, cравнение x2 a(mod m) разрешимо тогда и только тогда, когда a = 1 (mod 4) при n = 2; a = 1 (mod 8) при n  3 и

(a / p1) =(a / p2) =…=(a / ps) =1, где 2, p1, p2…,ps - простые числа из канонического разложения m.

Cравнение имеет 2s решений при n = 0 или n = 1;

2s+1 решений при n = 2;

2s+2 решения при n  3.

Следствие 2. Если число m имеет хотя бы два взаимно простых делителя, то число квадратичных вычетов по mod m строго меньше, чем число квадратичных невычетов.

Самостоятельная работа: [2]: 2, упр.15, 16.

II. Сложность основных целочисленных алгоритмов в кольце целых чисел, кольцах вычетов и конечных полях по книге А.В.Черемушкина “Лекции по арифметическим алгоритмам в криптографии”, Глава 1, §1 - §7.




  1. Оценки функции сложности

При оценке сложности применяются методы редукции и сведения к другим задачам с известными оценками сложности. Для функции сложности получаются неравенства вида

f (n)  c f (n / a) + b g (n) + dn, (1.1)

где a, b, c, d – некоторые положительные константы.

Свойства функции сложности:

a) f (n)  n;

b) k f (n)  f (kn), k >1.

Лемма 1. Если функции f (n) и g (n) удовлетворяют свойствам a), b) и при a>1, b>0, c>0 выполняется неравенство (1.1), то f (n) = O (g (n)).

Лемма 2. Если при некоторых константах a>0, c>0, d>0

f (1) = d, f (n) = c f (n / a) + dn, то при n>1

f (n) = O(n), при a>c; f (n) = O(n log n) при a=c; f (n) = O(nlog a c), при a
Пример использования леммы 2 – умножение методом Карацубы:

A, B – два n –разрядных числа. Разобьем их на два слоагаемых A = 2kA1 + A0,

B = 2kB1 + B0. Тогда AB = (2 2k + 2k) A1B1 + 2k (Ao – A1) (Bo – B1) + (2k +1)AoB0.

Таким образом, для вrычисления произведения двух n-разрядных чисел надо выполнить три умножения n / 2 – разрядных чисел и некоторое количество сложений, вычитаний и сдвигов. Имеем оценку f (n) = 3 f (n / 2) + сn, с>0. По лемме 2: сложность умножения

М(n) < f (n) = O (nlog 23).

Самостоятельная работа: Предлагается вычислить сложность арифметических операций с целыми числами.


  1. Сложность алгоритма Евклида

Пусть A>B>0. Обзначим A = r-1, B = r0, r i-2 = d i ri-1 +ri при i = 1,…,k и rk-1 = d k+1.

Тогда (A, B) = rk и до получения остатка rk+1 = 0 необходимо выполнить k+1 делений. Оценим число делений в алгоритме Евклида. Рассмотрим последовательность чисел Фибоначчи f0, f1,…,fk,…, где f0 = 0, f1 = 1, fk = fk-1 + fk-2, k2.



Лемма. При k>1 fkRk-2, где R = (1+5) /2.

Теорема (Ламе): Для любого N, где 0R N.

Непосредственно из этой теоремы получаем оценку сложности алгоритма Евклида

для нахождения (A,B) двух n-разрядных чисел:

O(M(n) (k+1)) = O (M(n) log n)  O(n2 log n).



Самостоятельная работа: 1) Найти оценки сложности для расширенного и бинарного алгоритма Евклида. 2)Изучить связь алгоритма Евклида с непрерывными дробями [1],§4.

3. Сложность операций в кольце вычетов

Элементы кольца вычетов ZN отождествляем с числами в интервале 0A

Нахождение вычета произведения состоит из одного умножения двух n-разрядных чисел и одного деления 2n-разрядного числа на n-разрядное, сложность равна O(M(n)).

Метод Монтгомери: A =  2i ai и B  AB = a0B + 2(a1B + …2(an-2B + 2an-1B)…).

Выполняется за n шагов, на каждом шаге к текущему значению R прибавляется aiB с последующим делением на 2, благодаря чему полученные значения находятся в интервале 0R-n AB modN и 22n modN снова применим алгоритм Монтгомери. Поскольку 22n modN вычисляется с помощью сдвигов и вычитаний сложностью O(n2), как и сам алгоритм, сложность вычисления

O(n2) двоичных операций.

Самостоятельная работа: Методом Монтгомери найти произведение [2]:2, упр.7.
4. Использование модульной арифметики

Алгоритм Шенхаге: Если M = m1m2 … mk, где m1, m2, …,mk взаимно простые числа (по b разрядов), 0u< M и ui  u mod mi , i = 1,…,k. По числу u вычисляется набор

(u1 ,…,uk). Для чего выполняется k делений kb-разрядного числа u на числа mi , i = 1,…,k, затрачивая O( k M(b)) битовых операций. Общая сложность алгоритма

O( k2 M(b)).

Оценку можно улучшить, если применить технику “разделяй и властвуй”.



Самостоятельная работа: Используя технику “разделяй и властвуй” при k = 2s, выполнить вычисления u(u1 ,…,uk) и, применяя китайскую теорему об остатках, реализовать обратный переход (u1 ,…,uk) u. Вычислить сложностную функция. [1], §5.
5. Вычисления с многочленами

Самостоятельная работа: [1], §6.


  1. Дискретное преобразование Фурье для кольца целых чисел

Пусть R – коммутативное кольцо с единицей. Элемент  кольца R называется примитивным корнем n-ой степени из единицы, если:

  1.   1;

  2. n = 1;

  3.   i j = 0, 1 i n.

Если, кроме того, элемент n обратим в кольце R, то задано дискретное преобразование Фурье, ставящее в соответствие каждому вектору a = (a0 ,…,an-1), aiR, i = 1,…, n-1, вектор F(a) = b = (b0 ,…,bn-1), где bi = aji j, 0  i  n-1.
Обратное дискретное преобразование Фурье определяется как F-1(b) = c, где координаты вектора c равны bi = n-1 bj- i j, 0  i  n-1.

Кроме того, F(a) есть значение многочлена с коэффициентами a0 ,…,an-1 в точках i,

i = 0,…,n-1, а обратное преобразование Фурье – интерполяции многочлена по его значениям в этих точках. То, что эти точки образуют циклическую мультипликативную подгруппу в R, позволяет построить быстрый алгоритм вычислений значения как прямого, так и обратного дискретного преобразования Фурье.

Ввиду того, что преобразование Фурье широко применяется, покажем эффективные методы его реализации.

Пусть n = 2k. Значение многочлена f(x) в точке x =  i совпадает с остатком от деления f(x) на x-  i , 0  i  n-1. Так как двучлены x- i , 0  i  n-1 попарно взаимно просты и их произведение равно xn – 1, то применим использованный в пункте 4 метод “разделяй и властвуй”: xn – 1 = (xn / 2 – 1)( xn / 2 –n / 2). Далее (xn / 2 – 1) =

(xn / 4 – 1)( xn / 4 –n / 4), ( xn / 2 –n / 2) = ( xn / 4 –n / 4) ( xn / 4 – 3n / 4) и т.д., до получения

линейных сомножителей ( x – i ). Заметим, что n / 2 = -1, n / 4 = –n / 2n / 4 = -  3n / 4.

Лемма. Пусть f(x) = aj x i. Тогда остаток от делении f(x) на (xn / 2 – с), где cR, равен

r(x) = ( aj + cac+n/2) x i

i=0…n/2-1

Из леммы следует алгоритм вычисления коэффициентов r(x): Разделить коэффициенты f(x) пополам, затем умножить на c коэффициенты второй половины и сложить их с коэффициентами первой половины, что требует не более n арифметических операций кольца R. Выполнение всего алгоритма происходит не более, чем за n+2n/2+4n/4+… +2kn/2k арифметических операций кольца, т.е. сложность алгоритма Фурье O(n log n).

Пример быстрого применения преобразования Фурье в кольце целых чисел:

Если коэффициенты f(x) ограничены некоторым числом M, выбираем n = 2k, тогда примитивный корень  в кольце ZM есть также некоторая степень 2. Это позволяет эффективно реализовать быстрое преобразование Фурье, используя двоичное представление чисел.



Теорема. Если n = 2k и  = 2g  1, то при M = n / 2 + 1 элемент n является обратимым в кольце ZM, а элемент  - примитивным корнем из 1 степени n.

Самостоятельная работа: Вычислить быстрое преобразование Фурье вектора

a = (0,1,2,3,4,5,6,7) в кольце Z / 65537Z при n = 23, k = 3,  = 16 – примитивный корень степени 8 из 1 по mod 65537.




  1. Арифметические алгоритмы (выполняются в виде лабораторных работ)

При выполнении работы «Проверка чисел на простоту» студенты должны написать программы, реализующие тесты Ферма, Соловэя — Штрассена и Миллера — Рабина убедиться в работоспособности алгоритмов (учитывая вероятностный характер тестирования), исследовать алгоритмы с точки зрения количества ошибок, допускаемых ими в зависимости от вида тестируемого числа (распознавание чисел Кармайкла) и от количества прогонов теста, обработать полученные статистические данные, а также измерить и сравнить время работы программ. [2], глава 5. Образцы выполнения лабораторных работ в Приложении 1.

В работу «Разложение чисел на множители» включены вероятностные методы разложения. Эти методы сравниваются по двум направлениям: специальные (методы Полларда), эффективность которых существенно зависит от вида составного числа, и универсальные(метод непрерывных дробей и метод квадратичного решета).[2], глава 6. Образцы выполнения лабораторных работ в Приложении 1.

В следующей лабораторной работе реализуются методы вычисления дискретного логарифма. [2], глава 7. Образцы выполнения лабораторных работ в Приложении 1.

Лабораторная работа “Криптографическая система RSA” . [2], глава 6.5. Образцы выполнения лабораторных работ в Приложении 1.


Язык программирования СИ++, а также рекомендуется язык Python и его модуль cryptolib, имеющий встроенную поддержку «длинной арифметики» и пакеты с реализацией низкоуровневых криптографических хэш-функций.

Перечень литературы



  1. А. В. Черемушкин Лекции по арифметическим алгоритмам в криптографии. ISBN 5-94057-060-7 М.: МЦНМО, 2002

  2. Е.Б.Маховенко. Теоретико-числовые методы в криптографии.M.:Гелиос АРБ,2006.

Раздел 1. Введение в теорию чисел. Классы чисел и основная теорема арифметики

§1. Делимость в кольце целых чисел

1.1. Временные оценки сложности арифметических операций


    1. Делимость и алгоритм Евклида.

    2. Основная теорема арифметики

    3. Распределение простых чисел

§2. Сравнения с одним неизвестным

    1. Отношение сравнимости. Полная система вычетов

    2. Теорема Эйлера. Теорема Ферма

    3. Сравнения 1-й степени

    4. Китайская теорема об остатках

Раздел 2. Первообразные корни и квадратичные вычеты

§1. Сравнение 2-й степени. Символы Лежандра и Якоби

§2. Квадратичный закон взаимности

§3. Методы решения сравнений 2-й степени

§4. Первообразные корни

Раздел 3. Цепные дроби. Уравнение Пелля

§1. Определение цепной дроби

§2. Подходящие дроби

§3. Бесконечные цепные дроби

§4. Квадратичные иррациональности

§5. Использование цепных дробей для решения задач

§6. Уравнение Пелля

Раздел 4. Основы абстрактной алгебры

§1. Кольца: Евлидовы. Безу. Факториальные. Главных идеалов.

§2. Различные формы китайской теоремы об остатках.

§3. Конечные поля. Неприводимые многочлены.

Раздел 5. Быстрые алгоритмы для алгебраических структур

§1. Арифметические операции над целыми числами и полиномами


    1. Сложность основных целочисленных алгоритмов

    2. Алгоритмы арифметики в системе счисления с основанием B.

    3. Умножение в классах вычетов

§2. Умножение с помощью быстрого преобразования Фурье

    1. Дискретное преобразование Фурье

    2. Алгоритм быстрого преобразования Фурье

2.3. Алгоритм Шенхаге-Штрассена для умножения целых чисел

§3. Модульное умножение

3.1. Метод Монтгомери

3.2. Модульное возведение в степень

§4. Целочисленное деление с остатком

4.1. Схема Горнера

4.2. Деление на 2m- c

4.3. Общий случай

Раздел 6. Тесты проверки чисел на простоту

§1. Вероятностные тесты проверки чисел на простоту


    1. Тест Ферма

    2. Тест Соловэя-Штрассена

    3. Тест Миллера-Рабина

§2. Детерминированные алгоритмы проверки чисел на простоту

    1. Проверка чисел Мерсенна

    2. Проверка с использованием разложения числа n-1

Раздел 7. Разложение чисел на множители

§1. Разложение чисел на множители



    1. Метод пробного деления

1.2.  - Метод Полларда

1.3. Факторизация Ферма и факторные базы

1.4. Метод квадратичного решета

1.5. Метод непрерывных дробей



§2. Приложения в криптографической системе RSA

Раздел 8. Факторизация многочленов над конечными полями

§1. Алгоритм Берлекемпа

§2. Метод Кантора-Цассенхауза



Практическая и самостоятельная работа

с методическими указаниями по разделам курса
Раздел 1: Введение в теорию чисел. Классы чисел и основная теорема арифметики

§1. Делимость в кольце целых чисел [1]:

1.1. Временные оценки сложности арифметических операций

1.2. Делимость и алгоритм Евклида.

1.3. Основная теорема арифметики

1.4. Распределение простых чисел


1. Оценки функции сложности

При оценке сложности применяются методы редукции и сведения к другим задачам с известными оценками сложности. Для функции сложности получаются неравенства вида

f(n)  cf(n/a) + bg(n) + dn, (1.1)

где a, b, c, d – некоторые положительные константы.

Свойства функции сложности:

a) f(n)  n;

b) kf(n)  f(kn), k >1.

Лемма 1. Если функции f(n) и g(n) удовлетворяют свойствам a), b) и при a>1, b>0, c>0 выполняется неравенство (1.1), то f(n) = O(g(n)).

Лемма 2. Если при некоторых константах a>0, c>0, d>0

f(1) = d, f(n) = cf(n/a) + dn, то при n>1



f(n) = O(n), при a>c; f(n) = O(n log n) при a=c; f(n) = O(n), при a<c.

Пример использования леммы 2 – умножение методом Карацубы:

A, B – два n–разрядных числа. Разобьем их на два слагаемых

A = 2kA1 + A0, B = 2kB1 + B0.

Тогда AB = (22k + 2k) A1B1 + 2k(Ao – A1)(Bo – B1)+ (2k +1)A0B0.



Таким образом, для вычисления произведения двух n-разрядных чисел надо выполнить три умножения n/2 – разрядных чисел и некоторое количество сложений, вычитаний и сдвигов. Имеем оценку f(n) = 3f(n/2) + сn, с>0. По лемме 2: сложность умножения

М(n) < f(n) = O(n).

Каталог: sites -> default -> files -> textdocsfiles -> 2014
2014 -> Методические указания к самостоятельной работе студентов к спецкурсу "Теоретико-числовые методы в криптографии"
2014 -> Рабочая программа дисциплины Органическая химия и основы супрамолекулярной химии Направление подготовки
2014 -> Материалы международной научно-практической конференции дыльновские чтения «повседневная жизнь россиян: социологический дизайн»
2014 -> Проблемы научной коммуникации преподавателей российских вузов
2014 -> Методические указания по производственной практике для студентов III и IV курсов по специальности 020302 Геофизика
2014 -> Пояснительная записка настоящая программа предназначена для подготовки и переподготовки рабочих по профессии «Бурильщик капитального ремонта скважин»
2014 -> Городские парки как место социальных коммуникаций: опыт исследования
2014 -> Пояснительная записка настоящая программа предназначена для подготовки и переподготовки (повышения квалификации) рабочих по профессии «Оператор по добыче нефти и газа»
2014 -> Экономическая география региона
2014 -> Абрамова Д. А., Толубаева М. Н. (г. Ульяновск) влияние сми на духовную жизнь


Поделитесь с Вашими друзьями:
  1   2   3   4   5   6


База данных защищена авторским правом ©grazit.ru 2019
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал