www.mikrocontroller.net

Forum: FPGA, VHDL & Co. Eignung von FPGA zum Knacken von RSA


Autor: Marc (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

Wie gut sind FPGAs geeignet, um aus ihnen eine RSA Cracker Platform zu 
bauen?  Im Gegensatz zu AES oder SHA sind die noetigen Rechenschritte ja 
weniger orthogonal.  Deshalb bin ich unsicher ob FPGAs hier so toll 
abschneiden wie bei anderen Anwendungen.

Zum Vergleich der Eignung koennte man die FPGAs zB normalen x86 Desktop 
Chips gegenueberstellen.

Wer kann hierzu einen Kommentar abgeben?

Gruss,
Marc

Autor: Morin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Kannst du sagen mit welchem Algorithmus du knacken willst? Davon hängt 
es maßgeblich ab, wie weit du parallelisieren kannst.

Allgemein gilt: Je paralleler, desto besser sind FPGAs. Wenn du aber 
sagst, dass sich dein Knack-Algo schlecht parallelisieren lässt, dann 
gilt das evtl. nur auf hoher Ebene (vgl. mehrere Intel-CPUs), aber es 
könnte sich in den Einzelschritten trotzdem noch was rausholen lassen.

Autor: Anonymous (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wie >>2 schon sagte, es hängt alles von deinem Algo ab.
Ich schätze mal du willst das ganze per BruteForce machen, stell dich 
also schonmal auf eine längere Wartezeit ein.

Autor: Frank (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hier gibts die passende Hardware dazu:
 http://de.wikipedia.org/wiki/Copacobana

Frank

Autor: Morin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Naja, "passend" ist relativ:

> Q: Can I break RSA or Diffie-Hellman with COPACOBANA?
> A: RSA and DH require quite different attack algorithms than symmetric ciphers. 
COPACOBANA is
> not the optimum machine for factoring large numbers or solving discrete 
logarithms. However,
> COPACOBANA can make sense as a coprocessor for factoring attacks against RSA, as 
stated in
> this paper.

Das Paper dazu: 
http://www.crypto.rub.de/imperia/md/content/texte/...

Autor: Thomas (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

ich geb dir mal einige Anregungen zu dem ganzen. Also das Knacken von 
RSA würd ich über die Faktorisierung das Public Keys machen.

Gut was nimmt man dazu?
Es gibt zwei subexponentielle Verfahren dazu:
1) das Quadratische Sieb
von der Theorie noch einigermaßen verständlich, aber sicher nicht 
einfach. In der deutschen Wikipedia gibt es einen sehr guten Artikel 
dazu.
2) des Zahlkörpersieb (Number Field Sieve NFS)
hat die beste Laufzeit. Allerdings ist der mathematische Apparat 
dahinter gewaltig und ohne Kenntnisse von höherer Mathematik aus 
Zahlentheorie und Gruppentheorie sicher nicht verständlich. Und wenn 
mans nicht versteht kann man es vielleichr noch implementieren aber 
nicht optimieren.

Beide Algorothmen gliedern sich in zwei Teile dem Siebschritt und dem 
Auswahlschritt.
Der Siebschritt ist ohne Porbleme parallelisierbar und braucht zudem 
wenig Resourcen zur Kommunikation. Scheint also ideal für FPGAs 
geeignet.
Der Auswahlschritt ist allerdings praktisch nicht parallelisierbar und 
wird auf Großrechnern durchgeführt.

Aber auch mit diesen Algorithmen ist man weit davon entfernt praktisch 
eingesetzte Schlüssellängen mal eben so zu brechen. Ab 200 stelligen 
Schlüssellängen wirds sehr schwer.

Soweit ich weiß ist das einzig praktisch umgesetzte Projekt in diese 
Richtung CAIRN 3 (NFS) bzw der Vorgänger CAIRN 2 (QS)
Es gibt auch einige Papers zu dem Thema eine Suche nach TWNIKLE, TWIRL 
oder SHARK oder Artikel von den 3 RSA Leuten Rivest, Shamir und Adleman 
ergibt einiges. Soweit ich weiß sind das aber nur Ansätze die noch nicht 
realisiert wurden.

Es gibt auch einige Bücher in die Richtung:
Primer Numbers, A computational perspective von Crandal und Pommerance
"Die Bibel" vom Bruce Schneier weiß aber grad nicht den Namen des Buchs, 
aber ist so der Klassiker bei den Informatikern

Autor: Walther Z. (chilipower)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Marc wrote:
> Hallo,
>
> Wie gut sind FPGAs geeignet, um aus ihnen eine RSA Cracker Platform zu
> bauen?  Im Gegensatz zu AES oder SHA sind die noetigen Rechenschritte ja
> weniger orthogonal.  Deshalb bin ich unsicher ob FPGAs hier so toll
> abschneiden wie bei anderen Anwendungen.
>

 Sie schneiden auch nicht besser ab. Um einen 2048 Bit String zu rechnen
 benötigst du etwa ~1300 Byte. In einem günstigen Spartan3-400 (xc3s400)
 hast du 16 Ram-Blöcke mit jeweils 2kbyte Kapazität. Die
 Word-Multiplikationen können bei etwa 100-150 Mhz durhgeführt werden.
 Jetzt kannste selbst rechnen...

> Zum Vergleich der Eignung koennte man die FPGAs zB normalen x86 Desktop
> Chips gegenueberstellen.

  Ist defintiv besser. Durch verteiltes Rechnen kommst du hier schneller
  zum Ziel.

walther

Autor: Sym (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Die Frage ist doch, ob man Dinge gleichzeitig rechnen kann. Das 
Versuchen verschiedener Schlüssel ist de facto immer möglich.

Man baue sich also einen kleine Kryptorechenknecht und instanziere den 
im FPGA 100-1000x. Dazu eine Steuereinheit, die die Arbeit austeilt. 
Viola.
Man muss eben zwischen Pipeling im Rechenknecht und der schieren Anzahl 
abwägen - das kommt darauf an wieviele bedingte Sprünge die Operationen 
haben.

Es gibt auch andere FPGAs als das Spartan-3 mit mehreren MBytes im FPGA 
und externer DDR Speicheranbindung.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [vhdl]VHDL-Code[/vhdl]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.