Interlude: un générateur de bruit / de nombres aléatoires

Entre mes deux projets, qui avancent à leur rythme (je ferai des mises à jour individuelles un peu plus tard, c’est plus complexe) je me détends parfois en faisant de petits montages simples.

Après des discussions sur la liste de diffusion de l’Electrolab, m’est venue l’idée de m’intéresser aux générateurs de nombres aléatoires. En effet, les nombres aléatoires ont un rôle très important pour la sécurité. On en utilise très souvent: dans SSL, dans les signatures numériques, dans PGP…

Il en existe en effet de deux types:

  • les générateurs déterministes ou pseudo aléatoires
  • les générateurs non déterministes ou réellement aléatoires

Générateurs pseudo-aléatoires (PRNG)

Dans un PRNG, on obtient des nombres aléatoires en appliquant (la plupart du temps) une fonction crypto (hash, chiffrement, registre à décalage type CRC, etc) ou une relation de récursivité (nouvelle_valeur = [constante*ancienne_valeur + constante] mod nombre_premier). En fait, ces générateurs produisent une séquence de bits très mélangés, qui dépend d’une graine initiale (seed) qu’il faut initialiser avec une valeur différente à chaque utilisation (par exemple , l’heure système de l’ordinateur en millisecondes: chaque exécution du programme utilisera une graine différente, ce qui produira une séquence aléatoire différente).

Chaque seed génère une séquence différente, mais si on réutilise la même seed, on se retrouve avec la même séquence pseudo aléatoire, c’est pour ça qu’on dit le générateur déterministe.

Les nombres produits ont quand même des caractéristiques des nombres réellement aléatoires, par exemple le nombre de bits à zéro doit être égal au nombre de bits à 1, l’autocorrélation du signal (similarité avec lui même) doit rester très faible, et d’autres propriétés statistiques doivent être vérifiées. Mais tout ceci dépend d’une graine

Générateurs réellement aléatoires (TRNG)

Dans un TRNG, on utilise un phénomène physique pour générer les valeurs aléatoires. Cela peut être:

  • la tension aux bornes d’une résistance de forte valeur: il s’agit de bruit thermique
  • le bruit d’un convertisseur analogique-numérique dans un microcontrôleur (méthode utilisée par le FST-01 et NeuG)
  • le bruit d’avalanche et d’effet tunnel généré par une jonction PN (diode, transistor) en régime d’avalanche
  • le bruit atmosphérique, obtenu par exemple en réglant une radio entre deux stations (c’est la méthode utilisée par random.org, que je n’aime pas car elle est attaquable en émettant des trucs sur la fréquence mesurée, qui doit donc rester secrète)
  • etc.

Ces générateurs sont en général analogiques. Une porte à trigger de Schmidt suffit à numériser le signal, on obtient alors un signal logique qui bascule à des intervalles aléatoires. On peut alors mesurer le signal avec le port GPIO d’un micro-contrôleur et s’en servir logiciellement. Par contre, il est impossible de prédire la sortie du générateur, qui est donc non-déterministe.

Il faut ensuite:

  • Annuler les biais (moyennes, etc) avec un algorithme de nettoyage qui peut être très simple: on acquiert 2 bits, et émet le premier bit d’entre eux s’ils sont différents, sinon jette les 2 bits. On en déduit que le débit d’un tel générateur n’est pas constant.
  • S’assurer des propriétés statistiques du générateur (moyenne=0.5, tous les bits basculent, pas de génération de séquence de bits consécutifs identiques, corrélation, etc)
  • Emettre les données sous un format utilisable

On se rend compte de plusieurs choses:

  • Il faut être sûr d’avoir du “bon” bruit pour générer des nombres suffisamment aléatoires
  • Le débit de bits aléatoires n’est pas extensible “a volonté”!

Un premier montage

Pour mettre ces théories en pratique, j’ai commencé par la base : un générateur de bruit. On en trouve tout plein de schémas, les plus simples se basant sur la jonction B-E d’un transistor NPN, comme celui ci:

