See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/331481686

Génération chaotique de nombres pseudo-aléatoires: d'une idée. .. à son

implantation efficace (10 ans)

Presentation · March 2019

CITATIONS READS

0 878

1 author:

Jean-François Couchot
University Bourgogne Franche-Comté
133 PUBLICATIONS 991 CITATIONS

SEE PROFILE

All content following this page was uploaded by Jean-François Couchot on 04 July 2022.

The user has requested enhancement of the downloaded file.

Génération chaotique de nombres
pseudo-aléatoires: d’une idée . . .
à son implantation efficace (10 ans)
Jean-François Couchot

Institut FEMTO-ST
Univ. Bourgogne Franche-Comté (UBFC), France

Technolab le 28/02/2019
Plan

Introduction

Construire un PRNG chaotique : facile !

La course au débit sur différents supports

Conclusion

Institut FEMTO-ST Univ. Bourgogne Franche-Comté (UBFC), France 2 / 25

Plan

Introduction

Construire un PRNG chaotique : facile !

La course au débit sur différents supports

Conclusion

Institut FEMTO-ST Univ. Bourgogne Franche-Comté (UBFC), France 3 / 25

Histoire de génération aléatoire, L’Ecuyer 1
Des dés et des pièces

• Invention des dés : en Irak, Iran et Chine il y a environ 5000 ans.

• Avec 1 à 6 points (comme aujourd’hui) : les symboles des

nombres pas encore inventés !
• Invention des générateurs de nombres aléatoires avant les
symboles pour représenter les nombres !

• Au temps des Romains : le jeu de hasard “navia aut caput” interprétable comme le premier générateur de
bits aléatoires.

Une première mise en cause de l’aléa

Dans la plupart des civilisations anciennes, les gens ne croyaient pas au hasard :
• Les résultats des dés : interprétés comme la décision d’un dieu.
• Les nombres aléatoires : déjà critiqués comme pas vraiment aléatoires.

1. L’Ecuyer, P. (2017, December). History of uniform random number generation. In 2017 Winter Simulation
Conference (WSC) (pp. 202-230). IEEE.

Institut FEMTO-ST Univ. Bourgogne Franche-Comté (UBFC), France 4 / 25

Gén. de nbres. pseudo-aléatoires (PRNG)
Utilisation des nombres aléatoires

• Vie courante : localisation GPS, cryptage de données (RSA) ;

• Science : statistiques, en probabilité, en simulation numérique.

Pseudo aléatoire : algorithme reproductible

6= Réellement aléatoire : processus physique non reproductible.

Formalisation 2 PRNG : (S, f , g, U, x 0 )

• S : espace d’état interne.

• U : espace de sortie.
• f : S → S : fonction interne de transition.
• g : S → U : fonction d’extraction de la sortie.
• x 0 : la graine.

2. L’Ecuyer, P. (1990). Random numbers for simulation. Communications of the ACM, 33(10), 85-97.

Institut FEMTO-ST Univ. Bourgogne Franche-Comté (UBFC), France 5 / 25

Un exemple de PRNG : congruentiel linéaire
Définition (Générateur Congruentiel Linéaire LCG)

Pour m, a, c ∈ N t.q. m ≥ a, c, un LCG de graîne x 0 est

