Шифрование методом RSA

[Raven!]

Добрый день. Помогите, пожалуйста, с алгоритмом шифрования RSA.
Задание
1. Выбираются два простых числа p и q (такие, что p не равно q) (Это единственное, что считаем дано, но проверяем на простоту - контроль).
2. Вычисляется модуль N=p∗q.
3. Вычисляется значение функции Эйлера от модуля N:φ(N)=(p−1)(q−1).
4. Выбирается число a, называемое открытой экспонентой, число a должно лежать в интервале 1< a <φ (N ), а так же быть взаимно простым со значением функции φ(N). (Выбор случайный + НОД - в цикле)
5. Вычисляется число α, называемое секретной экспонентой, такое, что a∗α=1(mod φ(N)), то есть является мультипликативно обратным к числу a по модулю φ(N).
В итоге получаем:
- пара (a,N) – открытый ключ;
- пара (α,N) – закрытый ключ.
Теперь шифруем-расшифровываем сообщение.

Нужно зашифровать и расшифровать используя НОД и быстрое возведение в степень.

function NOD(a,b:integer):integer;  //1. НОД
var i:integer;
begin
Result:=1;
if a>b then
  //поменять местами a и b
  begin
    i:=a;
    a:=b;
    b:=i;
  end;
Repeat
     i:=b mod a;
     b:=a;
     a:=i;
Until (i=0);
Result:=b;
end;
 
function Step(x, n,m:integer):integer; //2. Быстрое возведение в степень
var p:integer;
begin
p:=1;
while n>0 do
begin
  if n mod 2 = 1 then
  p:=(p*x) mod m;
  x:=(x*x) mod m;
  n:=n shr 1;
end;
Result:=p;
end;

[Raven!]

Добрый день. Вроде бы чутка разобралась, но никак не могу правильно зашифровать и расшифровать текст. Что-то с кодировкой или алгоритмом. Помогите, пожалуйста.

var
  Form1: TForm1;
  ti,ta, P, Q, N, Ne, E, D,cs : integer;
  tmp,tmp1:string;

implementation

{$R *.dfm}

function NOD(a,b:integer):integer;  //1. НОД
var i:integer;
begin
Result:=1;
if a>b then
  //поменять местами a и b
  begin
    i:=a;
    a:=b;
    b:=i;
  end;
Repeat
     i:=b mod a;
     b:=a;
     a:=i;
Until (i=0);
Result:=b;
end;

function Step(x, n,m:integer):integer; //2. Быстрое возведение в степень
var p:integer;
begin
p:=1;
while n>0 do
begin
  if n mod 2 = 1 then
  p:=(p*x) mod m;
  x:=(x*x) mod m;
  n:=n shr 1;
end;
Result:=p;
end;

function isprime(p:integer):boolean; //А эта функция проверяет, простое ли число ей
var i:longint;                       //подсунули. Использует тупой перебор
begin                                //от 2 до N-1. Если что-то поделилось
isprime:=true;                       //без остатка, функция завершается с
for i:=2 to p-1 do                   //результатом false (т. е. N не простое)
if p mod i = 0 then begin
isprime:=false; break; end;
end;

function rndprime():integer;        //Эта функция возвращает относительно
var t:real;                          //большие простые случайные числа. Насколько большие,
    s:integer;                       //зависит от коэффициента умножения.
begin
 repeat
  randomize;
  t:=random*1000;//коэффициент 1000. Добавь три-четыре нолика и дешифровка
  s:=trunc(t);   //займёт примерно недельку =). Не ассемблер же...
 until isprime(s);
rndprime:=s;
end;

function modinv (a,m:integer):integer;
var
i,b:integer;         //Вот здесь используется так называемый
x,j,y,c:integer;     //"расширенный алгоритм Евклида".
begin                //Возвращает такое D, что (E*D) mod N =1.
 b := m;
 c := a;             //Как он работает, я так и не понял...
 i := 0;             //Работает - не трогай! =)
 j := 1;
 while (c <> 0) do
  begin
   x := b div c;
   y := b mod c;
   b := c;
   c := y;
   y := j;
   j := i - j * x;
   i := y
  end;
 if (i < 0) then i := i+m;
 modinv:=i;
