X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/rairo15.git/blobdiff_plain/e878014111cef8e935255d892d3d132429d03469..4da7584dffe58a5bbdcd406436a5b139ee4c13fd:/chaos.tex diff --git a/chaos.tex b/chaos.tex index 74d07cf..d5ab5f9 100644 --- a/chaos.tex +++ b/chaos.tex @@ -1,60 +1,80 @@ +Let us us first recall the chaos theoretical context presented +in~\cite{bcgr11:ip}. In this article, the space of interest +is $\Bool^{{\mathsf{N}}} \times \llbracket1;{\mathsf{N}}\rrbracket^{\Nats}$ +and the iteration function $\mathcal{H}_f$ is +the map from +$\Bool^{{\mathsf{N}}} \times \llbracket1;{\mathsf{N}}\rrbracket^{\Nats}$ +to itself defined by +\[ +\mathcal{H}_f(x,s)=(F_f(x,s_0),\sigma(s)). +\] +In this definition, +$\sigma: \llbracket1;{\mathsf{N}}\rrbracket^{\Nats} \longrightarrow + \llbracket1;{\mathsf{N}}\rrbracket^{\Nats} +$ + is a shift operation on sequences (\textit{i.e.}, a function that removes the +first element of the sequence) formally defined with +$$ +\sigma((u^k)_{k \in \Nats}) = (u^{k+1})_{k \in \Nats}. +$$ + +We have proven~\cite[Theorem 1]{bcgr11:ip} that +$\mathcal{H}_f$ is chaotic in +$\Bool^{{\mathsf{N}}} \times \llbracket1;{\mathsf{N}}\rrbracket^{\Nats}$ +if and only if $\Gamma(f)$ is strongly connected. +However, the corrolary which would say that $\chi_{\textit{14Secrypt}}$ is chaotic +cannot be directly deduced since we do not output all the successive +values of iterating $F_f$. Only a a few of them is concerned and +any subsequence of a chaotic sequence is not necessarily +a chaotic sequence too. +This necessitates a rigorous proof, which is the aim of this section. -\subsection{Notations and terminologies}\label{sec:notations} -Denote by $\mathds{B}$ the Boolean set, by $\mathds{N}^\ast$ the set -of natural integers $\{1,2,3, \hdots \}$, and by $\mathds{N}=\mathds{N}^\ast \cup \{0\}$. -For $a,b \in \mathds{N}, a \leqslant b$, $\llbracket a, b \rrbracket$ means the set -$\{a, a+1, \hdots , b\}$ of integers belonging between $a$ and $b$. -For any finite set $X$, $|X|$ denotes its cardinality. -The $n-$th of a sequence $v$ of vectors is $v^n$ while its $i-$th component is $v_i^n$, -so $v=\left(v^n\right)_{n \in \mathds{N}}$. -Finally, $\overline{x}$ stands for the negation of the Boolean $x$, while $\lfloor y \rfloor$ is -the largest integer lower than $y$. -\subsubsection{Devaney's Chaotic Dynamical Systems} +\subsection{Devaney's Chaotic Dynamical Systems} \label{subsec:Devaney} Consider a topological space $(\mathcal{X},\tau)$ and a continuous function $f : \mathcal{X} \rightarrow \mathcal{X}$. -\begin{Def} +\begin{dfntn} The function $f$ is said to be \emph{topologically transitive} if, for any pair of open sets $U,V \subset \mathcal{X}$, there exists $k>0$ such that $f^k(U) \cap V \neq \varnothing$. -\end{Def} +\end{dfntn} -\begin{Def} +\begin{dfntn} An element $x$ is a \emph{periodic point} for $f$ of period $n\in \mathds{N}^*$ if $f^{n}(x)=x$.% The set of periodic points of $f$ is denoted $Per(f).$ -\end{Def} +\end{dfntn} -\begin{Def} +\begin{dfntn} $f$ is said to be \emph{regular} on $(\mathcal{X}, \tau)$ if the set of periodic points for $f$ is dense in $\mathcal{X}$: for any point $x$ in $\mathcal{X}$, any neighborhood of $x$ contains at least one periodic point (without necessarily the same period). -\end{Def} +\end{dfntn} -\begin{Def}[Devaney's formulation of chaos~\cite{Devaney}] +\begin{dfntn}[Devaney's formulation of chaos~\cite{Devaney}] The function $f$ is said to be \emph{chaotic} on $(\mathcal{X},\tau)$ if $f$ is regular and topologically transitive. -\end{Def} +\end{dfntn} The chaos property is strongly linked to the notion of ``sensitivity'', defined on a metric space $(\mathcal{X},d)$ by: -\begin{Def} +\begin{dfntn} \label{sensitivity} The function $f$ has \emph{sensitive dependence on initial conditions} if there exists $\delta >0$ such that, for any $x\in \mathcal{X}$ and any neighborhood $V$ of $x$, there exist $y\in V$ and $n > 0$ such that $d\left(f^{n}(x), f^{n}(y)\right) >\delta $. The constant $\delta$ is called the \emph{constant of sensitivity} of $f$. -\end{Def} +\end{dfntn} Indeed, Banks \emph{et al.} have proven in~\cite{Banks92} that when $f$ is chaotic and $(\mathcal{X}, d)$ is a metric space, then $f$ has the property of @@ -62,93 +82,106 @@ sensitive dependence on initial conditions (this property was formerly an element of the definition of chaos). -\subsubsection{Introducing the \textit{CIPRNG} categories of chaotic iterations based pseudorandom number generators} +\subsection{A Metric Space for PRNG Iterations} + +% Define by $\mathcal{S}_X$ the set of sequences whose elements belong in $X \subset \mathds{N}, X \neq \varnothing$, +% that is, $\mathcal{S}_X = \mathcal{X}^\mathds{N}$. +% Let $\mathsf{N} \in \mathds{N}^\ast$, $f:\mathds{B}^\mathsf{N} \rightarrow \mathds{B}^\mathsf{N}$, and +% $\mathcal{P} \subset \mathds{N}^\ast$ a non empty and finite set of integers. + +% Any couple $(u,v) \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket} \times \mathcal{S}_\mathcal{P}$ defines +% a ``chaotic iterations based'' pseudorandom number generator, which is denoted by $\textit{CIPRNG}_f^2(u,v)$~\cite{wbg10:ip}. It is +% defined as follows: +% \begin{equation} +% \label{CIPRNGver2} +% \left\{ +% \begin{array}{l} +% x^0 \in \mathds{B}^\mathsf{N}\\ +% \forall n \in \mathds{N}, \forall i \in \llbracket 1, \mathsf{N} \rrbracket, x_i^{n+1} = \left\{ \begin{array}{ll} f(x^n)_i & \text{if }~ i=u^n \\ x_i^n & \text{else} \end{array} \right.\\ +% \forall n \in \mathds{N}, y^n = x^{v^n} . +% \end{array} +% \right. +% \end{equation} +% The outputted sequence produced by this generator is $\left(y^n\right)_{n \in \mathds{N}}$. +% Remark that, given a sequence $S \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$ called a ``chaotic strategy'', +% the following way to iterate: +% $$x^0 \in \mathds{B}^\mathsf{N}, \forall n \in \mathds{N}, \forall i \in \llbracket 1, \mathsf{N} \rrbracket, x_i^{n+1} = \left\{ \begin{array}{ll} f(x^n)_i & \text{if }~ i=S^n \\ x_i^n & \text{else} \end{array} \right. ,$$ +% is referred in the discrete mathematics literature as ``chaotic iterations''~\cite{Robert} (a terminology which has +% \emph{a priori} no relation with the mathematical theory of chaos recalled previously), which +% explains the name provided to these categories of pseudorandom number generators. + + +% The formerly proposed $\textit{CIPRNG}_f^1(u)$~\cite{bgw09:ip,guyeuxTaiwan10} is equal to \linebreak $\textit{CIPRNG}_f^2\left(u,\left(1\right)_{n\in \mathds{N}}\right)$, where $\left(1\right)_{n\in \mathds{N}}$ is the sequence that is +% uniformly equal to 1. +% It has been proven as chaotic for the vectorial Boolean negation $f_0:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N}$, +% $(x_1, \hdots , x_\mathsf{N}) \longmapsto (\overline{x_1}, \hdots, \overline{x_\mathsf{N}})$ in \cite{bgw09:ip} +% and for a larger set of well-chosen iteration functions in~\cite{bcgr11:ip} but, +% as only one bit is modified at each iteration, this generator is not able to pass any reasonable statistical tests. + +% The $\textit{XOR~CIPRNG}(S)$, for its part~\cite{DBLP:journals/corr/abs-1112-5239}, is defined as follows: $x^0 \in \mathds{B}^\mathsf{N}$, and $\forall n \in \mathds{N}, x^{n+1} = x^n \oplus S^n$ +% where $S \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$ and $\oplus$ stands for the bitwise \emph{exclusive or} (xor) operation +% between the binary decomposition of $x^n$ and $S^n$. This is indeed a $CIPRNG_{f_0}^2 (u,v)$ generator: +% %, for +% %$u,v \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$: +% for any given $S \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$, $v^n$ is the number +% of 1's in the binary decomposition of $S^n$ while $u^{v^n}, u^{v^n+1}, \hdots , u^{v^{n+1}-1}$ +% are the positions of these ones. +% The $\textit{XOR~CIPRNG}$ has been proven chaotic and it is able to pass all the most stringent statistical +% batteries of tests~\cite{DBLP:journals/corr/abs-1112-5239}, namely: DieHARD~\cite{Marsaglia1996}, NIST~\cite{Nist10}, and TestU01~\cite{LEcuyerS07}, +% which encompasses the two former ones. Furthermore, the output sequence is cryptographically secure +% when $S$ is cryptographically secure~\cite{DBLP:journals/corr/abs-1112-5239}. +% We are then left to prove $\textit{CIPRNG}_f^2(u,v)$ is chaotic. + +% \subsection{The $\textit{CIPRNG}_f^2(u,v)$ is chaotic for well-chosen $f$}\label{sec:wellchosen} + +% \subsection{The generator as a discrete dynamical system} + + +% This algorithm may be seen as $\mathsf{p}$ functional composition of $F_f$. +% We thus introduce the function +% $F_{f,\mathsf{p}} : \mathds{B}^\mathsf{N} \times \llbracket 1, \mathsf{N} \rrbracket^\mathsf{p} \rightarrow \mathds{B}^\mathsf{N}$ defined by + +% $$ +% F_{f,\mathsf{p}} (x,(u^0, u^1, \hdots, u^{\mathsf{p}-1})) \mapsto +% F_f(\hdots (F_f(F_f(x,u^0), u^1), \hdots), u^{\mathsf{p}-1}). +% $$ + + + + +Let us first introduce $\mathcal{P} \subset \mathds{N}$ a finite nonempty +set having the cardinality $\mathsf{p} \in \mathds{N}^\ast$. +Intuitively, this is the set of authorized numbers of iterations. +Denote by $p_1, p_2, \hdots, p_\mathsf{p}$ the ordered elements of $\mathcal{P}$: $\mathcal{P} = \{ p_1, p_2, \hdots, p_\mathsf{p}\}$ +and $p_1< p_2< \hdots < p_\mathsf{p}$. In our algorithm, +$\mathsf{p}$ is 1 and $p_1$ is $b$. -Define by $\mathcal{S}_X$ the set of sequences whose elements belong in $X \subset \mathds{N}, X \neq \varnothing$, -that is, $\mathcal{S}_X = \mathcal{X}^\mathds{N}$. -Let $\mathsf{N} \in \mathds{N}^\ast$, $f:\mathds{B}^\mathsf{N} \rightarrow \mathds{B}^\mathsf{N}$, and -$\mathcal{P} \subset \mathds{N}^\ast$ a non empty and finite set of integers. -Any couple $(u,v) \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket} \times \mathcal{S}_\mathcal{P}$ defines -a ``chaotic iterations based'' pseudorandom number generator, which is denoted by $\textit{CIPRNG}_f^2(u,v)$~\cite{wbg10:ip}. It is -defined as follows: -\begin{equation} -\label{CIPRNGver2} -\left\{ -\begin{array}{l} - x^0 \in \mathds{B}^\mathsf{N}\\ - \forall n \in \mathds{N}, \forall i \in \llbracket 1, \mathsf{N} \rrbracket, x_i^{n+1} = \left\{ \begin{array}{ll} f(x^n)_i & \text{if }~ i=u^n \\ x_i^n & \text{else} \end{array} \right.\\ - \forall n \in \mathds{N}, y^n = x^{v^n} . -\end{array} -\right. -\end{equation} -The outputted sequence produced by this generator is $\left(y^n\right)_{n \in \mathds{N}}$. -Remark that, given a sequence $S \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$ called a ``chaotic strategy'', -the following way to iterate: -$$x^0 \in \mathds{B}^\mathsf{N}, \forall n \in \mathds{N}, \forall i \in \llbracket 1, \mathsf{N} \rrbracket, x_i^{n+1} = \left\{ \begin{array}{ll} f(x^n)_i & \text{if }~ i=S^n \\ x_i^n & \text{else} \end{array} \right. ,$$ -is referred in the discrete mathematics literature as ``chaotic iterations''~\cite{Robert} (a terminology which has -\emph{a priori} no relation with the mathematical theory of chaos recalled previously), which -explains the name provided to these categories of pseudorandom number generators. - - -The formerly proposed $\textit{CIPRNG}_f^1(u)$~\cite{bgw09:ip,guyeuxTaiwan10} is equal to \linebreak $\textit{CIPRNG}_f^2\left(u,\left(1\right)_{n\in \mathds{N}}\right)$, where $\left(1\right)_{n\in \mathds{N}}$ is the sequence that is -uniformly equal to 1. -It has been proven as chaotic for the vectorial Boolean negation $f_0:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N}$, -$(x_1, \hdots , x_\mathsf{N}) \longmapsto (\overline{x_1}, \hdots, \overline{x_\mathsf{N}})$ in \cite{bgw09:ip} -and for a larger set of well-chosen iteration functions in~\cite{bcgr11:ip} but, -as only one bit is modified at each iteration, this generator is not able to pass any reasonable statistical tests. - -The $\textit{XOR~CIPRNG}(S)$, for its part~\cite{DBLP:journals/corr/abs-1112-5239}, is defined as follows: $x^0 \in \mathds{B}^\mathsf{N}$, and $\forall n \in \mathds{N}, x^{n+1} = x^n \oplus S^n$ -where $S \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$ and $\oplus$ stands for the bitwise \emph{exclusive or} (xor) operation -between the binary decomposition of $x^n$ and $S^n$. This is indeed a $CIPRNG_{f_0}^2 (u,v)$ generator: -%, for -%$u,v \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$: -for any given $S \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$, $v^n$ is the number -of 1's in the binary decomposition of $S^n$ while $u^{v^n}, u^{v^n+1}, \hdots , u^{v^{n+1}-1}$ -are the positions of these ones. -The $\textit{XOR~CIPRNG}$ has been proven chaotic and it is able to pass all the most stringent statistical -batteries of tests~\cite{DBLP:journals/corr/abs-1112-5239}, namely: DieHARD~\cite{Marsaglia1996}, NIST~\cite{Nist10}, and TestU01~\cite{LEcuyerS07}, -which encompasses the two former ones. Furthermore, the output sequence is cryptographically secure -when $S$ is cryptographically secure~\cite{DBLP:journals/corr/abs-1112-5239}. -We are then left to prove $\textit{CIPRNG}_f^2(u,v)$ is chaotic. - -\subsection{The $\textit{CIPRNG}_f^2(u,v)$ is chaotic for well-chosen $f$}\label{sec:wellchosen} - -\subsubsection{The generator as a discrete dynamical system} - - -Using notations of the previous section, consider a $\textit{CIPRNG}_f^2(u,v)$ generator $G$, with -$\mathsf{N} \in \mathds{N}^\ast$, $f:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N}$, -$u \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$, and $v \in \mathcal{S}_\mathcal{P}$, with -$\mathcal{P} \subset \mathds{N}$ a finite nonempty set having the cardinality -$\mathsf{p} \in \mathds{N}^\ast$. -Denote by $p_1, p_2, \hdots, p_\mathsf{p}$ the ordered elements of $\mathcal{P}$: $\mathcal{P} = \{ p_1, p_2, \hdots, p_\mathsf{p}\}$ -and $p_1< p_2< \hdots < p_\mathsf{p}$. -Let -$$ -\begin{array}{cccc} - F_f: & \mathds{B}^\mathsf{N} \times \llbracket 1, \mathsf{N} \rrbracket & \longrightarrow & \mathds{B}^\mathsf{N}\\ - & (e,i) & \longmapsto & (e_1, \hdots , e_{i-1}, f(e)_i, e_{i+1}, \hdots , e_{\mathsf{N}}) -\end{array} -$$ -and +The Algorithm~\ref{CI Algorithm} +may be seen as $b$ functional composition of $F_f$. +However, it can be generalized with $p_i$, $p_i \in \mathcal{P}$, +functional compositions of $F_f$. +Thus, for any $p_i \in \mathcal{P}$ we introduce the function +$F_{f,p_i} : \mathds{B}^\mathsf{N} \times \llbracket 1, \mathsf{N} \rrbracket^{p_i} \rightarrow \mathds{B}^\mathsf{N}$ defined by + $$ -\begin{array}{cccc} - F_{f,\mathsf{p}} : & \mathds{B}^\mathsf{N} \times \llbracket 1, \mathsf{N} \rrbracket^\mathsf{p} & \longrightarrow & \mathds{B}^\mathsf{N}\\ - & (e,(u^0, u^1, \hdots, u^{\mathsf{p}-1})) & \longmapsto & F_f(\hdots (F_f(F_f(e,u^0), u^1), \hdots), u^{\mathsf{p}-1}) . -\end{array} +F_{f,p_i} (x,(u^0, u^1, \hdots, u^{p_i-1})) \mapsto +F_f(\hdots (F_f(F_f(x,u^0), u^1), \hdots), u^{p_i-1}). $$ -Denote by $\mathcal{X}_{\mathsf{N},\mathcal{P}}= \mathds{B}^\mathsf{N} \times \mathds{S}_{\mathsf{N},\mathcal{P}}$, where -$\mathds{S}_{\mathsf{N},\mathcal{P}}=\mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}\times \mathcal{S}_\mathcal{P}$, -we define the shift operation on sequences as follows, -$$\begin{array}{cccc} -\sigma:&\mathcal{S}_{X} &\longrightarrow -& \mathcal{S}_{X} \\ -& (u^k)_{k \in \mathds{N}} & \longmapsto & (u^{k+1})_{k \in \mathds{N}}, -\end{array} -$$ -and let + +The considered space is + $\mathcal{X}_{\mathsf{N},\mathcal{P}}= \mathds{B}^\mathsf{N} \times \mathds{S}_{\mathsf{N},\mathcal{P}}$, where +$\mathds{S}_{\mathsf{N},\mathcal{P}}= +\llbracket 1, \mathsf{N} \rrbracket^{\Nats}\times +\mathcal{P}^{\Nats}$. +Each element in this space is a pair where the first element is +$\mathsf{N}$-uple in $\Bool^{\mathsf{N}}$, as in the previous space. +The second element is a pair $((u^k)_{k \in \Nats},(v^k)_{k \in \Nats})$ of infinite sequences. +The sequence $(v^k)_{k \in \Nats}$ defines how many iterations are executed at time $k$ between two outputs. +The sequence $(u^k)_{k \in \Nats}$ defines which elements is modified. + +Let us define the shift function $\Sigma$ for any element of $\mathds{S}_{\mathsf{N},\mathcal{P}}$. $$\begin{array}{cccc} \Sigma:&\mathds{S}_{\mathsf{N},\mathcal{P}} &\longrightarrow &\mathds{S}_{\mathsf{N},\mathcal{P}} \\ @@ -174,7 +207,7 @@ X^{n+1} = G_f(X^n)$ on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$. -\subsubsection{A metric on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$} +\subsection{A metric on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$} We define a distance $d$ on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$ as follows. Consider @@ -203,7 +236,7 @@ part of $d(X,\check{X})$ is completed by 0's until reaching $p+n\times \max{(\mathcal{P})}$ digits. \item If $v^0<\check{v}^0$, then the $ \max{(\mathcal{P})}$ blocs of $n$ digits are $|u^0-\check{u}^0|$, ..., $|u^{v^0-1}-\check{u}^{v^0-1}|$, -$\check{u}^{v^0}$ (on $n$ digits), ..., $\check{u}^{\check{v}^0-1}$ (on $n$ digits), followed by O's if required. +$\check{u}^{v^0}$ (on $n$ digits), ..., $\check{u}^{\check{v}^0-1}$ (on $n$ digits), followed by 0's if required. \item The case $v^0>\check{v}^0$ is dealt similarly. \end{itemize} \item The next $p$ digits are $|v^1-\check{v}^1|$, etc. @@ -220,14 +253,14 @@ $s=\left\{ u=\underline{6,} ~ \underline{11,5}, ...\\ v=1,2,... \end{array} -\right.$\\ +\right.$ while $\check{s}=\left\{ \begin{array}{l} \check{u}=\underline{6,4} ~ \underline{1}, ...\\ \check{v}=2,1,... \end{array} -\right.$ +\right.$. So $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.010004000000000000000000011005 ...$ Indeed, the $p=2$ first digits are 01, as $|v^0-\check{v}^0|=1$, @@ -250,7 +283,7 @@ $s=\left\{ u=\underline{6,7,} ~ \underline{4,2,} ...\\ v=2,2,... \end{array} -\right.$\\ +\right.$ while $\check{s}=\left\{ \begin{array}{l} @@ -285,9 +318,9 @@ $$ %\left| \sum_{l=0}^{v^k-1} \dfrac{u^{\sum_{m=0}^{k-1} v^m +l}}{ 10^{l}} - \su Let us show that, -\begin{proposition} -$d$ is a distance on $\mathcal{X}$. -\end{proposition} +\begin{prpstn} +$d$ is a distance on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$. +\end{prpstn} \begin{proof} @@ -309,10 +342,10 @@ definition of $d$. Then, as digits between positions $p+1$ and $p+n$ are null an Before being able to study the topological behavior of the general chaotic iterations, we must first establish that: -\begin{proposition} +\begin{prpstn} For all $f:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N} $, the function $G_f$ is continuous on $\left( \mathcal{X},d\right)$. -\end{proposition} +\end{prpstn} \begin{proof} @@ -344,50 +377,71 @@ $G_f(x^n)_2$ is convergent to $G_f(x)_2$. \end{itemize} \end{proof} -\begin{figure}[h] -\centering -\includegraphics[scale=0.85]{graphe1.pdf} -\caption{Chaotic iterations of $f_0$, defining the $CIPRNG_{f_0}^1$ ($\mathsf{N}=2$)} -\label{graphe1} -\end{figure} -\subsubsection{The $\textit{CIPRNG}_f^2(u,v)$ as iterations on a graph} -We define the directed graph $\mathcal{G}_{f,\mathcal{P}}$ as follows. +\subsection{$\Gamma_{\mathcal{P}}(f)$ as an extension of $\Gamma(f)$} + +Let $\mathcal{P}=\{p_1, p_2, \hdots, p_\mathsf{p}\}$. +We define the directed graph $\Gamma_{\mathcal{P}}(f)$ as follows. \begin{itemize} \item Its vertices are the $2^\mathsf{N}$ elements of $\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 There is an arc labeled $a_1, \hdots, a_{p_i}$, $i \in \llbracket 1, \mathsf{p} \rrbracket$ between vertices $x$ and $y$ if and only if $y=F_{f,p_i} (x, (a_1, \hdots, a_{p_i})) $. + having their elements in $\llbracket 1, \mathsf{N} \rrbracket $. +\item There is an arc labeled $u_0, \hdots, u_{p_i-1}$, $i \in \llbracket 1, \mathsf{p} \rrbracket$ between vertices $x$ and $y$ if and only if +$y=F_{f,p_i} (x, (u_0, \hdots, u_{p_i-1})) $. \end{itemize} - -\begin{figure}[h] -\centering -\includegraphics[scale=0.85]{graphe2.pdf} -\caption{Iteration graph of $CIPRNG_{f_0}^2$, $\mathcal{P}=\{2,3\}$, $\mathsf{N}=2$} -\label{graphe2} +It is not hard to see that the graph $\Gamma_{\{1\}}(f)$ is +$\Gamma(f)$. + +\begin{figure}[ht] + \centering + \begin{subfigure}[b]{0.45\textwidth} + \centering + \includegraphics[scale=0.85]{graphe1.pdf} + \caption{$\Gamma(f_0)$} + \label{graphe1} + \end{subfigure}% + ~ %add desired spacing between images, e. g. ~, \quad, \qquad, \hfill etc. + % (or a blank line to force the subfigure onto a new line) + \begin{subfigure}[b]{0.3\textwidth} + \centering + \includegraphics[scale=0.85]{graphe2.pdf} + \caption{$\Gamma_{\{2,3\}}(f_0)$} + \label{graphe2} + \end{subfigure} + ~ %add desired spacing between images, e. g. ~, \quad, \qquad, \hfill etc. + \caption{Iterating $f_0:(x_1,x_2) \mapsto (\overline{x_1}, \overline{x_2})$} + \label{fig:itg} \end{figure} + \begin{xpl} -Consider for instance $\mathsf{N}=2$, $f_0:\mathds{B}^2 \longrightarrow \mathds{B}^2, (x_1,x_2) \longmapsto (\overline{x_1}, \overline{x_2})$, and -$\mathcal{P}=\{2,3\}$. Chaotic iterations of $f_0$ are given in Figure~\ref{graphe1} while the digraph $\mathcal{G}_{f_0,\{2,3\}}$ is depicted in -Figure~\ref{graphe2}. Notice that here, orientations of arcs are not necessary -since the function $f$ is equal to its inverse $f^{-1}$. +Consider for instance $\mathsf{N}=2$, +Let $f_0:\mathds{B}^2 \longrightarrow \mathds{B}^2$ be the negation function, +\textit{i.e.}, $f_0(x_1,x_2) = (\overline{x_1}, \overline{x_2})$, and consider +$\mathcal{P}=\{2,3\}$. The graphs of iterations are given in +\textsc{Figure~\ref{fig:itg}}. +The \textsc{Figure~\ref{graphe1}} shows what happens when +displaying each iteration result. +On the contrary, the \textsc{Figure~\ref{graphe2}} explicits the behaviors +when always applying 2 or 3 modification and next outputing results. +Notice that here, orientations of arcs are not necessary +since the function $f_0$ is equal to its inverse $f_0^{-1}$. \end{xpl} -\subsubsection{Proofs of chaos} +\subsection{Proofs of chaos} We will show that, -\begin{proposition} +\begin{prpstn} \label{prop:trans} - $\mathcal{G}_{f,\mathcal{P}}$ is strongly connected if and only if $G_f$ is + $\Gamma_{\mathcal{P}}(f)$ is strongly connected if and only if $G_f$ is topologically transitive on $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$. -\end{proposition} +\end{prpstn} \begin{proof} -Suppose that $\mathcal{G}_{f,\mathcal{P}}$ is strongly connected. +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 @@ -407,7 +461,7 @@ 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'))$. $\mathcal{G}_{f,\mathcal{P}}$ +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$), @@ -422,7 +476,7 @@ Let $y=(e,((u^0, ..., u^{\sum_{l=0}^{k_1}v^l-1}, a_0^0, ..., a_0^{|a_0|}, a_1^0, and $G_{f}^{k_1+k_2}(y)=\check{x}$. -Conversely, if $\mathcal{G}_{f,\mathcal{P}}$ is not strongly connected, then there are +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)$ @@ -431,10 +485,10 @@ cannot be reached from any neighborhood of $e_1$, and thus $G_f$ is not transiti We show now that, -\begin{proposition} -If $\mathcal{G}_{f,\mathcal{P}}$ is strongly connected, then $G_f$ is +\begin{prpstn} +If $\Gamma_{\mathcal{P}}(f)$ is strongly connected, then $G_f$ is regular on $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$. -\end{proposition} +\end{prpstn} \begin{proof} Let $x=(e,(u,v)) \in \mathcal{X}_{\mathsf{N},\mathcal{P}}$ and $\varepsilon >0$. @@ -443,7 +497,7 @@ 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))$. $\mathcal{G}_{f,\mathcal{P}}$ being strongly connected, +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: @@ -454,8 +508,25 @@ 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{Theo} -The pseudorandom number generator $\textit{CIPRNG}_f^2$ denoted by $G_f$ in -this section is chaotic on $(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$ if -and only if its graph $\mathcal{G}_{f,\mathcal{P}}$ is strongly connected. -\end{Theo} +\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} + +The next section shows how to generate functions and a iteration number $b$ +such that $\Gamma_{\{b\}}$ is strongly connected. + + + \ No newline at end of file