gint.pas

rsa加密算法实例

Procedure GIntDivByInt(GInt : TGInt; Var res : TGInt; by : longint; Var m : longint);
Var
   S, S1 : String;
Begin
   If (by Div 10000) = 0 Then
   Begin
      S := '';
      While GInt^.next <> Nil Do GInt := GInt^.next;
      S := inttostr(GInt^.value Div by);
      m := (GInt^.value Mod by);
      While GInt^.prev <> Nil Do
      Begin
         m := m * 10000;
         GInt := GInt^.prev;
         S1 := inttostr((GInt^.value + m) Div by);
         While length(S1) < 4 Do S1 := '0' + S1;
         S := S + S1;
         m := ((GInt^.value + m) Mod by);
      End;
      decstrtogint(S, res);
   End;
End;


// GInt modulo an integer, GInt mod by = m

Procedure GIntModByInt(GInt : TGInt; by : longint; Var m : longint);
Begin
   If (by Div 10000) = 0 Then
   Begin
      While GInt^.next <> Nil Do GInt := GInt^.next;
      m := (GInt^.value Mod by);
      While GInt^.prev <> Nil Do
      Begin
         m := m * 10000;
         GInt := GInt^.prev;
         m := ((GInt^.value + m) Mod by);
      End;
   End;
End;


// Compare two GInts in absolute value, GInt1 < : St, > : Lt, = : Eq, Error : Er GInt2

Function GIntCompareAbs(GInt1, GInt2 : TGInt) : TCompare;
Begin

   GIntCompareAbs := Er;

   While (GInt1^.next <> Nil) And (GInt2^.next <> Nil) Do
   Begin
      GInt1 := GInt1^.next;
      GInt2 := GInt2^.next;
   End;

   If (GInt1^.next = Nil) And (GInt2^.next <> Nil) Then GIntCompareAbs := St;

   If (GInt2^.next = Nil) And (GInt1^.next <> Nil) Then GIntCompareAbs := Lt;

   If (GInt1^.next = Nil) And (GInt2^.next = Nil) Then
   Begin
      While (GInt1^.value = GInt2^.value) And (GInt1^.prev <> Nil) Do
      Begin
         GInt1 := GInt1^.prev;
         GInt2 := GInt2^.prev;
      End;

      If (GInt1^.value > GInt2^.value) Then GIntCompareAbs := Lt
      Else If (GInt1^.value < GInt2^.value) Then GIntCompareAbs := St Else GIntCompareAbs := Eq;
   End

End;


// Change the sign of a GInt

Procedure GIntChangeSign(Var GInt : TGInt);
Begin
   If GInt^.sign = negative Then GInt^.sign := positive Else GInt^.sign := negative;
End;


// Returns the GInt in its absolute value

Procedure GIntAbs(Var GInt : TGInt);
Begin
   GInt^.sign := positive;
End;


// Add 2 GInts, GInt1 + GInt2 = sum

Procedure GIntAdd(GInt1, GInt2 : TGInt; Var sum : TGInt);
Var
   temp1, temp2 : TGInt;
   rest : integer;
   Tres : Longint;
