elgamal.pas

ElGamal数字签名算法

{License, info, etc
 ------------------

This implementation is made by Walied Othman, to contact me
mail to [e-mail] or
[e-mail], or ICQ me on 20388046.
If you 're going to use these implementations, at least mention my
name or something and notify me so I may even put a link on my page.
This implementation is freeware and according to the coderpunks'
manifesto it should remain so, so don 't use these implementations
in commercial applications.  Encryption, as a tool to ensure privacy
should be free and accessible for anyone.  If you plan to use these
implementations in a commercial application, contact me before
doing so.  If any algorithm is patented in your country, you should
acquire a license before using this software.  Modified versions of this
software must remain in the public domain and must contain an
acknowledgement of the original author (=me).
This implementaion is available at
http://ace.ulyssis.student.kuleuven.ac.be/~triade/GInt/index.htm


copyright 1999, Walied Othman
This header may not be removed.}

Unit ElGamal;

Interface

Uses Windows, SysUtils, Controls, GInt;

Procedure ElGamalSign(M : String; p, g, x, k : TGInt; Var a, b : String);
Procedure ElGamalVerify(g, y, p : TGInt; a, b, M : String; Var ok : Boolean);
Procedure ElGamalEncrypt(P : String; g, y, k, modp : TGInt; Var E : String);
Procedure ElGamalDecrypt(E : String; x, p : TGInt; Var D : String);

Implementation


{$H+}


// Sign a string with the ElGamal algorithm, a = g^k mod p, M = (x * a + k * b) mod (p-1)

Procedure ElGamalSign(M : String; p, g, x, k : TGInt; Var a, b : String);
Var
   temp1, temp2, temp3, pmin1, one : TGInt;
Begin
   GIntModExp(g, k, p, temp1);
   GInttostr(temp1, a);
   strtoGInt(M, temp2);
   decstrtoGInt('1', one);
   GIntsub(p, one, pmin1);
   GIntdestroy(one);
   GIntmod(temp2, pmin1, temp3);
   GIntdestroy(temp2);
   temp2 := temp3;
   GIntMulMod(x, temp1, pmin1, temp3);
   GIntdestroy(temp1);
   temp1 := temp3;
   GIntchangesign(temp1);
   GIntAddMod(temp2, temp1, pmin1, temp3);
   GIntdestroy(temp1);
   GIntdestroy(temp2);
   temp1 := temp3;
   GIntModInv(k, pmin1, temp2);
   GIntMulMod(temp1, temp2, pmin1, temp3);
   GIntdestroy(temp1);
   GIntdestroy(temp2);
   GIntdestroy(pmin1);
   GInttostr(temp3, b);
   GIntdestroy(temp3);
End;


// Verify an ElGamal Signature, y = g^x mod p, // Verification: (y^a) * (a^b) mod p = g^M mod p

Procedure ElGamalVerify(g, y, p : TGInt; a, b, M : String; Var ok : Boolean);
Var
   temp1, temp2, temp3, temp4 : TGInt;
Begin
   strtoGInt(a, temp1);
   strtoGInt(b, temp2);
   GIntModExp(y, temp1, p, temp3);
   GIntModExp(temp1, temp2, p, temp4);
   GIntdestroy(temp1);
   GIntdestroy(temp2);
   temp1 := temp3;
   temp2 := temp4;
   GIntMulMod(temp1, temp2, p, temp3);
   GIntdestroy(temp1);
   GIntdestroy(temp2);
   temp1 := temp3;
   strtoGInt(M, temp3);
   GIntModExp(g, temp3, p, temp4);
   GIntdestroy(temp3);
   temp2 := temp4;
   If GIntCompareAbs(temp1, temp2) = Eq Then ok := true Else ok := false;
   GIntdestroy(temp1);
   GIntdestroy(temp2);
End;


// Encrypt a string with the ElGamal algorithm,
// P*y^k mod modp = E

Procedure ElGamalEncrypt(P : String; g, y, k, modp : TGInt; Var E : String);
Var
   i, j, modbits : longint;
   PGInt, temp1, temp2, temp3, k1, kt : TGInt;
   tempstr1, tempstr2, tempstr3 : String;
