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
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.
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.
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/publications/journals/iee2005.pdf
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
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
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.
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.