Квадратичные сравнения. Символы Лежандра и Якоби и их свойства.

Рассмотрим квадратичные сравнения по модулю простого нечетного числа p

.                                                   (2)

Определение 1. Пусть (a, p) = 1. Число a   называется квадратичным вычетом по mod p, если сравнение (2) разрешимо. Число a   называется квадратичным невычетом по mod p, если сравнение (2) неразрешимо.

3⁰ Пусть (a, m) = 1. Число a   является квадратичным вычетом по mod p тогда и только тогда, когда

.                                                  (3)

Определение 2. Пусть (a, p) = 1. Символом Лагранжа числа a   по mod p называется символ ,читаемый a по p, который равен 1, если a - квадратичный вычет по mod p, и равен -1, если a - квадратичный невычет по mod p.

Из 3⁰ следует, что

.                                               (4)

Символ Лагранжа обладает следующими свойствами:

1⁰ Если a º b (mod p), то .

2⁰ .

3⁰ Если (ab,   p) = 1, то .

4⁰ Если (a,   p) = 1, то .

5⁰ Если (ab,   p) = 1, то .

6⁰  .

7⁰    (дополнительная теорема к закону взаимности).

8⁰ Если p, q – различные нечетные простые числа, то

 (теорема Гаусса, квадратичный закон взаимности).

 

Задание по части 1. Алгоритмы генерации первообразных корней.

1. Написать программу генерации простых чисел Жермен. Протестировать программу.

Потребуются программы a:=nextprime(a); isprime(p) из ЛР 2.

2. Написать программу нахождения первообразного корня простого числа Жермен. Протестировать программу. Использовать программу нахождения первообразного корня: with(numtheory),  primroot(),  которая имеется в Maple.

Потребуются программа BigStMod из ЛР 2.

1. Определить среднее время работы программы для нахождения перевообразных корней для простых чисел Жермен порядка 2^512.

 

Алгоритм Диффи-Хелмана.

Создание общего секретного ключа для КС с секретным ключом.

Рассмотрим случай двух абонентов A  и B.

1. Один из абонентов, например A определяет большое число p и вычисляет для него первообразный корень g.

2. Абонент A пересылает по открытому каналу числа p, g абоненту B.

3. Абонент A выбирает случайное число a, 1< a < p -1 и вычисляет число с º g^a (mod p).

4. Абонент B выбирает случайное число b, 1< b < p -1 и вычисляет число d º g^b (mod p).

5. Абонент A пересылает по открытому каналу число с абоненту B.

6. Абонент B пересылает по открытому каналу число d абоненту A.

7. Абонент A вычисляет число k ₁º d^a (mod p), 0< k ₁< p.

8. Абонент B вычисляет число k ₂º c^b (mod p), 0< k ₂< p.

Так как k ₁º d^a º (g^b) ^a º g^ba º g^ab º (g^a) ^b º c^b º k ₂ (mod p), и 0< k ₁< p, 0< k ₂< p, то 0< k ₁= k ₂. Следовательно, абоненты A  и B получили общий секретный ключ k = k ₁= k ₂., который не пересылался по открытому каналу связи.

Крипто аналитику необходимо по числам p, g, c, d, пересылаемым по открытым каналам связи необходимо вычислить общий секретный ключ, а для этого ему будет необходимо вычислить числа a или b, т.е. вычислить a º ind _g c (mod p -1) или b º ind _g d (mod p -1). Последнее связано с решение трудной задачи «Проблемы дискретного логараифма».

Потребуются программы:

Возведение целого числа в степень по модулю.

Программа вычисления простого числа Жермен.

Программа вычисления первообразного корня для простого числа Жермен.

 

Криптосистема Эль-Гамаля.

Генерация ключей.

Для группы пользователей выбирается большое число p (простое число С.Жермен) и вычисляет для него первообразный корень g.

Получатель секретного сообщения, например, B производит генерацию открытого ключа и закрытого ключа:

1) выбирает секретное число с;

2) вычисляет соответствующее ему открытое число d: d º g^c (mod p), 0< d < p;

3) определяет закрытый (секретный) ключ (p, g, c), оставляя его себе;

4) открытый ключ ((p, g, d)) сообщаются всем отправителям сообщений.

Шифрование

1. Шифруемое сообщение представляется в виде последовательности чисел X ₁, X ₂,… (0≤ X_i < p, i =1.2,…)

2   Каждый блок X_i, i =1.2,… шифруется по правилу:

1) формируется случайное число k; 0< k < p -1;

2) вычисляется число

Y_i º g ^k (mod p), 0< Y_i < p,                                                 (1)

3) вычисляется число

Z_i º X_i d ^k (mod p), 0< Z_i < p,                                                 (2)

1. Получателю B отправляется последовательность чисел Y ₁, Z ₁, Y ₂, Z ₂,….,  которая представляет собой зашифрованное сообщение.

Расшифровывание.

