RSA: Privaten Schlüssel schneller berechnen

[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

[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.

[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.

[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.