RSA: Privaten Schlüssel schneller berechnen

[WIN-MANww]

Hi zusammen

Ich bin seit letzter Zeit daran, eine RSA Verschlüsselung zu schreiben, nur habe ich Probleme mit der Berechnung des privaten Schlüssels, d.h. es funktioniert zwar, ist aber ziemlich langsam. Mein Code sieht bis jetzt so aus:

Delphi-Quellcode:

function PrivateKeyCalc(e, phi : String) : String;
var
 i, j: String;
begin
 i := '0';
 repeat
  i := GiantAddition(i, '1');
  result := i;
  j := GiantMod(GiantMultiplication(e, i), phi);
  Showmessage(j);
 until
  (GiantSizeTest(j, '1') = 0) and (GiantSizeTest(e, result) <> 0);
end;

Stört euch nicht an den Giant Dingern, das ist eine eigene Unit von mir um grosse Zahlen zu berechnen, nur ist die eben langsam, darum will ich bei der Berechnung des Schlüssels selber nicht so viele Operationen durchführen müssen. Ich versuche hier ja mit i den Schlüssel zu finden, jedoch ist das ziemlich langsam, weil es ja alle Werte von 1 bis zum gefundenen Schlüssel durchprobieren muss. Ich würde also gerne von euch wissen, ob man nicht einen genäueren Startwert für i berechnen könnte, damit man nur noch so 5 Durchläufe braucht. Danke schon im vorraus für die Antworten

[jfheins]

Ich an deiner Stelle würde mal schauen, ob du nicht noch was bei den GiantXXX-Funktionen rausholen kannst ;)

[negaH]

Sorry aber deine Frage ist sehr unklar.

Du möchtest den Privaten RSA Schlüssel aus dem öffentlichen Exponenten E und Phi == (P-1) * (Q-1) berechnen. Das geht nur über die Faktorization des öffentlichen Modulus N = P * Q. Dh. das was du machen möchtest ist es einen öffentlichen RSA Schlüssel zu knacken, richtig ?

Falls die beiden Primzahlen P,Q entsprechend groß und sauber gewählt wurden, wirst du selbst mit der besten mathm. Library und den besten mathematischen Verfahren nicht in der Lage sein mit vertretbaren zeitlichem/technischen Aufwand ein solches public Modul N in P,Q zu faktorisieren. Logisch, da ja exakt dieses Verhalten die Sicherheit ausmacht.


Solltest du aber mit deiner Frage auf die korrekte Erzeugung eines RSA Schlüsselpaares abzielen, dann gibt es tatsächlich weit bessere Verfahren.

Du hast

1.) die beiden Primzahlen P und Q erzeugt.
2.) den öffentlichen Esxponenten E berechnet oder dich für einen festen Exponenten E entschieden (z.b 3, 17, $10001)
3.) Phi = (P -1) * (Q -1) berechnet
4.) public Modul N = P * Q berechnet

und suchst nun den privaten Entschlüsselungs-Exponenten D.

Du rechnest jetzt

Delphi-Quellcode:

  U := LCM(P -1, Q -1); 
// LCM = Leat Common Multiple == letztes gemeinsames Vielfaches == Phi(N) falls N=P*Q Primzahlen sind.

  repeat
    repeat
      E := Random() mod (2^(Log2(Log2(N)) * 4)); 
      E := E or 1;
// erzeuge Zufälligen öffentlichen Exponenten E. Sollte 4*Ln2(Ln2(N)) Bits groß sein und ungerade.
// E sollte auch Teilerfremd zu P,Q sein. Wir überprüfen dies mit dem GCD = greatest common divisor == ggT() ==
// größter gemeinsammer Teiler. Da P,Q Primzahlen sind muß der GCD mit E immer 1 sein, ergo E kann und darf KEIN
// Teiler der Primzahlen P,Q sein. Sollte GCD <> 1 sein so kann P,Q keine Primzahl sein, ergo der RSA Schlüssel 
// wäre absolut unsicher weil man nicht mit Primzahlen arbeitet.
    until (GCD(E, P) == 1) and (GCD(E, Q) == 1); 
// erzeuge nun den privaten Entschlüsselungs Exponenten D
// D = E^-1 mod LCM(P-1, Q-1) == E^-1 mod Phi(N)
// E^-1 mod X ist eine Division in einem modularem Ring. Man lösst diese Berechnung mit Hilfe 
// des Muliplikativen Inversen. Das modulare Multiplikative Inverse lässt sich mit dem erweiterten GCD() berechnen. 
// D muß größer als E sein und teilerfremd zu N. Da die einzigsten Teiler von N die Primzahlen P,Q sein sollten
// kann D nur dann ein Teiler von N sein wenn D==P oder D==Q ist oder eben P,Q keine Primzahlen sind. 
// GCD(D, N) == 1 überprüfen wird dies.
  until NInvMod(D, E, U) and (NSize(D) >= NSize(E)) and NGCD1(D, N);

So fertig ist dein RSA Schlüsselpaar.

Die FGInt == Fast Gigantic Integers (M. Waldenburg glaube ich mich zu erinnern hat diese Lib gecodet) sind leider alles andere als Fast und Gigantic. Such hier im Forum nach meinem DEC und den vielen Beispielsourcen für RSA. Ich habe nämlich im besonderen RSA hier schon mehrmals als Source gepostet.
Denoch solltest du in den FGInt Sourcen alle angesprochenen Funktionen finden, sprich GCD(), LCM(), Modulare Inversion -> InvMod() oder ExtGCD(). Deren algorithmische Implementierung in FGInt ist allerdings alles andere als auf dem modernsten Stand der Mathematik, denoch aber korrekt.

