Recherche de facteurs premiers en grand nombre à l'aide de processeurs spécialement conçus

Question

D'après ce que j'ai compris, de nombreux algorithmes de chiffrement à clé publique reposent à l'heure actuelle sur de grands nombres premiers pour constituer les clés, et c'est la difficulté de factoriser le produit de deux nombres premiers qui rend le chiffrement difficile à casser. Je pense aussi que l’une des raisons pour lesquelles factoriser de tels nombres est si difficile, c’est que la taille même des nombres utilisés signifie qu’aucun processeur ne peut fonctionner efficacement sur les chiffres, car nos minuscules processeurs 32 et 64 bits ne sont pas compatibles. pour 1024, 2048 ou même 4096 bits. Des bibliothèques mathématiques spécialisées Big Integer doivent être utilisées pour traiter ces nombres, et ces bibliothèques sont intrinsèquement lentes car un processeur ne peut contenir (et traiter) que de petites quantités à la fois (32 ou 64 bits, par exemple).

Alors ...

Pourquoi ne pouvez-vous pas construire une puce personnalisée hautement spécialisée avec des registres à 2 048 bits et des circuits arithmétiques géants, de la même manière que nous avons mis à l'échelle des processeurs de 8 à 16 à 32 à 64 bits? ? Cette puce n'aurait pas besoin de la plupart des circuits sur les processeurs classiques, après tout, elle n'aurait pas besoin de gérer des tâches telles que la mémoire virtuelle, le multithreading ou les E / S. Il n'aurait même pas besoin d'être un processeur polyvalent prenant en charge des instructions stockées. Le strict minimum pour effectuer les calculs arithmétiques nécessaires sur des nombres ginormeux.

Je ne connais pas grand-chose à la conception de circuits intégrés, mais je me souviens de mon apprentissage du fonctionnement des portes logiques, de la création d’un demi-additionneur, d’un additionneur complet, puis de la liaison d’un groupe d’addeurs pour effectuer une arithmétique multibits. Juste à l'échelle. Beaucoup.

Maintenant, je suis à peu près sûr qu'il existe une très bonne raison (ou 17) de ne pas fonctionner avec ce qui précède (car sinon, une des nombreuses personnes plus intelligentes que moi l'aurait déjà fait), mais cela m'intéresse en sachant pourquoi cela ne fonctionnera pas.

(Remarque: cette question peut nécessiter une retouche, car je ne suis même pas encore sûr de savoir si la question a du sens.)

Answer 1

Ce que @cube a dit et le fait qu’une unité arithmétique gigantesque prendrait plus de temps à la stabilisation des signaux logiques et comprenait d’autres complications en matière de conception numérique. La conception de la logique numérique inclut quelque chose que vous prenez pour acquis dans le logiciel, à savoir que les signaux issus de la logique combinatoire prennent un temps court mais non nul pour se propager et se régler. Un multiplicateur 32x32 doit être conçu avec soin. Un multiplicateur 1024x1024 prendrait non seulement une énorme quantité de ressources physiques dans une puce, mais serait aussi plus lent qu'un multiplicateur 32x32 (bien que peut-être plus rapide qu'un multiplicateur 32x32 calculant tous les produits partiels nécessaires pour réaliser un multiplicateur 1024x1024). De plus, le goulot d'étranglement n'est pas le seul multiplicateur: vous avez des voies de mémoire. Vous devrez passer beaucoup de temps à rassembler les 1024 bits d'un circuit de mémoire de 32 bits seulement et à stocker les 2048 bits résultants dans le circuit de mémoire.

Il est presque certainement préférable d’utiliser un ensemble de "conventionnels". Systèmes 32 bits ou 64 bits fonctionnant en parallèle: vous bénéficiez de l’accélération sans la complexité de la conception matérielle.

modifier: si quelqu'un dispose d'un accès ACM (ce qui n'est pas le cas), consultez ce document pour voir ce qu'il dit.

Answer 2

C'est parce que cette accélération ne serait que dans O (n), mais la complexité de la factorisation du nombre est quelque chose comme O (2 ^ n) (en ce qui concerne le nombre de bits). Donc, si vous réalisiez ce processeur et que vous factorisiez les nombres 1000 fois plus rapidement, il ne me resterait plus qu'à augmenter les nombres de 10 bits et nous serions de retour au début.

Answer 3

Comme indiqué ci-dessus, le principal problème est simplement le nombre de possibilités qu’il vous faut passer pour factoriser un nombre. Cela étant dit, des ordinateurs spécialisés existent pour faire ce genre de chose.

Les progrès réels de ce type de cryptographie sont les améliorations apportées aux algorithmes de factorisation des nombres. Actuellement, l'algorithme général le plus rapide connu est le filtre de champ de numérotation général .

Historiquement, il semble que nous puissions factoriser des nombres deux fois plus importants chaque décennie. C’est en partie du matériel plus rapide, mais en partie une meilleure compréhension des mathématiques et de la manière de faire de la factorisation.

Answer 4

Je ne peux pas commenter la faisabilité d'une approche identique à celle que vous avez décrite, mais les gens font des choses similaires en utilisant fréquemment les FPGA:

• Crack DES clés
• Interrompre les conversations GSM
• Carte graphique Open Source

Answer 5

Shamir & amp; Tromer suggère une approche similaire, utilisant une sorte de calcul en grille :

  

Cet article décrit une nouvelle conception pour un matériel personnalisé.   mise en œuvre de l'étape de tamisage, qui   réduit [le coût du tamisage, par rapport à TWINKLE]] à environ 10 millions de dollars. Le nouveau dispositif,   appelé TWIRL, peut être considéré comme une extension du   Dispositif TWINKLE. Cependant, contrairement à TWINKLE,   ne comporte pas de composants optoélectroniques et peut   donc être fabriqué en utilisant la technologie standard VLSI   sur des plaquettes de silicium. L'idée sous-jacente est d'utiliser   une seule copie de l'entrée pour résoudre de nombreux sous-problèmes   en parallèle. Comme le stockage des intrants domine le coût, si le   la surcharge de parallélisation est maintenue faible, alors le résultat   L'accélération est obtenue essentiellement gratuitement. En effet, le   Le principal défi consiste à réaliser efficacement ce parallélisme tout en permettant un stockage compact de l’entrée.   Résoudre ce problème implique une multitude de considérations, allant de   de la théorie des nombres à la technologie VLSI.

Answer 6

Pourquoi ne pas essayer de construire un ordinateur uber-quantum et d’exécuter l’algorithme de Shor dessus?

  

"... Si un ordinateur quantique avec un nombre suffisant de qubits devait être construit, l'algorithme de Shor pourrait être utilisé pour casser des schémas de cryptographie à clé publique tels que le schéma RSA largement utilisé. RSA est basé sur l'hypothèse que la factorisation de grands nombres est infaisable en calcul. Pour autant que l'on sache, cette hypothèse est valable pour les ordinateurs classiques (non quantiques); aucun algorithme classique connu ne peut prendre en compte le temps polynomial. Cependant, l'algorithme de Shor montre que la factorisation est efficace sur un ordinateur quantique, de sorte qu'un ordinateur quantique suffisamment grand peut détruire RSA. ... " -Wikipedia