pt
Moulé à la louche depuis 1999
Les trucs qui m'énervent... et je vais pas prendre de pincettes
Internet, informatique, logiciel libre, économie, politique, vie courante et tout le reste...

Le hasard est une chose difficile pour un ordinateur

Jeudi 25 aout 2011

Vous ne le savez peut-être pas, mais générer de vrais nombres aléatoires sur un ordinateur est une tâche ardue. En fait, c'est tout simplement impossible: L'ordinateur est une machine par nature déterministe, il ne peut donc pas y avoir d'aléa (Oui je sais, ça paraît difficile à croire quand on voit tous les plantages auxquels on est soumis.). Les programmeurs débutants ont presque tous eu affaire à ce problème en programmant "Devinez un nombre": C'était toujours la même série de nombres qui sortait quand on démarrait le programme.

Ceci est très problématique pour la sécurité: La majorité des protocoles cryptographiques (SSL/HTTPS/chiffrement VOIP...) ont besoin de nombres vraiment aléatoires, impossibles à prédire, pour chiffrer les données et sécuriser les communications.

Alors on ruse: On prend la date, la charge du CPU, ce qui passe sur le réseau, les frappes clavier, les déplacements de la souris et on mélange tout ça par un programme qui sort des nombres à peu près aléatoires (On dit "pseudo-aléatoires"). Mais on peut encore trouver des corrélations, des biais... bref des moyens de prédire avec une certains précision la suite de nombres.

Pour parer à cela, certains s'étaient amusés à filmer des lava-lampes avec une webcam pour produire des nombres aléatoires: La circulation des fluides étant très difficile à prévoir (cf. la météo), c'était une assez bonne source de nombres aléatoires. Même si c'est amusant, avouez qu'avoir des lava-lampes sur votre bureau n'est pas très pratique (et je ne parle pas des ordinateurs portables).

Alors comment obtenir de vrais nombres aléatoires ?

En 1999, Intel avait inclus dans ses processeurs un générateur de nombres aléatoires basé sur le bruit généré par le mouvement brownien dû à la chaleur du processeur. Mais c'était un circuit analogique à la base, qui consommait trop de courant. Intel a bossé dur et a sorti un nouveau système entièrement digital, consommant moins de courant, mais influencé également par le "bruit thermique". Il est capable de générer un bit aléatoire (0 ou 1) à chaque cycle d'horloge, autrement dit il génère 3 milliards de bits aléatoires par seconde, ce qui est assez formidable.

Notez que certaines sociétés vendent également des cartes d'extension spécialisés pour PC pour générer des nombres aléatoires. Selon les fabriquants, ces systèmes utilisent:
  • des composants radioactifs équipés de circuits détectant les particules. La désintégration des particules est imprévisible et permet de générer des nombres aléatoires.
  • des circuits électroniques avec feedback (la sortie du circuit va vers son entrée), comme les ponts de diodes, permettant de générer un aléa correcte.
  • des systèmes optiques utilisant les propriétés quantiques des photons.

Aussi curieux que cela puisse paraître, le hasard est difficile à obtenir, mais indispensable pour la sécurité.

L'intérêt pour vous de ces progrès ? Une meilleure sécurité de vos communications.


EDIT: Guillaume me signale également une clé USB, ainsi que cette excellente page qui mesure la qualité de différents générateurs de nombres aléatoires et pseudo-aléatoires. La colonne à regarder est l'entropie. Dans ce test, elle doit tendre vers 8. Je suis content de voir que le bon vieux ISAAC (que j'avais ré-implémenté en Delphi il y a bien longtemps) a une bonne entropie comparé aux autres, et même meilleure que des solutions commerciales à 1000 dollars (avec en prime des débits supérieurs). (PS: Ce n'est pas moi qui ai inventé l'algo ISAAC, hein.).

Voir tous les billets