Suivez-nous sur X
|
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z,
ALL
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z
|
|
A propos d'Obligement
|
|
David Brunet
|
|
|
|
Dossier : Le calcul distribué
(Article écrit par Arnaud Danassié - août 2004)
|
|
Le calcul distribué, c'est quoi donc ?
L'idée n'est pas neuve puisque le concept de "downsizing" date des années 1970 : l'idée de base est de remplacer
un ou plusieurs gros ordinateurs (typiquement des serveurs IBM ou des supercalculateurs) par plusieurs unités plus
petites, et plus économiques, telles que nos ordinateurs personnels qui peuvent fournir la même puissance de calcul
pour beaucoup moins cher !
Depuis quelques années et la généralisation des accès Internet et des réseaux (Ethernet, etc.), il a été de plus en
plus facile de monter des projets de "parcellisation des calculs" : chacun en calcule un petit bloc dans son coin
et l'ensemble des blocs permet au final d'avoir la puissance de calcul nécessaire... que ce soit pour du rendu
d'images de synthèse, des calculs mathématiques ou scientifiques, des simulations pour certains industriels, etc.
Bref, c'est le principe des "petits ruisseaux qui forment les grandes rivières...". D'abord cantonné à quelques
Universités et entreprises, c'est désormais les particuliers qui peuvent offrir un peu de leur temps de calcul pour
des projets qui les intéressent tels que Seti@home (interprétation des signaux reçus de l'espace), Mersenne (recherche
de nombres premiers), des tas de projets médicaux (calculs basés sur l'ADN ou certaines protéines pour faire avancer
la recherche sur le cancer, le sida ou certaines maladies rares), etc.
L'un des projets les mieux organisés est celui de Distributed.net qui permet de fédérer des machines du monde
entier afin de concentrer leur puissance de calcul par le biais d'un petit programme (client Distributed.net, dit
"Dnetc", qui existe sous une foultitude de systèmes) qui, une fois installé sur votre machine, peut rapatrier
les blocs à calculer (2^32 clés = 1 bloc pour le projet RC5 par exemple) à partir d'un serveur. Une fois les calculs
effectuée, il les renvoie afin que le serveur comptabilise vos blocs et mette a jour ses statistiques
(et vous renvoie de nouveaux blocs à calculer).
Cette architecture client-serveur de blocs est utilisé par quasiment tous les projets de calculs distribués
(flexibilité, facilité de maintenance, etc.).
Le RC5-72 (alias RC5-32/12/9 pour les intimes)
RSA Labs a lancé en 1997 plusieurs "RSA Challenge" dotés de plusieurs prix de 10 000 $ afin d'inciter les participants
à "casser" plusieurs encryptages avec des algorithmes (DES, RC5) et des clés de différentes longueurs. A l'heure actuelle,
plusieurs de ces défis ont été remportés via la solution de Distributed.net qui consiste à utiliser la méthode dite
"brute" en testant toutes les clés possibles via des centaines de milliers de machines reliées par le Net et qui se
partagent les pièces de ce puzzle géant !
Pour les personnes intéressées par les détails de l'algorithme RSA (de MM. Ronald Rivest, Adi Shamir et Leonard Adleman
en avril 1977) ou la cryptographie à clé publique, reportez-vous au site des RSA Labs,
consultez leurs différents articles sur le sujet ou faites chauffer votre moteur de recherche préféré... L'algorithme du RC5
en lui-même a été présenté dans un article de M. Rivest en 1994.
Personnellement, je recommande aux personnes intéressées par la cryptographie la lecture du livre "L'histoire des code secrets"
de Simon Singh (éditions Le Livre de Poche, moins de 7 euros) qui aborde de façon relativement simple et détaillée l'histoire
de la cryptographie (de l'antiquité aux ordinateurs quantiques en passant par le décryptage des messages allemands encodés
avec les machines Enigma...) et explicite certains termes aux plus profanes ou rafraîchit la mémoire aux autres.
Le client Dnetc a évolué au fil des années et résolu brillamment plusieurs projets (DES, CSC, RC5-40 à 64 bits). Par exemple,
les projets RC5-56 et RC5-64 ont été découverts via le projet "Bovine" de Distributed.net (qui gère les serveurs alloués
au projet RC5) en respectivement 256 et 1 757 jours. Les réponses encryptées étaient :
RC5-56 : la bonne clé (0x532B744CC20999) a été trouvée le 19 octobre 1997 par Peter Stuer (Belgique).
"The unknown message is : It's time to move to a longer key length"
("Le message inconnu est : il est temps de passer à une plus grande taille de clé.").
RC5-64 : la bonne clé (0x63DE7DC154F4D039) a été trouvée le 14 juillet 2002 par une PIII/450 du côté de Tokyo.
331252 participants avaient alors testé 15 769 938 165 961 326 592 clés en 1757 jours avant de trouver la bonne,
soit 0x63DE7DC154F4D039 ce qui nous donnait en clair le message suivant :
"The unknown message is : some things are better left unread"
("Le message inconnu est : toute chose n'est pas bonne à lire.").
Le RC5-72 offrant 256 fois (2^8) plus de clés à tester que le RC5-64, on estime qu'au rythme actuel (moins de 1% déjà
testés par quelques milliers de participants) il faudrait théoriquement un peu plus de 1000 ans pour casser cette
clé par la méthode brute. Heureusement, plusieurs facteurs jouent en notre faveur : la progression de la puissance
de nos processeurs, la mobilisation de plus de machines (1000 fois plus de participants ramènerait ce délai à
un an) et l'amélioration continue des moteurs utilisés pour tester le plus de clés possibles (lisez l'historique
des différentes versions du client Dnet pour les détails).
Une autre piste serait qu'un petit génie des mathématiques trouve un algorithme rapide pour effectuer des factorisation :
de fait, tous les cryptages basés sur le RSA deviendraient rapidement périmés ! Mais personne n'a encore trouvé "officiellement"
la solution miracle pour décomposer un nombre (certains as de la cryptographie y travaillent depuis plus de 20 ans
et les mathématiciens depuis presque 2000 ans ! Le plus gros employeur de mathématiciens sur la planète, la NSA, pourrait
aussi très bien avoir effectué une percée rendant obsolète les systèmes de cryptage basés sur le RSA sans le crier sur
les toits au nom du "secret d'état") . La disposition des premiers ordinateurs quantiques devrait aussi grandement faire
évoluer les choses dans quelques (dizaines) d'années : une telle machine pourrait tester des milliards de clés en
une fraction de seconde, nul doute que les méthodes de cryptographie devront s'adapter à ces nouveaux outils. ;-)
Casser des clés, pour quoi faire ?
Apporter sa contribution au test "grandeur nature" du RC5 en testant son degré de sécurité, gagner éventuellement 1000 $
et faire profiter votre équipe de la même somme, Dnet de 2000 $ (le reliquat de 6000 $ étant versé a l'association sans
but lucratif pour qui les participants auront le plus voté : DNet, la Free Software Foundation, le projet Gutemberg,
l'Electronic Frontier Foundation, la Software in Public Interest, etc.) dans le cas hypothétique ou votre machine
trouverait la bonne clé ! Le projet Gutemberg a ainsi reçu 8000 $ lorsque Peter Stuer (équipe de Jo Hermans) a trouvé
la clé du RC5-56 le 19 octobre 1997, lui-même et Dnet ayant reçu chacun 1000 $.
Faire avancer la recherche scientifique (projet OGR actuellement en phase 2) en utilisant la puissance CPU inutilisée
de votre machine. A noter que le projet OGR ne permet pas de gagner d'argent, il permet juste de faire avancer les
connaissances scientifiques sur les "règles de Salomon Golomb" (OGR) qui ont des applications dans des domaines
comme l'astronomie, la cristallographie à rayons X ou les télécommunications.
Chaque projet est représenté par un logo : OGR un kangourou, RC5 une vache, etc.
Vous pouvez profiter des moments ou votre machine ne travaille pas ou peu pour laisser le client Dnetc tourner
en tache de fond. Sur mon Pegasos par exemple, il est systématiquement lancé via la WBStarturp et je n'ai constaté
aucun ralentissement même lorsque j'utilise MPlayer pour lire un DVD ou un DivX. Le PC de l'intranet familial a aussi
été réquisitionné au passage.
Vous pouvez concourir à titre individuel ou sous les couleurs d'un équipe (quelle que soit la machine utilisée, si vous
avez une PS2, une station Sun ou un PC vous pouvez aussi les mettre à contribution pour l'équipe "Distributed Amiga",
de l'Université machintruc ou du "club local des joyeux buveurs de bière"). Des clients Dnet existent pour une
foultitude de systèmes hétéroclites.
Des statistiques détaillées, remises à jour quotidiennement, permettent de suivre la progression de tel ou tel projet
(OGR, RC5-72), de connaître les OS des clients utilisés, les pays d'origine, le nombre de blocs calculés par telle
personne ou équipe, les chances de trouver la bonne clé, bref d'établir des classements qui entretiennent une saine
émulation entre les différentes équipes.
Après une période de flottement, les clients Amiga (68k/PowerPC/MorphOS) ont été fortement améliorés par une longue
liste de programmeurs plus ou moins connus (Olivier Roberts l'auteur des Warp Datatypes, Harry Sintonen, etc.) :
distributed.amiga.org/RC5-64/fm_intro-5.html.
Pour l'anecdote, le code PowerPC optimisé AltiVec du client Dnet MorphOS (seulement activé sous MorphOS 1.5 et supérieurs avec un G4)
est l'oeuvre de Didier Levet (auteur du fameux encodeur Pegase, souvenez-vous) qui travaille sur Mac depuis quelques mois.
Ainsi utiliser l'AltiVec du G4 permet de casser environ 2,8 fois plus de clés que le G4 seul. ;-)
Le client AmigaOS 4 vient tout juste d'être porté (version 2.9008-490 de mai 2004) mais n'offre pas encore de gestion
de l'AltiVec (d'après certains forums, il faudrait réviser ExecSG). Nul doute que les prochaines versions vont évoluer
à l'instar du client MorphOS qui a été amélioré au fil des versions.
Personnellement, je teste le client MorphOS depuis sa disponibilité en janvier 2004. Une page sur le site
www.morphos-news.de
fédère un peu plus de 100 utilisateurs du client MorphOS et leur propose un guide d'installation et des statistiques.
Bien évidemment, tous oeuvrent pour l'équipe Amiga (ex. The Amiga RC5 Team) ! En quelques mois, le clan Morphosien
a d'ailleurs dépassé le nombre de blocs RC5-72 calculés par les Amiga Classic (68k et PowerPC 603/604 depuis plusieurs années)
et le système MorphOS est remonté de plusieurs crans dans les OS utilisés.
A l'heure ou j'écris ces lignes, la version actuelle du client est la 2.9008.491 (la préversion 2.9008.493 est toutefois
déjà disponible en version prépublication). Une version supérieure ou égale à 2.9008.490 est requise si vous souhaitez
participer à l'OGR-Phase2 notamment !
L'ancienne équipe "The RC5 Amiga Team" (id 200) a changé depuis quelques semaines d'intitulé et se nomme
"Distributed Amiga" depuis juin dernier. Il vous faudra attendre une journée minimum après avoir soumis vos
premiers blocs pour que vous puissiez rallier une équipe en complétant un formulaire sur le site de statistiques
de Distributed.net.
Le site (très complet mais tout en anglais) se trouve toujours à l'adresse distributed.amiga.org/.
D'ici quelque temps, votre serviteur mettra en place quelques pages en français sur www.migazone.com/rc5/
(fin août d'après mon agenda).
Liens
www.distributed.net/.
www.distributed.net/ogr. Présentation du projet OGR.
www.distributed.net/rc5. Présentation du projet RC5.
stats.distributed.net/. Les statistiques mises à jour quotidiennement.
distributed.amiga.org/. Le site de l'équipe Distributed Amiga (id 200).
|