Begin
   GInttobinstr(modp, tempstr1);
   modbits := length(tempstr1);
   convert8to1bit(P, tempstr1);
   tempstr1 := '111' + tempstr1;
   j := modbits - 1;
   While (length(tempstr1) Mod j) <> 0 Do tempstr1 := '0' + tempstr1;
   GIntCopy(k, k1);
   GIntRandom1(k1, kt);

   j := length(tempstr1) Div j;
   tempstr2 := '';
   For i := 1 To j Do
   Begin
      tempstr3 := copy(tempstr1, 1, modbits - 1);
      While copy(tempstr3, 1, 1) = '0' Do delete(tempstr3, 1, 1);
      binstrtoGInt(tempstr3, PGInt);
      delete(tempstr1, 1, modbits - 1);
      GIntModExp(y, k1, modp, temp1);
      GIntMulMod(PGInt, temp1, modp, temp2);
      GIntdestroy(temp1);
      GIntModExp(g, k1, modp, temp1);
      GIntDestroy(PGInt);
      tempstr3 := '';
      GInttobinstr(temp2, tempstr3);
      While (length(tempstr3) - modbits) <> 0 Do tempstr3 := '0' + tempstr3;
      tempstr2 := tempstr2 + tempstr3;
      tempstr3 := '';
      GInttobinstr(temp1, tempstr3);
      While (length(tempstr3) - modbits) <> 0 Do tempstr3 := '0' + tempstr3;
      tempstr2 := tempstr2 + tempstr3;
      GIntdestroy(temp1);
      GIntdestroy(temp2);

      GIntRandom1(kt, temp3);
      GIntdestroy(kt);
      kt := temp3;
      GIntModExp(k1, kt, modp, temp3);
      GIntdestroy(k1);
      k1 := temp3;
   End;

   GIntDestroy(k1);
   GIntDestroy(kt);
   While (copy(tempstr2, 1, 1) = '0') Do delete(tempstr2, 1, 1);
   Convert1to8bit(tempstr2, E);
End;


// Decrypt a string with the ElGamal algorithm,
// E*(y^(-k)) mod p = D

Procedure ElGamalDecrypt(E : String; x, p : TGInt; Var D : String);
Var
   i, j, modbits : longint;
   EGInt, temp1, temp2, temp3 : TGInt;
   tempstr1, tempstr2, tempstr3 : String;
Begin
   GInttobinstr(p, tempstr1);
   modbits := length(tempstr1);
   convert8to1bit(E, tempstr1);
   While copy(tempstr1, 1, 1) = '0' Do delete(tempstr1, 1, 1);
   While (length(tempstr1) Mod (modbits * 2)) <> 0 Do tempstr1 := '0' + tempstr1;

   j := length(tempstr1) Div (modbits * 2);
   tempstr2 := '';
   For i := 1 To j Do
   Begin
      tempstr3 := copy(tempstr1, 1, modbits);
      While copy(tempstr3, 1, 1) = '0' Do delete(tempstr3, 1, 1);
      binstrtoGInt(tempstr3, EGInt);
      delete(tempstr1, 1, modbits);
      tempstr3 := copy(tempstr1, 1, modbits);
      While copy(tempstr3, 1, 1) = '0' Do delete(tempstr3, 1, 1);
      binstrtoGInt(tempstr3, temp1);
      delete(tempstr1, 1, modbits);

      GIntModExp(temp1, x, p, temp2);
      GIntDestroy(temp1);
      GIntModInv(temp2, p, temp1);
      GIntDestroy(temp2);

      GIntMulMod(EGInt, temp1, p, temp3);
      GIntDestroy(temp1);
      GIntDestroy(EGInt);
      tempstr3 := '';
      GInttobinstr(temp3, tempstr3);
      While (length(tempstr3) Mod (modbits - 1)) <> 0 Do tempstr3 := '0' + tempstr3;
      tempstr2 := tempstr2 + tempstr3;
      GIntdestroy(temp3);
   End;

   While (copy(tempstr2, 1, 3) <> '111') Do delete(tempstr2, 1, 1);
   delete(tempstr2, 1, 3);
   Convert1to8bit(tempstr2, D);
End;


End.