Abstract
In the last decade, a very interesting relationship between cryptography and chaos theory was developed. As a result of this close relationship, several chaos-based cryptosystems, especially using autonomous chaotic dynamical systems, have been put forward. However, this chapter presents a novel Chaotic Random Bit Generator (CRBG), which is based on the Poincaré map of a non-autonomous dynamical system. For this reason, the very-well known Duffing-van der Pol system has been used. The proposed CRBG also uses the X-OR function for improving the “randomness” of the produced bit streams, which are subjected to the most stringent statistical tests, the FIPS-140-2 suite tests, to detect the specific characteristics that are expected from random bit sequences.
Top1. Introduction
The rapid development of communication technology such as in Internet, in mobile networks and especially in military networks require enhanced security in the transmission of information. This means, that for any possible “intruder” in these networks the possibility of obtaining the information should be extremely low. For this reason, the “randomness” of the generated quantities in the sense that probability of any particular value being selected must be sufficiently small to preclude an adversary from gaining advantage through optimizing a search strategy based on such probability. In recent years, various techniques including the keystream in the one-time pad, the secret key in the DES encryption algorithm, the primes p, q in the RSA encryption and digital signature schemes, the private key a in the DSA, and the challenges used in challenge-response identification systems, have been developed and are commercially available.
In academic community and industry many research teams work on the design of devices or algorithms which are called Random Number Generators (RNGs) that satisfy the basic demand of generating unpredictable quantities. From these devices or algorithms, sequences of random bits can be obtained, which are very useful in many applications. In literature various implementations of Random Bit Generators (RBGs) have been presented. However, all these generators can be classified into three major types, the True Random Bit Generators (TRBGs), the Pseudo-Random Bit Generators (PRBGs) and the Hybrid Random Bit Generators (HRBGs), based on the source of the randomness (Shu, 1995).
The True Random Bit Generators require a naturally occurring source of randomness, which comes from an unpredictable natural process in a physical or hardware device. Until now, a great number of TRBGs based on various physical or hardware processes have been presented, such as the frequency instability of an oscillator (Fairfield, 1987), the integrating dark current from a metal insulator semiconductor capacitor (Agnew, 1986), the elapsed time during radioactive decay (Guide, 1985), the thermal from a resistor and the shot noise, which is a quantum mechanical noise source in electronic circuits (Holman, 1997), the nuclear decay radiation source detected by a Geiger counter attached to a PC and the mutually exclusive events of traveling photons through a semi-transparent mirror (Trcek, 2006), the environmental noise (Bardis, 2009), the amplification of the signal produced on the base of a reverse-biased transistor and the Zener breakdown noise from a reverse-biased Zener diode (Dube, 2008), the mouse movement (Hu, 2009) and the variations in disk drive response times (Davis, 1994).
However, designing a hardware device to exploit this randomness and produce a bit sequence that is free of biases and correlations is a difficult task. Additionally, for most cryptographic applications, the generator must not be subject to observation or manipulation by an adversary. Due to the fact that the TRBGs are based on natural sources of randomness, they are subject to influence by external factors which cause malfunctions.
Key Terms in this Chapter
Nonlinear Element: An electrical element which does not have a linear relationship between current and voltage.
FIPS Statistical Tests: A suite of statistical tests (Federal Information Processing Standards - FIPS) of the National Institute of Standards and Technology (NIST) for testing the “randomness” of random bit generators.
Chaotic Attractor: The attractor for which the approach to its final state in phase space is chaotic.
Poincaré Map: The intersection of an orbit in the state space of a continuous dynamical system with a certain lower dimensional subspace, called the Poincaré cross-section, transversal to the flow of the system.
Chaos: The type of behavior of a complex system, where tiny changes in a system’s initial conditions can lead to very large changes over time.
Random Bit Generator: A computational or physical device designed to generate a sequence of bits that lack any pattern, i.e. appear “random”.
Non-Autonomous Systems: Non-relativistic dynamical systems subject to time-dependent transformations.
Chaos Theory: The field of study in Mathematics that deals with nonlinear dynamics, in which seemingly “random” events are actually predictable from simple deterministic equations.
Bifurcation Diagram: A diagram in nonlinear dynamics, which shows the possible long-term values (equilibria/fixed points or periodic orbits) of a system as a function of a parameter.