X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/ab1271f8b9509a86f3434c2389be47fe3a1c4d04..refs/heads/master:/15RairoGen.tex diff --git a/15RairoGen.tex b/15RairoGen.tex index 38920d8..6832d33 100644 --- a/15RairoGen.tex +++ b/15RairoGen.tex @@ -9,15 +9,81 @@ comme un générateur aléatoire. Ce chapitre présente donc une application directe de la théorie développée ci-avant à la génération de nombres pseudo-aléatoires. +La section~\ref{sec:PRNG:chaos:autres} présente un état de l'art (incomplet) de l'exploitation de +fonctions au comportement chaotique pour obtenir des PRNGs. La section~\ref{sub:prng:algo} -présente tout d'abord l'algorithme de PRNG. La contrainte de +présente ensuite l'algorithme de PRNG. La contrainte de distribution uniforme de la sortie est discutée dans cette section. -La chaoticité du générateur est ensuite étudiée en +La chaoticité du générateur est étudiée en section~\ref{prng:unaire:chaos}. La section~\ref{sub:prng:algo} a été publiée à ~\cite{bcgw11:ip,bcgr11:ip}. +\section{Quelques PRNGs basés sur des fonctions aux itérations chaotiques}\label{sec:PRNG:chaos:autres} + +Les PRNGs chaotiques (CPRNGs) sont des générateurs non linéaires définis par +$x_0 \in \mathbb{R}$ et $x_{t+1} = f(x_t)$, où $f$ est une fonction au comportement chaotique. +Les raisons qui expliquent l'intérêt de telles fonctions sont naturellement la sensibilité aux conditions initiales, +leur imprévisibilité\ldots Cependant, comme l'ordinateur sur lequel elles s'exécutent a une précision finie, +les générateurs qui les embarquent peuvent avoir des périodes arbitrairement courtes, +ne pas fournir de sortie selon une distribution uniforme\ldots +D'un point de vue cryptographique, ces CPRNGs sont critiquables~\cite{wiggins2003introduction}. +Réduire ces critiques est l'objectif de nombreux travaux de recherche reportés ci dessous. + + +Parmi les suites simples classiquement embarquées dans les CPRNGs, on trouve principalement +la suite logistique, +la suite de Hénon. +La suite logistique~\cite{may1976simple} est définie de $[0;1]$ dans lui même par $x_{t+1} = r \times x_t(1-x_t)$ +avec $x_0 \in [0;1]$ et $3,57<r<4,0$. +La suite de Hénon~\cite{henon1976two} de $A \times B$ dans lui même, avec $A$ et $B$ deux sous-ensembles de $\R$, +est définie par +$x_{t+1} = (1-a x_t^2)+y_t$ et $y_{t+1}= bx_{t+1}$, où $a$ et $b$ sont les paramètres canoniques. +Pour $a=1,4$, $b=0,3$, $A=[-1,5;1,5]$ et $B=-[0,4;0,4]$ le comportement de cette suite est chaotique. + +La suite logistique est utilisée dans l'article~\cite{dabal2011chaos} dans lequel +les auteurs utilisent une représentation des réels à virgule fixe. +Les auteurs de~\cite{dabal2012fpga} comparent leur implantation de la suite logistique avec celle +de la suite de Hénon. +Les auteurs de~\cite{6868789} ont exploité la réécriture de la suite logistique sous la forme +$x_{t+1} = (r \times x_t)-(r \times x_t^2)$ et la possibilité de paralléliser ceci +pour accroître la fréquence du PRNG. +Les auteurs de~\cite{liu2008improved} proposent de coupler deux suites logistiques, +chacune étant paramétrée différemment ($x_0$, $r_1$ et $y_0$, $r_2$ respectivement). L'idée principale +est de modifier iterrativement le paramètre $r_2$ à l'aide des itérés de $x_t$. +Quant aux auteurs de~\cite{merahcoupling13}, ils couplent la suite logistique et celle de Hénon. +La première suite sert à sélectionner les éléments parmi ceux générés par la seconde. +Les auteurs de~\cite{mao2006design}, combinent spatialement $L$ suites logistiques +et construisent ainsi $x_t(0)$, \dots, $x_t(L-1)$ selon l'équation suivante: +\begin{equation} +x_{t+1}(i) = +(1- \varepsilon) f(x_t(i)) + +\frac{\varepsilon}{2} +(f(x_t(i-1)) + f(x_t(i+1))), +\label{eq:cml} +\end{equation} +\noindent où +$i \in \dfrac{\Z}{L\Z}$, +$f$ est une adaptation de la suite logistique au cas discret, +la graine $(X_0(0),\dots, X_0(L-1))$ et la pondération $\varepsilon$ sont fournies par l'utilisateur. + + +René Lozi a aussi étudié la construction de PRNGs en couplant +des suites de Lozi~\cite{espinelrojas:hal-00622989} (qui sont une variation des suites de Hénon: $x^2_t$ est remplacé par $| x_t|$), +la suite tente~\cite{DBLP:journals/ijbc/Lozi12} et en extrayant des +sous-suites pour construire la sortie du PRNG~\cite{lozi:hal-00813087}. + + + -\section{ Nombres pseudo-aléatoires construits par itérations unaires}\label{sub:prng:algo} +Certaines équations différentielles ont été à la base de PRNGs chaotiques. +On pense aux équations de Lorenz~\cite{Lorenz1963}, à celles de Rössler~\cite{Rossler1976397}\ldots +Celles-ci ont par exemple embarquées dans les PRNG dans les articles~\cite{Silva:2009:LLP:1592409.1592411} +et~\cite{mansingka2013fibonacci} respectivement. + + + + +\section{Nombres pseudo-aléatoires construits par itérations unaires}\label{sub:prng:algo} @@ -297,11 +363,11 @@ ait une distribution suffisamment proche de la distribution uniforme. On énonce directement le théorème suivant dont la preuve est donnée en annexe~\ref{anx:generateur}. \begin{restatable}[Uniformité de la sortie de l'algorithme~\ref{CI Algorithm}]{theorem}{PrngCIUniforme}\label{thm:prng:u} - Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\textsc{giu}(f)$ son + Soit $f: \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$, $\textsc{giu}(f)$ son graphe d'itérations , $\check{M}$ sa matrice d'adjacence et $M$ une matrice $2^n\times 2^n$ définie par - $M = \dfrac{1}{n} \check{M}$. + $M = \dfrac{1}{\mathsf{N}} \check{M}$. Si $\textsc{giu}(f)$ est fortement connexe, alors la sortie du générateur de nombres pseudo-aléatoires détaillé par l'algorithme~\ref{CI Algorithm} suit une loi qui @@ -325,22 +391,22 @@ Expliquons enfin comment a été calculé le nombre de la troisième colonne utilisé comme le paramètre $b$ dans l'algorithme~\ref{CI Algorithm}. -Soit $e_i$ le $i^{\textrm{ème}}$ vecteur de la base canonique de $\R^{2^{n}}$. -Chacun des éléments $v_j$, $1 \le j \le 2^n$, +Soit $e_i$ le $i^{\textrm{ème}}$ vecteur de la base canonique de $\R^{2^{\mathsf{N}}}$. +Chacun des éléments $v_j$, $1 \le j \le 2^{\mathsf{N}}$, du vecteur $e_i M_f^t$ représente la probabilité d'être dans la configuration $j$ après $t$ étapes du processus de Markov associé à $\textsc{giu}(f)$ en partant de la configuration $i$. Le nombre $\min \{ t \mid t \in \Nats, \vectornorm{e_i M_f^t - \pi} < 10^{-4} \}$ représente le plus petit nombre d'itérations où la distance de -ce vecteur au vecteur $\pi=(\frac{1}{2^n},\ldots,\frac{1}{2^n})$ +ce vecteur au vecteur $\pi=(\frac{1}{2^{\mathsf{N}}},\ldots,\frac{1}{2^{\mathsf{N}}})$ -- autrement dit, où la déviation par rapport à la distribution uniforme -- est inférieure à $10^{-4}$. En prenant le max pour tous les $e_i$, on obtient une valeur pour $b$. Ainsi, on a \begin{equation} -b = \max\limits_{i \in \llbracket 1, 2^n \rrbracket} +b = \max\limits_{i \in \llbracket 1, 2^{\mathsf{N}} \rrbracket} \left\{ \min \left\{ t \mid t \in \Nats, \vectornorm{e_i M_f^t - \pi} < 10^{-4} @@ -473,7 +539,7 @@ $F_{{f_u},p_i} : \mathds{B}^\mathsf{N} \times [\mathsf{N}]^{p_i} \rightarrow \mathds{B}^\mathsf{N}$ définie par $$ -F_{f_u,p_i} (x,(u^0, u^1, \hdots, u^{p_i-1})) \mapsto +F_{f_u,p_i} (x,(u^0, u^1, \hdots, u^{p_i-1})) = F_{f_u}(\hdots (F_{f_u}(F_{f_u}(x,u^0), u^1), \hdots), u^{p_i-1}). $$ @@ -504,7 +570,7 @@ sur la seconde. Ainsi, les sorties $(y^0, y^1, \hdots )$ produites par le générateur détaillé dans l'algorithme~\ref{CI Algorithm} sont les premiers composants des itérations $X^0 = (x^0, (u,v))$ et $\forall n \in \mathds{N}, -X^{n+1} = G_{f_u,\mathcal{P}}(X^n)$ dans $\mathcal{X}_{\mathsf{N},\mathcal{P}}$ où +X^{n+1} = G_{f_u,\mathcal{P}}(X^{\mathsf{N}})$ dans $\mathcal{X}_{\mathsf{N},\mathcal{P}}$ où $G_{f_u,\mathcal{P}}$ est définie par: @@ -758,6 +824,8 @@ est fortement connexe. % \end{proof} + + \section{Conclusion} Ce chapitre a proposé un algorithme permettant de construire un PRNG chaotique à partir d'un PRNG existant. Pour ce faire, il est nécessaire