RSA verschlüsselung

[negaH]

Wenn du das geschafft hast kopierst du die Procedure RSA aus dem gleichen Thread und baust sie wie oben in das Test Projekt ein.

Delphi-Quellcode:

procedure RSA; 
// RSA 1024 Bit verschlüsselung 
var 
  P,Q: IInteger; 
  N: IInteger;    
  E,D: IInteger;  
  U,Dp,Dq: IInteger; 
  M,C: IInteger;    
  X,Y: IInteger;    
begin 
// Schüssel Erzeugung 
// 1. Primzahlen P,Q erzeugen, jeweils 512 Bit groß, N=P*Q erzeugen
  repeat 
    NRnd(P, 512); 
    NBit(P, 512 -2, True); 
    NMakePrime(P, [1, 2]); 
    repeat 
      NRnd(Q, 512); 
      NBit(Q, 512 -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) = 1024; 
// 2. Exponenten E und D erzeugen
  NDec(P); 
  NDec(Q); 
  NLCM(U, P, Q);   // Phi   
  repeat 
    repeat 
      NRnd(E, NLog2(NSize(N)) * 4);    
      NOdd(E, True); 
    until NGCD1(E, P) and NGCD1(E, Q); 
  until NInvMod(D, E, U) and (NSize(D) >= NSize(E)) and NGCD1(D, N); 
// 3. Hilfsvariablen des privaten Keys erzeugen um die Entschlüsselung 400% zu beschleunigen
  NMod(Dp, D, P);    
  NMod(Dq, D, Q);    
  NInc(P); 
  NInc(Q); 
  NInvMod(U, P, Q);  

// privater und öffentlicher RSA 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 


// verschlüssele M den PlainText zu CipherText C = M^E mod N 
  NSet(M, 'Unser Geheimnis', 256); 
  NPowMod(C, M, E, N);          

// entschlüssele C per Chinese Remainder Theorem ca. 4 mal schneller als normale Variante 
  NPowMod(X, C, Dp, P); 
  NPowMod(Y, C, Dq, Q); 
  NCRT(Y, NInt([X, Y]), NInt([Dp, Dq]), NInt([U])); 

