RSA Hilfe

[nitschchedu]

Hallo Leute,
also ich will RSA benutzen am bessten ist es wenn ich das selber schreibe. Aber ich habe da ein verständnis problem.
Ich habe mir schon zahlreiche beiträge dazu angesehen aber konnte nix damit anfangen.
Habe mir auch das im Wiki angeschaut und habe das nicht so richtig verstanden.

Ich brauche das am ende so wie es in Python ist:

Code:

from Crypto.PublicKey import RSA
from Crypto.Hash import SHA

main_key_sign = RSA.construct((
    # n
    0x86724794f8a0fcb0c129b979e7af2e1e309303a7042503d835708873b1df8a9e307c228b9c0862f8f5dbe6f81579233db8a4fe6ba14551679ad72c01973b5ee4ecf8ca2c21524b125bb06cfa0047e2d202c2a70b7f71ad7d1c3665e557a7387bbc43fe52244e58d91a14c660a84b6ae6fdc857b3f595376a8e484cb6b90cc992f5c57cccb1a1197ee90814186b046968f872b84297dad46ed4119ae0f402803108ad95777615c827de8372487a22902cb288bcbad7bc4a842e03a33bd26e052386cbc088c3932bdd1ec4fee1f734fe5eeec55d51c91e1d9e5eae46cf7aac15b2654af8e6c9443b41e92568cce79c08ab6fa61601e4eed791f0436fdc296bb373L,
    # e
    0x07e89acc87188755b1027452770a4e01c69f3c733c7aa5df8aac44430a768faef3cb11174569e7b44ab2951da6e90212b0822d1563d6e6abbdd06c0017f46efe684adeb74d4113798cec42a54b4f85d01e47af79259d4670c56c9c950527f443838b876e3e5ef62ae36aa241ebc83376ffde9bbf4aae6cabea407cfbb08848179e466bcb046b0a857d821c5888fcd95b2aae1b92aa64f3a6037295144aa45d0dbebce075023523bce4243ae194258026fc879656560c109ea9547a002db38b89caac90d75758e74c5616ed9816f3ed130ff6926a1597380b6fc98b5eeefc5104502d9bee9da296ca26b32d9094452ab1eb9cf970acabeecde6b1ffae57b56401L,
    # d
    0x11L,
))

def rsa_sign_message_1024(rsakey, message) :

    digest = SHA.new(message).digest()

    fulldigest = "\x00\x01" + ("\xff" * 218) + "\x00\x30\x21\x30\x09\x06\x05\x2b\x0e\x03\x02\x1a\x05\x00\x04\x14" + digest

    signature = rsakey.encrypt(fulldigest, 0)[0]

    signature = signature.rjust(256, "\x00") # we aren't guaranteed that RSA.encrypt will return a certain length, so we pad it

    return signature


print rsa_sign_message_1024(main_key_sign, "HAllo")

Bitte um Hilfe.
ps: verlange keinen kompletten Code da ich das RSA selber schreiben will in einer Klasse ;-)

[edit=Luckie]Wir haben keine Python-Tags in der DP. :roll: Mfg, Luckie[/edit]

[Apollonius]

Was erwartest du jetzt eigentlich von uns? Nur auf konkrete Fragen kann man auch konkrete Antworten geben...

[nitschchedu]

Stimmt schon sorry. Aber habe irgendwie das Problem das zuverstehen wie das in Delphi schreiben soll. :cry:

[Assertor]

Hallo nitschchedu,

schau die doch mal das DEC von Hagen an. Da findest Du m.e. auch ein RSA Sign in der Unit TestUnit.pas. Was Du hast ist ja auch nur ein RSA PublicKey mit einem SHA Hash...

Denke mal, daß Du damit eine Nachricht bzw. Text signieren willst - und da solltest Du alles notwendige in der DEC finden.

Gruß winkel79

P.S.: Frage mich nicht, wo Du die DEC findest. Das weiß ich nicht mehr. Suche sonst mal in Google nach DEC (Delphi Encryption Compendium) in Version 5.1

[nitschchedu]

Ok schau mir das mal an, hoffe ich verstehe es.

[nitschchedu]

So toll ist das Beispiel auch nicht was da mit drin ist, das ganze mit RSA ist nicht mal in einer Klasse gekapselt :( .
Aber erstmal ne frage was genau macht das da oben, das Bsp ?
Edit: Was ich weiß ist das
n = Public Modulus
e = Public Exponent
d = Private Exponent

[Assertor]

Ich weiß nicht, ob Du einen freien Quelltext für die RSA Schlüsselerzeugung finden wirst, wegen der möglichen Patente von RSA.

Quelle: Informationen der TU-Berlin zur möglichen patentfreien RSA Nutzung

Ich kenne mich mit der Implementierung von RSA nicht aus, verwende selbst stets AES Verfahren wie z.B. Rijndael oder Serpent mit entsprechender Hash-Erzeugung. Wichtig ist natürlich auch noch der Block-Mode und die Hasherzeugung.

Es kommt darauf an, was Du machen willst.

Willst Du eine Signierung die kompatibel zu einer bestehen Software ist programmieren? Also den Python-Teil eines anderen Projektes in Delphi implementieren?

Es scheint ja so, als sei bei Dir der RSA-Key schon hinterlegt, also vermute ich Du brauchst nur die Signierung.

Da sage ich mal ganz laut: Hagen, Hilfe! ;)

Gruß winkel79

[negaH]

Zitat:

So toll ist das Beispiel auch nicht was da mit drin ist, das ganze mit RSA ist nicht mal in einer Klasse gekapselt

sorry, du erlaubst dir ein Urteil und verstehst noch nichtmal wie RSA funktioniert. Und gerade um solchen Anfängern wie dir näher zu bringen was hinter RSA steht, und wie man es minimalistich und doch mathematisdch richtig umsetzt, ist der Grund warum ich den RSA Demo Source auf das Wesentlichste beschränkt habe.

Gruß Hagen

[Assertor]

Hallo Hagen!

Danke, daß Du Dich hier einschaltest. Das übersteigt dann doch meinen Horizont ;)

@nitschchedu: Ich habe mir gerade mal den RSA Source angesehen und den kann man wirklich großzügig kommentiert nennen. Eine andere, korrekte Implementation zu finden, wird gerade wegen etwaiger Patente nicht so einfach. Warum brauchst Du eine Klasse, muß doch nicht alles in Delphi in Klassen sein. Und zur Not schreibst Du Dir selber eine mit den Funktionen. Das geht ja einfach.

@negaH: Ich möchte Dir einmal für die ganze Arbeit die Du Dir mit der DEC gemacht hast danken. Die hat mir sehr viel Arbeit erspart. Die DEC I nutze ich selbst und in meinem Programm findest Du Dich in der Aboutbox wieder ;)

Gruß winkel79

[nitschchedu]

Hallo Leute, erstmal Danke das ihr mir soweit geholfen habt ;-)
So hatte mir gestern mir das oben nochmal ganz genau angesehen und dann hat es klick gemacht. :roteyes:
Das Beispiel ist ja auch gut Komentiert aber konnte damit nix anfangen :cry: .
Aber nun mal ne frage was ich wieder da nicht weiß.

Also wenn ich das Bsp vom Wiki machen will http://de.wikipedia.org/wiki/RSA-Kryptosystem Das Verschlüsseln wie Stelle ich das in Delphi da ?
Und wie würde das dann mit Text gehen ? Da ja in den Bsp zahlen genohmmen werden.

[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 :roteyes: :balloon: :party:

[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