Вычисление первообразного корня (алгоритм Эль-Гамаля)

Общие положения

В основе алгоритма Эль-Гамаля лежит процедура открытого распределения ключей, опубликована в 1976 году в работе У. Диффи и М.Э. Хеллмана «Новые направления в криптографии».

Ключи шифрования и дешифрования вычисляются по алгоритму, где P - большое простое число, g - первообразный корень по модулю P. Секретное число a может быть любым целым числом, лучше случайным. Величина числа не ограничена.

Первообразным (примитивным) корнем по модулю P, будет число g < P и взаимно простое с P, принадлежащее показателю d. Показатель d (дискретный логарифм числа g по модулю P при основынии i т.е или) является наименьшим, натуральным числом, обеспечивающим сравнение. Отсюда следует, что для взаимно простых P и = P-1 чисел показатель (индекс) и следовательно, где: i = 2,3,4,…,P-2. Исходя из того факта, что первым основанием i, (для простого P и взаимно простого) образующим первый примитивный корень могут быть только числа 2 и 3, следовательно, вычислить первый корень не составляет труда. Например, для модуля P=11, первым корнем будет число 2, так как: = , где: и d = 5 = . Для модуля P = 7 первым корнем будет число 3^3(mod 7) = 6, а вторым корнем будет, 5^3(mod 7) = 6.

Первообразные корни образуют мультипликативную группу кольца, которая представляет ряд чисел, степени которых g 0 , g 1 , g 2 ,…g ц(m)-1 представляет собой совокупность всех взаимно простых с m чисел, меньших m. То есть g k пробегает систему вычетов при k = 1, 2,… ц(m), где: ц(m) - функция Эйлера.

В программе использовала компоненты SpinEdit 1,2,3- для ввода чисел, Memo 1,2 - для отображения результатов и командные кнопки Button 1,2. (рис. 9)

Примечание: Для вычисления значенией действительных чисел в раздел Uses Unit"aвключить модуль Math.

Реализация алгоритмов

function Simple(n:integer):Boolean;

var k:Boolean; i:integer;

if n<>2 then

for i:=2 to trunc(sqrt(n))+1 do

if n mod i = 0 then

function IntModPower(A,B,P:integer):integer;

x:array of integer;

for i:=2 to B do

x[i]:=x * A mod P;

procedure TForm1.Button1Click(Sender: TObject);

for i:= SpinEdit1.Value to SpinEdit2.Value do

if Simple(i) = true then Memo1.Lines.Add(IntToStr(i));

procedure TForm1.Button3Click(Sender: TObject);

P:= SpinEdit3.Value;

d:= (P-1) div 2;

for i:= 2 to P-2 do

if (IntModPower(i,d,P) = P-1) then

Memo2.Lines.Add("g = " + IntToStr(i) + " (^" + IntToStr(d) + ") = " + FloatToStr(Power(i,d)));

В настоящем пункте будем рассматривать число n , причем n -1= * - каноническое разложение на простые сомножители.

Теорема

O n (a )=n -1 1) a n -1 ≡1(mod n );

2) , 1(mod n ).

Доказательство:

Пусть O n (a )=n -1. Тогда (1) выполняется в силу определения порядка элемента в группе. Кроме того, , 1 ≤ < n -1= O n (a ), откуда в силу определения порядка элемента, выполняется (2).

Пусть теперь выполнены (1) и (2). Покажем, что O n (a )=n -1.

В силу (1), O n (a )\(n -1). В силу (2), O n (a ) не делит . Значит, O n (a )=n -1.

Результатами только что доказанной теоремы можно пользоваться для нахождения порождающего элемента группы U p , причем проверять стоит только второй пункт, так как первый для простого модуля выполняется автоматически согласно теореме Ферма. Кроме того, можно вывести правило : если a 1 , a 2 не являются порождающими элементами группы U p , то a 1 a 2 также не является порождающим элементом U p . Отсюда делаем вывод о том, что наименьший порождающий элемент группы U p – простое число.

Пример

p =71. p -1=70=2·5·7.

Для того чтобы a являлся порождающим элементом, необходимо и достаточно, чтобы выполнялись условия: a 10 1(mod n ), a 14 1(mod n ), a 35 1(mod n ).

Будем испытывать числа из U 71 . Вместо a b mod 71 для краткости будем писать a b .

2: 2 10 =30, 2 14 =54, 2 35 =1. 2 не является порождающим элементом.