(
x 0 ∈ N t.q. 0 ≤ x 0 ≤ m − 1
(1)
x t+1 = a × x t + c mod m.

• Bien choisir m, a, c et x0 : primordial !

Institut FEMTO-ST Univ. Bourgogne Franche-Comté (UBFC), France 6 / 25

c = 0 : conditions suff. pour une période max

Théorème (Période d’un LCG x t+1 = a × x t mod m, x 0 6= 0)

La période est m − 1 si

1. m est un nombre premier ;

2. a est d’ordre m − 1

Avec x 0 = 1, m = 181 et a = 19 × 80 × 125 ≡ 131 mod 181

1. m = 181 est un nombre premier ;

2. • 19 est d’ordre 4, 80 est d’ordre 9 et 125 est d’ordre 5 ;
• 4, 5 et 9 premiers entre eux a = 19 × 80 × 125 est d’ordre 180 ;
La période d’un tel générateur est 180.

Institut FEMTO-ST Univ. Bourgogne Franche-Comté (UBFC), France 7 / 25

Premier détecteur de PRNG : test spectral
Points . . . (x 3 , x 2 ), (x 2 , x 1 ), (x 1 , x 0 ) avec x1t+1 = 3x1t mod 31 et x2t+1 = 13x2t mod 31

• Distance entre lignes : ≈ 9.8. • Distance entre lignes : ≈ 5.76 < 9.8, plus étalé

RANDU (x t+1 = (216 + 3)x t ) vs. un générateur “moins régulier”

• Une analyse visuelle ne suffit cependant pas!

Institut FEMTO-ST Univ. Bourgogne Franche-Comté (UBFC), France 8 / 25

Tout semble si aléatoire !

Propriétés souhaitables des RNGs :

• Uniformité de la sortie ;
• Période longue ;
• Cryptographiquement sûrs ;
• Rapides ;
• Sensibles aux conditions initiales ;
• Succès aux tests statistiques.

Comment juger qu’une série de nombres aléatoires est vraiment

aléatoire ?
Quels critères pour choisir un bon générateur de nombres ?

Institut FEMTO-ST Univ. Bourgogne Franche-Comté (UBFC), France 9 / 25

Evaluation statistique des PRNGs : TestU01 3

Nombreux tests statistiques

• De nombreux tests embarqués : BigCrush ≈ 300 tests.

• Basés sur des tests d’adéquation à des lois de probabilité (χ2 ).
• Rang de matrice, spectral, linéarité, marche aléatoire. . .

• PRNG rapides en succès face à ce test : aucun au début 2010.

3. L’Ecuyer, P., & Simard, R. (2007). TestU01 : A C library for empirical testing of random number generators. ACM
Transactions on Mathematical Software (TOMS), 33(4), 22.

Institut FEMTO-ST Univ. Bourgogne Franche-Comté (UBFC), France 10 / 25

Le chaos de Devaney : solution ou problème ?

Définition (Chaos selon Devaney)

k continue sur (X , d) est chaotique 4 si elle est transitive, régulière et fortement sensible aux conditions initiales.
• Transitivité : pour chaque point, chacun de ses voisinages a un futur pouvant contenir tout point de l’espace.
• Régularité : l’ensemble de ses points périodiques est dense dans X .
• Forte sensibilité aux cond. initiales : pour chaque point, chacun de ses voisinages a un point dont un futur
est éloigné.

Questions

• Un PRNG existant : peut-il s’exprimer comme un système dynamique chaotique ?

• Oui : intérêt, autre que théorique ?
• Non : quoi lui ajouter ?
• Un système chaotique : suffisant pour avoir un PRNG statistiquement irréprochable ?
• Oui : Youpi !
• Non : quoi lui ajouter ?

4. Devaney, R. (2008). An introduction to chaotic dynamical systems. Westview press.

Institut FEMTO-ST Univ. Bourgogne Franche-Comté (UBFC), France 11 / 25

Plan

Introduction

Construire un PRNG chaotique : facile !

La course au débit sur différents supports

Conclusion

Institut FEMTO-ST Univ. Bourgogne Franche-Comté (UBFC), France 12 / 25

PRNG + déplacemts. ds. 1 cube spéc.= PRNG’
PRNGs jouets à base de Générateurs Congruentiels Linéaires

x t+1 = x t + 2 mod 3.
Sortie : 0, 2, 1, 0, 2, 1, · · · ∈ {0, 1, 2}N .

Graphes des déplacements pour (x1 , x2 , x3 ) 7→ ((x1 + x2 ).x3 , x1 .x3 , x1 + x2 + x3 ).

001 011

000 010

101 111

100 110

1 seul bit modifié : GIU(f )

PRNG’ : Algorithmes
Input: fonction f , nbre d’itérations b, conf. initiale x 0
Output: conf. x
x ← x0;
for i = 1, . . . , b do
s ← PRNG(0, N − 1) ;
x ← déplacement depuis x selon s ;
end
return x ;

Institut FEMTO-ST Univ. Bourgogne Franche-Comté (UBFC), France 13 / 25

PRNG + déplacemts. ds. 1 cube spéc.= PRNG’
PRNGs jouets à base de Générateurs Congruentiels Linéaires

x t+1 = x t + 2 mod 3. x t+1 = 5 × x t + 3 mod 8.

Sortie : 0, 2, 1, 0, 2, 1, · · · ∈ {0, 1, 2}N . Sortie : 0, 3, 2, 5, 4, 7, 6, 1, · · · ∈ {0, . . . , 7}N ≡ (B3 )N .

Graphes des déplacements pour (x1 , x2 , x3 ) 7→ ((x1 + x2 ).x3 , x1 .x3 , x1 + x2 + x3 ).

001 011 001 011

000 010 000 010

101 111 101 111

100 110 100 110

1 seul bit modifié : GIU(f ) 1 ensemble de bits modifiés : GIG(f )

PRNG’ : Algorithmes
Input: fonction f , nbre d’itérations b, conf. initiale x 0 Input: fonction f , nbre d’itérations b, conf. initiale x 0
Output: conf. x Output: conf. x
x ← x0; x ← x0;
for i = 1, . . . , b do for i = 1, . . . , b do
s ← PRNG(0, N − 1) ; s ← PRNG(0, 2N − 1) ;
x ← déplacement depuis x selon s ; x ← déplacement depuis x selon s ;
end end
return x ; return x ;

Institut FEMTO-ST Univ. Bourgogne Franche-Comté (UBFC), France 13 / 25

PRNG embarqué pour implantation sur FPGA ?

Pour implantation sur FPGA

• Générateur 32/64 bits choisi selon une étude exhaustive 5

• Multiplication : à proscrire ! (Exit LCG !)
• LFSR113 et Taus88 (Pr L’E CUYER).

5. Bakiri, M., Guyeux, C., Couchot, J. F., & Oudjida, A. K. (2018). Bakiri, M., Guyeux, C., Couchot, J. F., & Oudjida,
A. K. (2018). Survey on hardware implementation of random number generators on FPGA : Theory and
experimental analyses. Computer Science Review, 27, 135-153.

Institut FEMTO-ST Univ. Bourgogne Franche-Comté (UBFC), France 14 / 25

Fonction embarquée : conditions

Théorème (Itérations chaotique)

Soit f : BN → BN . Les itérations de la fonction sont chaotiques ssi son graphe d’itérations est fortement connexe 6 .

Théorème (Uniformité de la sortie6 )

Soit f : BN → BN , G son graphe d’itérations supposé fort. connexe, M̌ sa matrice d’adjacence. La sortie de PRNG’
1
suit une loi qui tend vers la distribution uniforme ssi M̌ est doublement stochastique.
N

6. Bahi, J. M., Couchot, J. F., Guyeux, C., & Richard, A. (2011, August). On the link between strongly connected
iteration graphs and chaotic boolean discrete-time dynamical systems. In International Symposium on
Fundamentals of Computation Theory (pp. 126-137). Springer, Berlin, Heidelberg.

Institut FEMTO-ST Univ. Bourgogne Franche-Comté (UBFC), France 15 / 25

Conxt. et dble. stochasticité : construction
Dans B3 : f ∗ (x1 , x2 , x3 ) = (x2 ⊕ x3 , x1 x3 + x1 x2 , x1 x3 + x1 x2 ) très faible b

f ∗ : 3-cube sans le cycle hamiltonien 000, 100, 101, 001, 011, 111, 110, 010, 000.
001 011

1 1 1 0 0 0 0 0
 
 1 1 0 0 0 1 0 0 
000 010
0 0 1 1 0 0 1 0
 
 
1  0 1 1 1 0 0 0 0

M =
 
1 0 0 0 1 0 1 0
 
3  
101 111

 0 0 0 0 1 1 0 1 

 0 0 0 0 1 0 1 1 
0 0 0 1 0 1 0 1
100 110

7. J.-F. Couchot, P.-C. Héam, C. Guyeux, Q. Wang, and J. Bahi. Pseudorandom number generators with balanced
gray codes. In Secrypt 2014, 11th Int. Conf. on Security and Cryptography, pages 469–475, August 2014.

Institut FEMTO-ST Univ. Bourgogne Franche-Comté (UBFC), France 16 / 25

Conxt. et dble. stochasticité : construction
Dans B3 : f ∗ (x1 , x2 , x3 ) = (x2 ⊕ x3 , x1 x3 + x1 x2 , x1 x3 + x1 x2 ) très faible b

f ∗ : 3-cube sans le cycle hamiltonien 000, 100, 101, 001, 011, 111, 110, 010, 000.
001 011

1 1 1 0 0 0 0 0
 
 1 1 0 0 0 1 0 0 
000 010
0 0 1 1 0 0 1 0
 
 
1  0 1 1 1 0 0 0 0

M =
 
1 0 0 0 1 0 1 0
 
3  
101 111

 0 0 0 0 1 1 0 1 

 0 0 0 0 1 0 1 1 
0 0 0 1 0 1 0 1
100 110

Théorème ( N-cube privé d’un cycle hamiltonien)

Dans un N-cube, dans lequel un cycle hamiltonien a été enlevé :

• Graphe d’itérations : fortement connexe 7 .
• Matrice de Markov : doublement stochastique.

7. J.-F. Couchot, P.-C. Héam, C. Guyeux, Q. Wang, and J. Bahi. Pseudorandom number generators with balanced
gray codes. In Secrypt 2014, 11th Int. Conf. on Security and Cryptography, pages 469–475, August 2014.

Institut FEMTO-ST Univ. Bourgogne Franche-Comté (UBFC), France 16 / 25

Chemins hamiltoniens : construction/marche
Exemples de cycles hamiltoniens dans le 4-cube

13
4 5 12
dim 4

6 7 14 15

dim 3 • Occur. des dim. : 8, 4, 2, 2

2 3 10 11

dim 2
dim 1 1 8
0 9

Théorème (Constr. de cycle hamiltonien équilibré)

Il existe une séquence (et construction de celle-ci) dans l’algorithme de Robinson-Cohn t. q. le cycle est équilibré 8

Théorème (Temps de mixage sans chemin hamiltonien)

La chaîne de Markov associée associée à une marche aléatoire paresseuse converge vers la distribution uniforme
et le temps de mixage est : tmix (ε) ≤ dlog2 (ε−1 )e4(8N2 + 4N ln(N + 1))
Plus récemment 9 en O(N ln(N)).

8. J.-F. Couchot, S. Contassot-Vivier, C. Guyeux, and P.-C. Héam. Random walk in a n-cube without hamiltonian
cycle to chaotic pseudorandom number generation : Theoretical and practical considerations. in International
Journal of Bifurcation and Chaos, 27 (1), pages : 1–18, 2017.

9. Contassot-Vivier, S., Couchot, J. F., & Héam, P. C. (2018). Gray Codes Generation Algorithm and Theoretical
Evaluation of Random Walks in N-Cubes. Mathematics, 6(6), 98.

Institut FEMTO-ST Univ. Bourgogne Franche-Comté (UBFC), France 17 / 25

Chemins hamiltoniens : construction/marche
Exemples de cycles hamiltoniens dans le 4-cube
12 13
4 5

dim 4
6 7 14 15

dim 3 • Occur. des dim. : 4, 4, 4, 4

2 3 10 11

dim 2
dim 1 1 8
0 9

Théorème (Constr. de cycle hamiltonien équilibré)

Il existe une séquence (et construction de celle-ci) dans l’algorithme de Robinson-Cohn t. q. le cycle est équilibré 8

Théorème (Temps de mixage sans chemin hamiltonien)

La chaîne de Markov associée associée à une marche aléatoire paresseuse converge vers la distribution uniforme
et le temps de mixage est : tmix (ε) ≤ dlog2 (ε−1 )e4(8N2 + 4N ln(N + 1))
Plus récemment 9 en O(N ln(N)).

8. J.-F. Couchot, S. Contassot-Vivier, C. Guyeux, and P.-C. Héam. Random walk in a n-cube without hamiltonian
cycle to chaotic pseudorandom number generation : Theoretical and practical considerations. in International
Journal of Bifurcation and Chaos, 27 (1), pages : 1–18, 2017.

9. Contassot-Vivier, S., Couchot, J. F., & Héam, P. C. (2018). Gray Codes Generation Algorithm and Theoretical
Evaluation of Random Walks in N-Cubes. Mathematics, 6(6), 98.

Institut FEMTO-ST Univ. Bourgogne Franche-Comté (UBFC), France 17 / 25

Plan

Introduction

Construire un PRNG chaotique : facile !

La course au débit sur différents supports

Conclusion

Institut FEMTO-ST Univ. Bourgogne Franche-Comté (UBFC), France 18 / 25

C. hamiltoniens : une forme canonique

Forme canonique pour un cycle hamiltonien

• Equivalences entre cycles égaux

• A un décallage près du point de départ.
• A une inversion près.
• A une permutation près des dimensions.

• Définition d’une forme canonique 10

Intérêt de la forme canonique

• Partitionnement de l’ensemble des cycles du N-cubes.

• Ordre total sur les formes canoniques :
• stockage et algorithmes de classification efficaces

10. S. Contassot-Vivier, and J.-F. Couchot. Canonical Form of Gray Codes in N-cubes. In Cellular Automata and
Discrete Complex Systems - 23rd IFIP International Workshop, AUTOMATA 2017, June, pages 68–80, 2017.

Institut FEMTO-ST Univ. Bourgogne Franche-Comté (UBFC), France 19 / 25

C. hamiltoniens : algorithmes
Extension à un algorithme de backtracking
tree of tree of
possible possible
cycles cycles 1. A partir d’une
configuration partielle
initial initial
cycle cycle profonde A : générer
B new backtrack depth tous les cycles.
A backtrack A old backtrack depth
depth 2. Pour plus de cycles :
Backtrack
remonter en B et générer
tous les chemins issus
GCs from node A
de B mais pas de A.
all cycles with ancestor A
GCs from node B

Algorithme par inversions de sous-séquences

Cj C j+1 Cj C j+1

Hamiltonian Sub−seq 1. Trouver toutes les inversions

cycle possibles dans un cycle donné.
Face of inversion 2. Appliquer une fermeture transitive.
the N−cube

C i−1 Ci C i−1 Ci

Expérimentations

• 1 classe pour N=2|3, 9 classes pour N=4, 237675 (toutes) classes pour N=5
• Impossible d’etre exhaustif pour N ≥6 : (777739016577752714 )

Institut FEMTO-ST Univ. Bourgogne Franche-Comté (UBFC), France 20 / 25

Une approche efficace

• Stratégie : générateur 32 bits Taus88.

• 4 fonctions 8 bits différentes.
• Permutation : simplification de PCG32 (O’Neil)
• Résultat : les PRNGs plus rapides 11 12 au monde (en
terme de débit par cycle d’horloge) sur FPGA qui
passent complètement le test statistique TestU01 (de
Pr. L’E CUYER).
• Sur CPU, évaluation avec l’outil de Pr. L EMIRE : débit
plus faible que PCG32.

11. Bakiri, M., Guyeux, C., Couchot, J. F., Marangio, L., & Galatolo, S. (2018). A Hardware and Secure
Pseudorandom Generator for Constrained Devices. IEEE Trans. on Industrial Informatics., Vol 14(8), 3754 - 3765.

12. Bakiri Mohammed, J.-F. Couchot, and C. Guyeux. (2018) CIPRNG : A VLSI Family of Chaotic Iterations
Post-Processings for F2-Linear Pseudorandom Number Generation Based on Zynq MPSoC. IEEE Trans. on Circuits
and Systems I : Regular Papers. 2018, pp 1628-1641
Institut FEMTO-ST Univ. Bourgogne Franche-Comté (UBFC), France 21 / 25
Sur CPU : moins efficace que PCG32, à priori
PCG32 13

uint32_t nextUInt ( ) {
uint64_t oldstate = state ;
s t a t e = o l d s t a t e * PCG32_MULT + i n c ;
• Un LCG.
uint32_t xorshifted = ( uint32_t )
( ( ( o l d s t a t e >> 18u ) ^ o l d s t a t e ) >> 27u ) ; • Une permutation.
u i n t 3 2 _ t r o t = ( u i n t 3 2 _ t ) ( o l d s t a t e >> 59u ) ;
r e t u r n ( x o r s h i f t e d >> r o t ) | ( x o r s h i f t e d << ( ( ~ r o t + 1u ) & 3 1 ) ) ;
}

Comparaisons en suivant Pr. L EMIRE 14

• PCG32 : 1 cycle par octet

• Taus88 + Saut dans N-cube dégradé (2 * 16 bits) + LFSR : 2.5 cycles par octet.

13. O’Neill, M. E. (2014). PCG : A family of simple fast space-efficient statistically good algorithms for random
number generation. ACM Transactions on Mathematical Software.

14. Lemire, D., & O’Neill, M. E. (2019). Xorshift1024*, xorshift1024+, xorshift128+ and xoroshiro128+ fail statistical
tests for linearity. Journal of Computational and Applied Mathematics, 350, 139-142.

Institut FEMTO-ST Univ. Bourgogne Franche-Comté (UBFC), France 22 / 25

Plan

Introduction

Construire un PRNG chaotique : facile !

La course au débit sur différents supports

Conclusion

Institut FEMTO-ST Univ. Bourgogne Franche-Comté (UBFC), France 23 / 25

Des PRNGs rapides et crypto : heure du bilan

Contexte, problématique

• TestU01, Pr. L’E CUYER :

• Vu comme une boite noire.
• Lauréats généralement lents.

• Lauréats les + rapides au monde sur FPGA : approche de Dr. B AKIRI, Pr. C ONTASSOT-V IVIER et
FEMTO-ST (8,5 Gbs−1 )
• Lauréat rapides sur CPU (selon Pr. L EMIRE) :
• PCG (LCG + xorshift), Pr. O’N EIL.
• Approche FEMTO-ST : 2,5 fois plus lente.
• Sécurité cryptographique :
• Approche FEMTO-ST, PCG : non !
• Pourquoi 32 bits ?

Institut FEMTO-ST Univ. Bourgogne Franche-Comté (UBFC), France 24 / 25

Des PRNGs rapides et crypto : pistes de travail

Approche théorique guidée par le TestU01

1. Ouvrir chaque test.

2. Conditions nécessaires/suffisantes à la réussite conjonction.
3. Construction de la famille des lauréats par construction.

Générateurs FEMTO-ST : amélioration pratique sur FPGA,

• Stratégie de parcours + mélangeur : à l’aide d’un unique générateur ?

• Choix des paramètres non déduits mathématiquement : par optimisation ?
• Autres fonctions que celles issues d’un cycle hamiltonien ?

Quête du graal sur CPU

• Lauréat du TestU01, minimalistes sur CPU :

• Taille de l’espace ?
• Nombre de cycle pour produire un octet ?

Institut FEMTO-ST Univ. Bourgogne Franche-Comté (UBFC), France 25 / 25

View publication stats