Eignung von FPGA zum Knacken von RSA

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.

Hier gibts die passende Hardware dazu:
 http://de.wikipedia.org/wiki/Copacobana

Frank

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

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.