Зашифрованное сообщение Y ₁, Z ₁, Y ₂, Z ₂,….,  расшифровывается по правилу:

X_i’ º Z _i Y_i ^{- c} º Z _i Y_i ^{p -1- c} (mod p),                                                  (3)

Ниже доказывается, что полученная последовательность чисел X ₁’, X ₂’,… (0≤ X_i ’ < p, i =1.2,…), совпадает с исходной последовательностью X ₁, X ₂,…, которая преобразуется в исходный текст.

Теорема 1. Шифрование с открытым ключом корректно, т.е. в предыдущих обозначениях X_i ’= X_i.

Доказательство. Из (1), (2), (3) получаем

X_i’ º Z _i Y_i ^{- c} º Z _i Y_i ^{p -1- c} º X_i (g^c) ^k (g ^k) ^{p -1- c} º X_i g^{c k} g ^{k (p -1)- kc} º X_i (g ^{p -1}) ^k º X_i (mod p).

Так как 0≤ X_i < p и 0≤ X_i ’ < p, то X_i ’= X_i для всех i =1.2,…. 

Сложностью крипто анализа в КС Эль-Гамаля является сложность решения проблемы дискретного алгоритма.

Потребуются программы.

Возведение целого числа в степень по модулю.

Программа вычисления простого числа Жермен.

Программа вычисления первообразного корня для простого числа Жермен.

Программа преобразования текста в числа с основанием счисления p.

Программа преобразования числа с основанием счисления p в текст.

Написать программы.

Программа генерации ключей El-Gamalia.

Программа решения линейного сравнения по модулю.

Программа шифрования El-Gamalia.

Программа расшифровывания El-Gamalia.

.

Криптосистема Шамира.

Шифр Шимира позволяет передавать сообщения по открытым каналам связи, когда нет никаких ни открытых ни секретных ключей, которые нужно передавать друг другу.

Пусть два абонента A и B соединены открытой линией связи. Пусть A хочет передать сообщение T абоненту B так, чтобы никто не узнал его содержимого.

1. A выбирает случайное большое простое число p и пересылает его по открытому каналу связи B.

2. A выбирает случайное большое число a взаимно простое с p -1 1< a < p -1 и вычисляет число с, решая сравнение ac º 1 (mod p -1), 1< c < p -1.

3. B выбирает случайное большое число b взаимно простое с p -1 1< b < p -1 и вычисляет число d, решая сравнение bd º 1 (mod p -1), 1< d < p -1.

Передаваемое сообщение представляется в виде последовательности чисел X ₁, X ₂,… (0≤ X_i < p, i =1.2,…). При этом для кодирования каждого из чисел X_i лучше выбирать случайно новые пары (a, c) и (b, d).

В настоящее время такой шифр, как правило используется для передачи чисел, меньших p, например, для передачи секретных ключей.

Опишем протокол передачи каждого из чисел X_i

1. A выбирает пару (a, c).

2. A вычисляет число Y_i º X_i ^a (mod p), 0< Y_i < p, и пересылает его B.                                                   

3. B выбирает пару (b, d).

4. B вычисляет число Z_i º Y_i ^b (mod p), 0< Z_i < p, и пересылает его A.    

5. A вычисляет число U_i º Z_i ^c (mod p), 0< U_i < p, и пересылает его B.                                                   

6. B вычисляет число V_i º U_i ^d (mod p), 0< V_i < p (ниже доказывается, что число V_i совпадает с числом X_i.  

Теорема. 1) В результате реализации протокола Шамира получим V_i = X_i.

2) крипто аналитик не может узнать, какое сообщение было передано.

Доказательство. Из условий под пар (a, c) и (b, d) следует, что

ac = 1 + k (p -1), bd = 1 + l (p -1), где k, l Î Z.

Тогда при X_i делящемся на p имеем V_i = X_i =0, а при X_i не делящемся на p имеем

V_i º U_i ^d º (Z_i ^c) ^d º Z_i ^cd º (Y_i ^b) ^cd º (Y_i ^bd) ^c º (Y_i ^{1+ 1(p- 1)}) ^c º (Y_i (Y_i ^{p- 1}) ^l) ^c º (Y_i) ^c º (X_i ^a) ^c º º X_i ^ac º X_i ^{1 + k (p -1)}  º X_i X_i ^{(p -1) k}   º X_i (mod p),

Так как 0≤ X_i < p и 0≤ V_i < p, то V_i = X_i для всех i =1.2,….

Доказательство второго утверждения основано на предположении, что злоумышленник, пытающийся определить X_i должен сначала определить c, из условия U_i º Z_i ^c (mod p), 0< Z_i < p, затем вычислить X_i из условия Y_i ^c º X_i ^ac º X_i (mod p), 1< X_i < p. 

Потребуются программы.

Возведение целого числа в степень по модулю.

Программа преобразования текста в числа с основанием счисления p.

Программа преобразования числа с основанием счисления p в текст.