X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/75aa438e61284f634375e2c1e62c79f2af12678f..c1f6ce3a24b92bfb8dd4da3d9092666c73adbcc9:/15RairoGen.tex?ds=sidebyside diff --git a/15RairoGen.tex b/15RairoGen.tex index 06f84b1..6832d33 100644 --- a/15RairoGen.tex +++ b/15RairoGen.tex @@ -6,26 +6,84 @@ le mot $x^b$ devrait \og sembler ne plus dépendre\fg{} de $x^0$. On peut penser à exploiter une de ces fonctions $G_f$ comme un générateur aléatoire. -Ce chapitre présente une application directe +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 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 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 é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,570.$$ On énonce le théorème classique suivant liant les -vecteur de probabilités +vecteurs de probabilités et les chaînes de Markov. @@ -147,8 +205,8 @@ et les chaînes de Markov. Montrons sur un exemple jouet à deux éléments que ce théorème permet de vérifier si la sortie d'un générateur de -nombres pseudo aléatoires est uniformément distribuée ou non. -Soit alors $g$ et $h$ deux fonctions de $\Bool^2$ +nombres pseudo-aléatoires est uniformément distribuée ou non. +Soient alors $g$ et $h$ deux fonctions de $\Bool^2$ définies par $g(x_1,x_2)=(\overline{x_1},x_1.\overline{x_2}) $ et $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$. Leurs graphes d'interactions donnés en figure \ref{fig:g:inter} et \ref{fig:h:inter} @@ -157,7 +215,7 @@ Leurs graphes d'itérations sont donc fortement connexes, ce que l'on peut vérifier aux figures~\ref{fig:g:iter} et~\ref{fig:h:iter}. \textit{A priori}, ces deux fonctions pourraient être intégrées -dans un générateur de nombres pseudo aléatoires. Montrons que ce n'est pas le cas pour $g$ et +dans un générateur de nombres pseudo-aléatoires. Montrons que ce n'est pas le cas pour $g$ et que cela l'est pour $h$. @@ -291,10 +349,10 @@ Alors d'après le théorème~\ref{th}, pour n'importe quel vecteur initial de probabilités $\pi^0$, on a $\lim_{k \to \infty} \pi^0 M^k_g = \pi_g$ et $\lim_{k \to \infty} \pi^0 M^k_h = \pi_h$. -Ainsi la chaîne de Markov associé à $h$ tend vers une +Ainsi la chaîne de Markov associée à $h$ tend vers une distribution uniforme, contrairement à celle associée à $g$. On en déduit que $g$ ne devrait pas être itérée dans -un générateur de nombres pseudo aléatoires. +un générateur de nombres pseudo-aléatoires. Au contraire, $h$ devrait pouvoir être embarquée dans l'algorithme~\ref{CI Algorithm}, pour peu que le nombre $b$ d'itérations entre deux mesures successives @@ -302,20 +360,20 @@ de valeurs soit suffisamment grand de sorte que le vecteur d’état de la chaîne de Markov ait une distribution suffisamment proche de la distribution uniforme. -On énonce directement le théorème suivant dont la preuve est donnée en annexes~\ref{anx:generateur}. +On énonce directement le théorème suivant dont la preuve est donnée en annexe~\ref{anx:generateur}. -\begin{theorem}\label{thm:prng:u} - Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\textsc{giu}(f)$ son +\begin{restatable}[Uniformité de la sortie de l'algorithme~\ref{CI Algorithm}]{theorem}{PrngCIUniforme}\label{thm:prng:u} + 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 + la sortie du générateur de nombres pseudo-aléatoires détaillé par l'algorithme~\ref{CI Algorithm} suit une loi qui tend vers la distribution uniforme si et seulement si $M$ est une matrice doublement stochastique. -\end{theorem} +\end{restatable} \subsection{Quelques exemples} @@ -333,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 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} @@ -439,7 +497,7 @@ $\mathcal{F}_{16}$ &14, 15, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 La qualité des séquences aléatoires a été évaluée à travers la suite de tests statistiques développée pour les générateurs de nombres -pseudo aléatoires par le +pseudo-aléatoires par le \emph{National Institute of Standards and Technology} (NIST). L'expérience a montré notamment que toutes ces fonctions passent avec succès cette batterie de tests. @@ -454,7 +512,7 @@ Montrer que les sous-séquences de suites chaotiques ainsi générées demeuren est l'objectif de la section suivante. -\section{Un PRNG basé sur des itérations unaires qui est chaotique } +\section{Un PRNG basé sur des itérations unaires qui est chaotique }\label{prng:unaire:chaos} Cette section présente un espace métrique adapté au générateur de nombres pseudo-aléatoires présenté à l'algorithme~\ref{CI Algorithm} et prouve ensuite que la fonction qu'il représente @@ -481,12 +539,12 @@ $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}). $$ -on construit l'espace +On construit l'espace $\mathcal{X}_{\mathsf{N},\mathcal{P}}= \mathds{B}^\mathsf{N} \times \mathds{S}_{\mathsf{N},\mathcal{P}}$, où $\mathds{S}_{\mathsf{N},\mathcal{P}}= [\mathsf{N}]^{\Nats}\times @@ -512,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: @@ -536,7 +594,7 @@ où $s=(u,v)$ et $\check{s}=(\check{u},\check{v})$ sont dans $ \mathds{S}_{\math \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket} \times \mathcal{S}_\mathcal{P}$. \begin{enumerate} \item $e$ et $\check{e}$ sont des entiers appartenant à $\llbracket 0, 2^{\mathsf{N}-1} \rrbracket$. -La distance de Hamming $d_{\mathds{B}^\mathsf{N}}$ sur entre les +La distance de Hamming $d_{\mathds{B}^\mathsf{N}}$ entre les décompositions binaires de $e$ et de $\check{e}$ (\textit{i.e.}, le le nombre de bits qu'elles ont de différent) constitue la partie entière de $d(X,\check{X})$. @@ -566,7 +624,7 @@ jusqu'à atteindre $p+n\times \max{(\mathcal{P})}$ éléments. \item Si $v^0<\check{v}^0$, alors les $ \max{(\mathcal{P})}$ blocs de $n$ éléments sont $|u^0-\check{u}^0|$, ..., $|u^{v^0-1}-\check{u}^{v^0-1}|$, -$\check{u}^{v^0}$ (sur $n$ éléments), ..., $\check{u}^{\check{v}^0-1}$ (sur $n$ éléments), suivi par des 0, si besoin. +$\check{u}^{v^0}$ (sur $n$ éléments), ..., $\check{u}^{\check{v}^0-1}$ (sur $n$ éléments), suivis par des 0, si besoin. \item Le cas $v^0>\check{v}^0$ est similaire, et donc omis \end{enumerate} \item Les $p$ suivants sont $|v^1-\check{v}^1|$, etc. @@ -623,7 +681,7 @@ On prend alors le $v^0=1$ premier terme de $u$, chaque terme étant codé sur $n=2$ éléments, soit 06. Comme on itère au plus $\max{(\mathcal{P})}$ fois, on complète cette valeur par des 0 de sorte que -la chaîne obtenue a $n\times \max{(\mathcal{P})}=22$ éléments, soit: +la chaîne obtenue ait $n\times \max{(\mathcal{P})}=22$ éléments, soit: 0600000000000000000000. De manière similaire, les $\check{v}^0=2$ premiers termes de $\check{u}$ sont représentés par @@ -660,10 +718,12 @@ la séquence. -On a la proposition suivante, qui est démontrée en annexes~\ref{anx:generateur}. -\begin{lemma} +On a la proposition suivante, qui est démontrée en annexe~\ref{anx:generateur}. + + +\begin{restatable}[Une distance dans $\mathcal{X}_{\mathsf{N},\mathcal{P}}$]{theorem}{distancedsxnp} $d$ est une distance sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$. -\end{lemma} +\end{restatable} \subsection{Le graphe $\textsc{giu}_{\mathcal{P}}(f)$ étendant $\textsc{giu}(f)$} @@ -677,7 +737,7 @@ définit le graphe orienté $\textsc{giu}_{\mathcal{P}}(f)$ de la manière suiva \item il y a un arc libellé $u_0, \hdots, u_{p_i-1}$, $i \in \llbracket 1, \mathsf{p} \rrbracket$ entre les n{\oe}uds $x$ et $y$ si et seulement si $p_i$ est un élément de $\mathcal{P}$ (\textit{i.e.}, on peut itérer $p_i$ fois), et pour chaque $k$, $0 \le k \le p_i-1$, on a - $u_k$ qui apaprtient à $[\mathsf{N}]$ et + $u_k$ qui appartient à $[\mathsf{N}]$ et $y=F_{f_u,p_i} (x, (u_0, \hdots, u_{p_i-1})) $. \end{itemize} Il n'est pas difficile de constater que $\textsc{giu}_{\{1\}}(f)$ est $\textsc{giu}(f)$. @@ -728,12 +788,12 @@ $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$ déjà détail Le graphe $\textsc{giu}_{\{1\}}(h)$ a déjà été donné à la figure~\ref{fig:h:iter}. Les graphes $\textsc{giu}_{\{2\}}(h)$, $\textsc{giu}_{\{3\}}(h)$ et -$\textsc{giu}_{\{2,3\}}(h)$ sont respectivement donnés aux figure~\ref{fig:h2prng}, ~\ref{fig:h3prng} et ~\ref{fig:h23prng}. +$\textsc{giu}_{\{2,3\}}(h)$ sont respectivement donnés aux figures~\ref{fig:h2prng}, ~\ref{fig:h3prng} et ~\ref{fig:h23prng}. Le premier (respectivement le second) illustre le comportement du générateur lorsque qu'on itère exactement 2 fois (resp. 3 fois) puis qu'on affiche le résultat. Le dernier donnerait le comportement d'un générateur qui s'autoriserait -à itérer en interne systématiquement 2 ou trois fois avant de retourner un résultat. +à itérer en interne systématiquement 2 ou 3 fois avant de retourner un résultat. \end{xpl} @@ -741,26 +801,37 @@ Le dernier donnerait le comportement d'un générateur qui s'autoriserait \subsection{le PRNG de l'algorithme~\ref{CI Algorithm} est chaotique sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$} Le théorème suivant, similaire à ceux dans $\mathcal{X}_u$ et dans $\mathcal{X}_g$ -est prouvé en annexes~\ref{anx:generateur}. +est prouvé en annexe~\ref{anx:generateur}. -\begin{theorem} +\begin{restatable}[Conditions pour la chaoticité de $G_{f_u,\mathcal{P}}$]{theorem}{thmchoticitgfp} La fonction $G_{f_u,\mathcal{P}}$ est chaotique sur $(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$ si et seulement si -graphe d'itération $\textsc{giu}_{\mathcal{P}}(f)$ +le graphe d'itérations $\textsc{giu}_{\mathcal{P}}(f)$ est fortement connexe. -\end{theorem} -On alors corollaire suivant +\end{restatable} +% On alors corollaire suivant + +% \begin{corollary} +% Le générateur de nombre pseudo aléatoire détaillé +% à l'algorithme~\ref{CI Algorithm} +% n'est pas chaotique +% sur $(\mathcal{X}_{\mathsf{N},\{b\}},d)$ pour la fonction négation. +% \end{corollary} +% \begin{proof} +% Dans cet algorithme, $\mathcal{P}$ est le singleton $\{b\}$. +% Que $b$ soit pair ou impair, $\textsc{giu}_{\{b\}}(f)$ +% n'est pas fortement connexe. +% \end{proof} -\begin{corollary} - Le générateur de nombre pseudo aléatoire détaillé - à l'algorithme~\ref{CI Algorithm} - n'est pas chaotique - sur $(\mathcal{X}_{\mathsf{N},\{b\}},d)$ pour la fonction négation. -\end{corollary} -\begin{proof} - Dans cet algorithme, $\mathcal{P}$ est le singleton $\{b\}$. - Que $b$ soit pair ou impair, $\textsc{giu}_{\{b\}}(f)$ - n'est pas 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 +et suffisant que la fonction $f$ qui est itérée un nombre $b$ de fois +possède un $\textsc{giu}_{\{b\}}(f)$ fortement connexe et que sa matrice de Markov associée soit doublement stochastique. +Le chapitre suivant montre comment construire une telle fonction. + + +