RSA: Privaten Schlüssel schneller berechnen

[negaH]

Zitat von Bjoerk:

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 von Micha88:

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 von Bjoerk:

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

[himitsu]

Zitat von Bjoerk:

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 von BUG:

Zitat von Bjoerk:

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

Doch, genauso einfach ist es. Siehe #18.

[BUG]

Zitat von Bjoerk:

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 von BUG:

Zitat von Bjoerk:

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;