Алгоритм RSA

[danek130995]

Преподаватель дал задание реализовать алгоритм RSA. Попытался сделать по этому мануалу: http://www.e-nigma.ru/stat/rsa/
Интересно то, что для чисел, которые даны в мануале, все работает, но если искать самому в коде другие, то получается вообще непонятно что. Походу в примере они взяли числа и им повезло. Либо я что-то не так делаю. Пожалуйста, проверьте меня, что может быть не так. Заккоменчены те числа, для которых работает.

function bukvatocifra(bukva: char): integer;
begin
  if bukva = 'A' then
    Result := 1;
  if bukva = 'B' then
    Result := 2;
  if bukva = 'C' then
    Result := 3;
  if bukva = 'D' then
    Result := 4;
  if bukva = 'E' then
    Result := 5;
  if bukva = 'F' then
    Result := 6;
  if bukva = 'G' then
    Result := 7;
  if bukva = 'H' then
    Result := 8;
  if bukva = 'I' then
    Result := 9;

  if bukva = 'J' then
    Result := 10;
  if bukva = 'K' then
    Result := 11;
  if bukva = 'L' then
    Result := 12;
  if bukva = 'M' then
    Result := 13;
  if bukva = 'N' then
    Result := 14;
  if bukva = 'O' then
    Result := 15;
  if bukva = 'P' then
    Result := 16;
  if bukva = 'Q' then
    Result := 17;
  if bukva = 'R' then
    Result := 18;

  if bukva = 'S' then
    Result := 19;
  if bukva = 'T' then
    Result := 20;
  if bukva = 'U' then
    Result := 21;
  if bukva = 'V' then
    Result := 22;
  if bukva = 'W' then
    Result := 23;
  if bukva = 'X' then
    Result := 24;
  if bukva = 'Y' then
    Result := 25;
  if bukva = 'Z' then
    Result := 26;

end;

function cifratobukva(cifra: integer): char;
begin
  if cifra = 1 then
    Result := 'A';
  if cifra = 2 then
    Result := 'B';
  if cifra = 3 then
    Result := 'C';

  if cifra = 4 then
    Result := 'D';

  if cifra = 5 then
    Result := 'E';
  if cifra = 6 then
    Result := 'F';
  if cifra = 7 then
    Result := 'G';
  if cifra = 8 then
    Result := 'H';
  if cifra = 9 then
    Result := 'I';

  if cifra = 10 then
    Result := 'J';
  if cifra = 11 then
    Result := 'K';
  if cifra = 12 then
    Result := 'L';
  if cifra = 13 then
    Result := 'M';
  if cifra = 14 then
    Result := 'N';
  if cifra = 15 then
    Result := 'O';
  if cifra = 16 then
    Result := 'P';
  if cifra = 17 then
    Result := 'Q';
  if cifra = 18 then
    Result := 'R';

  if cifra = 19 then
    Result := 'S';
  if cifra = 20 then
    Result := 'T';
  if cifra = 21 then
    Result := 'U';
  if cifra = 22 then
    Result := 'V';
  if cifra = 23 then
    Result := 'W';
  if cifra = 24 then
    Result := 'X';
  if cifra = 25 then
    Result := 'Y';
  if cifra = 26 then
    Result := 'Z';
end;

function Evklid(a,b:integer):integer;
begin
  while (a<>0) and (b<>0)
    do
    if a > b then
        a := a mod b
    else
        b := b mod a;
    result := (a+b)
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  n, p, q, e, d, i, j, pq, large: integer;
  C, M: array of integer;
  res:string;

begin
  res:='';
  large := 6;
  setlength(C, length(edit1.Text));
  setlength(M, length(edit1.Text));

  repeat
    p := random(large);
    q := random(large);
  until p <> q;

  n := p * q;
  pq := (p-1) * (q-1);

  repeat
    d := random(large);
  until (((Evklid(d,(p-1)))=1) and ((Evklid(d,(q-1)))=1));

  repeat
    e := random(large);
  until ((e * d) mod pq) = 1;
   
