Лабораторная работа №8 (Вычисление первообразного корня)

(алгоритм Эль-Гамаля)

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

В основе алгоритма Эль-Гамаля лежит процедура открытого распределения ключей, опубликована в 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⁰, g¹, g²,…g ^φ(m)-1 представляет собой совокупность всех взаимно простых с m чисел, меньших m. То есть g^k пробегает систему вычетов при k = 1, 2,… φ(m), где: φ(m) – функция Эйлера.

Выполнение работы

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

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

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

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

{------------------------------------------------------------------} {--- функция проверки чисел на их простоту ---} {-----------------------------------------------------------------} function Simple(n:integer):Boolean; var k:Boolean; i:integer; begin k:=true; if n<>2 then for i:=2 to trunc(sqrt(n))+1 do if n mod i = 0 then begin k := false; break; end; Result:=k; end;

{--------------------------------------------------------------------} {---- функция дискретного возведения числа A --} {-- в степень B по модулю P. N = A^B (mod P) --} {-------------------------------------------------------------------} function IntModPower(A,B,P:integer):integer; var x:array of integer; i:integer; begin SetLength(x,P); x[1]:=A mod P; for i:=2 to B do x[i]:=x[i-1] * A mod P; Result:=x[B]; end;

// Команда вывода простых чисел в диапазоне N:M procedure TForm1.Button1Click(Sender: TObject); var i:integer; begin Memo1.Clear; for i := SpinEdit1.Value to SpinEdit2.Value do if Simple(i) = true then Memo1.Lines.Add(IntToStr(i)); end;

// Команда вычисления первообразных корней g по модулю P procedure TForm1.Button3Click(Sender: TObject); var i,d,P: integer; begin Memo2.Clear; 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))); end;

13