{License, info, etc ------------------ This implementation is made by Walied Othman, to contact me mail to Walied.Othman@Student.KULeuven.ac.be or Triade@ace.Ulyssis.Student.KULeuven.ac.be, always mention wether it 's about the FGInt for Delphi or for FreePascal, or wether it 's about the 6xs, preferably in the subject line. 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 software. 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, that way you can license the software to use it in commercial Software. If any algorithm is patented in your country, you should acquire a license before using this software. Modified versions of this software must contain an acknowledgement of the original author (=me). This implementaion is available at http://ace.ulyssis.student.kuleuven.ac.be/~triade/ copyright 2000, Walied Othman This header may not be removed. } Unit FGIntRSA; Interface Uses Windows, SysUtils, Controls, FGInt; Procedure RSAEncrypt(P : String; Var exp, modb : TFGInt; Var E : String); Procedure RSADecrypt(E : String; Var exp, modb, d_p, d_q, p, q : TFGInt; Var D : String); Procedure RSASign(M : String; Var d, n, dp, dq, p, q : TFGInt; Var S : String); Procedure RSAVerify(M, S : String; Var e, n : TFGInt; Var valid : boolean); Implementation {$H+} // Encrypt a string with the RSA algorithm, P^exp mod modb = E Procedure RSAEncrypt(P : String; Var exp, modb : TFGInt; Var E : String); Var i, j, modbits : longint; PGInt, temp, zero : TFGInt; tempstr1, tempstr2, tempstr3 : String; Begin Base2StringToFGInt('0', zero); FGIntToBase2String(modb, tempstr1); modbits := length(tempstr1); convertBase256to2(P, tempstr1); tempstr1 := '111' + tempstr1; j := modbits - 1; While (length(tempstr1) Mod j) <> 0 Do tempstr1 := '0' + tempstr1; j := length(tempstr1) Div (modbits - 1); tempstr2 := ''; For i := 1 To j Do Begin tempstr3 := copy(tempstr1, 1, modbits - 1); While (copy(tempstr3, 1, 1) = '0') And (length(tempstr3) > 1) Do delete(tempstr3, 1, 1); Base2StringToFGInt(tempstr3, PGInt); delete(tempstr1, 1, modbits - 1); If tempstr3 = '0' Then FGIntCopy(zero, temp) Else FGIntMontgomeryModExp(PGInt, exp, modb, temp); FGIntDestroy(PGInt); tempstr3 := ''; FGIntToBase2String(temp, tempstr3); While (length(tempstr3) Mod modbits) <> 0 Do tempstr3 := '0' + tempstr3; tempstr2 := tempstr2 + tempstr3; FGIntdestroy(temp); End; While (tempstr2[1] = '0') And (length(tempstr2) > 1) Do delete(tempstr2, 1, 1); ConvertBase2To256(tempstr2, E); FGIntDestroy(zero); End; // Decrypt a string with the RSA algorithm, E^exp mod modb = D // provide nil for exp.Number if you want a speedup by using the chinese // remainder theorem, modb = p*q, d_p*e mod (p-1) = 1 and // d_q*e mod (q-1) where e is the encryption exponent used Procedure RSADecrypt(E : String; Var exp, modb, d_p, d_q, p, q : TFGInt; Var D : String); Var i, j, modbits : longint; EGInt, temp, temp1, temp2, temp3, ppinvq, qqinvp, zero : TFGInt; tempstr1, tempstr2, tempstr3 : String; Begin Base2StringToFGInt('0', zero); FGIntToBase2String(modb, tempstr1); modbits := length(tempstr1); convertBase256to2(E, tempstr1); While copy(tempstr1, 1, 1) = '0' Do delete(tempstr1, 1, 1); While (length(tempstr1) Mod modbits) <> 0 Do tempstr1 := '0' + tempstr1; If exp.Number = Nil Then Begin FGIntModInv(q, p, temp1); FGIntMul(q, temp1, qqinvp); FGIntDestroy(temp1); FGIntModInv(p, q, temp1); FGIntMul(p, temp1, ppinvq); FGIntDestroy(temp1); End; j := length(tempstr1) Div modbits; tempstr2 := ''; For i := 1 To j Do Begin tempstr3 := copy(tempstr1, 1, modbits); While (copy(tempstr3, 1, 1) = '0') And (length(tempstr3) > 1) Do delete(tempstr3, 1, 1); Base2StringToFGInt(tempstr3, EGInt); delete(tempstr1, 1, modbits); If tempstr3 = '0' Then FGIntCopy(zero, temp) Else Begin If exp.Number <> Nil Then FGIntMontgomeryModExp(EGInt, exp, modb, temp) Else Begin FGIntMontgomeryModExp(EGInt, d_p, p, temp1); FGIntMul(temp1, qqinvp, temp3); FGIntCopy(temp3, temp1); FGIntMontgomeryModExp(EGInt, d_q, q, temp2); FGIntMul(temp2, ppinvq, temp3); FGIntCopy(temp3, temp2); FGIntAddMod(temp1, temp2, modb, temp); FGIntDestroy(temp1); FGIntDestroy(temp2); End; End; FGIntDestroy(EGInt); tempstr3 := ''; FGIntToBase2String(temp, tempstr3); While (length(tempstr3) Mod (modbits - 1)) <> 0 Do tempstr3 := '0' + tempstr3; tempstr2 := tempstr2 + tempstr3; FGIntdestroy(temp); End; If exp.Number = Nil Then Begin FGIntDestroy(ppinvq); FGIntDestroy(qqinvp); End; While (Not (copy(tempstr2, 1, 3) = '111')) And (length(tempstr2) > 3) Do delete(tempstr2, 1, 1); delete(tempstr2, 1, 3); ConvertBase2To256(tempstr2, D); FGIntDestroy(zero); End; // Sign strings with the RSA algorithm, M^d mod n = S // provide nil for exp.Number if you want a speedup by using the chinese // remainder theorem, n = p*q, dp*e mod (p-1) = 1 and // dq*e mod (q-1) where e is the encryption exponent used Procedure RSASign(M : String; Var d, n, dp, dq, p, q : TFGInt; Var S : String); Var MGInt, SGInt, temp, temp1, temp2, temp3, ppinvq, qqinvp : TFGInt; Begin Base256StringToFGInt(M, MGInt); If d.Number <> Nil Then FGIntMontgomeryModExp(MGInt, d, n, SGInt) Else Begin FGIntModInv(p, q, temp); FGIntMul(p, temp, ppinvq); FGIntDestroy(temp); FGIntModInv(q, p, temp); FGIntMul(q, temp, qqinvp); FGIntDestroy(temp); FGIntMontgomeryModExp(MGInt, dp, p, temp1); FGIntMul(temp1, qqinvp, temp2); FGIntCopy(temp2, temp1); FGIntMontgomeryModExp(MGInt, dq, q, temp2); FGIntMul(temp2, ppinvq, temp3); FGIntCopy(temp3, temp2); FGIntAddMod(temp1, temp2, n, SGInt); FGIntDestroy(temp1); FGIntDestroy(temp2); FGIntDestroy(ppinvq); FGIntDestroy(qqinvp); End; FGIntToBase256String(SGInt, S); FGIntDestroy(MGInt); FGIntDestroy(SGInt); End; // Verify digitally signed strings with the RSA algorihthm, // If M = S^e mod n then ok:=true else ok:=false Procedure RSAVerify(M, S : String; Var e, n : TFGInt; Var valid : boolean); Var MGInt, SGInt, temp : TFGInt; Begin Base256StringToFGInt(S, SGInt); Base256StringToFGInt(M, MGInt); FGIntMod(MGInt, n, temp); FGIntCopy(temp, MGInt); FGIntMontgomeryModExp(SGInt, e, n, temp); FGIntCopy(temp, SGInt); valid := (FGIntCompareAbs(SGInt, MGInt) = Eq); FGIntDestroy(SGInt); FGIntDestroy(MGInt); End; End.