//p:=3; q:=11; n:=p*q; d:=3; e:=7;

  for i := 1 to length(Edit1.Text) do
    C[i - 1] := round((Math.power(bukvatocifra(edit1.Text[i]), e))) mod n;

  for i := 1 to length(Edit1.Text) do
    M[i - 1] := round((Math.power(C[i - 1], d))) mod n;


       memo1.Lines.add('---Содержимое C---');
  for i := 0 to length(C) - 1 do
     res:=res+inttostr(C[i])+' ';
    memo1.Lines.add(res);
     res:='';

       memo1.Lines.add('---Содержимое M---');
  for i := 0 to length(M) - 1 do
     res:=res+inttostr(M[i])+' ';
    memo1.Lines.add(res);
    res:='';

     memo1.Lines.add('---Результат распознования---');
      for i := 0 to length(M) - 1 do
     res:=res+cifratobukva(M[i]);
      memo1.Lines.add(res);
end;

end.

Если делать все по формулам, то может получится вот это для ABC:

p=4,q=5,n=20,pq=12,d=5,e=5
---Содержимое C---
1 12 3
---Содержимое M---
1 12 3
---Результат распознования---
ALC

Как видим, нам возвращается 12, а должно вернутся 2.
Помогите пожалуйста разобраться

[Аватар]

Весь код в bukvatocifra и cifratobukva можно одной строчкой заменить используя ord и chr. А разбираться нужно в отладчике

[danek130995]

Я пытался, разбирался, пробовал, я вручную пересчитывал. Также получается. Мне кажется. ошибка в алгоритме самом RSA. На счет одной строчки кода-точно, Ord и Char, забыл. Спасибо.

[Streletz]

Сообщение от danek130995

Мне кажется. ошибка в алгоритме самом RSA.

Скорее в его конкретной реализации и/или конкретных исходных данных.

Сообщение от danek130995

Походу в примере они взяли числа и им повезло.

Или они эти числа просто выбрали правильно, то есть в соответствии с описанием алгоритма.
К слову, в приведённом Вами мануале чёрным по белому написано:

Возьмем два больших простых числа p and q.

У Вас:

Сообщение от danek130995

p=4,q=5

Числа не только "маленькие". Одно из них ещё и составное.
В общем, внимательно перечитывайте мануал и сверяйте с ним Ваши данные и код. Если что, лучший друг программиста (уже упомянутый отладчик) в помощь.

[danek130995]

Ой, забыл про простые числа, спасибо! Сейчас попробую. А маленькие взял чтобы проверить вручную легче было. На самом деле маленькие можно брать, главное чтобы простые были. Просто если они маленькие шифр легче взломать

Для больших p и q рандомить может бесконечно..

Теперь я проверяю числа на простые, но работает все равно неверно:

function isProstoe(a:integer):boolean;
var
  i:integer;
begin
    if a=2 then
    begin
      result:=true;
      exit;
    end;
  if odd(a) then
      begin
         for i:=3 to a-1 do
            if (a mod i=0) then
                begin
                result:=false;
                exit;
                end;
                result:=true;
      end
      else
      result:=false;
end;   

      
  repeat
    p := random(large);
    q := random(large);
  until ((p <> q) and (isProstoe(p)) and (isProstoe(q)));

Ввожу BLUECAT:

p=5,q=3,n=15,pq=8,d=9,e=9
---Содержимое C---
2 12 6 5 3 1 5
---Содержимое M---
2 12 6 5 3 1 5
---Результат распознавания---
BLFECAE

Также, почему-то, после повторного нажатия кнопки вылетает ошибка исключение SIGFPE на строке

until ((e*d) mod pq) = 1

[danek130995]

нашел ошибку-невнимательно смотрел мануал, буква должна быть представлена в виде числа до n-1.

[danek130995]

Аватар, я заменил код cifratobukva и bukvatocifra, но он возвращает непонятные значки, а то вообще не возвращает.

function bukvatocifra(bukva: char): integer;
begin
  result:=ord(bukva);
end; 

function cifratobukva(cifra: integer): char;
begin
    result:=chr(cifra);
end.

В чем может быть дело?

[Аватар]

Ну во-первых нужно со смещением. Ord('A') совсем не 1
Во-вторых, если делфи юникодный, то так не пойдет

[danek130995]

Аватар, так у меня кодируется А не как единица, а кодируется уже ее номер char. Зачем тут смещение? У меня Lazarus

[Serge_Bliznykov]

для прописных (Больших) латинских букв (и исключительно только для них!) попробуйте такой вариант:

function bukvatocifra(bukva: char): integer;
begin
  result:=ord(bukva)-ord('A')+1;
end; 

function cifratobukva(cifra: integer): char;
begin
    result:=chr(cifra+ord('A')-1);
end