Factorisation de clefs Nspire

→ **MyCalcs** profile · by **critor** » 03 Jul 2010, 10:52

Omnimaga s'est mis à retravailler sur le programme distribué de factorisation de clefs publiques RSA.

http://www.omnimaga.org/index.php?topic=3639.0

Le but si j'ai bien compris, et de le rendre plus rapide en utilisant du C au lieu de Perl, et de modifier l'algorithme afin de lui permettre gérer des nombres de plus de 512bits (1024bits pour la Nspire).

Bon sinon comme déjà dit, c'est 10 ans trop tôt...

Prenons une métaphore pour comprendre; représentons le travail de factorisation par l'océan.
Le travail que que pourraient faire une 100aine d'ordinateurs quadri-core actuels en quelques mois ne représenterait qu'une goutte d'eau dans cet océan.
Les laisser tourner des années n'y changera rien: ils ne termineront jamais de notre vivant.

Il faut attendre 2020 avec, si tout continue comme prévu, des ordinateurs 32 fois plus puissants que ce que l'on a actuellement, pour envisager une factorisation d'une clef Nspire 1024 bits en quelques mois.

→ **MyCalcs** profile · by **fugitifduck** » 03 Jul 2010, 19:07

hum, même en mettant tout le paquet? (carte graphique haut de gamme, les render farm qu'on avait utilisé cet été..., des

Show/Hide spoilerAfficher/Masquer le spoiler

botnets

)

→ **MyCalcs** profile · by **Lionel Debroux** » 04 Jul 2010, 08:04

Le travail que que pourraient faire une 100aine d'ordinateurs quadri-core actuels en quelques mois ne représenterait qu'une goutte d'eau dans cet océan.

L'analogie est bonne, mais encore extrêmement en-dessous de la réalité

:
C'est 10^-55, à quelques ordres de grandeur près, d'une particule élémentaire de l'univers.
A cà´té de ça, gagner à n'importe quel jeu de hasard courant est une absolue trivialité

:

Sur un coeur des machines auxquelles j'ai accès (Core 2 Duo T7200 et T7600, 2 GHz et 2.33 GHz), le programme fait environ 10^6 itérations par seconde, après mes améliorations.
Supposons que chaque coeur fasse tourner le programme 10^6 secondes, c'est à dire environ 12 jours, et qu'il y ait 10^3 coeurs qui tournent le programme: 10^15 entiers impairs seront donc essayés.

Sachant qu'il y a ~10^155 nombres impairs de 512 bits (et parmi ceux-là , environ 1 sur 200 est probablement premier, mais les tests de pseudo-primalité gaspillent un temps fou), l'espace inexploré par un travail de deux semaines sur 1000 coeurs reste ~10^155.
L'utilisation de GPU (si tant est que TF pour des nombres de cette taille-là soit réalisable efficacement sur GPU ?) et de davantage de machines changeraient peut-être le nombre absolu d'essais de deux ou trois ordres de grandeur - mais en proportion de l'immensité de l'espace à explorer, cela ne changerait presque rien.

Cette recherche est donc absolument vaine, même si nous pouvons avoir une chance immense. Ma motivation principale pour optimiser ce programme était d'apprendre un peu l'API GMP.

→ **MyCalcs** profile · by **Naruto`kun** » 11 Jul 2010, 10:59

bah écoute concrètement, mon Core2Quad 8200 overclocké a 3.01GHz fais 101 milliards de hash par secondes (les 4 cores réunis)... mon ATI 4870 non oc en fais 23727 milliards de hash a la seconde... c'est quand même pas négligeable?
alors si ma petite machine de guerre, fais ça, que font les nouveaux serveurs de nvidia ayant 4 gpu a la place d'un cpu?

edit: nvidia anonce ça: http://www.nvidia.fr/object/product-tesla-S2050-fr.html
ça peux allez un peu plus vite =p

→ **MyCalcs** profile · by **Lionel Debroux** » 11 Jul 2010, 11:42

Hashing et trial division par des entiers de cette taille sont des opérations très différentes...

Même si mon estimation (pourtant déjà a priori haute !) était pessimiste de dix ordres de grandeur (!!), il resterait vrai que 10^155 - 10^30 ~ 10^155, c'est à dire qu'on n'aurait exploré qu'un sous-ensemble ridiculement petit (en relatif) de l'ensemble immense des entiers possibles.

→ **MyCalcs** profile · by **Naruto`kun** » 11 Jul 2010, 13:36

ou simplement on demande a Ti sa clé pour les cas+?
bon ok, je sort --[]

→ **MyCalcs** profile · by **Zoetrem** » 14 Jul 2010, 21:09

Je suis quasiment certain que si on rassemblait toute la capacité possible de tout les ordinateurs de cette planète (En supposant qu'ils seraient tous connectés et capables d'interagir, chose impossible), on arriverait pas à factoriser la clé je pense.

→ **MyCalcs** profile · by **Lionel Debroux** » 15 Jul 2010, 05:38

Par TF, en effet, puisque le nombre d'essais nécessaires en moyenne est très grand devant le nombre estimé d'atomes dans l'univers.
Ca serait jouable par GNFS (si on dispose de 10000 à 100000 TB d'espace disque - extrapolé de l'espace disque nécessaire pour RSA-512, moins de 10 GB, et de RSA-768, +/- 10 TB, et du fait que RSA-1024 soit estimé à 1000 fois plus difficile que RSA-768), mais on n'a déjà pas accès publiquement aux implémentations spéciales qui ont permis la factorisation de RSA-768...

→ **MyCalcs** profile · by **Naruto`kun** » 10 Sep 2010, 21:12

domage que j'ai raté la news de la ti-84+ qui hack la ps3, sinon on aurrais fais des homebreux qui se lancent depuis la caltoch pour factoriser la clé en réseau... en mettant 30-40 en réseau... ça devrais prendre un ou deux ans xD

après autre question... qui paye le courant? xD

(dommage mon n900 hackais aussi la ps3...)

et par contre... heureusement que sony réagit plus vite que TI pour les corrections de failles xD