криптосистема Эль-Гамаля

[Nanochka]

Привет! я сдесь новенькая, завела нужда! в университете задали написать на Делфи программу, тема: "Криптоситема Эль-Гамаля"(должна зашифровывать сообщение), весь инет перерыла, очень много бьяснений самого алгоритма, но нет никаких подсказок к написанию программы, надеюсь на вашу помошь, заранее спасибо!

[Nanochka]

Генерация ключей:
Выбираются случайные простые числа P и Q так, что Q<P, затем выбирается случайное число X<P , которое является секретным ключом
1. Вычисляется y = Q^x mod p.
Открытым ключом является тройка (p,q,y), закрытым ключом — число x.
Шифрование
В дальнейшем будем понимать под М — исходное сообщение.
1. Выбирается случайное секретное число k, взаимно простое с p − 1.
2. Вычисляется a = q^Kmod p, b = y^K*Mmod p, где M — исходное сообщение.
Пара чисел (a,b) является шифротекстом. При этом длина шифротекста длиннее исходного сообщения M вдвое.
Дешифрование
Зная закрытый ключ x, исходное сообщение получается из шифротекста (a,b) по формуле: M = b / (a^X)mod p.
Нетрудно проверить, что a^X=Q^KX mod p
b/a^X=(y^KM)/a^X=(Q^KX*M)/Q^KX=M(mod p)

Порядок выполнения работы:
1. проверить 2 больших чиcла на взаимную простоту;
2. вычислить степень большого целого числа;
3. решить сравнение a*x=b mod p
Сдесь нужно использовать алгоритм Евклида для вычисления наибольшего общего целого (b)

еще есть вот такой код выдернутый из программы (я не специалист но похоже на С++) может вы знаете как его адаптировать что бы это выглядело как прога на DELPHI???

void __fastcall TMainForm::RunElGamaleExecute(TObject *Sender)
{
 RunElGamale->Enabled=false;

  unsigned int G,P,X,Y,M,A,B, cnt=0,K; 
 ElGmlB: 
 ListBox4->Clear();
 Application->ProcessMessages();
 cnt=0;
  P=simple[random(R-3)+3];     
  G=random(P-2)+1;
  X=random(P-2)+1;
/*  
  P=11; G=2;
  X=8;
  */
  Y=XYmodP(G,X,P);
  
 ListBox4->Items->Add("Публичные параметры:  P="+IntToStr(P)+",  G="+IntToStr(G));
 ListBox4->Items->Add("B:  X="+IntToStr(X)+" секретный параметр");
 ListBox4->Items->Add("B:  Y="+IntToStr(Y)+" публикуется");

  M=random(P-2)+1;
// M=5; 

  ListBox4->Items->Add("A: Сообщение M="+IntToStr(M));
  do
  {
   K=simple[random(R)];
   cnt++;
   if (cnt> 0xffff) goto ElGmlB;
  }
  while(K%(P-1) == 0) ;
  
//  K=9;

  ListBox4->Items->Add("A: Для подписи сообщения M выбирается случайное число K="+IntToStr(K));

  A=XYmodP(G,K,P);
  ListBox4->Items->Add("A->B:  a="+IntToStr(A)+" передается по сети");  
 /* B=0;
  do
  {
   B++;
   cnt++;
   if (cnt> 0xffff) goto ElGmlB;
  }
  while(M != ((X*A+K*B)%(P-1)));
  B=  (unsigned int)pow(Y,K) % P;*/
  B=Y_K_M_mod_P(Y,K,M,P);
  ListBox4->Items->Add("A->B:  b="+IntToStr(B)+" передается по сети");
  //(M*aX mod P)=(b mod P); 

  M=0;
  do
  {
   M++;
   cnt++;
   if (cnt> 0xffff) goto ElGmlB;
  }
  while( M_A_X_mod_P(M,A,X,P)   != (B%P));
//  Y_K_M_mod_P
 ListBox4->Items->Add("В:  M="+IntToStr(M)+"");
 RunElGamale->Enabled=true;

[Nanochka]

Ребятушки! ну неужели никто не знает как это делается??
вот я попыталась это сделать, но мне непонятны некоторые моменты! посмотрите, пожалуйста!!!:

unit Unit1;

interface

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

type
  TForm1 = class(TForm)
    Edit1: TEdit;
    Button1: TButton;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;
  G,P,X,Y,M,A,B,R:integer;

implementation

{$R *.dfm}




procedure TForm1.Button1Click(Sender: TObject);
begin
 Edit1.Clear;
 Application.ProcessMessages;
  P:=random(R-3)+3;
  G:=random(P-2)+1;
  X:=random(P-2)+1;
  P:=11;
  G:=2;
  X:=8;
  Y:=(X*Y) mod P;
 Writeln('Публичные параметры:P:=P,G:=G');
 Writeln('Cекретный параметр: X:=X');
 Writeln('Y:=Y -Публикуется');
  M:=random(P-2)+1;
// M=5;
  Writeln('Сообщение M:=M');
   while(K,(P-1)) == 0) ;

