Показатели по модулю и их свойства.

Дискретное логарифмирование

План.

 

1. Показатели по модулю и их свойства.

2. Первообразные корни их существование и свойства

3. Индексы и их свойства. Определение дискретного логарифма

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

5. Первообразные корни их существование и свойства

6. Индексы и их свойства. Определение дискретного логарифма

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

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

9. Криптосистема Рабина.

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

 

Показатели по модулю и их свойства.

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

.                                           (1)

Обозначаем порядок числа a по модулю m через P_m (a). Порядок по модулю обладает следующими свойствами.

1⁰ Если (a, m) =1 то P_m (a) существует и P_m (a) £. j(a).

2⁰ Если (a, m) =1 и b º a (mod m), то P_m (b) = P_m (a).

3⁰ Если d = P_m (a) и , то d|a.

4⁰ Если d = P_m (a), то d|j(m).

5⁰ Если (a, m) =1 и d = P_m (a), , то aºb(mod d).

6⁰ Если (a, m) =1 и d = P_m (a), то все степени попарно несравнимы по модулю m..

Алгоритм нахождения показателя r = P_m (a).

Ввод: Проверяемое число a и модуль m..

m:=0; r:= b;a 1:= a;;b 1:= b;

d:= function НОД (a, m);

  if d >1 then s $:= «показатель P_m (a) не существует»      

  else P:=1; (q, r): = div (a, m);

while r   ¹ 1 do P:= P + 1; (q, r): = div (ra, m); end while;

s $:= «показатель P_m (a) равен»;

     end if

Вывод: s $и P.

Так как по свойству 4⁰ порядок числа P_m (a) делит число j(m), то найдя каноническое разложение числа j(m) можно перебирать только делители числа j(m). Тогда алгоритм вычисления показателя принимает следующий вид.

Алгоритм нахождения показателя r = P_m (a).

Ввод: Проверяемое число a и модуль m..

m:=0; r:= b;a 1:= a;;b 1:= b;

d:= function НОД (a, m);

if d >1 then s $:= «показатель P_m (a) не существует»      

else

f: = function j(m)

procedure Факторизация(f; A, k);{A- матрица, имеющая две строки, в первой       строка матрицы, простые числа, делящие число m, вторая – соответствующие показатели этих простых чисел в каноническом разложении числа f, k – число различных простых множителей в каноническом разложении числа f }

d:=1; (q, r): = div (a, m);

for i:= 1 to k; B (i, 1):=1; B (i, 2):=0; end for; i:=1;         

while r   ¹ 1 do d:= d + 1; (q, r): = div (ra, m);

r:=0; {Перебор делителей числа j(m) до тех пор пока не будет r   = 1}

while r   = 0 do

  if B (i, 2) < A (i, 2) then

        B (i, 2):= B (i, 2) +1; p:= A (i, 2); v:= a;

     while p > 0 do

        (p, u):= div (p,2)

        if u = 1 then (q, B (i, 1)):= div (B (i, 1)* v, m); end if

        ( q, v):= div (v* v, m);

     end while;

     r:= B (i, 1);

     while i > 1 do i:=i- 1; B (i, 1):= r; B (i, 2):=0; end while;

  else

    i:=i+ 1;

end while;

end while;

P:=1;

for i:= 1 to k;

while B (i, 2)> 0 do P:= P*A (i, 1); B (i, 2):= B (i, 2)-1; end while;

end for;

s $:= «показатель P_m (a) равен»; P;

end if.

Вывод: s $и r.

Пример 2. Найти показатель числа 7 по модулю 15. Так как (7, 15) =1, то показатель существует. Вычисляем j(15) = 2×4 = 8. Делители числа j(15);1, 2, 4, 8.

Так как 7T1(mod 15), 7² º 49 º 4 T1(mod 15), 7⁴ º 4² º1(mod 15), то P ₁₅(7) = 4.

 

End while

End while

End while

End while

End while

End while

Вывод: p и K, P, a.

Нахождение первообразного корня g по модулю p простого числа типа Жермен.

