Finding Primfaktoren eine große Anzahl speziell gestaltete CPUs

Question

Mein Verständnis ist, dass viele öffentliche Schlüssel Verschlüsselungsalgorithmen in diesen Tagen auf großen Primzahlen hängen die Schlüssel zu machen, und es ist die Schwierigkeit, das Produkt zweier Primzahlen in Factoring, die die Verschlüsselung schwer zu brechen macht. Es ist auch mein Verständnis, dass einer der Gründe dafür, dass eine solche große Zahl Factoring so schwierig ist, ist, dass die schiere Größe der verwendeten Zahlen bedeutet, dass keine CPU effizient auf die Zahlen arbeiten können, da unsere Minuskel 32 und 64-Bit-CPUs nicht gewachsen sind für 1024, 2048 oder sogar 4096-Bit-Zahlen. Specialized Big Integer Mathematik-Bibliotheken müssen verwendet werden, um diese Zahlen zu verarbeiten, und diese Bibliotheken sind von Natur aus langsam, da eine CPU nur (und Verfahren) kleine Stücke halten kann (wie 32 oder 64 Bit) auf einmal.

So ...

Warum kann man nicht einen hoch spezialisierten Custom-Chip mit 2048-Bit-Registern, und riesige Rechenschaltungen, viel in der gleichen Art und Weise aufzubauen, die wir von 8 bis 16 bis 32 64-Bit-CPUs skaliert, nur baut eine viel größer ? Dieser Chip würden die meisten der Schaltung auf herkömmliche CPUs nicht brauchen, schließlich wäre es nicht Dinge wie den virtuellen Speicher umgehen müssen, Multithreading oder I / O. Es wäre nicht einmal benötigt ein Allzweckprozessor unterstützt gespeicherte Befehle sein. Nur das Nötigste, die notwendigen arithmetischen Berechnungen auf ginormous Zahlen auszuführen.

Ich weiß nicht, eine ganze Menge über IC-Design, aber ich erinnere mich zu lernen, wie Logikgatter arbeiten, wie einen Halbaddierer, Volladdierer zu bauen, dann eine Reihe von Addierern miteinander verbinden Multi-Bit-Arithmetik zu tun. Nur vergrößern. Eine Menge.

Nun, ich bin ziemlich sicher, dass es einen sehr guten Grund (oder 17), dass die oben nicht funktionieren wird (da sonst eine der vielen Menschen klüger als ich es bereits getan haben, bin würde), aber ich bin interessiert zu wissen, warum es wird nicht funktionieren.

(Hinweis: Diese Frage einige Nacharbeiten müssen, wie ich bin nicht einmal sicher noch, wenn die Frage macht Sinn)

Answer 1

Was sagte @cube, und die Tatsache, dass ein riesiges Rechenwerk mehr Zeit für die Logiksignale nehmen würde zu stabilisieren und auch andere Komplikationen in digitalem Entwurf. Digitales Logik-Design enthält etwas, das Sie in der Software selbstverständlich ist, nämlich die kombinatorische Logik nimmt die Signale durch eine kleine, aber von Null verschiedene Zeit zu propagieren und zu begleichen. Ein 32x32-Multiplizierer muss sorgfältig ausgeführt werden. Ein 1024x1024 Multiplikator würde nicht nur eine riesige Menge an physischen Ressourcen in einem Chip, aber es wäre auch langsamer sein als ein 32x32-Multiplizierer (wenn auch vielleicht schneller als ein 32x32-Multiplizierer all Teilprodukte Berechnung benötigt, um eine 1024x1024 mehrfach durchzuführen). Außerdem ist es nicht nur der Multiplikator, der Engpass ist: Sie haben Speicherpfade bekommen. Sie müssten eine Menge Zeit zu sammeln, die 1024 Bits von einer Speicherschaltung verbringen, die breit nur 32 Bits ist, und Speichern der resultierenden 2048 Bits zurück in die Speicherschaltung.

Mit ziemlicher Sicherheit ist es besser, eine Reihe von „konventionellen“ 32-Bit- oder 64-Bit-Systemen parallel arbeiten zu bekommen. Sie Speedup bekommen w / o die Hardware-Design-Komplexität