Générateur de bruit
Générateur de bruit. Source: David Eather, Silicon Chip Online, 2005 ( http://archive.siliconchip.com.au/cms/A_103659/article.html )

 

 

Oui, oui, le collecteur reste en l’air! Ce n’est pas une erreur! C’est la jonction B-E qui nous intéresse. On pourrait utiliser une diode à la place, mais en général les diodes supportent beaucoup mieux une tension inverse, donc il faudrait une alim de plusieurs dizaines de volts.

En voici la réalisation:

Générateur de bruit numéro 1
Générateur de bruit numéro 1

C’est vraiment un des montages les plus simples.

Pour que le transistor génère du bruit, il faut l’alimenter avec une tension assez élevée (ici 12 volts, le VBE max du 2N2222A utilisé est donné pour 6 volts, il faut donc aller au delà pour entrer en régime d’avalanche). Le bruit généré est d’environ 1Vpp. Après avoir ajouté un condensateur de liaison à la sortie du montage, j’ai pu attaquer directement la carte son de mon PC. A l’oreille, on reconnait bien le “psssssshhh” caractéristique du “bruit blanc”. Voici le spectre mesuré par Audacity:

Bruit généré - Spectre linéaire
Bruit généré – Spectre linéaire

On observe bien que toutes les fréquences sont présentes. Dans les aigus, on voit l’influence des filtres de la carte son (ou du montage? il va falloir le déterminer!) Dans les graves, on voit l’effet des capas de liaison qui empêchent les basses fréquences de passer. Dans l’ensemble, le bruit a l’air bien “blanc”. Maintenant, on voit quand même des petits “pics” à gauche. Une échelle de fréquence “log” permet de zoomer dans les graves:

Bruit généré - Zoom dans les graves
Bruit généré – Zoom dans les graves

Et c’est la cata! Tous ces pics ne sont pas “petits” mais correspondent à quelque chose de précis: le secteur, le 50 Hz! Eh oui on observe bien 50,100,150,200,250,300 Hz qui sont des harmoniques (pairs et impairs) du secteur!

Comment peut-on expliquer ceci? Eh bien, je pense, par l’alimentation! J’ai pourtant utilisé une alim de labo linéaire (et non à découpage) qui n’est pourtant pas si mauvaise. Et la “ronflette” passe quand même! Une autre cause possible est la récup de signaux par la patte non connectée du transistor. Autant dire que c’est très mauvais pour un générateur aléatoire, car bien évidemment, les valeurs du signal ont une corrélation importante, dû aux signaux périodiques sinusoïdaux qui se superposent au bruit ! 50 fois par seconde, une partie des signaux est égale à ce qui se passait 1/50ème de seconde avant! On le voit parfaitement avec l’ “autocorrélation avancée” disponible dans Audacity:

Autocorrélation du signal généré
Autocorrélation du signal généré

Ici, c’est explicite: le signal décalé de 0,2 secondes est partiellement superposable au signal original. Et il est encore superposable au signal décalé de 0,4 secondes. Ce signal n’est pas du tout aléatoire!

Voici comment va se dérouler la suite de l’étude:

  • Blindage du transistor générateur
  • Mesure du signal avec une alimentation sur batterie
  • Optimisation des condensateurs de liaison pour être sûr de la bande passante
  • Mise en place d’un filtrage énergique pour éviter au maximum les bruits! En gros, il faut un filtre passe très-très bas sur l’alim! Donc des capas de découplage, et en amont, une résistance en série dans l’alim. Il y aura aussi des inductances, utilisées pour leur fonction de base “je m’oppose aux variations du courant”.

En conclusion, voici un montage simple, amusant, et qui ne demande qu’à être optimisé. J’ai plein d’idées pour la génération aléatoire proprement dite… Mais on verra plus tard!

Mise à jour du 19 Septembre 2013:

Après mon passage sur Dangerous Prototypes, Jon a commenté sur la version anglaise de l’article pour me faire remarquer que le bruit provenait probablement de ma carte son. J’ai donc fait un enregistrement audacity du signal de mon générateur, mais SANS l’alimenter. Le résultat est sans appel:

Signal résiduel de la carte son
Signal résiduel de la carte son

C’est donc la carte son de mon laptop qui me pourrit le signal, il va donc falloir passer à autre chose sans trop m’inquiéter ! Merci, Jon!