Nombres aléatoires
Bibliographie
- "random number generators : principles and practices de David Johnston"
La solution la plus simple est de faire $n$ pile ou face pour créer un nombre aléatoire à $n$ bits. Cette solution n'est pas réaliste mais il faut utiliser un processus physique quelque-part car tout algorithme est déterministe. Il est également exclu d'utiliser des humains pour générer des suites aléatoire car l'humain n'est pas fait pour reconnaître l'aléatoire : on cherchera à avoir des suite équilibrées de 0 et de 1 ce qui n'est pas du tout aléatoire :
TRNG
Il existe des moyens de générer des nombres aléatoire, on appelle ces générateur TRNG : pour True Random Generator.
TBD avec des dés plusieurs bits avec 1 lancé : https://stackoverflow.com/questions/20804899/how-to-generate-an-un-biased-random-number-within-an-arbitrary-range-using-the-f/20818831#20818831 TBD présenter niquist TBD quantique, etc. TBD ring oscillatro : https://www.youtube.com/watch?v=fwU8s1BMNlA https://www-verimag.imag.fr/~async/CCIS/talk_12/Lubicz_talk.pdf et https://pqshield.com/wp-content/uploads/2022/02/2021-1363.pdf
Entropie
Cependant créer un nombre aléatoire est un processus coûteux en temps et en énergie. On utilisera alors souvent des processus approchés pour extraire de l'aléatoire : générer $n$ bits presque aléatoires à partir de $m < n$ bits vraiment aléatoires.
TBD à revoir et à présenter :
Implémentation
Implémentations :
Et ces méthodes sont implémentées directement sur le processeur ou via le système d'exploitation :
xxd < /dev/random
Ou de façon plus "lisible" :
echo "hasard : "$(base64 </dev/random 2>/dev/null| head -c 100)
Sous windows (attention pas cryptographique) :
powershell -command "[Convert]::ToBase64String((1..64|%{[byte](Get-Random -Max 256)}))"
dans le processeur
- latch bistable
- pour changer les imperfections on déplace les proba à chaque tirage : on ajoute de l'auto-correlation avec des capacités qui se chargent à gauche ou à droite. pour arriver à 50% de 1 et de 0.
- différence portes https://pages.hmc.edu/harris/cmosvlsi/4e/lect/lect9.pdf
- supprimer l'autocorrelation : post-processing :
- Von Neumann Corrector (Correcteur de Von Neumann) : Read bits in non-overlapping pairs. Discard 00 and 11, output 0 for 01, and output 1 for 10. Note: This removes bias and first-order serial correlation, though it reduces your bit rate by at least 75%.
- XOR Decimation (Décimation par XOR) : XOR consecutive bits together (e.g., (B_{out} = B_n \oplus B_{n-1}), or across multiple independent latches). If the serial correlation coefficient between adjacent bits is ρ, XORing k bits reduces the correlation exponentially to (\rho ^{k}).
- LFSR or Cryptographic Hashing (LFSR ou hachage) : Feed the raw bitstream into a Linear Feedback Shift Register (LFSR) or a lightweight hash function (like SHA-256 or Toeplitz hashing) to whiten the output and destroy temporal dependencies.