RSA: Privaten Schlüssel schneller berechnen

[negaH]

Code:

  repeat
    repeat
      P = RandomPrime()                       // Primzahl P erzeugen
      Q = RandomPrime()                       // Primzahl Q erzeugen 
      N = P * Q                               // Public Modul N erzeugen
      E = Random() mod (2^(Ln2(Ln2(N)) * 4))  // public Exponent erzeugen, sollt BitSize(BitSize(N))*4
                                              // Bits groß sein BitSize(N) = Ln2(N)
    until GCD(E, N) = 1                       // E muß teilerfremd zu N = P*Q und somit auch P und Q sein
 
    Phi = LCM(P -1, Q -1)                     // Phi(N) = LCM(P -1, Q -1), 
                                              //   das geht weil wir wissen das N in P,Q faktorisierbar ist
    
  until (ExtGCD(D, T, E, Phi) == 1) and       // D = E^-1 mod Phi(N), Decryption Exponent erzeugen
        (D > E) and                           // D muß größer E sein
        (GCD(D, N) = 1)                       // D muß teilerfremd zu N sein, und somit auch zu P und Q

R = ExtGCD(var U,V; const A,B) ist definiert als R = U*A + V*B

und nachfolgend mal eine RSA Schlüsselerzeugung als praktischer Source in meinem DECMath

Delphi-Quellcode:

procedure RSA;
// RSA 1024 Bit verschlüsselung
var
  P,Q: IInteger;     // primzahlen
  N: IInteger;        // modulus
  E,D: IInteger;     // public/private exponent
  U,Dp,Dq: IInteger; // private values to speedup decryption by factor 4
  M,C: IInteger;     // Plaintext/Ciphertext
  X,Y: IInteger;     // helper
begin
  repeat
  // erzeuge 512 Bit Primzahl P
    NRnd(P, 512);
    NBit(P, 512 -2, True);     // setze 2'höchstes Bit in P um sicherzustellen das P*Q ein 1024 Bit N erzeugen
    NMakePrime(P, [1, 2]);
  // erzeuge 512 Bit Primzahl Q
    repeat
      NRnd(Q, 512);
      NBit(Q, 512 -2, True);
      NMakePrime(Q, [1, 2]);
    until NCmp(P, Q) <> 0; // verhindere unwahrscheinlichen Fall das P gleich Q ist
    if NCmp(P, Q) < 0 then NSwp(P, Q);   // make sure P > Q
  // erzeuge public Modul N = 1024 Bit,  N = P * Q
    NMul(N, P, Q);
  until NSize(N) = 1024;  // verhindere unwahrscheinlichen Fall das N nicht wie gewünscht 1024 Bit groß ist

// erzeuge sicheren public Exponenten E, private Exponenten D zur entschlüsselung
  NDec(P);
  NDec(Q);
  NLCM(U, P, Q);       // U = LCM(P -1, Q -1)
  repeat
    repeat
      NRnd(E, NLog2(NSize(N)) * 4);    // Exponent sollte 4*Log2(Log2(N)) groß sein, zufällig und ungerade
      NOdd(E, True);
    until NGCD1(E, P) and NGCD1(E, Q); // Exponent darf keinen gemeinsammen Teiler mit P oder Q haben, sprich nicht durch P,Q teilbar sein
 // erzeuge private Entschlüsselungsexponent D, D sollte >= E sein und keinen gemeinsammen Teiler mit N haben
  until NInvMod(D, E, U) and (NSize(D) >= NSize(E)) and NGCD1(D, N);

  NMod(Dp, D, P);    // Dp = D mod (P -1), wird benötigt für Chinese Remainder Theorem CRT
  NMod(Dq, D, Q);    // Dq = Q mod (Q -1)
  NInc(P);
  NInc(Q);
  NInvMod(U, P, Q);  // U = P^-1 mod Q
// unser privater und öffentlicher Schlüssel sind nun fertig
// N,E ist der öffentliche Schlüssel
// N,D der private Schlüssel, wobei
// U,Dp,Dq,P,Q dazu gehören damit wir die Entschlüsselung um Faktor 4 beschleunigen können


// nun verschlüsseln wir M den PlainText
  NSet(M, 'Unser Geheimnis', 256);
  NCut(M, NHigh(N));          // M muß kleiner public Modul N sein
// CipherText C = M^E mod N
  NPowMod(C, M, E, N);          // C = M^E mod N

  Write(#21);
  WriteLn(#2'PlainText   : '#0, NStr(M, 16), ' = ', NStr(M, 256) );
  WriteLn(#3'CipherText : '#0, NStr(C, 16) );
  Write(#20#0);

// nun entschlüsseln wir auf herkömmliche Art,
//     X = M = C^D mod N
  WriteLn(#2'normal entschlüsselt'#0#30);

  NPowMod(X, C, D, N);

  WriteLn( NStr(X, 256) );

// nun die schnelle Variante per CRT = Chinese Remainder Theorem ca. 4 mal schneller
  WriteLn(#10#2'per CRT entschlüsselt: '#0#30);

  NPowMod(X, C, Dp, P);
  NPowMod(Y, C, Dq, Q);
  NSub(Y, X);
  NMulMod(Y, U, Q);
  NMul(Y, P);
  NAdd(Y, X);

  WriteLn( NStr(Y, 256), ' = ', NStr(Y, 16));

// oder
  WriteLn(#30);
  NPowMod(X, C, Dp, P);
  NPowMod(Y, C, Dq, Q);
  NCRT(Y, NInt([X, Y]), NInt([Dp, Dq]), NInt([U]));
  WriteLn( NStr(Y, 256) );
end;

NInvMod(var R, const A, const M) = modulares Inverses ist definiert als ExtGCD(var R, var Dummy, const A, const M).
NInvMod() ist damit nur eine spezialisierte Funktion des erweiterten ggT() -> extended GCD().


Gruß Hagen