Gruß Hagen

[WIN-MANww]

Entschuldigung für die schlechte Fragestellung, also nochmal:

Mein Ziel ist es NICHT RSA zu knacken, ich will es lediglich anwenden. Mein Problem ist nun die Berechnung des privaten Exponenten d. Das funktioniert zwar nach dem Code, den ich am Anfang gepostet habe, ist aber ziemlich langsam...

Nochmal den Code von vorher als als Text:

Delphi-Quellcode:

function PrivateKeyCalc(e, phi : String) : String; 
var 
i, j: String; 
begin 
i := '0'; 
repeat 
  i um 1 erhöhen. 
  Resultat auf i setzen. 
  Ein Mod zwischen e*i und phi durchführen, das Ergebnis in j schreiben.  
until 
 Durchführen bis j 1 ist und e alles andere als i  
end;

Hoffe, das man es jetzt verstanden hat, denn das Problem ist ja: 1 = e*d mod phi(n)
Da es aber mehrere Lösungen dafür geben würde nehme ich j und multipliziere den ständig ändernden wert i mit e, bis j endlich 1 ist, dann habe ich d = i.

[negaH]

1 == e*d mod Phi(N), stellen wirs mal um ergibt dann

d = e^-1 mod Phi(N)

du musst also das Multiplikative Inverse von E berechen, also E^-1 mod X und hast dann D direkt berechnet.
Man macht dies intern fast immer mit dem Erweiterten ggT() oder in englisch dem extended GCD().

Der eggT() berechnet

D = U * A + V * B

wir benötigen

D == 1
A == E
B == Phi(N)
U == E^-1

ergibt


1 = E^-1 * E + V * Phi(N)

wobei wir V am Ende nicht benötigen.

Wir berechnen also ExtGCD(var E^-1, var V, const E, const Phi(N)) == 1, und sind daran interessiert das das Resultat == 1 sein muß (ansonsten gibts kein modulares multiplikatives Inverse), der Rückgabewert V nicht interersiert und wird unser E^-1 geliefert bekommen, da dies unser Decryption Exponent D ist.

Es kann nun sein das der Wert E^-1 vom ExtGCD() negativ ist. Halb so wild denn in diesem Falle addieren wir auf diese Variable einfach Phi(N) dazu.

E^-1 * E == 1 und somit ist V * Phi(N) == 0 mod Phi(N) da wir ja die Gleichung
1 = E^-1 * E + V * Phi(N) vorliegen haben.
1 = 1 + 0.

Dh. das multiplikative Inverse von E ist E^-1 und definiert als 1 == E * E^-1.

Gruß Hagen

[WIN-MANww]

Ah danke Hagen, nur werde ich aus deiner Antwort nicht so recht schlau... öhm woher bekomme ich jetzt D? Aus E^-1? Aber E^-1 ist ja meist keine natürliche Zahl.. Könntest du vielleicht einen Pseudocode schreiben, mit dem man direkt d erhalten würde wenn man jetzt e und phi(n) kennen würde? Also ich kenne ja noch mehr, auch p und q, aber ich denke die braucht man ja nicht... würde mich sehr freuen.

[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

[negaH]

Zitat:

aus E^-1? Aber E^-1 ist ja meist keine natürliche Zahl.

Falsch bzw. richtig ;)

Also nochmal

1 = D * E mod Phi(N) -> D = E^-1 mod Phi(N).

Wir arbeiten hier immer in Modularen Ringen und somit sind alle Resultate ganze Zahlen. Da das Modul Phi(N) und N positive Zahlen sind könnte man das sogar einschränken auf die natürlichen Zahlen, sprich ganze positive Zahlen.

Das was dich nun stört ist die separate Betrachtung von E^-1. Als einfache Operation betrachtet ist es richtig was du sagst, eine reelle Zahl. Aber wir arbeiten ja modular mod Phi(N) und somit muß D = E^-1 mod Phi(N) dann ebenfalls eine postive ganze Zahl zwischen 0 und Phi(N) -1.

Die Inversion einer Zahl in einem Modularen Ring ist dabei aber nur unter bestimmten Umständen definiert. Wenn das Modul N oder Phi(N) teilerfremd zu E ist so können wir definitiv das modulare multiplikative Inverse berechnen.

Mit Hilfe des erweiteren ggT() können wir nun direkt aus E,Phi(N) dessen inverses E^-1 berechnen und dies alles im Zahlenbereich der ganzen Zahlen.

Gruß Hagen

[WIN-MANww]

Das hört sich alles sehr plausibel an, nur wenn ich das eggt von zum beispiel e= 229 und phi(n) = 288 berechne bekomme ich als eggt 1, was ja auch der grösste teiler ist, nur ist da keine spur von d, was nach meiner berechnung 205 sein sollte....

[negaH]

Das stimmt ja auch:

1 = U * A + V * B, umgestellt zu unseren Parametern

1 = (E^-1) * E + V * Phi(N)

1 = -83 * 229 + 66 * 288

e^-1 = d = -83

da wir aber im modularem Ring von Phi(N) == 288 arbeiten und das negative Vorzeichen von d = -83 nicht erwünscht ist rechnen wir noch

d = e^-1 mod Phi(N) was bei negativem d identisch ist zu
d = e^-1 + Phi(N) also

d = -83 mod 288 == -83 + 288 = 205

also

d = 205.

So, nun zeige mal den Funktionrumpf deiner erwetereten ggT() Funktion. Diese sollte 2 Eingabeparamater A,B haben und 3 Ausgabeparameter R,U,V.