end;

procedure TForm1.Button1Click(Sender: TObject);
begin
edit1.Text:=inttostr(rndprime());
edit2.Text:=inttostr(rndprime());
end;

procedure TForm1.Button2Click(Sender: TObject);
begin

P:=strtoint(edit1.Text);  //P и Q инициализируем из текстовых полей
Q:=strtoint(edit2.Text);
N:= P*Q;                  //По алгоритму RSA N - это произведение P и Q
label4.Caption := inttostr(N);
Ne:=(P-1)*(Q-1);          //Вспомогательная переменная Ne высчитывается
label6.Caption := inttostr(Ne); //по функции Эйлера (P-1)*(Q-1)

E:=3; // 3 - минимально возможное значение Е (открытого показателя)
ta:=Ne;
while NOD(E,ta)<>1 do inc(E,2); //Проверяем Ne и E на взаимную простоту
                                //с помощью нашей функции nod()
  label8.Caption:=inttostr(E);
  label8.Repaint;

D:=modinv(E,Ne);  //Здесь по мегаалгоритму Евклида считаем D (секретный показатель)
label10.Caption:=inttostr(D);
 cs:=(E*D) mod Ne;   //Считаем контрольную сумму
if  cs<>1 then begin //она должна быть = 1
    showmessage ('Инизиализаторы P и Q не подходят! (Контрольная сумма = '+inttostr(cs)+' <> 1). Перегенерируем.');
    button1.Click;
    button2.Click;
                         end;             //Выводим ключи
memo3.Text:='('+inttostr(E)+', '+inttostr(N)+')';  //Открытый
memo4.Text:='('+inttostr(D)+', '+inttostr(N)+')';  //и Секретный
end;

procedure TForm1.Button3Click(Sender: TObject);
begin
form1.Close;
end;

procedure TForm1.Button4Click(Sender: TObject);
var y,tfn,tfe,ttmp,N,i,x:integer;
stmp:string;
begin
memo2.Clear;
if (label4.Caption<>'') or (label8.Caption<>'')then begin
tfn:=strtoint(Label4.Caption); //Получение значения N...
tfe:=strtoint(Label8.Caption); //...и Е
tmp:=memo1.Text;

//инициализация индикатора процесса... так, для красоты.
progressbar1.min:=1;
progressbar1.max:=length(tmp);
progressbar1.Step:=1;
progressbar1.Position:=1;

for ti:=1 to length(tmp) do begin             //Непосредственно, шифровка.
stmp:=inttostr(ord(tmp[ti]));                 //Берём по одному символу из текста
                                            //получаем его CHR код, к которому
for I := 0 to Length(tmp)-1 do
y:=Step(ord(char(stmp[i+1])), tfe, tfn);                         //и применяем согласно RSA алгоритм
//x:=Step(ttmp,tfn,y);                             //y=(x^e) mod n. Где x-исходная, а
stmp:=inttostr(x);                  //y-зашифрованная информация,
memo2.Text:=memo2.Text+stmp+' ';              //а Е - открытый ключ.
                                              //Все эти Y и выводим справа
progressbar1.position:=progressbar1.position+1;//через пробел. Уф...
progressbar1.Repaint;
end;
end else
end;

procedure TForm1.Button5Click(Sender: TObject);
var tfn,tfd,ttmp,x,y,i:integer;                   //долго, т. к. много раз
temp:string;                                 //нужно возводить многозначные
begin                                          //числа в ещё более многозначную степень.
memo1.Clear;

if (label4.Caption<>'') or (label10.Caption<>'') then begin
tfn:=strtoint(Label4.Caption); //Получение значения N...
tfd:=strtoint(Label10.Caption); //...и D

tmp:=memo2.Text;
                                             //Здесь всё практически так же,