Ввод: p – простое число, K, P – факторизация числа p -1

g:=1;pr:=0;

while pr=0 do

g:=g+1; i:=0

while k[i]>0 and pr=0 and i<6 do;

if BigStMod(g,(p-1)/P[i],p) =1 then pr:=0; i:=7; else i:=i+1;end if;

if i=6 then pr:=1;end if;

end while

end while;

  Вывод: g.

 

 

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

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

Рассмотрим случай двух абонентов 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 в текст.

Криптосистема Рабина.

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

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

1. B выбирает случайно два различные большие простое число p и q. Эти числа представляют секретный ключ. Удобно выбирать p º 3 (mod 4), q º 3 (mod 4).

1. Тогда открытый ключ представляет произведение n = pq.

Шифрование.

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

1. Каждое X_i шифруется по формуле Y_i º X_i ²(mod n), 0≤ Y_i < n.
2. Последовательность чисел   Y ₁, Y ₂, …. пересылается B.                                              

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

Расшифровывание полученной последовательности Y ₁, Y ₂, …. состоит в решении для

каждого Y_i квадратичного сравнения

Y_i º X ²(mod n).                                                       (4)

Для B, знающего разложение числа n = pq, это сравнение равносильно системе сравнений

Y_i º X ²(mod p),                                                      (5)

 Y_i º X ²(mod q).                                                      (6)

Тогда при X_i делящемся на p имеем X º V_i º X_i º0(mod p), а при X_i не делящемся на p имеем.

Так как p º 3 (mod 4), то решение X сравнения (5) можно найти по формул X º Y_i ^{( p +1)/4}(mod p). Действительно,

X ²º Y_i ^{(p +1)/2}º Y_i Y_i ^{(p- 1)/2} º Y_i X_i ^{(p- 1)} º Y_i (mod p).

Таким образом, для каждого из сравнений (5) и (6) мы можем найти по два решения

X º ± Y_i ^{(p +1)/4}(mod p), X º ± Y_i ^{(q +1)/4}(mod q).

Тогда, используя китайскую теорему об остатках найдем 4 решения сравнения (4). Возникает неоднозначность расшифровывания. Если открытое сообщение обладает некоторой избыточностью, например, написано на естественном языке, то это не должно стать помехой для расшифровывания.

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

Теорема. 1) В результате реализации протокола Рабина получим X = X_i.

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

Доказательство. Первая часть утверждения была обоснована выше.

Если крипто аналитик не зная разложение числа n на простые множители, то он может решить сравнение (4) только перебором. Поэтому, для того, чтобы решить сравнение (4) необходимо знать разложение числа n на простые множители. Последняя задача трудно решаемая и связана с проблемой разложения целого числа на простые множители.

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

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

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

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

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

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

Программа генерации ключей Рабина.

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

Программа реализующая китайскую теорему об остатках.

Программа шифрования Рабина.

Программа расшифровывания Рабина.

Вопросы.

1. Определение показателя числа по модулю.

2. Свойства показателя числа по модулю.

3. Алгоритм вычисления показателя числа по модулю.

4. Определение первообразного корня.

5. Условие существования первообразного корня.

6. Число первообразных корней в полной системе вычетов по модулю.

7. Алгоритм нахождения первообразного корня.

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

9. Определение индекса (дискретного логарифма) числа по модулю.

10. Свойства индексов.

11. Вычисление индексов.

12. Определение квадратичного вычета по модулю.

13. Определение символа Лежандра.

14. Теорема Эйлера.

15. Свойства Символа Лежандра. Квадратичный закон взаимности.

16. Вычисление символа Лежандра.

17. Символ Якоби и его свойства.

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

19. Крипто система Эль-Гамаля. Генерация ключей. Шифрование и расшифровывание.

20. Криптосистема Шамира. Генерация ключей. Шифрование и расшифровывание.

21. Криптосистема Рабина. Генерация ключей. Шифрование и расшифровывание.

22. Теорема Эйлера и возможность ее использования для тестирования простых чисел на простоту.

23. Псевдопростые числа Эйлера.