//  K=9;
  Writeln('Для подписи сообщения M выбирается случайное число K:=K');

  A=(X*Y) mod P;
  Writeln('a:=a передается по сети');
 /* B=0;
  do
  {
   B++;
   cnt++;
   if (cnt> 0xffff) goto ElGmlB;
  }
  while(M != ((X*A+K*B)%(P-1)));  B:=(unsigned int)pow(Y,K) % P;*/
  B:=(Y*K*M)mod P;
 Writeln('b:=b передается по сети');
  //(M*aX mod P)=(b mod P);

  M=0;
  do
  {
   M++;
   cnt++;
   if (cnt> 0xffff) goto ElGmlB;  }
  while( M_A_X mod P(M,A,X,P) != (B%P));
//  Y_K_M_mod_P
  Writeln('M:=M');
 RunElGamale.Enabled;
end;
end;

end.

[Nanochka]

Ну ребята!!!! HELP!!! Мне правда срочно надо!!!!

[Nanochka]

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

Ну ребята!!!! HELP!!! Мне правда срочно надо!!!!

ну где же вы???

[Serge_Bliznykov]

Nanochka, Вы ж поймите, раз никто не отзывается, значит нечего сказать... а не потому, что Вас игнорируют! Вы вообще умница. Хорошо копаете...
А вот тема у Вас очень непростая...

Теперь по существу.
Я абсолютно не уверен, что Вы правильно переводите алгоритм.. (некогда разбираться и копать глубоко ;-(

1) даже если Вы правильно и полностью переведёте вышеприведённую программу с C на Pascal - всё равно не получится - в коде программы на C используется, например, функции XYmodP() или Y_K_M_mod_P(), которые Вам прийдётся писать самостоятельно...

2) перед первым выделенным красным кодом
while(K,(P-1)) == 0) ;
в программе на C есть присвоение K=simple[random(R)];
где это у Вас?..

3) while(K,(P-1)) == 0) ;
на Паскале (Delphi) будет так:
while( (K mod (P-1)) = 0) do ...

4) выделенный второй участок кода находится в ЗАКОММЕНТИРОВАННОЙ части программы...

и т.д....

[Nanochka]

Ну хоть на это спасибо

[Serge_Bliznykov]

к сожалению, не за что...
лучше расскажите - 1) каковы сроки?
2) насколько Ваш проект должен быть приближён к практической жизни? (можно ли использовать МАЛЕНЬКИЕ простые числа? просто для иллюстрации работы алгоритма?)

[Nanochka]

сроков сдачи уже нету, на следующей неделе-расстрел.
в программе не должно быть ничего особенного, вплоть до того, что пример шифруемого текста может нажодиться не на форме, а в тексте программы, но программа должна его шифровать и куда-нибудь выводить полученвые значения,больше никаких ограничений!

[Nanochka]

может кто нибудь в нете что встречал?