Bearbeiten , wenn jemand ACM Zugriff hat (ich nicht), nehmen Sie vielleicht einen Blick auf dieses Papier , um zu sehen, was es sagt.

Answer 2

Sein, weil diese Speedup wäre nur in O (n), aber die Komplexität die Anzahl von Factoring ist so etwas wie O (2 ^ n) (in Bezug auf die Anzahl der Bits). Also, wenn Sie diese überprocessor gemacht und die Zahlen 1000-mal schneller faktorisiert, würde ich nur die Zahlen 10 Bits größer machen und wir würden wieder auf dem Start zurück.

Answer 3

Wie oben angegeben, ist das primäre Problem einfach, wie viele Möglichkeiten Sie gehen müssen, um durch eine Reihe Faktor. Davon abgesehen, spezialisierte Computer existieren diese Art der Sache zu tun.

Der wirkliche Fortschritt für diese Art von Kryptographie ist es, Verbesserungen in der Anzahl Factoring-Algorithmen. Derzeit ist der schnellste bekannte allgemeinen Algorithmus der allgemeine Zahlkörpersieb .

Historisch gesehen, scheinen wir in der Lage zu sein, Zahlen Faktor doppelt so groß ist jedes Jahrzehnt. Ein Teil davon ist schnelle Hardware, und einen Teil davon ist einfach ein besseres Verständnis der Mathematik und wie Factoring durchzuführen.

Answer 4

Ich kann nicht kommentieren dem Machbarkeit einen Ansatz genau wie die, die Sie beschrieben, aber die Leute tun ähnlich Dinge sehr häufig mit FPGAs:

• Riss DES-Schlüssel
• Sprung GSM Gespräche
• Open-Source-Grafikkarte

Answer 5

Shamir & Tromer deutet darauf hin, einen ähnlichen Ansatz, eine Art von Grid-Computing mit:

  

Dieser Artikel beschreibt ein neues Design für eine kundenspezifische Hardware   Umsetzung des Siebschritt, die   reduziert [die Kosten für die Siebung, bezogen auf Twinkle,] auf etwa 10 Millionen $. Das neue Gerät,   genannt TWIRL kann als Erweiterung der gesehen werden   TWINKLE Gerät. Doch anders als es TWINKLE   hat keine optoelektronischen Komponenten und kann   somit Standard VLSI-Technologie hergestellt werden   auf Silizium-Wafern. Die zugrunde liegende Idee ist, zu verwenden,   eine einzelne Kopie des Eingangs viele Teilprobleme zu lösen   parallel zu. Da Eingangsspeicher dominiert Kosten, wenn die   Parallelisierung Overhead niedrig gehalten wird, dann die resultierende   Beschleunigung wird im wesentlichen kostenlos erhalten. Tatsächlich ist die   größte Herausforderung liegt diese Parallelität effizient und ermöglicht eine kompakte Lagerung des Eingangs zu erreichen.   Addressing dies beinhaltet unzählige Überlegungen, angefangen   aus der Zahlentheorie zu VLSI-Technologie.

Answer 6

Warum versuchen Sie nicht den Aufbau eines uber-Quantencomputer und führen Sie Shor-Algorithmus auf sie?

  

“... Wenn ein Quantencomputer mit einer ausreichenden Anzahl von Qubits zu errichte ist, Shor-Algorithmus verwendet werden könnte, Public-Key-Kryptographie Systeme wie das weit verbreiteten RSA-Schema zu brechen. RSA Bisher liegt die Annahme zugrunde, dass eine große Zahl Factoring rechnerisch nicht machbar ist, wie bekannt ist, diese Annahme gilt für klassische (nicht-Quanten) Computer;. kein klassischer Algorithmus ist bekannt, dass in Polynomialzeit Faktor jedoch Shor-Algorithmus zeigt, dass. Factoring auf einem Quantencomputer effizient ist, so dass ein ausreichend großer Quantencomputer kann RSA brechen. ...“ -Wikipedia