AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Sprachen und Entwicklungsumgebungen Sonstige Fragen zu Delphi Delphi RSA: Privaten Schlüssel schneller berechnen

RSA: Privaten Schlüssel schneller berechnen

Ein Thema von WIN-MANww · begonnen am 1. Jun 2006 · letzter Beitrag vom 17. Sep 2012
Antwort Antwort
Seite 3 von 5     123 45   
Benutzerbild von negaH
negaH

Registriert seit: 25. Jun 2003
Ort: Thüringen
2.950 Beiträge
 
#21

AW: RSA: Privaten Schlüssel schneller berechnen

  Alt 11. Nov 2011, 02:27
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
  Mit Zitat antworten Zitat
Benutzerbild von negaH
negaH

Registriert seit: 25. Jun 2003
Ort: Thüringen
2.950 Beiträge
 
#22

AW: RSA: Privaten Schlüssel schneller berechnen

  Alt 11. Nov 2011, 02:55
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
  Mit Zitat antworten Zitat
Bjoerk

Registriert seit: 28. Feb 2011
Ort: Mannheim
1.376 Beiträge
 
Delphi 2007 Professional
 
#23

AW: RSA: Privaten Schlüssel schneller berechnen

  Alt 11. Nov 2011, 10:25
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.
  Mit Zitat antworten Zitat
Benutzerbild von BUG
BUG

Registriert seit: 4. Dez 2003
Ort: Cottbus
2.094 Beiträge
 
#24

AW: RSA: Privaten Schlüssel schneller berechnen

  Alt 11. Nov 2011, 10:47
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
Intellekt ist das Verstehen von Wissen. Verstehen ist der wahre Pfad zu Einsicht. Einsicht ist der Schlüssel zu allem.
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
34.967 Beiträge
 
Delphi 10.2 Tokyo Professional
 
#25

AW: RSA: Privaten Schlüssel schneller berechnen

  Alt 11. Nov 2011, 10:52
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.
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
Delphi-Tage 2005-2014

Geändert von himitsu (11. Nov 2011 um 11:01 Uhr)
  Mit Zitat antworten Zitat
Bjoerk

Registriert seit: 28. Feb 2011
Ort: Mannheim
1.376 Beiträge
 
Delphi 2007 Professional
 
#26

AW: RSA: Privaten Schlüssel schneller berechnen

  Alt 11. Nov 2011, 10:54
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.
  Mit Zitat antworten Zitat
Benutzerbild von BUG
BUG

Registriert seit: 4. Dez 2003
Ort: Cottbus
2.094 Beiträge
 
#27

AW: RSA: Privaten Schlüssel schneller berechnen

  Alt 11. Nov 2011, 11:12
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.
Intellekt ist das Verstehen von Wissen. Verstehen ist der wahre Pfad zu Einsicht. Einsicht ist der Schlüssel zu allem.
  Mit Zitat antworten Zitat
gammatester

Registriert seit: 6. Dez 2005
999 Beiträge
 
#28

AW: RSA: Privaten Schlüssel schneller berechnen

  Alt 11. Nov 2011, 11:25
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.
  Mit Zitat antworten Zitat
Bjoerk

Registriert seit: 28. Feb 2011
Ort: Mannheim
1.376 Beiträge
 
Delphi 2007 Professional
 
#29

AW: RSA: Privaten Schlüssel schneller berechnen

  Alt 11. Nov 2011, 11:27
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.
  Mit Zitat antworten Zitat
Micha88
(Gast)

n/a Beiträge
 
#30

AW: RSA: Privaten Schlüssel schneller berechnen

  Alt 11. Nov 2011, 13:16
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;

Geändert von Micha88 (11. Nov 2011 um 13:21 Uhr)
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 14:07 Uhr.
Powered by vBulletin® Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2019 by Daniel R. Wolf