progressbar1.min:=1;                         //как и при шифровке.
progressbar1.max:=length(tmp);               //Берём каждое из разделённых
progressbar1.Step:=1;                        //пробелами число и применяем
progressbar1.Position:=1;                    //к нему обратную операцию с
                                             //использованием секретного
while length(tmp)<>0 do begin                //ключа.
temp:=copy(tmp,1,pos(' ',tmp)-1) ;           //Это поучается

for I := 0 to Length(temp)-1 do
    y:=ord(chr(Step(ord(temp[i]), tfd, tfn)));
temp:=inttostr(y);

memo1.Text:=memo1.Text+chr(strtoint(temp));  //chr()
memo1.Repaint;
delete(tmp,1,pos(' ',tmp));
progressbar1.Position:=progressbar1.Max-length(tmp);
progressbar1.Repaint;
end;
end else

end;


procedure TForm1.FormCreate(Sender: TObject);
begin
randomize; //Инициализация генератора случайных чисел.
button1.Click; //Генерация чисел P, Q происходит при нажатии на кнопку
end;       // "Random P, Q". Здесь мы вызываем эту процедуру.

end.

[BDA]

Чуть поправил код. Форматировать нужно тщательнее - читать неудобно. Передавать значения через лейблы не комильфо. И называть все элементы лучше более осмысленно (некоторые переименовал).

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls, ComCtrls;

