RSA: Warum gibt es keine Rainbowtables?! (ger)
Man findet Rainbowtables für MD5, für DES und diverse andere, aber keine für RSA - warum eigentlich nicht? Die Antwort auf die Frage ist einfach, aber der Spannung halber, werde ich sie erst am Ende beantworten 
RSA verwendet zwei hohe Primzahlen, welche miteinander multipliziert werden. Aus der Multiplikation geht der öffentliche Schlüßel hervor. Das Hauptproblem um RSA zu knacken liegt also darin, dass man diese multiplizierte Zahl faktorisieren müsste und das geht selbst mit dem Sieb des Atkins nur sehr ineffizient.
Da das Faktorisieren also ausscheidet, könnte man ja Rainbowtables anlegen. Sinnvollerweise würde so eine Tabelle jede Multiplikationsmöglichkeit und das Ergebnis bereit halten. Das Suchen in so einer Tabelle geht sehr schnell.
Kommen wir zum Problem… RSA mit einem öffentlichen Schlüßel von 1024 Bit hat ca. 300 Dezimalstellen, also eine Zahl die ungefähr so aus sieht: 1,2545252 * 10 ^ 300
Da rein theoretisch auch 2 eine Primzahl ist, die eingesetzt werden könnte und somit die anderePrimzahl extrem hoch sein würde, schauen wir uns an, wie viele Primzahlen bis 10 ^ 300 existieren. Mit der einfachen Formel f(x) = x / ln x und 10 ^ 300 als x existieren also 1.4476 * 10 ^ 297 Primzahlen - jede Menge Jetzt müssen immer 2 Primzahlen multipliziert werden, und zwar, wenn möglich jede mal mit jeder. Das ist dann eine Kombination mit Zurücklegen. Dadurch wird solch eine Tabelle unermeßlich groß und die Kosten für die benötigten Festplatten dürften in Millionhöhe schnellen - ganz zu schweigen vom technischen Aufwand.
Man kann diese Tabelle zwar verkürzen, indem man z.b. die ersten Zahlen des Produktes speichert, dann die Länge und die letzten Zahlen und natürlich die beiden benutzten Primzahlen bzw. deren Indezes davon… die Tabellen haben aber trotzdem genau so viele Einträge, jetzt eben nur mit weniger Speicherbelegung pro Eintrag.
Weiterhin besteht das Problem der effektiven Primzahlerzeugung, hier bietet sich das Sieb des Eratosthenes oder das optimierte Sieb des Atkin. Man könnte die Erzeugung theoretisch auch auf FPGAs oder auf Grafikprozessoren verlagern, z.B. mit CUDA von Nvidia auf G80 GPUs, die bei mathematischen Funktionen doch einen enormen Geschwindigkeitsvorteil bieten.
Auch könnte man versuchen die Primzahlerzeugung weiter zu optimieren, Atkin und Bernstein haben mit dem Sieb des Atkin quadratische Zahlen verwendet - ähnlich eines Kreises, eventuell könnte man das Ganze im dreidimensionalen Raum versuchen. In der heutigen Zeit wird ja auch viel aus der Natur abgeschaut, eventuell treten Primzahlen ja auch hier auf…
Vorerst habe ich die Idee der Rainbowtables für RSA aber aufgrund des Umfangs auf Eis gelegt.