From 35f9a1f25d6fb4d3d2993aa5d75b474742eb8ac6 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Jean-Fran=C3=A7ois=20Couchot?= Date: Fri, 17 Jul 2015 13:10:25 +0200 Subject: [PATCH 1/1] ajout preuve chaos --- 15RairoGen.tex | 85 +++++++++++++++++++++++++++++++- annexePreuveDistribution.tex | 94 ++++++++++++++++++++++++++++++++++++ images/h23prng.dot | 21 ++++++++ images/h2prng.dot | 15 ++++++ images/h3prng.dot | 21 ++++++++ 5 files changed, 234 insertions(+), 2 deletions(-) create mode 100644 images/h23prng.dot create mode 100644 images/h2prng.dot create mode 100644 images/h3prng.dot diff --git a/15RairoGen.tex b/15RairoGen.tex index aff664f..4c9a25b 100644 --- a/15RairoGen.tex +++ b/15RairoGen.tex @@ -146,8 +146,8 @@ 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} vérifient les hypothèses du théorème~\ref{th:Adrien}. 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}. +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 que cela l'est pour $h$. @@ -648,5 +648,86 @@ $d$ est une distance sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$. \subsection{Le graphe $\textsc{giu}_{\mathcal{P}}(f)$ étendant $\textsc{giu}(f)$} +A partir de $\mathcal{P}=\{p_1, p_2, \hdots, p_\mathsf{p}\}$, on +definit le graphe orienté $\textsc{giu}_{\mathcal{P}}(f)$ de la manière suivante: +\begin{itemize} +\item les n{\oe}uds sont les $2^\mathsf{N}$ configurations de $\mathds{B}^\mathsf{N}$, +%\item Each vertex has $\displaystyle{\sum_{i=1}^\mathsf{p} \mathsf{N}^{p_i}}$ arrows, namely all the $p_1, p_2, \hdots, p_\mathsf{p}$ tuples +% having their elements in $\llbracket 1, \mathsf{N} \rrbracket $. +\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), +chaque $u_k$ de la suite 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)$. + + + + + +\begin{figure}%[t] + \begin{center} + \subfigure[$\textsc{giu}_{\{2\}}(h)$]{ + \begin{minipage}{0.30\textwidth} + \begin{center} + \includegraphics[height=4cm]{images/h2prng.pdf} + \end{center} + \end{minipage} + \label{fig:h2prng} + } + \subfigure[$\textsc{giu}_{\{3\}}(h)$]{ + \begin{minipage}{0.40\textwidth} + \begin{center} + \includegraphics[height=4cm]{images/h3prng.pdf} + \end{center} + \end{minipage} + \label{fig:h3prng} + } + \subfigure[$\textsc{giu}_{\{2,3\}}(h)$]{ + \begin{minipage}{0.40\textwidth} + \begin{center} + \includegraphics[height=4cm]{images/h23prng.pdf} + \end{center} + \end{minipage} + \label{fig:h23prng} + } + + \end{center} + \caption{Graphes d'iterations $\textsc{giu}_{\mathcal{P}}(h)$ pour $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$} + \label{fig:xplgraphIter} + \end{figure} + + + + +\begin{xpl} +On reprend l'exemple où $\mathsf{N}=2$ et +$h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$ déjà détaillé +à la section~\ref{sub:prng:unif}. + +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}. +Le premier (repsectivement 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. + +\end{xpl} + + \subsection{le PRNG de l'algorithme~\ref{CI Algorithm} est chaotique sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$} +Le théorème suivant, similaire à celui dans $\mathcal{X}_u$ et dans $\mathcal{X}_g$ +est prouvé en annexes~\ref{}. + +\begin{theorem} +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)$ +est fortement connexe. +\end{theorem} + + + diff --git a/annexePreuveDistribution.tex b/annexePreuveDistribution.tex index 8de466c..878b317 100644 --- a/annexePreuveDistribution.tex +++ b/annexePreuveDistribution.tex @@ -85,3 +85,97 @@ et en vérifiant tous les $n \times \max{(\mathcal{P})}$ blocs, $u=\check{u}$. aussi. \end{itemize} \end{proof} + + + +\begin{theorem} +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)$ +est fortement connexe. +\end{theorem} + +\begin{proof} +Suppose that $\Gamma_{\mathcal{P}}(f)$ is strongly connected. +Let $x=(e,(u,v)),\check{x}=(\check{e},(\check{u},\check{v})) +\in \mathcal{X}_{\mathsf{N},\mathcal{P}}$ and $\varepsilon >0$. +We will find a point $y$ in the open ball $\mathcal{B}(x,\varepsilon )$ and +$n_0 \in \mathds{N}$ such that $G_f^{n_0}(y)=\check{x}$: this strong transitivity +will imply the transitivity property. +We can suppose that $\varepsilon <1$ without loss of generality. + +Let us denote by $(E,(U,V))$ the elements of $y$. As +$y$ must be in $\mathcal{B}(x,\varepsilon)$ and $\varepsilon < 1$, +$E$ must be equal to $e$. Let $k=\lfloor \log_{10} (\varepsilon) \rfloor +1$. +$d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))$ must be lower than +$\varepsilon$, so the $k$ first digits of the fractional part of +$d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))$ are null. +Let $k_1$ the smallest integer such that, if $V^0=v^0$, ..., $V^{k_1}=v^{k_1}$, + $U^0=u^0$, ..., $U^{\sum_{l=0}^{k_1}V^l-1} = u^{\sum_{l=0}^{k_1}v^l-1}$. +Then $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))<\varepsilon$. +In other words, any $y$ of the form $(e,((u^0, ..., u^{\sum_{l=0}^{k_1}v^l-1}), +(v^0, ..., v^{k_1}))$ is in $\mathcal{B}(x,\varepsilon)$. + +Let $y^0$ such a point and $z=G_f^{k_1}(y^0) = (e',(u',v'))$. $\Gamma_{\mathcal{P}}(f)$ +being strongly connected, there is a path between $e'$ and $\check{e}$. Denote +by $a_0, \hdots, a_{k_2}$ the edges visited by this path. We denote by +$V^{k_1}=|a_0|$ (number of terms in the finite sequence $a_1$), +$V^{k_1+1}=|a_1|$, ..., $V^{k_1+k_2}=|a_{k_2}|$, and by +$U^{k_1}=a_0^0$, $U^{k_1+1}=a_0^1$, ..., $U^{k_1+V_{k_1}-1}=a_0^{V_{k_1}-1}$, +$U^{k_1+V_{k_1}}=a_1^{0}$, $U^{k_1+V_{k_1}+1}=a_1^{1}$,... + +Let $y=(e,((u^0, ..., u^{\sum_{l=0}^{k_1}v^l-1}, a_0^0, ..., a_0^{|a_0|}, a_1^0, ..., a_1^{|a_1|},..., + a_{k_2}^0, ..., a_{k_2}^{|a_{k_2}|},$ \linebreak + $\check{u}^0, \check{u}^1, ...),(v^0, ..., v^{k_1},|a_0|, ..., + |a_{k_2}|,\check{v}^0, \check{v}^1, ...)))$. So $y\in \mathcal{B}(x,\varepsilon)$ + and $G_{f}^{k_1+k_2}(y)=\check{x}$. + + +Conversely, if $\Gamma_{\mathcal{P}}(f)$ is not strongly connected, then there are +2 vertices $e_1$ and $e_2$ such that there is no path between $e_1$ and $e_2$. +That is, it is impossible to find $(u,v)\in \mathds{S}_{\mathsf{N},\mathcal{P}}$ +and $n \mathds{N}$ such that $G_f^n(e,(u,v))_1=e_2$. The open ball $\mathcal{B}(e_2, 1/2)$ +cannot be reached from any neighborhood of $e_1$, and thus $G_f$ is not transitive. +\end{proof} + + +We show now that, +\begin{prpstn} +If $\Gamma_{\mathcal{P}}(f)$ is strongly connected, then $G_f$ is +regular on $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$. +\end{prpstn} + +\begin{proof} +Let $x=(e,(u,v)) \in \mathcal{X}_{\mathsf{N},\mathcal{P}}$ and $\varepsilon >0$. +As in the proofs of Prop.~\ref{prop:trans}, let $k_1 \in \mathds{N}$ such +that +$$\left\{(e, ((u^0, ..., u^{v^{k_1-1}},U^0, U^1, ...),(v^0, ..., v^{k_1},V^0, V^1, ...)) \mid \right.$$ +$$\left.\forall i,j \in \mathds{N}, U^i \in \llbracket 1, \mathsf{N} \rrbracket, V^j \in \mathcal{P}\right\} +\subset \mathcal{B}(x,\varepsilon),$$ +and $y=G_f^{k_1}(e,(u,v))$. $\Gamma_{\mathcal{P}}(f)$ being strongly connected, +there is at least a path from the Boolean state $y_1$ of $y$ and $e$. +Denote by $a_0, \hdots, a_{k_2}$ the edges of such a path. +Then the point: +$$(e,((u^0, ..., u^{v^{k_1-1}},a_0^0, ..., a_0^{|a_0|}, a_1^0, ..., a_1^{|a_1|},..., + a_{k_2}^0, ..., a_{k_2}^{|a_{k_2}|},u^0, ..., u^{v^{k_1-1}},$$ +$$a_0^0, ...,a_{k_2}^{|a_{k_2}|}...),(v^0, ..., v^{k_1}, |a_0|, ..., |a_{k_2}|,v^0, ..., v^{k_1}, |a_0|, ..., |a_{k_2}|,...))$$ +is a periodic point in the neighborhood $\mathcal{B}(x,\varepsilon)$ of $x$. +\end{proof} + +$G_f$ being topologically transitive and regular, we can thus conclude that +\begin{thrm} +The function $G_f$ is chaotic on $(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$ if +and only if its iteration graph $\Gamma_{\mathcal{P}}(f)$ is strongly connected. +\end{thrm} + +\begin{crllr} + The pseudorandom number generator $\chi_{\textit{14Secrypt}}$ is not chaotic + on $(\mathcal{X}_{\mathsf{N},\{b\}},d)$ for the negation function. +\end{crllr} +\begin{proof} + In this context, $\mathcal{P}$ is the singleton $\{b\}$. + If $b$ is even, any vertex $e$ of $\Gamma_{\{b\}}(f_0)$ cannot reach + its neighborhood and thus $\Gamma_{\{b\}}(f_0)$ is not strongly connected. + If $b$ is even, any vertex $e$ of $\Gamma_{\{b\}}(f_0)$ cannot reach itself + and thus $\Gamma_{\{b\}}(f_0)$ is not strongly connected. +\end{proof} diff --git a/images/h23prng.dot b/images/h23prng.dot new file mode 100644 index 0000000..1605403 --- /dev/null +++ b/images/h23prng.dot @@ -0,0 +1,21 @@ +digraph { + 00 -> 00 [label="11,22,112,211,222"] + 00 -> 10 [label="21,111,122,221"] + 00 -> 11 [label="12,212"] + 01 -> 01 [label="11,22,112,211,222"] + 01 -> 10 [label="12,212"] + 01 -> 11 [label="21,111,122,221"] + 10 -> 00 [label="12,111,122,221"] + 10 -> 01 [label="21,212"] + 10 -> 10 [label="11,22,121"] + 11 -> 00 [label="21,212"] + 11 -> 01 [label="12,111,122,221"] + 11 -> 11 [label="11,22,121"] + + 00 -> 01 [label="121"] + 01 -> 00 [label="121"] + 10 -> 11 [label="112,211,222"] + 11 -> 10 [label="112,211,222"] + + +} diff --git a/images/h2prng.dot b/images/h2prng.dot new file mode 100644 index 0000000..bc3fe76 --- /dev/null +++ b/images/h2prng.dot @@ -0,0 +1,15 @@ +digraph { + 00 -> 00 [label="11,22"] + 00 -> 10 [label="21"] + 00 -> 11 [label="12"] + 01 -> 01 [label="11,22"] + 01 -> 10 [label="12"] + 01 -> 11 [label="21"] + 10 -> 00 [label="12"] + 10 -> 01 [label="21"] + 10 -> 10 [label="11,22"] + 11 -> 00 [label="21"] + 11 -> 01 [label="12"] + 11 -> 11 [label="11,22"] + +} diff --git a/images/h3prng.dot b/images/h3prng.dot new file mode 100644 index 0000000..f911ba5 --- /dev/null +++ b/images/h3prng.dot @@ -0,0 +1,21 @@ +digraph { + 00 -> 00 [label="112,211,222"] + 00 -> 10 [label="111,122,221"] + 00 -> 11 [label="212"] + 01 -> 01 [label="112,211,222"] + 01 -> 10 [label="212"] + 01 -> 11 [label="111,122,221"] + 10 -> 00 [label="111,122,221"] + 10 -> 01 [label="212"] + 10 -> 10 [label="121"] + 11 -> 00 [label="212"] + 11 -> 01 [label="111,122,221"] + 11 -> 11 [label="121"] + + 00 -> 01 [label="121"] + 01 -> 00 [label="121"] + 10 -> 11 [label="112,211,222"] + 11 -> 10 [label="112,211,222"] + + +} -- 2.39.5