17 septembre 2013

Un générateur de signaux 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:

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:

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:

On se rend compte de plusieurs choses:

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 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

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

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

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é

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:

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

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!