R = eggt(out U,V, in A,B)

R = U * A + V * B umgestellt auf unsere Variablennamen wäre dies dann

1 = D * E + V * Phi(N) wobei

D = E^-1 ist also

1 = E^-1 * E + V * Phi(N)

und da E^-1 das multiplikative Inverse von E ist muß demzufolge

E^-1 * E = 1 sein. Somit ergibt sich für den Rest der Formel logischerweise

1 = 1 + V * Phi(N) und der formale Teil V * Phi(N) muß selber 0 ergeben damit der Rest der Formel stimmt, also

1 = 1 + 0

Verifizieren wir das

1 = D * E + V * Phi(N) -> 1 == -83 * 229 + 66 * 288 mod Phi(N)

66 * 288 == 19008 mod Phi(N) == 0 mod 288 und

-83 * 229 == -19007 mod Phi(N) == 205 mod 288

Das heist

1.) wir arbeiten in modularen Ringen und das bedeutet das wir JEDE Operation in einer solchen Formel (Kongruenzklasse) immer modulo Phi(N) rechnen müssen. Um den Unterschied zwischen normalen Formel und modularen Formeln hervorzuheben benutzt man das doppelte Gleichheitszeichen.
Beispiel:

1 == d * e mod Phi(N) bedeutet ausgeschrieben

1 mod Phi(N) = ((d mod Phi(N)) * (e mod Phi(N))) mod Phi(N)

und

d == e^-1 mod Phi(N) wäre

d mod Phi(N) = (e mod Phi(N))^-1 mod Phi(N).

2.) der erweiterte ggT() muß also als Rückgabewert immer 1 ergeben, was bedeutet das eine Inversion rechnerisch durchführbar ist. Sollte also 1 != D * E + v * Phi(N) rauskommen, der ggT() also NICHT 1 als Resultat liefern dann ist die Berechnung des modularen multiplikativen Inversen in dem gewählten Ring zum Modul Phi(N) nicht eindeutig. Das bedeutet E ist nicht teilerfremd zu Phi(N). Im Falle von RSA und der bekannten Faktorization von N in die zwei Primzahlen P,Q bedeutet dies das P oder/und Q keine richtigen Primzahlen sind. Liefert der erweiteret ggT() also nicht 1 so wissen wir das unsere Primzahlen P,Q falsch sind.


Fazit:

Du hast

1 == D * E mod Phi(N) in Worten also, D mal E ist kongruent zu 1 mod Phi(N). Das bedeutet D muß identisch zum modularen multiplikativen Inversen von E sein, als D == E^-1 mod Phi(N). Ergo:

1 == D * E mod Phi(N) ist identisch zu
1 == E^-1 * E mod Phi(N) und umgestellt ergibt das

D = E^-1 mod Phi(N).

Der private Decryption Exponent D ist einfach nur das Multiplkative Inverse im modularen Ring Z(N) vom public Encryption Exponenten E.

Da wir zur Berechnung von D die Faktorization von N in P,Q kennen müssen um Phi(N) berechen zu können entsteht eine "Trapdoor" Funktion (Hintertür Funktion). Denn ein Angreifer der aus N den privaten Decryption Exponenten berechnen will muß erstmal Phi(N) berechnen und dazu muß er N in P,Q faktorisieren.

Kennt man P,Q so kennt man Phi(N) und kann über den eggT() sehr einfach D berechnen aus E. Das geht sehr schnell.
Kennt man nur N so muß man N faktorisieren in P,Q was bei goßen P,Q (>= 512 Bit) eben praktisch unmöglich ist.

Eine Trapdoor Funktion ist also eine Funktion die mathematisch beweisbar mindestens 2 Wege bietet um ein Resulat zu berechnen. Der eine Weg, bei dem alle wichtigen Parameter bekannt sind, ist ein sehr leicht mathematisch zu berechnender Weg.
Der andere Weg bei dem bestimmte Parameter NICHT bekannt sind (hier P,Q und D und Phi(P*Q)) ist zwar auch mathemqtisch berechenbar, die dafür nötigen Algorithmen sind aber so komplex das sie mit berechenbar großen Parametern (P,Q) parktisch undurchführbar sind. (bzw. mann kan es versuchen wird aber mit heutiger Technik viele tausende Jahre benötigen).

Das Geheimnis vom RSA ist also diese Trapdoor Funktion und die gezielte Verteilung des RSA Schlüssels in ZWEI Teile: dem privaten Schlüsselteil und dem öffentlichen Schlüsselteil.

Wenn wir also beim RSA vom

öffentlichen Schlüssel E,N und vom
privaten Schlüssel D,N reden

so stimmt das eigentlich garnicht. Denn in beiden Fällen handelt es sich nur um EINEN Schlüssel aber in unterschiedlichen Formen !!

Denn in Wahrheit ist der

öffentliche Schlüssel E, P*Q
private Schlüssel E^-1, P*Q

der RSA Schüssel ist also E und P*Q denn wir können davon ZWEI unterschiedliche Formen ableiten

öffentliche Schlüsselform E und N
private Schlüsselform E^-1 und P*Q

Auf Grund das wir im öffenbtlichen Schlüssel nur E und N publizieren muß ein Angreifer sehr umständlich N faktorisieren in P * Q um dann Phi(P*Q) berechnen zu können und finaly aus E den pivaten Exponneten D = E^-1

Also poste mal den Funktionsrumpf deiner eggT() Funktion, damit ich beurteilen kann ob du die richtige Funktion benutzt.

Gruß Hagen

[Micha88]

