1 \chapter{General Notions}
2 \label{General Notions}
5 This chapter, serving as the background of this thesis, is devoted to basic notations and terminologies in the fields of random number and its classification.
9 A random bit sequence could be interpreted as the result of the flips of an unbiased "fair" coin with sides
10 that are labeled "0" and "1," with each flip having a probability of exactly $1/2$ of producing a "0" or "1."
11 Furthermore, the flips are independent of each other: the result of any previous coin flip does not affect
12 future coin flips. The unbiased "fair" coin is thus the perfect random bit stream generator, since the "0"
13 and "1" values will be randomly distributed (and [0,1] uniformly distributed). All elements of the
14 sequence are generated independently of each other, and the value of the next element in the sequence
15 cannot be predicted, regardless of how many elements have already been produced.
16 Obviously, the use of unbiased coins for cryptographic purposes is impractical. Nonetheless, the
17 hypothetical output of such an idealized generator of a true random sequence serves as a benchmark for
18 the evaluation of random and pseudorandom number generators.~\cite{ANDREW2008}
20 \section{Types of Random Number Generators (RNGs)}
21 A RNG is a computational or physical device designed to generate a sequence of numbers or symbols that lack any pattern, i.e. appear random.
23 It is always a difficult task to generate good random number/sequence. Although it is accepted that rolling a dice or drawing cards is random these mechanical methods are not practical. in the past, random numbers are usually generated offline based on some dedicated setup or devices, and the sequences are stored in table ready for use. These random tables are still available in the world-wide-web or some data CDROMs.
25 However, due to the online requirements and the security issues, random table becomes inappropriate, and hence different RNGs have been proposed, especially after the introduction of computer.
27 In general, RNGs can be grouped into two classes, namely true random number gernerators and pseudo random number generators, depending on their sources of randomness.
28 RNGs can be classified as:
29 \subsection{True Random Number Generators (TRNGs)}
30 A TRNG is one which generates statistically independent and unbiased bits. These are also
31 called as non-deterministic RNGs. In computing, a True random number generator is an apparatus that generates random numbers from a physical process. Such devices are often based on microscopic phenomena that generate a low-level, statistically random "noise" signal, such as thermal noise or the photoelectric effect or other quantum phenomena. These processes are, in theory, completely unpredictable, and the theory's assertions of unpredictability are subject to experimental test. A quantum-based hardware random number generator typically consists of a transducer to convert some aspect of the physical phenomena to an electrical signal, an amplifier and other electronic circuitry to bring the output of the transducer into the macroscopic realm, and some type of analog to digital converter to convert the output into a digital number, often a simple binary digit 0 or 1. By repeatedly sampling the randomly varying signal, a series of random numbers is obtained.
33 \subsection{Pseudo Random Number Generators (PRNGs)}
34 A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG),~\cite{Barker05recommendationfor} is an algorithm for generating a sequence of numbers that approximates the properties of random numbers. The sequence is not truly random in that it is completely determined by a relatively small set of initial values, called the PRNG's state. Although sequences that are closer to truly random can be generated using hardware random number generators, pseudorandom numbers are important in practice for simulations (e.g., of physical systems with the Monte Carlo method), and are central in the practice of cryptography and procedural generation. Common classes of these algorithms are linear congruential generators, Lagged Fibonacci generators, linear feedback shift registers, feedback with carry shift registers, and generalised feedback shift registers. Recent instances of pseudorandom algorithms include Blum Blum Shub, Fortuna, and the Mersenne twister.
37 \section{Cryptographically secure pseudo random number generators}
40 A PRNG suitable for cryptographic applications is called a cryptographically secure PRNG (CSPRNG). A requirement for a CSPRNG is that an adversary not knowing the seed has only negligible advantage in distinguishing the generator's output sequence from a random sequence. In other words, while a PRNG is only required to pass certain statistical tests, a CSPRNG must pass all statistical tests that are restricted to polynomial time in the size of the seed. Though such property cannot be proven, strong evidence may be provided by reducing the CSPRNG to a known hard problem in mathematics (e.g., integer factorization). In general, years of review may be required before an algorithm can be certified as a CSPRNG.
42 Some classes of CSPRNGs include the following:
46 \item Block ciphers running in counter or output feedback mode.
47 \item PRNGs that have been designed specifically to be cryptographically secure, such as Microsoft's Cryptographic
48 Application Programming Interface function CryptGenRandom, the Yarrow algorithm (incorporated in Mac OS X and FreeBSD), and Fortuna.
49 \item Combination PRNGs which attempt to combine several PRNG primitive algorithms with the goal of removing any non-randomness.
50 \item Special designs based on mathematical hardness assumptions. Examples include Micali-Schnorr and the Blum Blum Shub algorithm, which provide a strong security proof. Such algorithms are rather slow compared to traditional constructions, and impractical for many applications.
53 A stream cipher is a cryptographic technique that encrypts binary digits individually, using a transformation that changes with time. This is contrasted to a block cipher, where a block of binary data is encrypted simultaneously, with the transformation usually being constant for each block.
55 In specific applications, stream ciphers are more appropriate than block ciphers~\cite{Preneel03nessied20,Robshaw95streamciphers}:
57 \item Stream ciphers are generally faster than block ciphers, especially in hardware.
58 \item Stream ciphers have less hardware complexity and less memory requirements for both hardware and software.
59 \item Stream ciphers process the plaintext character by character, so no buffering is required to accumulate a full plaintext block (unlike block ciphers).
60 \item Synchronous stream ciphers have no error propagation.
63 \section{Stream Cipher}
64 A stream cipher generates successive elements of the keystream based on an internal state. This state is updated in essentially two ways: if the state changes independently of the plaintext or ciphertext messages, the cipher is classified as a synchronous stream cipher. By contrast, self-synchronising stream ciphers update their state based on previous ciphertext digits.
66 \subsection{One-Time Pad (Vernam Cipher)}
67 In modern terminology, a Vernam cipher is a stream cipher in which the plaintext is XORed with a random or pseudorandom stream of data (the keystream) of the same length to generate the ciphertext. If the keystream is truly random and used only once, this is effectively a one-time pad.
69 Shannon~\cite{shannon-otp} showed that the one-time pad provides perfect security. This means
70 that the conditional entropy of the message $M$ knowing the ciphertext $C$ is the same as the
71 entropy of the original message, i.e. $H(M|C) = H(M)$. He also showed that the one-time
72 pad is optimal in the sense that the previous conditions cannot be achieved with a key of
73 size smaller than the message.
75 The problem of the one-time pad is that we first have to agree on a key of the same
76 length as the message. For most applications this is not practical. The next two schemes
77 try to produce a ``random looking`` keystream from a short key and IV. By random looking,
78 we mean that we cannot distinguish the keystream from a random sequence in a complexity
79 less than trying all possible keys.
81 \subsection{Synchronous stream ciphers}
82 In a synchronous stream cipher a stream of pseudo-random digits is generated independently of the plaintext and ciphertext messages, and then combined with the plaintext (to encrypt) or the ciphertext (to decrypt). In the most common form, binary digits are used (bits), and the keystream is combined with the plaintext using the exclusive or operation (XOR). This is termed a binary additive stream cipher.
84 In a synchronous stream cipher, the sender and receiver must be exactly in step for decryption to be successful. If digits are added or removed from the message during transmission, synchronisation is lost. To restore synchronisation, various offsets can be tried systematically to obtain the correct decryption. Another approach is to tag the ciphertext with markers at regular points in the output.
86 If, however, a digit is corrupted in transmission, rather than added or lost, only a single digit in the plaintext is affected and the error does not propagate to other parts of the message. This property is useful when the transmission error rate is high; however, it makes it less likely the error would be detected without further mechanisms. Moreover, because of this property, synchronous stream ciphers are very susceptible to active attacks -- if an attacker can change a digit in the ciphertext, he might be able to make predictable changes to the corresponding plaintext bit; for example, flipping a bit in the ciphertext causes the same bit to be flipped in the plaintext.
88 \subsection{Self-synchronizing stream ciphers}
89 Another approach uses several of the previous N ciphertext digits to compute the keystream. Such schemes are known as self-synchronizing stream ciphers, asynchronous stream ciphers or ciphertext autokey (CTAK). The idea of self-synchronization was patented in 1946, and has the advantage that the receiver will automatically synchronise with the keystream generator after receiving N ciphertext digits, making it easier to recover if digits are dropped or added to the message stream. Single-digit errors are limited in their effect, affecting only up to N plaintext digits.
91 An example of a self-synchronising stream cipher is a block cipher in cipher feedback (CFB) mode.
95 \section{Chaos-based random number generators}
96 Since the seventies, the use of chaotic dynamics for the generation of random sequences and cryptographical applications has raised a lot of interests. It is clearly pointed out by some researchers that there exists a close relationship between chaos and cryptography, and many research works have been witnessed in the last two decades.
98 chaotic dynamics are usually studied in two different domains, the continuous time domain where the dynamics are generated from a chaotic system specified in differential equations, or a chaotic map quoted with recurrence relationship in the discrete time domain.
100 chaos possesses several distinct propertie, including sensitivity to initial conditions, ergodicity and wide band spectrum. contributing its unpredictable and random manner in practice. Although it is still controversy to equate these properties with randomness and claim a chaos-based random number generator to be good enough, a lot of designs and applications, in particularly, related with the secure communications have been proposed.
102 It is common to use a chaotic map for pseudo-random number generation. Due to the recent design of electonic circuits for the realization fo chaotic systems, it is also possible to generate the bit sequence by observing such dynamics, as a replacement of those physical random sources.
104 \section{Continuous Chaos in Digital Computers}
106 In the past two decades, the use of chaotic systems in the design of cryptosystems, PRNG, and hash functions, has become more and more frequent.
107 Generally speaking, the chaos theory in the continuous field is used to analyze performances of related systems.
109 However, when chaotic systems are realized in digital computers with finite computing precisions, it is doubtful whether or not they can still preserve the desired dynamics of the continuous chaotic systems. Because most dynamical properties of chaos are meaningful only when dynamical systems evolve in the continuous phase space, these properties may become meaningless or ambiguous when the phase space is highly quantized (i.e., latticed) with a finite computing precision (in other words, dynamical degradation of continuous chaotic systems realized
110 in finite computing precision).
112 The quantization errors, which are introduced into iterations of digital chaotic systems for every iteration, will make pseudo orbits depart from real ones with very complex and uncontrolled manners. Because of the sensitivity of chaotic systems on initial conditions, even ''trivial'' changes of computer arithmetic can definitely change pseudo orbits' structures.
114 Although all quantization errors are absolutely deterministic when the finite precision and the arithmetic are fixed, it is technically impossible to know and deal with all errors in digital iterations. Some random perturbation models have been proposed to depict quantization errors in digital chaotic systems, but they cannot exactly predict the actual dynamics of studied digital chaotic systems and has been criticized because of their essentially deficiencies
117 When chaotic systems are realized in finite precision, their dynamical properties will be deeply different from the properties of continuous-value systems and some dynamical degradation will arise, such as short cycle length and decayed distribution. This phenomenon has been reported and analyzed in various situations~\cite{Binder1986,Wheeler1989,Palmore1990,Blank1997,Li2005}.
120 Therefore, continuous chaos may collapse into the digital world and the ideal way to generate pseudo-random sequences is to use Chaotic iterations.
125 \section{Chaos for Discrete Dynamical Systems}
127 Consider a metric space $(\mathcal{X},d)$ and a continuous function $f:\mathcal{X}\longrightarrow \mathcal{X}$, for one-dimensional dynamical systems of the form:
129 x^0 \in \mathcal{X} \textrm{ and } \forall n \in \mathds{N}^*, x^n=f(x^{n-1}),
132 the following definition of chaotic behavior, formulated by Devaney~\cite{Dev89}, is widely accepted:
135 A dynamical system of form~\ref{Devaney} is said to be chaotic if the following conditions hold.
137 \item Topological transitivity:
140 \forall U,V \textrm{ open sets of } \mathcal{X}, ~\exists k>0, f^k(U) \cap V \neq \varnothing
143 Intuitively, a topologically transitive map has points which eventually move under iteration from one arbitrarily small neighborhood to any other. Consequently, the dynamical system can not be decomposed into two disjoint open sets which are invariant under the map. Note that if a map possesses a dense orbit, then it is clearly topologically transitive.
144 \item Density of periodic points in $\mathcal{X}$:
146 Let $P=\{p\in \mathcal{X}|\exists n \in \mathds{N}^{\ast}:f^n(p)=p\}$ the set of periodic points of $f$. Then $P$ is dense in $\mathcal{X}$:
149 \overline{P}=\mathcal{X}
152 Intuitively, Density of periodic orbits means that every point in the space is approached arbitrarily closely by periodic orbits. Topologically mixing systems failing this condition may not display sensitivity to initial conditions, and hence may not be chaotic.
153 \item Sensitive dependence on initial conditions:
155 $\exists \varepsilon>0,$ $\forall x \in \mathcal{X},$ $\forall \delta >0,$ $\exists y \in \mathcal{X},$ $\exists n \in \mathbb{N},$ $d(x,y)<\delta$ and $d\left(f^n(x),f^n(y)\right) \geqslant \varepsilon.$
157 Intuitively, a map possesses sensitive dependence on initial conditions if there exist points arbitrarily close to $x$ which eventually separate from $x$ by at least $\varepsilon$ under iteration of $f$. Not all points near $x$ need eventually separate from $x$ under iteration, but there must be at least one such point in every neighborhood of $x$. If a map possesses sensitive dependence on initial conditions, then for all practical purposes, the dynamics of the map defy numerical computation. Small errors in computation which are introduced by round-off may become magnified upon iteration. The results of numerical computation of an orbit, no matter how accurate, may bear no resemblance whatsoever with the real orbit.
161 When $f$ is chaotic, then the system $(\mathcal{X}, f)$ is chaotic and quoting Devaney: ``it is unpredictable because of the sensitive dependence on initial conditions. It cannot be broken down or decomposed into two subsystems which do not interact because of topological transitivity. And, in the midst of this random behavior, we nevertheless have an element of regularity.'' Fundamentally different behaviors are consequently possible and occur in an unpredictable way.
166 \section{Chaotic iterations}
167 \label{subsection:Chaotic iterations}
170 \label{Chaotic iterations}
171 The set $\mathds{B}$ denoting $\{0,1\}$, let $f:\mathds{B}^{\mathsf{N}%
172 }\longrightarrow \mathds{B}^{\mathsf{N}}$ be an ``iteration'' function and $S\in \mathbb{S}
173 $ be a chaotic strategy. Then, the so-called \emph{chaotic iterations} are defined by~\cite{Robert1986}:
176 \left\{\begin{array}{l}
177 x^0\in \mathds{B}^{\mathsf{N}}, \\
178 \forall n\in \mathds{N}^{\ast },\forall i\in \llbracket1;\mathsf{N}\rrbracket%
182 x_i^{n-1} & \text{if}~S^n\neq i \\
183 f(x^{n-1})_{S^n} & \text{if}~S^n=i.
191 In other words, at the $n^{th}$ iteration, only the $S^{n}-$th cell is
192 \textquotedblleft iterated\textquotedblright . Note that in a more general
193 formulation, $S^n$ can be a subset of components and $f(x^{n-1})_{S^{n}}$ can
194 be replaced by $f(x^{k})_{S^{n}}$, where $k < n$, describing for
195 example delays transmission (see \emph{e.g.}~\cite{Bahi2000}). For the
196 general definition of such chaotic iterations, see, e.g.~\cite{Robert1986}.
198 Chaotic iterations generate a set of vectors (boolean vector in this paper),
199 they are defined by an initial state $x^{0}$, an iteration function $f$, and a chaotic strategy $S$.
200 The next subsection gives the outline proof that chaotic iterations satisfy Devaney's topological chaos property. Thus they can be used to define a new pseudo-random bit generator.