Begin
   If (GInt1^.sign = GInt2^.sign) Then
   Begin

      new(temp2);
      temp2^.prev := Nil;
      Tres := GInt1^.value + GInt2^.value;
      temp2^.value := Tres Mod 10000;
      temp2^.sign := GInt1^.sign;
      If Tres >= 10000 Then rest := 1 Else rest := 0;

      While (GInt1^.next <> Nil) And (GInt2^.next <> Nil) Do
      Begin
         GInt1 := GInt1^.next;
         GInt2 := GInt2^.next;
         new(temp1);
         Tres := GInt1^.value + GInt2^.value + rest;
         temp1^.value := Tres Mod 10000;
         If Tres >= 10000 Then rest := 1 Else rest := 0;
         temp1^.prev := temp2;
         temp2^.next := temp1;
         temp2 := temp1;
      End;

      While (GInt1^.next) <> Nil Do
      Begin
         GInt1 := GInt1^.next;
         new(temp1);
         Tres := GInt1^.value + rest;
         temp1^.value := Tres Mod 10000;
         If Tres >= 10000 Then rest := 1 Else rest := 0;
         temp1^.prev := temp2;
         temp2^.next := temp1;
         temp2 := temp1;
      End;

      While (GInt2^.next) <> Nil Do
      Begin
         GInt2 := GInt2^.next;
         new(temp1);
         Tres := GInt2^.value + rest;
         temp1^.value := Tres Mod 10000;
         If Tres >= 10000 Then rest := 1 Else rest := 0;
         temp1^.prev := temp2;
         temp2^.next := temp1;
         temp2 := temp1;
      End;

      If rest <> 0 Then
      Begin
         new(temp1);
         temp1^.value := (rest) Mod 10000;
         temp1^.prev := temp2;
         temp2^.next := temp1;
         temp2 := temp1;
      End;

      temp2^.next := Nil;
      sum := temp2;
      While sum^.prev <> Nil Do sum := sum^.prev;

   End
   Else
   Begin
      If (GIntCompareAbs(GInt1, GInt2) = Lt) Or (GIntCompareAbs(GInt1, GInt2) = Eq) Then
      Begin

         new(temp2);
         temp2^.prev := Nil;
         temp2^.sign := GInt1^.sign;
         Tres := 10000 + GInt1^.value - GInt2^.value;
         temp2^.value := Tres Mod 10000;
         If (GInt1^.value - GInt2^.value) < 0 Then rest := -1 Else rest := 0;

         While (GInt1^.next <> Nil) And (GInt2^.next <> Nil) Do
         Begin
            GInt1 := GInt1^.next;
            GInt2 := GInt2^.next;
            new(temp1);
            Tres := GInt1^.value - GInt2^.value + rest;
            temp1^.value := (10000 + Tres) Mod 10000;
            If Tres < 0 Then rest := -1 Else rest := 0;
            temp1^.prev := temp2;
            temp2^.next := temp1;
            temp2 := temp1;
         End;

         While (GInt1^.next) <> Nil Do
         Begin
            GInt1 := GInt1^.next;
            new(temp1);
            Tres := GInt1^.value + rest;
            temp1^.value := (10000 + Tres) Mod 10000;
            If Tres < 0 Then rest := -1 Else rest := 0;
            temp1^.prev := temp2;
            temp2^.next := temp1;
            temp2 := temp1;
         End;


         If rest <> 0 Then
         Begin
            new(temp1);
            temp1^.value := (10000 + rest) Mod 10000;
            temp1^.prev := temp2;
            temp2^.next := temp1;
            temp2 := temp1;
         End;

         While (temp2^.value = 0) And (temp2^.prev <> Nil) Do
         Begin
            temp2 := temp2^.prev;
            dispose(temp2^.next);
            temp2^.next := Nil;
         End;
         temp2^.next := Nil;
         sum := temp2;
         While sum^.prev <> Nil Do sum := sum^.prev;

      End

      Else
         GIntadd(GInt2, GInt1, sum);

   End

End;


// Subtract 2 GInts, GInt1 - GInt2 = dif

Procedure GIntSub(GInt1, GInt2 : TGInt; Var dif : TGInt);
Begin
   GIntchangesign(GInt2);
   GIntadd(GInt1, GInt2, dif);
   GIntchangesign(GInt2);
End;


// Multiply 2 GInts, GInt1 * GInt2 = prod

Procedure GIntMul(GInt1, GInt2 : TGInt; Var prod : TGInt);
Var
   zero, temp1, temp2, temp : TGInt;
   sign : Tsign;
   rest, Trest : longint;