Leider geht aus diesem Thread nicht hervor, wie man den private key mit Hilfe des public keys findet.

Geht das überhaupt?

[Namenloser]

Zitat:

Zitat von Micha88 (Beitrag 1135590)

Leider geht aus diesem Thread nicht hervor, wie man den private key mit Hilfe des public keys findet.

Geht das überhaupt?

Ich bin wirklich kein Krypto-Experte, aber eins weiß ich mit Sicherheit: Man kann den Private Key nicht aus dem Public Key errechnen, denn das ist ja gerade der Sinn der Sache.

[Micha88]

Möglich ist es, "soll" es aber nicht. So habe ich es gelesen.

Mhh.. Demnach kann man RSA-verschlüsselte Texte ja niemals einsehen, wenn man den private key nicht weiß.

Das Problem sind die riesen (Prim)zahlen.

[Namenloser]

Zitat:

Zitat von Micha88 (Beitrag 1135594)

Möglich ist es, "soll" es aber nicht.

Also zumindest mit unseren heutigen Computern geht es wohl nicht in absehbarer Zeit.

[Bjoerk]

Zitat:

Zitat von NamenLozer (Beitrag 1135593)

Zitat:

Zitat von Micha88 (Beitrag 1135590)

Leider geht aus diesem Thread nicht hervor, wie man den private key mit Hilfe des public keys findet.

Geht das überhaupt?

Ich bin wirklich kein Krypto-Experte, aber eins weiß ich mit Sicherheit: Man kann den Private Key nicht aus dem Public Key errechnen, denn das ist ja gerade der Sinn der Sache.

Das ist leider nicht richtig.

RSA-Encryption:
2 Prime P, Q
P <> Q
N = P*Q
M = (P-1)*(Q-1)
Find an E and a D so that is:
S * M + 1 = E * D, E <> D, E relatively prime to M, D 1..M, E 1..M, S > 0
Encrypt: J = I^E mod N, I 0..N
Decrypt: I = J^D mod N

N, E = Public
M, P, Q, D = Private

Der Private Schlüssel D lässt sich sogar direkt aus N und E berechnen.
Guckst du hier:

Delphi-Quellcode:

procedure TRSAEncryption.FindD(const N, E: int64); // get the private Key D
var
  P, Q, M: int64;
begin
  FE:= 0;
  FD:= 0;
  FN:= 0;
  FM:= 0;
  FP:= 0;
  FQ:= 0;
  P:= 2;
  while P < N do
  begin
    if IsPrimeNumber(P) then
    begin
      Q:= N div P;
      if IsPrimeNumber(Q) then
      begin
        if P*Q = N then
        begin
          M:= (P-1)*(Q-1);
          if GreatestCommonDivisor(M, E) = 1 then
          begin
            FD:= InversMod(E, M);
            FE:= E;
            FN:= N;
            FM:= M;
            FP:= P;
            FQ:= Q;
            Break;
          end;
        end;
      end;
    end;
    P:= P+1;
  end;
end;

Fazit: Der einzige Schutz, den man bei der RSA Verschlüsselung hat, ist, das bei großen Zahlen, empfohlen sind 155 Stellen (int512), diese Procedure Jahre dauert. Für Zahlen im int64 Bereich ist die RSA Verschlüsselung nicht geeignet.

[Bummi]

Dann sind wir alle jetzt beruhigter...

[negaH]

Zitat:

Zitat von Bjoerk (Beitrag 1135617)

Das ist leider nicht richtig.

Leider ist das was du als Beispiel bringst ebenfalls nicht richtig. Du berechnest nicht direkt aus dem öffentlichen Schlüssel den privaten sondern du testest alle Kandidaten durch bis es stimmt. Das ist ein Unterschied.

Man kann N faktorisieren und das wird letzendlich, nach meinem Wissenstand, immer ein Such-Algorithmus sein der letzendlich per Trial&Error funktioniert.

Ich kenne kein praktisches Verfahren um eine zusammengesetzte Zahl, wie beim RSA notwendig, direkt in ihre Primzahlfaktoren zu zerlegen.

Gruß Hagen

[Bjoerk]

Doch, da N das Produkt von 2 Primzahlen ist, gibt es genau eine Möglichkeit. Und D = InversMod(E, M)

[Micha88]

Ich bekomme es fast kompiliert.

Nur findet er InversMod() nicht.
Gibt es dazu einen Code? Möchte nur ungern eine komplette Komponente nur für eine Funktion installieren.

[Bjoerk]

Delphi-Quellcode:

function GreatestCommonDivisorAdvanced
  (A, B: int64; var U, V: int64): int64;
var
  U0, V0: int64;
begin
  if B = 0 then
  begin
    Result:= A;
    U:= 1;
    V:= 0;
  end
  else
  begin
    Result:= GreatestCommonDivisorAdvanced(B, A mod B, U0, V0);
    U:= V0;
    V:= U0-(A div B)*V0;
  end;
end;

function InversMod(A, B: int64): int64;
var
  V: int64;
begin
  GreatestCommonDivisorAdvanced(A, B, Result, V);
  if Result < 0 then Result:= Result+B;
end;

[negaH]

Zitat:

Zitat von Bjoerk (Beitrag 1135631)

Doch, da N das Produkt von 2 Primzahlen ist, gibt es genau eine Möglichkeit. Und D = InversMod(E, M)

ich denke du verstehst mich falsch.

Du berechnest nicht P,Q direkt aus N sondern du gehst alle Primzahlen per Brute Force durch, also Trial & Error. Wenn es eine mathm. Formel gäbe mit der man aus N direkt dessen Primzahlfaktorization berechnen könnte dann wärste jetzt ein gemachter Mann.