3: 3 10 =48, 3 14 =54, 3 35 =1. 3 не является порождающим элементом.

5: 5 10 = 1. 5 не является порождающим элементом.

7: 7 10 =45, 7 14 =54, 7 35 =70. 7 – порождающий элемент.

Итак, наименьший порождающий элемент группы U 71 (или первообразный корень по модулю 71) есть 7.

Существование и количество первообразных корней.

Первообразные корни существуют не для всякого модуля. Действительно, как было показано в Примере 2 п.1, не существует первообразных корней по модулю 8.

Теорема 1

Первообразные корни по модулю m существуют m =2, 4, p α или 2p α , где p – простое нечетное число.

Теорема 2

Количество первообразных корней по модулю m , если они существуют, есть φ(φ(m )).

Пример:

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

10 = 2·5=2р . Первообразные корни существуют. Найдем их количество.

φ(φ(10))=φ(4)=2.

Проверим результат. U 10 ={1, 3, 7, 9}

3 2 =9, 3 3 =7, 3 4 =1. O 10 (3)=4=φ(10). 3 – первообразный корень.

7 2 =9, 7 3 =3, 7 4 =1. O 10 (7)=4=φ(10). 7 – первообразный корень.

9 2 =1. O 10 (9)=2.

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

Теорема 3

Пусть с =φ(m ), q 1 , q 2 , … , q k – различные простые делители с . Тогда g : (g ,m )=1 – первообразный корень по модулю m не выполняется ни одно из сравнений , i= 1,2,…,k .

Теорема, доказанная в предыдущем пункте, является частным случаем данной теоремы при простом n .

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

Если g – первообразный корень по модулю m (порождающий элемент U m ), то, если γ пробегает полную систему вычетов по модулю φ(m ), то g γ пробегает приведенную систему вычетов по модулю m .

Для чисел a : (a ,m )=1 введем понятие об индексе, или о дискретном логарифме.

Если a≡g γ (mod m ), то γ называется индексом , или дискретным логарифмом числа а по основанию g по модулю m .

В теории чисел принято употреблять слово «индекс» и писать γ=ind g a , но в криптографии применяют сочетание «дискретный логарифм» и пишут γ=log g a . Поскольку на протяжении настоящего пособия не раз встретится упоминание о так называемой задаче дискретного логарифмирования, будем употреблять последний вариант названия и написания. Тем более, что дискретные логарифмы обладают некоторыми свойствами логарифмов непрерывных:

Свойство 1: Дискретный логарифм разнозначен в полной системе вычетов по модулю φ(m ).

Свойство 2: log g ab …h≡ log g a +log g b +…+log g h (mod φ(m )).

Свойство 3: log g a n ≡n log g a (mod φ(m )).

Доказательство этих свойств не представляет сложности и является прямым следствием определений дискретного логарифма и первообразного корня.

В настоящем пункте будем рассматривать число n , причем n -1= * - каноническое разложение на простые сомножители.

Теорема

O n (a )=n -1 1) a n -1 ≡1(mod n );

2) , 1(mod n ).

Доказательство:

Пусть O n (a )=n -1. Тогда (1) выполняется в силу определения порядка элемента в группе. Кроме того, , 1 ≤ < n -1= O n (a ), откуда в силу определения порядка элемента, выполняется (2).

Пусть теперь выполнены (1) и (2). Покажем, что O n (a )=n -1.

В силу (1), O n (a )\(n -1). В силу (2), O n (a ) не делит . Значит, O n (a )=n -1.

Результатами только что доказанной теоремы можно пользоваться для нахождения порождающего элемента группы U p , причем проверять стоит только второй пункт, так как первый для простого модуля выполняется автоматически согласно теореме Ферма. Кроме того, можно вывести правило : если a 1 , a 2 не являются порождающими элементами группы U p , то a 1 a 2 также не является порождающим элементом U p . Отсюда делаем вывод о том, что наименьший порождающий элемент группы U p – простое число.

Пример

p =71. p -1=70=2·5·7.

Для того чтобы a являлся порождающим элементом, необходимо и достаточно, чтобы выполнялись условия: a 10 1(mod n ), a 14 1(mod n ), a 35 1(mod n ).

Будем испытывать числа из U 71 . Вместо a b mod 71 для краткости будем писать a b .

2: 2 10 =30, 2 14 =54, 2 35 =1. 2 не является порождающим элементом.

3: 3 10 =48, 3 14 =54, 3 35 =1. 3 не является порождающим элементом.