24. Что такое криптосистема? Основные задачи криптографии.

25. Криптографический алгоритм. Криптографический протокол.

26. Принцип Керкгоффса.

27. Уязвимости RSA относительно активных и пассивных атак.

 

Дискретное логарифмирование

План.

 

1. Показатели по модулю и их свойства.

2. Первообразные корни их существование и свойства

3. Индексы и их свойства. Определение дискретного логарифма

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

5. Первообразные корни их существование и свойства

6. Индексы и их свойства. Определение дискретного логарифма

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

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

9. Криптосистема Рабина.

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

 

Показатели по модулю и их свойства.

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

.                                           (1)

Обозначаем порядок числа a по модулю m через P_m (a). Порядок по модулю обладает следующими свойствами.

1⁰ Если (a, m) =1 то P_m (a) существует и P_m (a) £. j(a).

2⁰ Если (a, m) =1 и b º a (mod m), то P_m (b) = P_m (a).

3⁰ Если d = P_m (a) и , то d|a.

4⁰ Если d = P_m (a), то d|j(m).

5⁰ Если (a, m) =1 и d = P_m (a), , то aºb(mod d).

6⁰ Если (a, m) =1 и d = P_m (a), то все степени попарно несравнимы по модулю m..

Алгоритм нахождения показателя r = P_m (a).

Ввод: Проверяемое число a и модуль m..

m:=0; r:= b;a 1:= a;;b 1:= b;

d:= function НОД (a, m);

  if d >1 then s $:= «показатель P_m (a) не существует»      

  else P:=1; (q, r): = div (a, m);

while r   ¹ 1 do P:= P + 1; (q, r): = div (ra, m); end while;

s $:= «показатель P_m (a) равен»;

     end if

Вывод: s $и P.

Так как по свойству 4⁰ порядок числа P_m (a) делит число j(m), то найдя каноническое разложение числа j(m) можно перебирать только делители числа j(m). Тогда алгоритм вычисления показателя принимает следующий вид.

Алгоритм нахождения показателя r = P_m (a).

Ввод: Проверяемое число a и модуль m..

m:=0; r:= b;a 1:= a;;b 1:= b;

d:= function НОД (a, m);

if d >1 then s $:= «показатель P_m (a) не существует»      

else

f: = function j(m)

procedure Факторизация(f; A, k);{A- матрица, имеющая две строки, в первой       строка матрицы, простые числа, делящие число m, вторая – соответствующие показатели этих простых чисел в каноническом разложении числа f, k – число различных простых множителей в каноническом разложении числа f }

d:=1; (q, r): = div (a, m);

for i:= 1 to k; B (i, 1):=1; B (i, 2):=0; end for; i:=1;         

while r   ¹ 1 do d:= d + 1; (q, r): = div (ra, m);

r:=0; {Перебор делителей числа j(m) до тех пор пока не будет r   = 1}

while r   = 0 do

  if B (i, 2) < A (i, 2) then

        B (i, 2):= B (i, 2) +1; p:= A (i, 2); v:= a;

     while p > 0 do

        (p, u):= div (p,2)

        if u = 1 then (q, B (i, 1)):= div (B (i, 1)* v, m); end if

        ( q, v):= div (v* v, m);

     end while;

     r:= B (i, 1);

     while i > 1 do i:=i- 1; B (i, 1):= r; B (i, 2):=0; end while;

  else

    i:=i+ 1;

end while;

end while;

P:=1;

for i:= 1 to k;

while B (i, 2)> 0 do P:= P*A (i, 1); B (i, 2):= B (i, 2)-1; end while;

end for;

s $:= «показатель P_m (a) равен»; P;

end if.

Вывод: s $и r.

Пример 2. Найти показатель числа 7 по модулю 15. Так как (7, 15) =1, то показатель существует. Вычисляем j(15) = 2×4 = 8. Делители числа j(15);1, 2, 4, 8.

Так как 7T1(mod 15), 7² º 49 º 4 T1(mod 15), 7⁴ º 4² º1(mod 15), то P ₁₅(7) = 4.