Der RSA Schlüssel, bzw. dessen Sicherheit besteht nur aus P*Q=N wobei P,Q zur privaten Schlüsselform und N zur öffentlichen Schlüsselform zählen. Mathematisch gibt es keinen Unterschied von N zu P*Q da ja N = P*Q ist. Deshalb sollte man von Formen des gleichen RSA Schlüssels reden, da erst die gelieferte Form, also N oder eben P,Q entscheidet wie schnell man die einzelnen RSA Operationen durchführen kann.

D ergibt sich direkt aus E dem öffentlichen Exponenten wenn man P,Q kennt. Du kannst D, privater Exponent, nur dann berechnen wenn du vorher N in P,Q faktorisiert hast. Und es gibt keinen Faktorizierungsalgo. der aus N direkt P,Q berechnen kann. Alle Algos. müssen per Trial&Error arbeiten. Somit kann man einen Algorithmus programmieren der zwar iterativ sich der korrekten Lösung durch Versuche immer weiter annähert, aber es gibt keinen Algorithmus der aus einer beliebigen zusammengesetzen Zahl direkt deren Faktorisation berechnen kann. Und dein Beispiel faktoriziert noch nichtmal N sondern geht alle Primzahlen solange durch bis er durch Produktbildung ein gleiches Modul N erzeugt hat.

Und exakt das es so ist bedeutet kryptographische berechenbare Sicherheit beim RSA Verfahren.

Gut lange Rede wenig Inhalt, letztendlich geile ich mich nur an der falschen Wortwahl auf. Man kann sich nun streiten ob "berechnen" das ist was dein Algo. da macht, ich sehe es bischen strikter in der Wortwahl.

Gruß Hagen

[negaH]

Zitat:

Zitat von Micha88 (Beitrag 1135590)

Leider geht aus diesem Thread nicht hervor, wie man den private key mit Hilfe des public keys findet.

Geht das überhaupt?

Ja kann man. Die Sicherheit von RSA, bzw. jeder Kryptographie kannst du dir so vorstellen:

Ich baue einen riesigen Sandhaufen und setze mich drauf. Vorher berechne ich das ich 100 Jahre leben möchte und das mich keiner in dieser Zeit vom Haufen stoßen kann. Ergo berechne ich wie lange ein Angreifer benötigen würde um meinen Sandhaufen zu erklimmen. Dann schütte ich den Sandhaufen so hoch das man 200 Jahre benötigen würde um ihn zu erklettern.

Von vornherein ist klar das man den Sandhaufen erklimmen kann, es gibt also ein schon bekanntes Verfahren. Aber ich stelle nur sicher das man mit allen bekannten Verfahren während meiner 100 Lebensjahre nicht auf meinen Sandhaufen hinauf kommt.

Das einzige was einen Strich durch meine Rechnung machen könnte ist neues Wissen. Zb. die Erfindung des Helikopters der nun in Minuten Leute auf meinen Sandhaufen rauffliegen kann. Und exakt darum geht es wenn die Kryptographen fordern das alles an einem Kryptosystem öffentlich sein muß (also die Formeln etc.pp nicht die Passwörter ;). Denn unser zukünftiges Wissen ist es das unsere heutige Kryptographie brechen wird.

Als potentielle Faktorisierungsalgos. gelten das Quadratische Sieb QS, Elliptische Kurven Methode ECM, Field Number Sieve GNFS -> SNFS usw.

Allerdings gilt: heute sichere RSA Schlüssel können mit keinem der bekannten Verfahren in erträglicher Zeit mit erträglichen Aufwand geknackt werden.

Wenn dann sehe ich eher die Chance das die neusten Entwicklungen bei den Quantencomputern das ändern könnten. Aber nur dann wenn die Verfügbarkeit dieser Technologie eingeschränkt ist. Dh. der Angreifer hat diese Technologie und das Opfer muß weiterhin mit unserer heutigen Rechentechnik arbeiten. Sollten beide Seiten die gleiche Rechenpower haben dann egalisiert sich das wieder da nun der Komplexitätsfaktor der Trapdoorfunktion wieder wirkt. Also mit Quantencomputern auf beiden Seiten wird RSA wieder "unknackbar" der einzige Unterschied zu heuten RSA dürften die viel größeren Zahlengrößen, mit denen man dann rechnet, sein.

Gruß Hagen

[Bjoerk]

Gut, Programmtechnisch habe ich das so gemacht. Man könnte aber auch eine Tabelle erstellen und hieraus P und Q ablesen. Eine direkte Berechnung dafür gibt es nicht, da hast du völlig Recht.

[BUG]

Zitat:

Zitat von Bjoerk (Beitrag 1135667)

Man könnte aber auch eine Tabelle erstellen und hieraus P und Q ablesen.

Vergiss es. Es gibt genug große Primzahlen innerhalb bei den Schlüsselgrößen.
Wenn es so einfach wäre, würde man RSA nicht einsetzten.

Natürlich könnte man theoretisch jeden Algorithmus, dessen Eingabelänge durch eine Konstante beschränkt ist, durch eine Lookup-Tabelle ersetzten und in O(1) (<- Länge der Tabelle ist konstant) einen Lookup ausführen.
Rate mal warum man das meist nicht macht :stupid:

[himitsu]

Zitat:

Zitat von Bjoerk (Beitrag 1135667)

Eine direkte Berechnung dafür gibt es nicht, da hast du völlig Recht.

Quasi eine Rainbowtable?