Begin
   decstrtogint('0', zero);
   If Not ((GIntcompareabs(zero, GInt1) = Eq) Or (GIntcompareabs(zero, GInt2) = Eq)) Then
   Begin
      If GInt1^.sign = GInt2^.sign Then sign := positive Else sign := negative;
      temp1 := GInt1;

      new(temp2);
      temp2^.sign := sign;
      temp2^.prev := Nil;
      temp2^.value := (GInt2^.value * temp1^.value) Mod 10000;
      rest := (GInt2^.value * temp1^.value) Div 10000;
      temp2^.next := Nil;
      prod := temp2;
      While temp1^.next <> Nil Do
      Begin
         temp1 := temp1^.next;
         new(temp);
         temp^.value := (GInt2^.value * temp1^.value + rest) Mod 10000;
         rest := (GInt2^.value * temp1^.value + rest) Div 10000;
         temp^.next := Nil;
         temp2^.next := temp;
         temp^.prev := temp2;
         temp2 := temp2^.next;
      End;
      If rest <> 0 Then
      Begin
         new(temp);
         temp^.value := rest;
         temp^.next := Nil;
         temp^.prev := temp2;
         temp2^.next := temp;
      End;

      While GInt2^.next <> Nil Do
      Begin
         If prod^.next = Nil Then
         Begin
            new(temp2);
            temp2^.value := 0;
            temp2^.prev := prod;
            prod^.next := temp2;
            temp2^.next := Nil;
         End;
         prod := prod^.next;
         GInt2 := GInt2^.next;
         temp1 := GInt1;
         temp2 := prod;
         rest := (GInt2^.value * temp1^.value + temp2^.value) Div 10000;
         temp2^.value := (GInt2^.value * temp1^.value + temp2^.value) Mod 10000;

         While temp1^.next <> Nil Do
         Begin
            temp1 := temp1^.next;
            If temp2^.next = Nil Then
            Begin
               new(temp);
               temp^.value := 0;
               temp^.next := Nil;
            End
            Else temp := temp2^.next;
            trest := (GInt2^.value * temp1^.value + rest + temp^.value) Div 10000;
            temp^.value := (GInt2^.value * temp1^.value + rest + temp^.value) Mod 10000;
            rest := trest;
            temp2^.next := temp;
            temp^.prev := temp2;
            temp2 := temp2^.next;
         End;
         If rest <> 0 Then
         Begin
            If temp2^.next = Nil Then
            Begin
               new(temp);
               temp^.value := 0;
               temp^.next := Nil;
            End
            Else temp := temp2^.next;
            temp^.value := temp^.value + rest;
            temp^.next := Nil;
            temp^.prev := temp2;
            temp2^.next := temp;
         End;

      End;

      While prod^.prev <> Nil Do prod := prod^.prev;
   End
   Else decstrtogint('0', prod);
   GIntdestroy(zero);

End;


// Prod = GInt1 * By, By < 10000

Procedure GIntMulByInt(GInt1 : TGInt; By : Longint; Var prod : TGInt);
Var
   temp2, temp : TGInt;
   sign : Tsign;
   rest : longint;
Begin
   If By < 0 Then sign := negative Else sign := positive;
   If GInt1^.sign = sign Then sign := positive Else sign := negative;
   by := abs(by);

   new(temp2);
   temp2^.sign := sign;
   temp2^.prev := Nil;
   temp2^.value := (GInt1^.value * by) Mod 10000;
   rest := (GInt1^.value * by) Div 10000;
   temp2^.next := Nil;
   prod := temp2;

   While GInt1^.next <> Nil Do
   Begin
      GInt1 := GInt1^.next;
      new(temp);
      temp^.value := (GInt1^.value * By + rest) Mod 10000;
      rest := (GInt1^.value * By + rest) Div 10000;
      temp^.next := Nil;
      temp2^.next := temp;
      temp^.prev := temp2;
      temp2 := temp2^.next;
   End;

   If rest <> 0 Then
   Begin
      new(temp);
      temp^.value := rest;
      temp^.next := Nil;
      temp^.prev := temp2;
      temp2^.next := temp;
   End;


   While prod^.prev <> Nil Do prod := prod^.prev;

End;


// GInt = GInt * By, By < 10000

Procedure GIntMulByIntBis(Var GInt : TGInt; By : Longint);
Var
   temp1, temp : TGInt;
   sign : Tsign;
   rest, TRes