RSA Hilfe

[Apollonius]

Du gehst für jedes Zeichen einzeln vor. Wenn du mit dem ASCII-Zeichensatz arbeitest, ist jedes Zeichen genau ein Byte.
Mit Ord(Zeichen) kannst du auf den Zahlenwert zugreifen.

[nitschchedu]

Und wie mach ich die Formel in Delphi ?

http://upload.wikimedia.org/math/d/9...f00398c7c7.png

Und habe noch woanders gelesen das man auf sehr große zahlen achten soll, also die größer sind als Integer oder Int64. Könnte das für mich ein Problem werden ?

[Apollonius]

Es gibt eine spezielle Technik zum Potenzieren mit mod. Du quadrierst einfach immer nur und nimmst jedes mal wieder mod, also:
7^23=7^16*7^4*7^2*7^1
7^1 ist bekannt, ebenso 7^2. 7^4 ist 7^2 zum Quadrat, darauf wendest du dann schon mod an, um die Zahlen kleinzuhalten.
Diese "modulierte" 7^4 kannst du quadrieren und erhältst 7^8, worauf du natürlich nochmals mod anwenden musst.
Erst ganz am Ende mussst du dann vier Zahlen, die alle nicht größer sind als 143, miteinander multiplizieren.

Und die Größe der Zahlen... Es gibt kein Problem, solange n<=sqrt(high(int64)), aber so erreichst du absolut keine Sicherheit.

[negaH]

Zitat:

Du gehst für jedes Zeichen einzeln vor. Wenn du mit dem ASCII-Zeichensatz arbeitest, ist jedes Zeichen genau ein Byte.
Mit Ord(Zeichen) kannst du auf den Zahlenwert zugreifen.

Vorsicht, das ist unsicher.

RSA wird und sollte immer als Hybrid eingesetzt werden, das ist wichtig. Hybride Verfahren (fast alle praktischen Verfahren sind Hybride) benutzen asymmetrische wie auch symmetrische Verfahren als Kombination.

Im Falle von RSA könnte das so aussehen:

1.) erzeuge einen 256 Bit langen sicheren Zufallswert -> Sessionkey.
2.) verschlüssele eine Nachricht mit zb. AES-Rijndael (symmertsiches Verfahren) und benutze obigen Sessionkey als Passwort
3.) verschlüssele diesen Sessionkey mit dem RSA Public Key des Empfängers (asymmetrisches Verfahren)
4.) speichere beide verschlüsselte Datenblöcke in eine Datei/EMail etc.pp.

5.) wenn's noch sicherer sein soll ziehe über die unverschlüsselte Nachricht mit einem Hash-Algortihmus (symmetrisch Einweg) einen digitalen Fingerabdruck
6.) ent-schlüssele diesen mit dem eigenen Privaten RSA Key
7.) hänge das als Digitale Signatur mit an die Daten dran

Benutzt man RSA wie oben vorgeschlagen so kann man die Nachricht knacken !

Gruß hagen

[nitschchedu]

Würde es gerne am Ende so wie ganz oben das Beispiel haben.
Also vorher würd die nachricht SHA und dann in RSA.
Aber wie ist das nun nihmt RSA nun jedes einzelne Zeichen oder wie ?

[nitschchedu]

Hey Leute ich habe da was gefunden das ist einfach nur geil RSA .... das ist einfach nur geil, einfach + Übersichtlich und es geht

[andy21]

Hallo,

bei mir kommt ein Exception-Fehler der Klasse Iinteger, wenn ich mit RSA wieder entschlüsseln will (und den geheimen Schlüssel d über den euklidischen Algorithmus ermittele). Und zwar "Iinteger division by zero", welches auf die Zeile u:=v0; zeigt. Welche Division meint der Compiler? Die nmod zwei Zeilen darüber oder ndiv zwei Zeilen darunter? Ich weiß auch nicht warum dort etwas null sein sollte. Diese Fehlermeldung macht mich noch fertig.

Code:

function tform1.invers_mod(e,o: iinteger): iinteger;
  var d,v: iinteger;
begin
  nrnd(d,4048);
  nrnd(v,4048);
  ggTerw(e,o,d,v); //der Funktionswert von ggT wird nicht benötigt
  if ncmp(d,z) < 0 then nadd(d,o);
  result := d;
end;


Function tform1.ggTerw(a,b: iinteger; var u,v: iinteger):iinteger;
  var u0, v0,z1,z2:iinteger;
begin
  nrnd(z1,4048);
  nrnd(z2,4048);
  if b = z then Begin
    nset(result,a);
    nset(result,1);
    nset(v,0);
  End else Begin
    nmod(a,b);
    result := ggTerw(b, a, u0, v0);//rekursiv
    u := v0;  //Hier zeigt der Pfeil hin, wenn das Programm abkracht.
    a := z2;
    ndiv(z2,b);
    nmul(z2,v0);
    nsub(v,u0,z2); //    v := u0 - (a div b)*v0;
  End;
end;

Kann mir jemand sagen wo der Fehler liegt?

Edit: Ach, anscheinend liegt es an ndiv, ich habe den Fehler gefunden; falsch verglichen.

[negaH]

anbei mal der RSA DEMO Source aus meinem Test projekt das im DEC 5.1c mit enthalten ist.

Delphi-Quellcode:

procedure Step7;
// 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
  Write(#8);        // clear screen

  repeat
  // erzeuge 512 Bit Primzahl P
    NRnd(P, 512);
    NBit(P, 512 -2, True);
    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;

1.) Warum benutzt du nicht NInvMod() um die inverse modulare Multiplikation zu machen ?
2.) Warum benutzt du nicht NGCD() um den ggT() zu berechnen ?

Gruß Hagen