Sowas gibt's z.B. (teilweise) schon für MD5 und Co. wo man schon viele fertige "Passwörter" vorberechnet hat und man dann nur noch den MD5 Wert als Suchmuster, in dieser Tabelle nutzen muß.

Das Problem dabei sind aber die Datenmengen und die Zeit.
- man braucht etwas Zeit, um diese Tabellen zu erstellen
- und man braucht genügend Platz, um dieses zu speichern

Und bei den Unmassen an Primzahlen/Schlüsselgrößen kommt da so Einiges zusammen, wenn man "alle" möglichen Kombinationen berechnen und speichern will.

[Bjoerk]

Zitat:

Zitat von BUG (Beitrag 1135672)

Zitat:

Zitat von Bjoerk (Beitrag 1135667)

Man könnte aber auch eine Tabelle erstellen und hieraus P und Q ablesen.

Vergiss es. Es gibt genug große Primzahlen innerhalb bei den Schlüsselgrößen.
Wenn es so einfach wäre, würde man RSA nicht einsetzten.

Natürlich könnte man theoretisch jeden Algorithmus, dessen Eingabelänge durch eine Konstante beschränkt ist, durch eine Lookup-Tabelle ersetzten und in O(1) (<- Länge der Tabelle ist konstant) einen Lookup ausführen.
Rate mal warum man das meist nicht macht :stupid:

Doch, genauso einfach ist es. Siehe #18.

[BUG]

Zitat:

Zitat von Bjoerk (Beitrag 1135676)

Doch, genauso einfach ist es. Siehe #18.

Und was soll das Helfen?
Das Faktorisieren ist das Problem. Und das löst du mit einer Schleife:

Delphi-Quellcode:

while P < N do
  // ...
  P:= P+1;

Deshalb braucht dein Algorithmus exponentiell viel Zeit (abhängig von der Bitzahl von N).

Analog bei einer Tabelle: Deine Schlüsselgröße ist binär kodiert, also gibt es 2^Schlüsselgröße viele Werte. Dafür brauchst du dann ne Menge Zeilen.

[gammatester]

Faktorisieren ist nur im wesentlich äquivalent zur Lösung des RSA-Problems, wenn die Parameter keine besonderen Strukturen haben und das ganze Verfahren sauber implementiert ist.

Es ist zB leicht aus diesem öffentlichen 1024-Bit-Schlüssel

Code:

n = 11035463747532637445226478138892854615229059147212549
    68896762858332342093837672821832724506937118395830515
    42309222330083659850689603243353126318276768089312034
    96804364642955524979983163555511613010051847637101545
    96069745366463800922497122292314425797037111134964839
    84161919815499556858239868898947449128902601

e = 26326725747121311076993928624541179659819098893929617
    86499375829797582796176216915533598300276887773916687
    83001258781296352479713656037757260244893098410205283
    74818927737874803364784332966924327053140787641069444
    36542882371682465118650762071857029055046908790050276
    263181232199669270812448604459328490393

innerhalb von Millisekunden p und q auszurechnen. Warum? Weil RSA nur dann sicher ist, wenn die Schlüssellänge ausreichend ist und Schlüsselerzeugung + Verfahrensimplementation korrekt sind. Warum ist das hier nicht der Fall? Antwort: hier ist der private Exponent

Code:

d = 25490678353771676657590727529736038476443354503415832
    014317168968016770420021

viel zu klein, so daß die sogenannte Wiener-Attacke angewendet werden kann. Es gibt zahlreiche weitere Fehlermöglichkeiten für RSA-Implementationen.

[Bjoerk]

Zitat:

Zitat von BUG (Beitrag 1135681)

Zitat:

Zitat von Bjoerk (Beitrag 1135676)

Doch, genauso einfach ist es. Siehe #18.

Und was soll das Helfen?
Das Faktorisieren ist das Problem. Und das löst du mit einer Schleife:

Delphi-Quellcode:

while P < N do
  // ...
  P:= P+1;

Deshalb braucht dein Algorithmus exponentiell viel Zeit (abhängig von der Bitzahl von N).

Analog bei einer Tabelle: Deine Schlüsselgröße ist binär kodiert, also gibt es 2^Schlüsselgröße viele Werte. Dafür brauchst du dann ne Menge Zeilen.

Nö, probier #15 (mit #20) selbst aus. Für Zahlen im int64 Bereich sollte das in vergleichsweiser kurzer Rechenzeit erledigt sein. Und dein Kommunikationsparter muß über die entsprechende CharTable auch verfügen, sonst kann er dir keine Nachricht schicken.

Bei Zahlen dürfte die RSA allerdings relativ sicher sein, weil man einer Zahlenfolge 7139 nicht ansieht, ob sie Sinn ergibt oder nicht, im Gegensatz zu einem Wort. Wichtig ist also, nicht einfach den Wert der ASCII Tabelle zu verwenden, sondern einen eigenen.

[Micha88]

Vielen Dank für diese Beschreibung, Hagen. Sehr gut verständlich.


Also funktionieren tut das alles nicht so recht.

Delphi-Quellcode:

uses IsPrimeHRUnit {DEC 5.2}
// ...

var FE, FD, FN, FM, FP, FQ: Int64;

function GreatestCommonDivisor(a, b: Int64): Int64;
VAR
 r: INTEGER;
begin
 if b = 0 then
  begin
   result := 0;
   exit;
  end;

 while b > 0 do
  begin
   r := a mod b;
   a := b;
   b := r;
  end;

 result := a;
end;

function InversMod(a, b: Int64): Int64;
var
 V: Int64;
