See discussions, stats, and author profiles for this publication at: https://www.researchgate.net/publication/229344343
Chaos-based cryptosystem on DSP ARTICLE in CHAOS SOLITONS & FRACTALS · NOVEMBER 2009 Impact Factor: 1.45 · DOI: 10.1016/j.chaos.2009.03.160
CITATIONS
READS
6
57
4 AUTHORS, INCLUDING: Véronique Guglielmi
Daniele Fournier-Prunaret
Université de Perpignan
Institut National des Sciences Appliqu…
20 PUBLICATIONS 57 CITATIONS
143 PUBLICATIONS 603 CITATIONS
SEE PROFILE
All in-text references underlined in blue are linked to publications on ResearchGate, letting you access and read them immediately.
SEE PROFILE
Available from: Véronique Guglielmi Retrieved on: 15 January 2016
Chaos, Solitons and Fractals 42 (2009) 2135–2144
Contents lists available at ScienceDirect
Chaos, Solitons and Fractals journal homepage: www.elsevier.com/locate/chaos
Chaos-based cryptosystem on DSP Véronique Guglielmi a,*, Pierre Pinel b, Danièle Fournier-Prunaret b, Abdel-Kaddous Taha b a b
Laboratoire ELIAUS, University of Perpignan, 52 Avenue Paul Alduy, 66860 Perpignan cedex 9, France Laboratoire LATTIS, INSA Toulouse, 135 Avenue de Rangueil, 31077 Toulouse cedex 4, France
a r t i c l e
i n f o
Article history: Accepted 30 March 2009
a b s t r a c t We present a numeric chaos-based cryptosystem, implemented on a Digital Signal Processor (DSP), which resists all the attacks we have thought of. The encryption scheme is a synchronous stream cipher. Its security arises from the properties of the trajectories in a chaotic attractor, reinforced by the use of a nonlinear non-invertible two-dimensional map, the introduction of jumps between successive points of the orbits and the retaining of only one bit of the representation of real values. We describe the results obtained through a cryptanalytic study, we detail how to adjust the different parameters of the cryptosystem in order to ensure security, and we apply the NIST (National Institute of Standards and Technology) standard tests for pseudo-randomness to our construction. The originality of this work lies in the end in the way we were able to improve the security of our system, so that it is from now on possible to envisage the use, in more general cryptographic purposes, of other recurrences than those classically employed. Ó 2009 Elsevier Ltd. All rights reserved.
1. Introduction The use of chaotic signals to encipher transmissions has been studied [1] for several years, using for example nonlinear maps to generate pseudo-random sequences [2]. The interest of chaos in this context is double. First of all, sequences that are not periodical, or are periodical but whose periods are great, are easily computable. Next, the use of chaotic maps allows us to generate, by slightly modifying the initial conditions or the parameters, sequences possessing similar distributions but nevertheless never taking the same values; these sequences cannot be reconstructed by anyone ignoring the exact values of the parameters and initial conditions. We propose thus a cryptosystem implementing a symmetric (e.g. private-key) encryption scheme whose keystreams are constituted by the trajectories of a chaotic attractor, whereas the secret key is given by the initial conditions and the parameters of these trajectories. The algorithm is a stream cipher (it encrypts a single bit of plaintext at a time); the generation of the keystreams is independent of the plaintext and the ciphertext (synchronous stream cipher). Well-known stream ciphers, such as linear-feedback shift registers (LFSR) ciphers, RC4 (Rivest Cipher 4 or Ron’s Code 4) and SEAL (Software-optimized Encryption ALgorithm), implement the encryption by exclusively-oring (XOR) a pseudo-random keystream to the plaintext message. Unlike them, the security of our cipher relies on the difficulty to discriminate between two chaotic keystreams: our cryptosystem shifts between different orbits of a same attractor, which are indistinguishable one from another for any adversary. Besides, it uses chaotic sequences generated by a two-dimensional map, which leads to better performances as onedimensional maps generally used for cryptography [3,4].
* Corresponding author. Fax: +33 4 68 66 22 87. E-mail address:
[email protected] (V. Guglielmi). 0960-0779/$ - see front matter Ó 2009 Elsevier Ltd. All rights reserved. doi:10.1016/j.chaos.2009.03.160
2136
V. Guglielmi et al. / Chaos, Solitons and Fractals 42 (2009) 2135–2144
Lastly, its originality also lies in the way we arrived at a secure system satisfying basic requirements for cryptography [5]: both through the introduction of jumps between successive points of the orbits of chaotic attractors and through the retaining of only one bit of the representation of real values. The whole cryptosystem (as well the encoder as the decoder) was implemented on a Motorola MSC8101 fixed-point DSP, using a CodeWarrior C compiler which allows to manipulate IEEE-754 floating-point single-precision real numbers. We also wrote a Matlab application, working in single-precision as well as in double, as a reference to improve the system. Section 2 of our paper describes our cryptosystem and its security features; Section 3 studies it under a cryptanalytical point of view; Section 4 explains how we improved the security of the system; Section 5 examines the quality of its pseudorandomness; and Section 6 summarizes the constraints bearing on the cryptosystem, as well as its performances. 2. Description of the cryptosystem 2.1. Ciphering algorithm Fig. 1 illustrates our cryptographic ciphering scheme, which uses two keystreams {sn } and {tn } stemming from a single chaotic map. In our implementation, we make use of the cubic map T defined by:
xnþ1 ¼ yn ;
ynþ1 ¼ a x3n þ xn þ b y3n þ yn
ð1Þ
where (xn ; yn ) are real variables and (a, b) real parameters. The parameters a and b being fixed, the values of yn follow some orbit of a chaotic attractor of our system, depending on the values of the initial conditions x0 and y0 . Our keystreams will comprise only yn values [6]. For the cubic map defined by (1), the evolution of attractors and their basins (i.e. the set of initial conditions giving rise to iterated sequences converging towards the considered attractor) has been studied and is thoroughly explained in [7]. We consider two different orbits {sn } and {t n }, arising from two different initial conditions chosen inside the basin of an attractor. For the nth bit pn of the plaintext (supposed in binary form) let us describe what the nth enciphered value cn (also in binary form) will be. Before the shift between the 2 orbits, the real values composing these orbits are quantized, and this on only one bit. Within the IEEE-754 floating-point format, the real value sn of the first orbit is coded by N bits (N equals 32 in single-precision or 64 in double-precision): fsn;1 ; sn;2 ; . . . ; sn;N g. Similarly, the real value tn of the second orbit is also coded by N bits: ftn;1 ; tn;2 ; . . . ; t n;N g. We compare the two suites fsn;1 ; sn;2 ; . . . ; sn;N g and ftn;1 ; tn;2 ; . . . ; tn;N g to determine the position i of the first different bit: i is the smallest integer between 1 and N that verifies sn;i – tn;i (when beginning the numbering with the bit of the weakest weight). At the output of the quantizer, we conserve only the ith bit sn;i of sn and the ith bit tn;i of t n . Then, the ciphered value cn shifts between the 2 orbits according to the corresponding value pn of the cleartext:
pn ¼ 0 ) cn ¼ sn;i ;
pn ¼ 1 ) cn ¼ tn;i
ð2Þ
Fig. 1. Encoder block diagram.
V. Guglielmi et al. / Chaos, Solitons and Fractals 42 (2009) 2135–2144
2137
Obviously, the value of i is not fixed but varies with index n. Let us emphasize the different data types. Whatever the index n, the encryption of a single bit pn uses the real numbers sn and t n ; finally, the ciphertext cn contains only one bit. To take a numerical example, let us suppose that, for n given, one has:
sn ¼ 5:811592191069209 101 t n ¼ 4:127794853300177 101 In double-precision for example, the binary representation of sn is (when starting with the bit of the weakest weight):
1100111100010101010111111110110011011011000110010100011111111100 while that of tn is:
1100101111110111001111101010010101011111010101100101101111111101 The first bit different between the representation of sn and that of tn is thus the bit of position: i ¼ 6. At exit of the quantizer, we will have 1 for sn;i and 0 pour t n;i . So the ciphered bit cn will be 1 if pn ¼ 0 and 0 if pn ¼ 1. 2.2. First level of security: chaos sensitivity to initial conditions The encryption security relies on three features. In a classic way in chaotic transmissions, the first one consists in the switching between keystreams sn and tn . Because of the sensitivity to initial conditions (SIC), which is typical of chaotic systems, the sequences {sn } and {tn } will be similar from a qualitative point of view, but will also verify sn – tn for each n. For example, when a ¼ 2:2 and b ¼ 0:91, a chaotic attractor exists (after an initializing period of about 1000 iterations), which can be observed in the phase plane of Fig. 2. Two different sets of initial conditions, numerically as close as possible to each other (in Fig. 2, 0:7 þ 1016 is the next larger value to 0.7 in double-precision format whereas 0:5 þ 1016 is the next larger value to 0.5), lead to two different orbits. The corresponding sequences yn are equally distributed (see Fig. 3), but differ always at least of 105 (in relative distance). They represent real values statistically indistinguishable one from another, as detailed further. 2.3. Second level of security: chaos representation The second security feature is more original: it consists in the one-bit quantization of the real values sn and t n (as previously described). Only one bit of the representation of the real number sn or t n is taken as the ciphertext cn . Due to our simultaneous knowledge of sn and t n , this bit transmitted for each number contains enough information as to determine to which orbit the corresponding real-valued point belongs (in order to be able to decipher). First of all, this allows to have no message expansion: for each plaintext bit, there is one ciphertext bit. Then, it improves the security of the system by decreasing considerably the amount of information carried by the ciphertext: the knowledge of the ciphertext does not give any more to the attacker the knowledge of the points of the chaotic orbits. Therefore, the only attacks possibly victorious, besides that in brute force, are those whose context is very favorable to the attacker (chosenplaintext or chosen-ciphertext attacks that we shall detail further in Sections 3.2 and 3.3). Any attack in a less critical context for the system seems likely to fail, since, from the only transmitted bits (1 bit out of 32 in single-precision or 1 bit out of 64 in double-precision), it cannot go back to the real values of the sequences.
Fig. 2. Phase plane (xn ; yn ) (3000 points shown, from n ¼ 1001 to n ¼ 4000) of the cubic map with parameter values a ¼ 2:2, b ¼ 0:91, for two different sets of initial conditions. Point () marker type: x0 ¼ 0:7, y0 ¼ 0:5; cross () marker type: x0 ¼ 0:7 þ 1016 , y0 ¼ 0:5 þ 1016 .
2138
V. Guglielmi et al. / Chaos, Solitons and Fractals 42 (2009) 2135–2144
Fig. 3. Sequences yn (500 points shown, from n ¼ 1001 to n ¼ 1500) of the cubic map with parameter values a ¼ 2:2 and b ¼ 0:91, for two different sets of initial conditions. Due to SIC, the orbits issued from two very close different initial conditions move away one from the other. Point () marker type: x0 ¼ 0:7, y0 ¼ 0:5 ; cross () marker type: x0 ¼ 0:7 þ 1016 , y0 ¼ 0:5 þ 1016 .
2.4. Third level of security: pseudo-randomness of the orbits In a very general way, it is clear that we can claim a secure system only if the keystreams {sn } and {tn } can be considered as pseudo-random. Among the numerous standard existing tests to test the pseudo-randomness, we applied the tests of the NIST. Then, as we will detail in Sections 4 and 5, we introduce jumps between successive points of the orbits, and this allows to obtain, after quantization on one bit, pseudo-random binary sequences (in the sense that they satisfy the NIST tests). Just like the quantization on one bit only, these jumps represent an original part of our work, part whose principal interest is to allow the use in cryptography of other recurrences than those classically employed, and in particular of a two-dimensional recurrence. 2.5. Deciphering Deciphering is carried out by comparing the ciphertext cn to sn;i and t n;i and deducing the value of pn . The initial conditions and parameter values constitute the secret communication key (set up, e.g., by means of a public-key protocol) and are thus known by the decipherer. We easily and often modify the key, by keeping the same parameters and by changing the initial conditions. And one can also intend to use recurrences of even superior dimension, which increases considerably the space of the keys and thus allows to change them still more often. As both systems calculate and quantize the chaotic sequences independently, we avoid the classical chaos synchronization problem [8] between emitter and receiver. Of course, it implies that the decrypting system computes the chaotic sequences with exactly the same precision than the encrypting one. Besides, let us note that the possible transmission errors do not propagate in the receiver: a one-bit error in a ciphertext no longer affects the decrypted plaintext after one bit. 3. Cryptanalytic study Our cryptosystem is easy to implement and economical in computing time. It takes 4 multiplications at each iteration of (1) if we rewrite the calculation of the ðn þ 1Þth point (xnþ1 ; ynþ1 ) from the nth point (xn ; yn ) as follows:
xnþ1 ¼ yn
Dy ¼ y3n þ yn
ð2 multiplicationsÞ
ynþ1 ¼ aDx þ bDy ð2 multiplicationsÞ
Dx ¼ Dy We study now its security, attaching ourselves to the main characteristic of chaotic sequences: their sensitivity to initial conditions and parameters values. 3.1. Brute force attacks Due to the SIC, a very great number of ciphering keys exist, which allows to replace them often and to accept many interlocutors (each emitter/receiver couple having its own communication key). Besides, this great number of keys makes a ‘brute force’ attack (i.e. systematically trying each possible key value) prohibitive: our tests have demonstrated that, with the same
V. Guglielmi et al. / Chaos, Solitons and Fractals 42 (2009) 2135–2144
2139
computing power as that of the cryptosystem, about 1016 h, that is to say 1140 billion years, would be needed to scan the space of a single initial condition. These tests are detailed in [9]. 3.2. Chosen-plaintext attacks In a far better scenario [10] for the attacker, let us now suppose that he has gained access to an encoder, but without having a physical access to its ciphering key, and that he wants to decrypt messages enciphered with the same key. A ‘chosenplaintext’ attack allows him to produce the sequences {sn } and {tn }, which means considerable power. Indeed, if the sequences {sn } and {t n } are periodic and if they were not one-bit quantized, the attack would succeed in theory: the adversary generates a sequence over one period, then compares the generated values to the challenge ciphertext. In practice, if periods are great enough, the attack fails because of memory size limitations and a too important attack duration compared to the validity time of the key. Here, sequences are necessarily periodic since they are generated on a digital machine (thus with a finite number of different possible values). But, as we will see in Section 6.2, the periods are large enough to ensure security. Anyway, as the sequences are one-bit quantized, the knowledge of both sn and tn is no longer sufficient for an attacker to decipher: the knowledge of the rank n of the iteration becomes also necessary. But n is a priori unknown in a chosen-plaintext attack. So the retaining of only one bit of the representation of real values ruins any attack conducted as described above, and this whatever be the period. We thus conclude that the attacker cannot decipher by using the periodicity of the sequences; he has to build his attack differently. Then, always under a chosen-plaintext model, the ability to produce the sequences {sn } and {tn } results useless to decrypt past ciphertexts if the chaotic map is non-invertible. To decrypt current or future ciphertexts, the attacker may try to match subsequences of the keystream with known or guessed pieces of the cleartext; but this is pointless if it is impossible to deduce the next value of a keystream from the knowledge of its predecessors. So, the security of the system is related with two characteristics of our sequences: their non-invertibility and their non-predictability. 3.3. Chosen-ciphertext attacks We give now the adversary the ability of a chosen-plaintext attack, and also the ability to know the plaintext for ciphertexts of his choice [11] (chosen before obtaining the challenge ciphertext cn or even after). It’s like having temporally access to encryption/decryption equipment (for some particular hidden key), the only restriction being that the attacker may not ask for the decryption of the challenge ciphertext itself. Here, this model appears equivalent to a chosen-plaintext attack. The strength of our system rests ultimately on the difficulty to estimate the parameters a and b of a sequence, knowing a certain number of points of this sequence. So we developed an attack algorithm, based on the research of successive points of a same orbit and the determination of a and b by the Newton–Raphson optimization method. It fails as soon as the encryption scheme skips between points as explained below. 4. Estimation of a chaotic trajectory 4.1. Chaos sensitivity to parameters In a chosen-ciphertext or chosen-plaintext context, the adversary may of course try to guess the parameters a and b of a sequence and build an estimated orbit. However, because of the sensitivity of chaotic systems to parameter values (SP), the estimated orbit will quickly drift away wildly from the true one (except in the exceptional case where the exact values are guessed by chance) after a short transient regime extending at most over 500 points, and it will thus become totally nonexploitable for the attacker. ~ of the parameters a and b: ða ~ – ða; bÞ. We call y the trajectory that the ~ and b ~; bÞ Let us consider a non-exact estimation a n ~ ~ ~ attacker tries to recover and yn the estimate he builds from a and b: yn is generated by (1) starting from the initial conditions ~ as ~ and b ~n is generated by (1) starting from the same initial conditions (x0 ; y0 ) but with a (x0 ; y0 ) with a and b as parameters ; y parameters. ~n allows deciphering only if no other trajectory y0n (of the same attractor than yn ) is closer Whatever the attack algorithm, y ~n cannot serve to distinguish between the points from yn and those from y0n . ~n than yn is. Otherwise, y to y So, we take some orbit y0n of the same attractor as yn : y0n is generated by (1) with a and b as parameters but starting from initial conditions (x00 ; y00 ) different from (x0 ; y0 ). We set, for any index n:
an ¼ yn y~n ; bn ¼ y0n y~n ; dn ¼ y0n yn ~ and the initial conditions (x0 ; y ) ~ and b We were able to notice that, whatever the parameters a and b, their estimations a 0 0 0 and (x0 ; y0 ), a nonzero integer S exists such as, for the S first points (re-indexed from 1 to S):
max jan j min jbn j
n2f1;...;Sg
n2f1;...;Sg
~n is closer to the true orbit yn than to y0n ). (that is, the estimate y
2140
V. Guglielmi et al. / Chaos, Solitons and Fractals 42 (2009) 2135–2144
These S first points constitute the transient regime of the estimation, during which deciphering is possible (see Fig. 4). If the attacker sets a threshold Dt such as:
max jan j 6 Dt min jbn j
n2f1;...;Sg
n2f1;...;Sg
~n j between the challenge ciphertext cn and the estimated orbit y ~n he may decrypt by comparing Dt to the distance cn ¼ jcn y and deciding that:
cn 6 Dt ) pn ¼ 0; cn Dt ) pn ¼ 1 assuming that yn stands for the sequence sn in (2) whereas y0n stands for t n . If the true cipher corresponds to the opposite case, (yn stands for t n whereas y0n stands for sn ) the decrypted message only needs a logical NOT to become correct. ~ do not allow deciphering ~ and b On the contrary, for any index n S, the probability of having j an jPj bn j is about 1=2. a any more because, due to SP, the estimation error a becomes comparable with the distances b and d: all three an , bn and dn have an erratic time evolution, while remaining in the same amplitude interval (between 0.1% and 105 % in relative values) ~n themselves (the order of the relative error and mostly taking values of the same order of magnitude as the points yn , y0n and y is 100%). It is the permanent regime, during which a given orbit yn cannot any more be differentiated from some other orbit y0n of the same attractor. Fig. 5 shows an example of the existence of these two estimation regimes. ~ are to the exact values a and b, the longer is the transient regime, and the ~ and b The closer the estimated parameters a steeper the transition between the 2 regimes. Ultimately, the best estimation of the parameters (other than the exact one) is fixed by the distance eps(x) between a real number x in floating-point format and the closest real number (coded with the same precision). For example, for a ¼ 2:2 or b ¼ 0:91, this distance is about 1016 in double-precision. We have measured ~ equals b þ epsðbÞ, S ranges from 100 to 500 according to the attractors and their ~ equals a þ epsðaÞ or b that, when either a orbits. 4.2. Increase of the map order We hence iterate S ¼ 500 times the map between a value of a keystream and the next one (i.e. we skip 500 points). This allows to avoid the transient regime and makes any estimation of the parameters useless for the attacker, by making the orbits of a chaotic attractor indistinguishable one from another. This ensures also the non-invertibility of our cryptosystem, by increasing the order of the resulting map and so rendering fully impracticable any analytical or numerical attempt to calculate the predecessors of a value. For example, in a chosenplaintext context, it can be demonstrated [12] that the knowledge of successive points of a keystream leads to a polynomial system whose degree (with respect to the parameters a and b) varies exponentially with the number S of points skipped. For the cubic map, our attack algorithm, based on the Newton–Raphson method, fails as soon as we skip at least 4 points between each value of a keystream (the degree then equals 40). When S ¼ 500, the system owns about 10238 solutions and so is totally unsolvable. 5. Pseudo-randomness of the chaotic orbits 5.1. The standard NIST tests Among the numerous standard tests for pseudo-randomness, a convincing way to show the randomness of the produced sequences is to confront them to the Statistical Test Suite of the NIST (National Institute of Standards and Technology). The NIST has developed a package of statistical tests to detect deviations from randomness in binary sequences produced by ran-
Fig. 4. Qualitative representation of the transient regime.
V. Guglielmi et al. / Chaos, Solitons and Fractals 42 (2009) 2135–2144
2141
Fig. 5. Transient and permanent regimes of the estimation. True parameters values: a ¼ 2:2, b ¼ 0:91; estimated ones: 2.2, 0:91 þ 1016 . Two different sets of initial conditions: (0.7, 0.5) and (0:7 þ 1016 ; 0:5 þ 1016 ). Point () marker type: distance an ; cross () marker type: distance bn .
dom number generators (RNG) or pseudo-RNG. These tests focus on a variety of different types of non-randomness that could exist in a sequence. More information about description and meaning of all the tests can be found in [13]. The latest version of the test suite (version 1.8, March 22, 2005, available on line at http://csrc.nist.gov/rng/) contains: the Frequency (Monobit) test, the Frequency test within a Block, the Cumulative Sums tests (2 tests), the Runs test, the test for the Longest Run of Ones in a Block, the Binary Matrix Rank test, the Discrete Fourier Transform (Spectral) test, the Maurer’s ‘‘Universal Statistical” test, the Approximate Entropy test, the Serial tests (2 tests), the Linear Complexity test, the Overlapping (Periodic) Template Matching test, the Random Excursions tests (8 tests), the Random Excursions Variant tests (18 tests) and the Non-overlapping (Aperiodic) Template Matching tests (148 tests). So the NIST V1.8 Test Suite consists in fact in a battery of 188 statistical tests, proved by the NIST to be without large redundancy and able to detect a reasonable range of patterned behaviours. Each test gives rise to a P-value, which is the probability that a perfect random number generator would have produced a sequence less random than the sequence that was tested (given the kind of non-randomness assessed by the test). We have performed the 188 tests of the V1.8 NIST Test Suite on two samples. Each sample is constituted of 100 binary sequences {sn;i }, generated by the cubic map from 100 initial conditions for {sn } and 100 different initial conditions for {tn }, with parameter values a ¼ 2:2 and b ¼ 0:91. Each sequence is a 106 elements sequence, corresponding at the ciphered output of our cryptosystem when the 106 plaintext bits always equal 0. The first sample has been generated without jumps between successive points of the orbits {sn } and {t n }, whereas the second sample has been generated with 500 jumps between successive points. For each sample, a set of 100 P-values is produced for each of the 188 tests of the suite, corresponding to the set of sequences. A sequence ’passes’ a test whenever the P-value equals or exceeds the level of significance of the test and fails otherwise. The level of significance of the test is the probability that the test will indicate that the sequence is not random when it really is random. Prior to the tests, we have set the level of significance to 0.01 (a common value in cryptography). But, to conclude regarding the randomness or non-randomness of the sequences of a sample, a more in-depth analysis of the 18,800 P-values must be performed. This interpretation of test results can be conducted in a number of ways. We have adopted the two approaches recommended by NIST: the examination of the proportion of sequences that pass a statistical test and the distribution of P-values to check for uniformity. 5.2. Proportion of sequences passing a test For each test, we compute the proportion of sequences that pass. The range of acceptable proportions is determined using a confidence interval: if the proportion falls outside of this interval, we will consider there is evidence that the data is nonrandom. It is easily to demonstrate that the confidence interval can be defined by:
rffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi ^ ð1 p ^Þ p m
^3 p
^ ¼ 0:99, and m is the sample size. where p With the exception of the 8 Random Excursion tests and the 18 Random Excursion Variant tests, the minimum pass rate is approximately 0.960150 and the maximum pass rate 1.019850 (then bounded of course by 1). The 8 Random Excursion tests and the 18 Random Excursion Variant tests are applicable only to 37 sequences (out of 100) for the first sample and 68 sequences for the second sample. Then, the minimum pass rate for the first sample is approximately 0.940928 whereas the maximum pass rate is calculated to be 1.039072 and so is of course bounded by 1; the
2142
V. Guglielmi et al. / Chaos, Solitons and Fractals 42 (2009) 2135–2144
minimum pass rate for the second sample is approximately 0.953802 whereas the maximum pass rate is calculated to be 1.026198 and so is of course bounded by 1. The proportions of sequences passing the tests are plotted in Fig. 6 for the first sample and in Fig. 7 for the second one. The tests are indexed from 1 to 188, in order of the tests list previously given. It can be observed that the 188 proportions are all in the confidence interval for sequences generated with jumps between successive points, whereas only 63 proportions are in the confidence interval for sequences generated without jumps. 5.3. Uniform distribution of the P-values of a test For each statistical test, the distribution of P-values must be examined to ensure uniformity. To do so, for each of the 188 statistical tests, we perform a chi-square test of the null hypothesis that the P-values calculated by the test are uniformly distributed, against the alternative that they are not. And we reject the null hypothesis at the 0.1% significance level. For sequences generated without jumps between successive points, 119 of the 188 tests have P-values that cannot be considered uniformly distributed; for sequences generated with jumps, each of the 188 tests leads to P-values uniformly distributed. 5.4. Conclusions of the tests So the analysis of the P-values, conducted both in the way of the proportion of sequences that pass a statistical test and in the way of the distribution of P-values, does not indicate a deviation from randomness, as long as we introduce jumps between successive points of the chaotic orbits. A conclusion as for the quality of the binary ciphering sequences produced by our cryptosystem can therefore be made: these sequences are random enough for RNG application and for transmission and cryptographic applications, at least as regards their statistical properties (it is clear that no set of statistical tests can serve as a substitute for cryptanalysis, cf. Section 4). 6. Performances and constraints 6.1. First constraint: skipping points As seen previously, it is at the relatively low price of 500 supplementary iterations between each point of a keystream that we can satisfactorily consider our numeric chaotic sequences as, at the same moment, statistically indistinguishable, non-invertible and pseudo-random.
Fig. 6. Proportions of sequences passing the NIST Tests, without jumps between successive points. Cubic map with parameter values a ¼ 2:2 and b ¼ 0:91.
V. Guglielmi et al. / Chaos, Solitons and Fractals 42 (2009) 2135–2144
2143
Fig. 7. Proportions of sequences passing the NIST Tests, with 500 jumps between successive points. Cubic map with parameter values a ¼ 2:2 and b ¼ 0:91.
6.2. Second constraint: precision of the numbers Another constraint is to represent the values of the keystreams in double-precision, in order to generate orbits with great enough periods. Because of the finite number N of real values which can be coded digitally, any sequence of points becomes periodic when it is implemented on a microprocessor. Our sequence being generated by an order 2 map (i.e. yn is function of yn1 and yn2 ), its period P lies between 1 and N 2 (hence the interest of an order 2 or more). Moreover, an attractor is limited in size (see Fig. 2), which still reduces the possible maximum value of P. The smallest values of P that we have found correspond to a ¼ 2:2 and b ¼ 0:91, which yield P = 187,490 in single-precision, whereas N 2 ¼ 18 1018 and the attractor size reduces this possible maximal value of the period to 4:33 1016 . In doubleprecision, P = 227,104,267, while N 2 ¼ 3:4 1038 and the attractor size reduces this maximal value to 1035 . It is the worst case: for example, if b ¼ 0:99 instead of 0:91, P becomes about 106 in single-precision and is higher than 1013 in double. 6.3. Performances of the cryptosystem We arrive ultimately at the following dimensioning for our cubic map. Taking a wide security margin, we suppose P superior or equal to 108 and we replace the key as soon as 108 bits have been enciphered. We work in double-precision format. If the number S of jumps between successive points and the period P of the sequence have a common divisor (other than 1), the period of the suite, after skipping, will be divided by this common divisor. So, to avoid a decrease of the period, we vary periodically the number of jumps, by successively taking for S one of the 5 prime numbers closest to 500 per higher value: we skip 503 points between two values of the keystreams, then 509 points between the next values, then 521 points, then 523 points, then 541 points, then again 503 points, and so on. Doing this leads to a suite, after skipping, which is still periodic of period superior or equal to 108 . If one page of text contains about 4000 characters, 3125 pages could be encrypted safely with the same key. Let us note that a simple way to still improve these performances would be to increase the arithmetical precision of the calculations, by working for example on binary representations of real numbers constituted by 512 bits instead of 64. This would allow to increase very significantly at the same time the period of the generated orbits and the space of ciphering keys, without increasing the binary rate of transmission since we would always preserve in the end only a single bit by point. 7. Conclusion Our cryptosystem works and resists all the attacks which we set up. It is classically based at first on shift-keying between two chaotic sequences according to the value of the plaintext, but it is enhanced by two supplementary features: the intro-
2144
V. Guglielmi et al. / Chaos, Solitons and Fractals 42 (2009) 2135–2144
duction of jumps between successive points of the orbits and the retaining of only one bit of the representation of real chaotic values. So its strength resides both in the impossibility to estimate chaotic sequences (due to the number of iterations performed between the successive values) and in the impossibility to estimate real numbers of the chaotic sequences (due to the transmission of only one bit of the floating-point representation). The secret communication key of the system can be changed easily and often, by modifying the values of the initial conditions and keeping the same parameters. Then, using an order 2 map increases both the space keys and the period of the sequences when coded on our processor, and thus makes the cryptosystem more powerful. We plan to continue our work by using maps of dimension at least equal to 3. Indeed, the originality of our system lies in the fact that, thanks to the improvements of the security which we were able to realize (the introduction of jumps and the retaining of only one bit), it works correctly while basing on a recurrence seeming a priori little adapted. Thus, it is henceforth possible to approve in cryptography more recurrences than those usual, and in particular to pass to recurrences of superior dimensions, which should allow to reach better global performances. Acknowledgement This work was supported in part by the French Fonds National pour la Science (ACI ‘Transchaos’ 4E01). References [1] Kocarev L. Chaos-based cryptography: a brief overview. IEEE Circuits Syst Mag 2001;1:6–21. [2] Kocarev L, Jakimoski G. Pseudorandom bits generated by chaotic maps. IEEE Trans Circuits Syst I 2003;50:123–6. [3] Stojanovski T, Kocarev L. Chaos-based random number generators – part I: analysis [cryptography] and part II: practical realization. IEEE Trans Circuits Syst I 2001;48:281–8. and 382–5. [4] Chargé P, Fournier-Prunaret D, Guglielmi V. Features analysis of a parametric PWL chaotic map and its utilization for secure transmissions. Chaos, Solitons & Fractals 2008;38:1411–22. [5] Alvarez G, Li S. Some basic cryptographic requirements for chaos-based cryptosystems. Int J Bifurcat Chaos 2006;16:2129–51. [6] Bénéteau L, Fournier-Prunaret D, Guglielmi V, Pinel P, Rouabhi S, Taha AK. Two encryption schemes using the chaotic dynamics of two-dimensional noninvertible maps. In: Complements to proceedings of the international conference on nonlinear dynamics of electronic systems (NDES’02), Izmir, Turkey; June 2002. [7] Fournier-Prunaret D, Guglielmi V. Bifurcations and attractors in two-dimensional maps of cubic type. In: Proceedings of the international symposium on nonlinear theory and its applications (NOLTA’99), Hawaii, USA; November–December 1999. [8] Chu Y-H, Chang S. Dynamical cryptography based on synchronized chaotic systems. Electron Lett 1999;35:974–5. [9] Guglielmi V, Besnard PY, Fournier-Prunaret D, Pinel P, Taha AK, Bénéteau L. Un système numérique de cryptographie basé sur les propriétés des signaux chaotiques discrets. In: Proceedings of the GRETSI 2003, Paris, France; September 2003. [10] Sobhy MI, Shehata AR. Methods of attacking chaotic encryption and countermeasures. In: Proceedings of the international conference on acoustics, speech and signal processing, Salt Lake City, USA, vol. 2; May 2001. p. 1001–4. [11] Alvarez G, Montoya F, Romera M, Pastor G. Cryptanalysis of a chaotic secure communication system. Phys Lett A 2003;306:200–5. [12] Guglielmi V, Bonnefont M, Fournier-Prunaret D, Pinel P, Taha AK. Performances d’un cryptosystème numérique à base de chaos. In: Proceedings of the GRETSI 2005, Louvain-la-Neuve, Belgium; September 2005. [13] Revised NIST special publication 800-22. A statistical test suite for random and pseudorandom number generators for cryptographic applications; May 15, 2001. .
