Gibt es ein Konzept, bei dem vorberechnete Tabellen zur Faktorisierung von Primzahlen verwendet werden können? Ist es möglich, dass ein Computer Millionen von Primzahlen generieren, speichern und dann die Faktoren effektiv bestimmen kann?
Es ist unwahrscheinlich. Die beteiligten Primzahlen sind riesig , daher ist der Schlüsselbereich riesig. Wie massiv es ist, hängt von Ihrer Schlüsselgröße ab. Lassen Sie uns jedoch 512-Bit-Primzahlen für ein Beispiel mit niedrigerer Grenze auswählen.
Die Primzählfunktion gibt uns eine Schätzung der Anzahl der Primzahlen unter einer bestimmten Zahl. Es ist schwierig, genau zu berechnen, aber eine genaue Schätzung ist definiert als π (x) = x / ln (x) , wobei ln der natürliche Logarithmus ist. Als solches können wir eine Schätzung der erwarteten Anzahl von Primzahlen unter dem höchsten Wert in einer n -Bit-Zahl berechnen, indem wir π (2 ^ n) berechnen. Wenn wir alle Zahlen ausschließen möchten, die nicht genau n -bit sind, berechnen wir π (2 ^ n) - π (2 ^ (n-1)) . Dies ist technisch nicht erforderlich , gibt uns jedoch eine schöne Untergrenze dafür, wie viele große Primzahlen für diese Schlüsselgröße vorhanden sind.
Für n = 512 Die Anzahl der für eine vollständige Liste erforderlichen Primzahlen beträgt 1,885 × 10 151 sup>. Wenn wir jede Primzahl in einem 512-Bit-Eintrag speichern können, sind das 1,207 × 10 153 sup> Bytes, das sind 132 Größenordnungen mehr als die Speicherkapazität der Festplatte weltweit .
Also nein, nicht wirklich machbar.
Regenbogentabelle: Jede "Farbe" nimmt eine zufällige Eingabe (den Ausgabe-Hash der letzten Iteration oder den ursprünglichen Hash) und gibt eine Ausgabe zurück, die einem beliebigen Muster zugeordnet ist (z. B. alle Buchstaben). Das wird dann gehasht und an die Eingabe zurückgemeldet.
Da wir auch eine Reduktionsfunktion angeben können, die eine beliebige zufällige Zeichenfolge verwendet und diese deterministisch einem beliebigen Ausgabemuster zuordnet, funktioniert dies für Kennwörter. Es gibt jedoch keine definierbare Funktion, um einen Eingabewert zu verwenden und eine Zahl auszugeben, von der bekannt ist, dass sie eine Primzahl ist.
Jede Zahl, von der nicht bekannt ist, dass sie eine Primzahl ist, weil Sie sie bereits getestet haben muss auf Primheit geprüft werden. Sofern eine Zahl nicht als bekannter Primwert gespeichert ist, ist somit kein Zeit- / Speicher-Kompromiss zu erzielen.
Worüber Sie hier sprechen, ist nicht machbar. Crypto berechnet nicht einfach große Primzahlen, sondern Sie müssen das Produkt aus zwei Primzahlen faktorisieren.
Sie müssten Millionen von Primzahlen berechnen und in ein wahnsinnig großes Array einspeisen. Dann müssten Sie dieses Array duplizieren, damit Sie ein zweidimensionales Array haben. Dann müssten Sie jeden einzelnen Eintrag in der ersten Dimension mit jedem einzelnen Eintrag in der zweiten Dimension multiplizieren und die beiden Primzahlen und das Ergebnis in einem zweiten Array speichern. Dieses zweite Array wäre gigantisch, und mit gigantisch meine ich, dass es in keiner Weise gespeichert werden kann, aber es würde Ihre Antworten enthalten.
Sicher nicht einfach, aber ... "Wo ein Wille ist, ist auch ein Weg" WENN Sie alle Primzahlen von Nummer 2 -> 512 Bit in einer Tabelle haben wollten, dann alle möglichen Produkte, dann wäre dies ja unvorstellbar groß. Aber lassen Sie uns zurückgehen und darüber spekulieren, warum jemand es will. Nehmen wir nur an, jemand hat ein Szenario, in dem er ein Paar von Primzahlen mit ähnlicher Bitlänge verwendet, um eine große Zahl zu erstellen, die für andere nur schwer in ein Paar von Primzahlen einfließen kann (klingt vertraut ...?). Nicht alle möglichen Kombinationen von Primzahlen wären erforderlich, da nur ähnliche Bitlängen verwendet würden. Dadurch wird die Tabellengröße drastisch reduziert. Um pedantisch zu sein, wäre dies eine Rainbow Cube -Tabelle, da dies mehrere Dimensionen erfordert. Die Fähigkeit, Fakten dieser großen Primzahlen zu bestimmen, ist sicherlich schwierig, da die speicherresidente Größe der Cubes (wenn sie für eine effiziente Analyse im RAM gespeichert werden) für einen billigen PC zu groß ist. Es gibt jedoch sicherlich einige große Organisationen, die riesige mehrdimensionale Strukturen besitzen dieser Art von Proportionen (wie Google für ihre Suche). Es ist höchst unwahrscheinlich, dass es keine stark ausgestatteten Organisationen gibt, die solche Prime Cubes bereits berechnet und verwendet haben. Die Schwierigkeit, das Paar von Primzahlen zu berücksichtigen, ist die "Überschriften" -Schwierigkeit für z. RSA, aber unterschätzen Sie nicht die zusätzliche Schwierigkeit, die durch den Schritt zum Generieren des privaten Schlüssels entsteht, da er eine modulare Berechnung aufweist.
Wie bereits oben erwähnt, ist auf der ganzen Welt nicht annähernd der erforderliche Speicherplatz vorhanden. Ich würde wetten, dass ein Quantencomputer, auf dem Shors Algorithmus (oder ein ähnlicher Algorithmus) ausgeführt wird, die Notwendigkeit zunichte gemacht hat, bevor wir überhaupt zu dieser Speichermenge gelangen.