begin
 V := GreatestCommonDivisor(a, b);
 if result < 0 then
  result := result + b;
end;

procedure FindD(const N, E: Int64); // get the private Key D
var
 P, Q, M: Int64;
begin
 FE := 0;
 FD := 0;
 FN := 0;
 FM := 0;
 FP := 0;
 FQ := 0;
 P := 2;
 while P < N do
  begin
   if IsPrime(P) then
    begin
     Q := N div P;
     if IsPrime(Q) then
      begin
       if P * Q = N then
        begin
         M := (P - 1) * (Q - 1);
         if GreatestCommonDivisor(M, E) = 1 then
          begin
           FD := InversMod(E, M);
           FE := E;
           FN := N;
           FM := M;
           FP := P;
           FQ := Q;
           Break;
          end;
        end;
      end;
    end;
   P := P + 1;
  end;
end;

procedure TForm1.Button1Click(Sender: TObject);
begin
 FindD(StrToInt(Edit1.Text), StrToInt(Edit2.Text));

 // Alles ist '0'
 Label3.Caption := IntToStr(FE);
 Label4.Caption := IntToStr(FN);
 Label5.Caption := IntToStr(FM);
 Label6.Caption := IntToStr(FQ);
end;

[gammatester]

Zitat:

Zitat von Micha88 (Beitrag 1135692)

Also funktionieren tut das alles nicht so recht.

Wie soll's es auch, wenn Du planlos einen normalen GGT statt eines erweiterten GGT zur Berechnung des modularen Inversen einsetzt:stupid:. Versuchs mal mit Bjoerks GreatestCommonDivisorAdvanced.

[Bjoerk]

Zitat:

Zitat von Micha88 (Beitrag 1135692)

Vielen Dank für diese Beschreibung, Hagen. Sehr gut verständlich.


Also funktionieren tut das alles nicht so recht.

Delphi-Quellcode:

uses IsPrimeHRUnit {DEC 5.2}
// ...

var FE, FD, FN, FM, FP, FQ: Int64;

function GreatestCommonDivisor(a, b: Int64): Int64;
VAR
 r: INTEGER;
begin
 if b = 0 then
  begin
   result := 0;
   exit;
  end;

 while b > 0 do
  begin
   r := a mod b;
   a := b;
   b := r;
  end;

 result := a;
end;

function InversMod(a, b: Int64): Int64;
var
 V: Int64;
begin
 V := GreatestCommonDivisor(a, b);
 if result < 0 then
  result := result + b;
end;

procedure FindD(const N, E: Int64); // get the private Key D
var
 P, Q, M: Int64;
begin
 FE := 0;
 FD := 0;
 FN := 0;
 FM := 0;
 FP := 0;
 FQ := 0;
 P := 2;
 while P < N do
  begin
   if IsPrime(P) then
    begin
     Q := N div P;
     if IsPrime(Q) then
      begin
       if P * Q = N then
        begin
         M := (P - 1) * (Q - 1);
         if GreatestCommonDivisor(M, E) = 1 then
          begin
           FD := InversMod(E, M);
           FE := E;
           FN := N;
           FM := M;
           FP := P;
           FQ := Q;
           Break;
          end;
        end;
      end;
    end;
   P := P + 1;
  end;
end;

procedure TForm1.Button1Click(Sender: TObject);
begin
 FindD(StrToInt(Edit1.Text), StrToInt(Edit2.Text));

 // Alles ist '0'
 Label3.Caption := IntToStr(FE);
 Label4.Caption := IntToStr(FN);
 Label5.Caption := IntToStr(FM);
 Label6.Caption := IntToStr(FQ);
end;

Also, Copy and Paste Fähigkeiten hab' ich jetzt einfach mal vorausgesetzt...:roll:

Edit: Die while Schleife braucht übrigens nur bis <= N div 2 zu laufen

[Micha88]

Was bringt mir denn aber FE, FN, FM und FQ. Wie berechnet man daraus den Private Key?

[gammatester]

Zitat:

Zitat von Micha88 (Beitrag 1135706)

Was bringt mir denn aber FE, FN, FM und FQ. Wie berechnet man daraus den Private Key?

Das steht doch da:

Delphi-Quellcode:

  FD := InversMod(E, M);
  FN := N;

Das Paar (N,D) bzw. (FN,FD) ist der private Schlüssel! Vielleicht solltest Du Dich mal mit den Grundlagen vertraut machen.

[Bjoerk]

Was auch ganz interessant ist, daß P und Q nicht unbedingt Primzahlen sein müssen. Dann muß man aber vorher auf Plausibilität prüfen, d.h. für alle zu verschlüsselnden I muß die Bedingung I = Decrypt(Encrypt(I)) erfüllt sein.

P: 190
Q: 129
N : 24510
M: 24192
E: 14417
D: 11825

Für I im Bereich 1..255 getestet.

[negaH]

Zitat:

Zitat von Bjoerk (Beitrag 1135729)

Was auch ganz interessant ist, daß P und Q nicht unbedingt Primzahlen sein müssen. Dann muß man aber vorher auf Plausibilität prüfen, d.h. für alle zu verschlüsselnden I muß die Bedingung I = Decrypt(Encrypt(I)) erfüllt sein.