// Y = M entschlüsselt 
// Ausgabe

  WriteLn('Schlüssel');
  WriteLn('P  : ', NStr(P));
  WriteLn('Q  : ', NStr(Q));
  WriteLn('N  : ', NStr(N));
  WriteLn('E  : ', NStr(E));
  WriteLn('D  : ', NStr(D));
  WriteLn('U  : ', NStr(U));
  WriteLn('Dp : ', NStr(Dp));
  WriteLn('Dq : ', NStr(Dq));
  WriteLn(#13, 'Verschlüsselung');
  WriteLn('M  : ', NStr(M, 256));
  WriteLn('M  : ', NStr(M));
  WriteLn('C  : ', NStr(C));
  WriteLn(#13, 'Entschlüsselung');
  WriteLn('Y  : ', NStr(Y, 256));
  WriteLn('Y  : ', NStr(Y));
  WriteLn(#13'fertig'#13);
end;

Gruß Hagen

[NicNacMan]

respect!

hat alles super gefunzt, danke

[NicNacMan]

ich hab gestern nacht mal 6-stelligen zahlen mit den public keys e und N verschlüsselt
und dann mit der musterlösung verglichen (das ganze is so ne art test):
24540494168278770214786214883175221254310871335534 1721279658
aber davon stimmte kein wert.

kann es sein, dass man verschiedene lösungen erhält, je nachdem wie man etwas verschlüsselt.
ich hab das soweit verstanden, dass man nicht die ganze zahl hoch e nimmt und dann mod N,
sondern in stückchenweise.
aber kommt dann auch das gleiche raus?

[negaH]

Hi,

ich verstehe deine Frage nicht zu 100%. Anscheinend hast du Musterlösungen poste doch ein par hier. Fakt ist das die Verschlüsselung beim RSA exakt C = M^E mod N ist und nicht anders. Das ist natürlich nur rein mathematisch gesehen korrekt den technologisch werden nun darüber die verschiedenen Protokolle drübergestülpt. Und exakt diese Protokolle beschreiben wie zb. die Zahlen Formate aussehen, wie eine lange Message in Teilstücken zu zerlegen ist, welche zusätzlichen Daten in die Message vor der Verschlüsselung einzuarbeiten ist usw. usw. Es könnte also duchaus sein das deine Testcases schon solchen Regeln unterworfen wurde. Sage mir doch mal was in diesen Testcases und Aufgabenstellungen alles für Randbedingungen existieren.

Eines kann ich dir aber absolut garantieren: mit DECMath wird alles korrekt berechnet falls man die Inputdaten auch im richtigen Format übergibt. Seit Veröffentlichung des DECMaths hier wurde bisher nur ein Fehler in den Funktionen gefunden, übrigens in einer kryptographisch sehr unwichtigen Funktion.

Als ersten Test würde ich mal mit NStr(C, 16) die Ausgabewerte in HEX anzeigen lassen. Dann nimmst du die angeblich korrekte Lösungszahl und zeigst sie mit NSet(L, '12345....123423434'); WriteLn(NStr(L, 16)); ebenfalls in HEX an. Eine zweite Ausgabe von L dann so NSwp(L, piBit); WriteLn(NStr(L, 16)); Dabei wird die Reihenfolge der Bits in L von Litte Endianess in Big Endianess umgewandelt. Ich empfehle das weil ich weis das ein großer "Anfängerfehler" bei solchen Sachen immer wieder die interne Darstellung der Zahlen ist. Es gibt verschiedene math. Libraries die intern in Big Endian speichern und es zulassen das bei der Ausgabe dieser Zahl nicht die math. korrekte Zahl ausgegeben wird.

Gruß Hagen

[NicNacMan]

also das ganze kommt von der seite www.i-nerds.com
man kann halt verschiedene aufgaben "hackits" lösen und bekommt dann punkte dafür.
ich hab mich an "Be a millionaire" versucht, wo man versuchen muss eine online überweisung zu fälschen. (natürlich keine echte *g*)
zuerst braucht man eine gültige pin, mit der kann man dann die tan anfordern, ...

die tan bekommt man per email zugeschickt:
[spoiler]
Sehr geehrter Herr Brathering,

vielen Dank für die Nutzung unseres Online-Transaktionsmanagers.
Um den Transaktionsmanager nun in dem vollen Umfang nutzen zu können, benötigen Sie neben der PIN (Persönliche Identifikations Nummer), auch eine 6 stellige TAN (Trans Aktions Nummer).
Um Ihre hundertprozentige Sicherheit während der Online-Transaktion zu gewährleisten, wurde die TAN mittels "RSA" verschlüsselt.
Benutzen Sie zum entschlüsseln Ihren privaten Schlüssel, den Sie bei der Konto-Eröffnung von uns erhalten haben, und geben die dechiffrierte TAN in dem dafür vorgesehenem Feld ein.

Mit freundlichen Grüßen, Ihre Deutsche Bank...

Ihre verschlüsselte TAN lautet: 24540494168278770214786214883175221254310871335534 1721279658

Special 3 - www.i-nerds.com - /* © 2003 by z3r0x */
[/spoiler]

die public keys bekommt man dann, wenn man einen (nachgebauten) htaccess passwortschutz "geknackt" hat^^:
[spoiler]
RSA Public Key 'N': 26967259745684484909271072928592253020339168682042 2133286759
RSA Public Key 'e': 5456431
[/spoiler]

da ich keinen private key hab, musste ich alle möglichen tans (also alle 6 stelligen zahlen) mit den public keys verschlüssel.
die hab ich dann mit der verschüsselten tan verglichen, aber nichts gefunden.
keine der 999.999 tans passt.
aber zum glück hat das mit deiner hilfe nur 59 sekunden gedauert alle tans zu verschlüsseln

da ich jetzt aber keine übereinstimmung gefunden hab, bin ich mal wieder ratlos.
ich hatte mir bei den zahlreichen komponenten, die ich schon getestet hatte ein paar mal genauer angeguckt und rausgefunden, dass die rechnung schrittweise gerechnet wird.
999999^5456431 ist auch nicht gerade die kleinste zahl.

ich werd das mit der hexadezimal darstellung gleich mal versuchen.
thx&cu nicnacman

[negaH]

Sie schicken dir eine Liste von möglichen TANs und eine davon soll die richtige sein ?
Wie passt aber nun der öffentliche RSA Schlüssel ins Bild ?
Ich vermute mal eher das du mit dem Privaten Schlüssel des öffentlichen RSA Schlüssel eine beliebige TAN mit einer gültigen digitalen Signatur versehen musst. D.h. du musst zur TAN die du verschickt eine digitale Unterschrift erzeugen. Dazu benötigst du aber den privaten Teil deines RSA Schlüssel's den du nicht in der nötigen Form besitzt. Denn du besitzt N das aus P*Q errechnet wird, du benötigst nun P und Q um den korrekten Entschlüsselungs-Exponenten D erzeugen zu können. Dieser wird dann samt P,Q benötigt um eine digitale Unterschrift zu erzeugen. Nun, deine Aufgabe ist es aus N die beiden Primzahlen P,Q zu errechnen, per Faktorization. Das ist mit < 128 Bit N eventuell noch auf deinem PC möglich, aber bei N mit mehr als 128 Bits sehe ich echt schwarz. Es sei denn die Primzahlen P,Q in N sind von sehr schlechter Qualität, also einfach zu finden.

Gruß Hagen

[NicNacMan]

ich denke mal das mit dem öffentlichen schlüssel aus der email (den man bei der kontoeröffnung bekommen haben soll) ist nur show.
wenn man weiß, dass die tan aus 6 zahlen besteht, dann ist es doch deutliche einfacher alle zu verschlüsseln und zu gucken was rauskommt, als N in p und q zu zerlegen um D rauszubekommen, oder?

ich hab jetzt alle nochmal in hex verglichen und mit der anderen bit reihenfolge, aber wieder nichts gefunden.

wenn ich es jetzt versuchen würde N in p und q zu zerlegen,
dann müsste ich doch für p alle primzahlen bis sqrt(N) nehmen und gucken, ob N mod p = 0 ist.
soweit ich das verstanden habe darf diese hilfszahl z = (p-1) * (q-1) kein vielfaches von e sein
und e * D mod z muss 1 sein.

[negaH]

Ja das ist alles richtig. Du musst nicht bis N^0.5 suchen, es gibt weit weit bessere Faktorisierungsverfahren. Denoch, bei großem N, hast du keine wirkliche Chance das N zu zerlegen, es ist einfach viel zu groß. Es sei denn P,Q wurden absichtlich so schlecht gewählt das du eine Chance im Spiel absichtlich bekommen hast. (was ich nicht glaube).

Meine Vermutung ist eher das das Spiel anders verläuft, sprich N,E für andere Aufgaben benötigt wird. Leider habe ich nichts darüber gefunden was man im Spiel eigentlich machen soll. Und ehrlich gesagt interessiert mich das auch nicht so wirklich.

Gruß hagen

[NicNacMan]

ok danke.

wäre auch zu schön gewesen, wenn das so einfach wäre.

thx&cu nicnacman

[gammatester]

Mit diesen Werten

"also die public keys sind:
N = 26967259745684484909271072928592253020339168682042 2133286759
e = 5456431"

kommt man nicht ohne Multipräzisionszahlen aus. Wenn Du DEC nicht benutzen kannst/willst, findest Du auf meiner Seite <http://home.netsurf.de/wolfgang.ehrhardt/misc_de.html#mpint> das mpint_2006-03-12.zip. Darin sind zwei kleine Beispielprogramme zum RSA.

Gruß
Wolfgang