type
  TForm1 = class(TForm)
    GenPQ: TButton;
    GenKeys: TButton;
    Encrypt: TButton;
    Decrypt: TButton;
    PEdit: TEdit;
    QEdit: TEdit;
    Label4: TLabel;
    Label6: TLabel;
    Label8: TLabel;
    Label10: TLabel;
    Memo1: TMemo;
    Memo2: TMemo;
    Memo3: TMemo;
    Memo4: TMemo;
    ProgressBar1: TProgressBar;
    procedure GenPQClick(Sender: TObject);
    procedure FormCreate(Sender: TObject);
    procedure GenKeysClick(Sender: TObject);
    procedure EncryptClick(Sender: TObject);
    procedure DecryptClick(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;
  P, Q, N, Ne, E, D: integer;

implementation

{$R *.dfm}

function NOD(a, b: integer): integer; // 1. НОД
var
  i: integer;
begin
  if a > b then
  // поменять местами a и b
  begin
    i := a;
    a := b;
    b := i;
  end;
  Repeat
    i := b mod a;
    b := a;
    a := i;
  Until (i = 0);
  Result := b;
end;

function Step(x, n, m: Int64): Int64; // 2. Быстрое возведение в степень
var
  p: Int64;
begin
  p := 1;
  while n > 0 do
  begin
    if n mod 2 = 1 then
      p := (p * x) mod m;
    x :=(x * x) mod m;
    n := n shr 1;
  end;
  Result := p;
end;

function isprime(p: integer): boolean; // А эта функция проверяет, простое ли число ей
var                                    // подсунули. Использует тупой перебор
  i: integer;                          // от 2 до N-1. Если что-то поделилось
begin                                  // без остатка, функция завершается с
  Result := true;                      // результатом false (т. е. N не простое)
  for i := 2 to p - 1 do
    if p mod i = 0 then
    begin
      Result := false;
      break;
    end;
end;

function rndprime(): integer; // Эта функция возвращает относительно
var                           // большие простые случайные числа. Насколько большие,
  t: real;                    // зависит от коэффициента умножения.
  s: integer;
begin
  repeat
    randomize;
    t := random * 1000; // коэффициент 1000. Добавь три-четыре нолика и дешифровка
    s := trunc(t);      // займёт примерно недельку =). Не ассемблер же...
  until isprime(s);
  Result := s;
end;

function modinv(a, m: integer): integer;
var
  i, b: integer;         // Вот здесь используется так называемый
  x, j, y, c: integer;   // "расширенный алгоритм Евклида".
begin                    // Возвращает такое D, что (E*D) mod N =1.
  b := m;
  c := a;             // Как он работает, я так и не понял...
  i := 0;             // Работает - не трогай! =)
  j := 1;
  while (c <> 0) do
  begin
    x := b div c;
    y := b mod c;
    b := c;
    c := y;
    y := j;
    j := i - j * x;
    i := y
  end;
  if (i < 0) then i := i + m;
  Result := i;
end;

procedure TForm1.GenPQClick(Sender: TObject);
begin
  PEdit.Text := inttostr(rndprime());
  QEdit.Text := inttostr(rndprime());
end;

procedure TForm1.GenKeysClick(Sender: TObject);
var
  ta, cs: integer;
begin
  P := strtoint(PEdit.Text);  // P и Q инициализируем из текстовых полей
  Q := strtoint(QEdit.Text);
  N := P * Q;                 // По алгоритму RSA N - это произведение P и Q
  label4.Caption := inttostr(N);
  Ne := (P - 1) *(Q - 1);     // Вспомогательная переменная Ne высчитывается
  label6.Caption := inttostr(Ne); //по функции Эйлера (P-1)*(Q-1)

  E := 3; // 3 - минимально возможное значение Е (открытого показателя)
  ta := Ne;
  while NOD(E, ta) <> 1 do inc(E, 2); // Проверяем Ne и E на взаимную простоту
                                      // с помощью нашей функции nod()
  label8.Caption := inttostr(E);
  label8.Repaint;

  D := modinv(E, Ne); // Здесь по мегаалгоритму Евклида считаем D (секретный показатель)
  label10.Caption := inttostr(D);
  cs := (E * D) mod Ne; // Считаем контрольную сумму
  if cs <> 1 then
  begin // она должна быть = 1
    showmessage(
      'Инизиализаторы P и Q не подходят! (Контрольная сумма = ' +
      inttostr(cs) +
      ' <> 1). Перегенерируем.'
    );
    GenPQ.Click;
    GenKeys.Click;
  end;
  // Выводим ключи
  memo3.Text := '(' + inttostr(E) + ', ' + inttostr(N) + ')'; // Открытый
  memo4.Text := '(' + inttostr(D) + ', ' + inttostr(N) + ')'; // и Секретный
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
  randomize;   // Инициализация генератора случайных чисел.
  GenPQ.Click; // Генерация чисел P, Q происходит при нажатии на кнопку
end;           // "Random P, Q". Здесь мы вызываем эту процедуру.

procedure TForm1.EncryptClick(Sender: TObject);
var
  y, tfn, tfe, i: integer;
  tmp: string;
begin
  if (label4.Caption <> '') or (label8.Caption <> '') then
  begin
    tfn := strtoint(Label4.Caption);
    tfe := strtoint(Label8.Caption);
    tmp := memo1.Text;

    progressbar1.min := 1;
    progressbar1.max := length(tmp);
    progressbar1.Step := 1;
    progressbar1.Position := 1;

    Memo2.Clear;
    with Memo2.Lines do
      for i := 1 to length(tmp) do
      begin
        y := Step(ord(tmp[i]), tfe, tfn);
        Add(inttostr(y));
        progressbar1.position := i;
        progressbar1.Repaint;
      end;
  end;
end;

procedure TForm1.DecryptClick(Sender: TObject);
var
  tfn, tfd, y, i: integer;             
  tmp: string;
begin
  if (label4.Caption <> '') or (label10.Caption <> '') then
  begin
    tfn := strtoint(Label4.Caption);
    tfd := strtoint(Label10.Caption);

    tmp := '';

    progressbar1.min := 0 ;
    progressbar1.max := memo2.Lines.Count - 1;
    progressbar1.Step := 1;
    progressbar1.Position := 0;

    for i := 0 to memo2.Lines.Count - 1 do
    begin
      y := Step(strtoint(memo2.Lines[i]), tfd, tfn);
      tmp := tmp + chr(y);
      progressbar1.Position := i;
      progressbar1.Repaint;
    end;

    memo1.Text := tmp;
  end;
end;

end.

[Raven!]

Спасибо большое! Прям жизнь спас!)