Diese Annahme ist korrekt und falsch zugleich. Mathem. kann man RSA auch mit zusammengesetzten Zahlen machen das wäre dann ein RSA dessen N aus mehr als 2 Primzahlen besteht. Das ist aber kryptographisch nur dann vergleichbar sicher zu einem RSA Modul aus 2 Primzahlen wenn alle Primzahlen so groß sind wie die 2 Primzahlen. Dh. ein 1024 Bit RSA Schlüssel besteht aus zwei Primnzahlen a 512 Bit. Nehmen wir mal an wir lösen diese Forderung bischen auf und nehmen eine 1020 Bit Primzahl und eine 4 Bit Primzahl. Jeder kann sich ausrechnen wie lange nun die Suche bei der Faktorisierung dieses N nach dieser 4 Bit Primzahl dauert. Kryptographsich ist das also ziemlicher Blödsinn es so zu machen. Falls aber N zb. 2048 Bit groß wäre und das Produkt aus 4 Primzahlen a 512 Bit ist dann wäre dieser RSA fast so sicher wie ein 2048 Bit Schlüssel der aus 2x 512Bit Primzahlen bestünde.

Gammatester hat s schon korrekt angesprochen: asymmertische Kryptoverfahren sind sehr anfällig für Designfehler. Weit mehr anfällig als symmetrische Verfahren wie AES, SHA1 usw. Denn selbst bei der Wahl der zB. beiden 512 Bit Primzahlen eines 1024 RSA Schlüssels muß man höllisch aufpassen. Die Primzahlen dürfen von keiner speziellen Form sein, bzw. wenn diese Formk von spezieller Natur ist dann muß es eine sein die nachweislich sicher ist, zB. sogenannte Safe primes = Sophie Germain Primzahlen wären solche Kandidaten. Deren Nutzen im Vergleich zu guten industriellen Primzahlen beim RSA aber sehr gering ist. Dem gegenüber steht der Aufwand solche Primzahlen zu erzeugen.

Aber gerade diese Schlüsselerzeugung ist es die man so manipulieren kann das man einen verdeckten Kanal in das public Modul N einbauen kann. Dabei gilt das dieser verdeckte Kanal selber geschützt wird durch das Faktorisierungsproblem. Dh. der "Angreifer" der einem solchen Schlüssel unterjubeln kann hat die Chance sehr effeizient aus einem solchen public Modul N die Faktorisation zu berechnen. Ich selber habe dazu den praktischen Beweis angetreten. Fazit: traue niemals einem privatem RSA Schlüssel den du selber nicht berechnet hast und bei dem die Art&Weise der Erzeugung der benutzten Primzahlen nicht bekannt und nicht verifizierbar ist. Das betrifft jede Technologie wie SmartCards oder komplexe Cryptobibliotheken ohne Sourcen wie das MS CryptoAPI oder die erzeugten Schlüssel eines TrustCenters für dessen Kunden.

Gruß hagen

[Bjoerk]

Du kennst dich da mit Sicherheit besser aus als ich, ein Vorteil dabei ist m. E. jedoch nicht von der Hand zu weisen: Es gibt dann mehrere Möglichkeiten, aus denen sich N zusammensetzen kann, was den Hackeraufwand erheblich verlängern dürfte.

[negaH]

Zitat:

Zitat von Bjoerk (Beitrag 1135736)

Du kennst dich da mit Sicherheit besser aus als ich, ein Vorteil dabei ist m. E. jedoch nicht von der Hand zu weisen: Es gibt dann mehrere Möglichkeiten, aus denen sich N zusammensetzen kann, was den Hackeraufwand erheblich verlängern dürfte.

Ne eben nicht, das Gegenteil wäre der Fall. Je zusammengestzter N ist desto kleiner werden seine Primzahlpotenzen der Faktorisation und das würde bedeuten das umgekehrt exponentiell die Geschwindigkeit des Knackens wächst. Es erleichtert also das Knakcen von RSA da es gerade an dem Punkt wodurch RSA erst sicher wird eine Schwäche einbaut.

Es gibt/gab Versuche mit RSA in dieser Richtung weil man damals wollte das die RSA Operationen schneller ablaufen. Das ist auch der Fall da man mit solchen RSA Schlüssel und dem CRT (Chinese Remainder Theorem) besonders die Entschlüsselung beschleunigen kann. Bei RSA mit 2 Primzahlen im N kann man mit dem CRT (Garner Algorithmus) die Entschlüsselung um Faktor 4 beschleunigen. Das steigert sich je mehr Primzahlen man im Modul N benutzt.

Und es gibt tatsächlich Algorithmen die die sich ergebenden Schwächen bei der Benutzung vom mehr als 2 Primzahlen so ausgleichen können das dieser RSA Schlüssel nicht ganz so unsicher ist als wenn man wahlfrei mit mehr als 2 Primzahlen arbeitet. Denoch sind solche Schlüssel eben weniger stark als diejenigen die mit 2 etwa gleichgroßen, zufällig gewählten Primzahlen arbeiten. Da die Rechentechnik aber fortgeschiritten ist, der Schlüsselerzeugungprozess offline und nicht zeitkritisch ist, man heute ohne Probleme im Millisekundenbereich 512 Bit Primzahlen erzeugen kann, sind diese speziellen RSA Varianten überflüssig geworden.

Gruß hagen

[Bjoerk]

Okay. Aber mal was anderes. Wenn man mit mehr als 2 Primzahlen arbeiten möchte, ist das Procedere dann analog, also N=P*Q*R M:=(P-1)*(Q-1)*(R-1) usw. ?

[gammatester]

Der Standard RFC 3447 - PKCS #1: RSA Encryption Version 2.1 (Abschnitt 3.2) nimmt hier die Carmichaelfunktion M = lambda(N), wobei in Deinem Fall, wenn P,Q,R paarweise verschiedene Primzahlen sind, lambda(N) = LCM(P-1,Q-1,R-1) das kleinste gemeinsame Vielfache ist.