Potenzieren mit sehr großen Zahlen ohne modulus?????

[negaH]

Sag das doch gleich.

Deine Formel Ce^x * Cf^y = (m^e)^x*(m^f)^y = m^(e*x+y*f) = m^1 = m ist unvollständig !
Wir arbeiten beim RSA immer in einem modularem Ring zu N, ergo richtig ist

Ce^x * Cf^y == m mod N

m = Ce^x * Cf^y mod N
m = (ce^x mod N * Cf^y mod N) mod N

Kopiere nachfolgenden Source in TestUnit.pas und registriere mit RegisterProc('\RSA\Test', '', Test, vk_F8) diese Procedure. Dann startest du Test.exe und drückst F8. Fertig.

Dieser Angriff kann also nur funktionieren weil beide Parteien das gleiche N benutzen und die Message M NICHT mit Zufallsdaten expandiert haben. Es ist also WICHTIG beim RSA die Nachricht M vor der Verschlüsselung immer mit Zufall zu expandieren ! Besonders bei digitalen Signaturen ist dies wichtig.

Gruß Hagen

Delphi-Quellcode:

procedure Test;
const
  KeySize = 256;
  QSize   = KeySize div 2;
  PSize   = KeySize - QSize;

var
  P,Q,U: IInteger;
  N: IInteger;
  E1,D1,C1: IInteger;
  E2,D2,C2: IInteger;
  M,X,Y: IInteger;
begin
// bilde RSA Domain, P,Q,N
  repeat
    NRnd(P, PSize);
    NBit(P, PSize -2, True);
    NMakePrime(P, [1, 2]);
    repeat
      NRnd(Q, QSize);
      NBit(Q, QSize -2, True);
      NMakePrime(Q, [1, 2]);
    until NCmp(P, Q) <> 0;
    if NCmp(P, Q) < 0 then NSwp(P, Q);
    NMul(N, P, Q);
  until NSize(N) = KeySize;
  WriteLn('N : ', NStr(N));
  
// erzeuge public/private Ver/Entschlüsselung Exponenten
  NDec(P);
  NDec(Q);
  NLCM(U, P, Q);
  repeat
    repeat
      NRnd(E1, NLog2(NSize(N)) * 4);
      NOdd(E1, True);
    until NGCD1(E1, P) and NGCD1(E1, Q);
  until NInvMod(D1, E1, U) and (NSize(D1) >= NSize(E1)) and NGCD1(D1, N);

  repeat
    repeat
      NRnd(E2, NLog2(NSize(N)) * 4);
      NOdd(E2, True);
    until NGCD1(E2, P) and NGCD1(E2, Q) and NGCD1(E1, E2);
  until NInvMod(D2, E2, U) and (NSize(D2) >= NSize(E2)) and NGCD1(D2, N);

  WriteLn('E1 : ', NStr(E1));
  WriteLn('E2 : ', NStr(E2));

  NSet(M, 'unser Geheimnis', 256);

  NPowMod(C1, M, E1, N); // verschlüssele M mit E1
  NPowMod(C2, M, E2, N); // verschlüssele M mit E2

  WriteLn('C1 : ', NStr(C1));
  WriteLn('C2 : ', NStr(C2));

  NGCD(U, X, Y, E1, E2); // erweiterter GCD()

  NPowMod(U, NInt([C1, C2]), NInt([X, Y]), N); // U = C1^X * C2^Y mod N

  WriteLn('M  : ', NStr(M, 256));
  WriteLn('M'' : ', NStr(U, 256)); // U = M
  WriteLn;
end;