A Secret Key Cryptosystem by Iterating a Chaotic Map
Toshiki Habutsu
Yoshifumi Nishio
lwao Sasase
Shinsaku Mori
Department of Electrical Engineering, Keio University

3-14-1 Hiyoshi, Kohoku-ku, Yokohama 223 JAPAN
Tel. +81-45563-1141 Ext. 3319
Fax. +81-45563-3421

Abstract
Chaos i s introduced to cryptology. As an example of the applications, a secret key cryptosystemby iterating a one dimensional chaotic map i s proposed. This system is based on the characteristics

of chaos, which are sensitivity of parameters, sensitivity of initial points, and randomness of sequences
obtained by iterating a chaotic map. A ciphertext is obtained by the iteration of a inverse chaotic

map from an initial point, which denotes a plaintext. If the times of the iteration is large enough, therandohinets of the encryption and the decryption function i s so large that attackers cannot break thiscryptosystem by statistic characteristics. In addition t o the security of the statistical point, even if thecryptosystern is composed by a tent map, which is one of the simplest chaotic maps, setting a finite
computation size avoids a ciphertext only attack. The most attractive point of the cryptosystem isthat the cryptosystem i s composed by only iterating a simple calculations though the information rateof the cryptosystem is about 0.5.

1 Introduction
Random oscillation of the solutions in deterministic systems described as differential or difference equations, is called chaos [l]. Recently many types of chaos-generating systems have been proposed andanalyzed in various fields. Especially, chaotic behavior of solutions i n some types of onedimensional
difference equations

X,+I = F ( X )X, E [a, 11(1)

is investigated in detail [2]. Onedimensional discrete maps F generating chaotic solutions are calledchaotic maps.
Chaotic solutions have the following features.
1. Sensitivity of parameters. - If a parameter (the shape of F ) varies slightly, two sequences o btained from repeated calculations on a chaotic map from an initial point, eventually become quite
different.

2. Sensitivity of initial points. - If an initial point X, varies slightly, two sequences obtained fromrepeated calculations on a chaotic map with a parameter, eventually become quite different.

D.W. Davies (Ed.): Advances in Cryptology - EUROCRYPT '91, LNCS 547, pp. 127-140, 1991.
0 Springer-Verlag Berlin Heidelberg 1991

128

3. Randomness.

- Solutions starting from almost all X o in [0, I] wander in [0,1] a t random and theirdistribution i s uniform.
Therefore. if one doesn't know both the exact parameter and the exact initial point, he cannot expect
the motion of the chaotic solution.
In this paper, we propose a secret key cryptosystem by iterating a onedimensional map F generating
chaos. This system is based on repeated calculations on a chaotic map as X , = F"(X0). We use theparameter Q of the map for a secret key, a n d a point p in an interval [0,1] for plaintext. Encryptionfunction is n-times composite of F-I and decryption function i s n-times composite of F. Therefore,
encryption and decryption are achieved by only repeating a very simple calculation.
Generally, because F i s rn to one map, one plaintext has m" ciphertexts and any one of m"ciphertexts can be deciphered only using the secret key. Therefore, senders can select the ciphertexts

by any arbitrary random generator. We determine the parameter sizes to prevent statistic attacks. If
the times of composite is large enough, it is expected that ciphertext variations act a t random and are
independent of key variations, because of the characteristics of chaotic maps.
We also discuss about a ciphertext only attack. In the following section, we explain our cryptosysternby iterating a tent map. Although tent map has linearity, we can prevent the ciphertext only attackfrom breaking our cryptosystem by setting finite computation size.

2

A Secret Key Cryptosystem by Iterating a Tent Map

In this section, we explain our cryptosystem. As an example of chaotic maps, we use tent map which
is one of the most popular and the simplest chaotic maps.

2.1

Preliminaries

Tent map is a onedimensional and piecewise linear map. Figures l(a) and l(b) show a tent map andi t s inverse map. These maps transform an interval [O, 11 onto itself and contain only one parameter a,which represents the location of the top of the tent. These maps are described as follows.

Xk-1 =
F-' :
xk-1

c*xk

or
= (a- 1)xk

(3)

+ 1.

Sequences calculated from arbitrary initial point with iterating F act chaotically because the function

F is expansionary everywhere i n the interval [0,1]. Such the sequences obtained by iterating a tent
map distribute in uniform U ( 0 , l ) [3].

F is two to one map and F-' is one to two map. Therefore, F" is 2" t o one map and F-" is one
to 2" map. Since X = F ( F - ' ( X ) ) is always satisfied, X = F " ( F - " ( X ) ) i s also satisfied.

129

2.2

Cryptosystem(1) Secret Key
A parameter a denotes a secret key. If a sender and a receiver have a secret key, they are able tocalculate the function F accurately.

(2) Encryptioni) - Set an initial point as a plaintext p , where 0 < p < 1.

ii) - Calculate n-times composite of the inverse map F-"(p) by calculating F-' repeatedly.

c = F-'(F-'(. .. F-'(p) * . .)) = F-"(p).

(4)

On each calculation, select one of two equations of F-' in eq. (3) in any arbitrary way. Thismeans that one plaintext has 2" ciphertexts and one of 2" ciphertexts is sent to the receiver.
Finally, send the value C to the receiver.

(3) Decryption
Calculate n-times composite of the map F"(C) by calculating F repeatedly and recover theplaintext p .

p = F ( F ( . . . F ( C ) .. .)) = F"(C) = F"(F-"(p)).

(5)

Note that only a i s required for this computation. The information about which of two
equations is used for each encryption process ( P I ) , is not necessary for the decryption
process. Any one of 2" ciphertexts, even when the coin-flipping is used in the encryption
process, is deciphered without fail.
Figure 2 visualizes an encryption and a decryption. Firstly, a sender sets an initial point p as aplaintext. On the first step of the encryption, he chooses right or left. If he chooses right, p is mappedto X-'

in the figure. The sender repeats this n times. The receiver only has to do is to trace inversely.

The plaintext p which is eractly equal to a, i s not a singular point. It is easy to confirm that theplaintext is enciphered similar to another plain texts: simply choose right or left side as the otherplaintexts.
The encryption and the decryption are achieved by repeating a simple calculation. They require ntimes m.sltiplications. On the each calculation, it is necessary to set a computation size. There are
two reasons to set it. The first reason is that memory size of computer is finite. The second reason

is about security of our cryptosystem. Because tent map is piecewise linear, our cryptosystem also has
linearity. If ciphertext is described with the whole size digits, there exists a ciphertext only attack to
our cryptosystem because of its linearity. We discuss about this problem in the following section.

130

Discussions

3

In this section, we discuss about the security and performances of our cryptosystem. Firstly, we d etermine the size of the parameters to prevent statistical attack and stepby-step attack. Secondly,
we discuss about the size of ciphertexts to prevent failing decryption. Thirdly, we discuss about the
ciphertext only attack. And finally, we discuss about the other chaotic maps to increase the security.

3.1

Requirements of the Parameters

3.1.1

Secret Key and Plaintext Size

Figures 3(a) and 3(b) show the distribution of the ciphertexts for different parameters. When a is close
to 0.the distribution of ciphertexts is narrow as in figure 3(a) and eavesdroppers have larger probabilityof the achievement of attacking the key. Similarly, a must not be near 1. However when Q i s around

0.5 as in figure 3(b), the distribution of the ciphertexts is uniform enough. Therefore, we assume thatQ

should be between 0.4 and 0.6.
The key space size and the plaintext size are required 64 bits against stepby-step attack. If they

are described with 20 digits, both of the key space size and the plaintext size are about 64 bits.

3.1.2

The Time6 of Mapping : n

If a ciphertext is deciphered with two keys which are slightly different, the sequences are separating as
n is getting larger, and eventually they become independent. Therefore, we determine n so as to satisfy

the following two conditions.

i) By selecting some keys and computing plaintexts by deciphering a ciphertext, the distribution of
the plaintexts for respective keys i s uniform distribution Lr(0,l).

ii) Changing the keys chosen in i)slightly makes the distribution independence from the distributionin i).

If these two conditions are satisfied, attackers cannot expect the plaintext from the ciphertext, as far
as they do not know the accurate key.
Figure 4 shows the distribution of plaintexts obtained from a ciphertext with 1000 keys, wheren = 75. It is shown that the distribution is consistent with uniform distribution U(0,l). Therefore,
condition i) is satisfied.
In order to test the condition ii),we use x2 test. The concept of the methods is as follows. Further
details about the test of independence are in [4].

i) Divide the interval [0,1]into I class intervak.

ii) Compute the N pairs of F,"(C) and F,+b,"(C), and make 1 x 1 contingency table (frequency= kij).

131...
IN) Compute

i=l

>=1

If this value is smaller than the upper 5% point of x2 of which the number of the degrees of
freedom is (I- 1) x (I - 1). the independence is not rejected using the level of significance 0.05.

Figure 5 shows times of mapping n versus x2, where 1 = 11, N = 1000 and Aa =upper 5% point of x:,.

Because theis 124.3, the independence is not rejected when n 2 73.

Leaving a safety margin, we determine that the times of mapping n i s 75.

3.2

Ciphertext Size

Ciphertext size is equal to calculation size. If we have a computer with infinite memory, it is clear thatthe decryption process has no error. However, digital computer's memory is finite, so calculation error
always exist. For this reason, we determine the size S not to occur any calculation error.
Firstly, we discuss about error in encryption process. Encryption function is contractional and its
coefficient is about 0.5. At worst, error is 0.5 x

on each step of encryption and it i s accumulated.

Consequently, the error in encryption process is a t worst

Secondly, we discuss about error in decryption process. Decryption function is expansionary and its
coefficient is about 2. Consequently, the error in decryption process is a t worst

c 2k.

n-1

Ed = 0.5 x lo-'x

k=O

Totally, computation error i s a t worst

E = 2" x E, + Ed = 3 x 2n-' x lo-'.
If this error is smaller than 0.5 x(9)plaintext i s always recovered. Consequently, calculation size

should bes > nlogl,2 + log103+ 20 = 43.05.

(10)

Figure 6 shows the rate of the correct decryption versus the significant digits obtained by a computer
experiment. Since the times of composite of inverse map is 75, the size of ciphertext space is 20 digits+75 bits (= 42.58 digits). Actually, some more digits are required because computation error isaccumulated by each step. As a result, if 44 digits is taken for the computation size, the decryption
process is always correct.
We briefly discuss about the information rate of the cryptosystem. The information rate R i s

R = plaintext size -2o N 0.5.
ciphertext size44

132
If you use FEAL or DES, for example, with a 32 bits message and a 32 bits random number, this system
is similar to our cryptosystern, because its information rate is 0.5 and one message has Z32ciphertexts,

which all can be deciphered with the same decryption key. However, our cryptosystem is only composedof an easy function, which is an interesting point of our cryptosystem.

3.3

Ciphertext Only Attack

Because tent map is piecewise linear. n-times composite of tent map is also piecewise linear. Therefore,

our cryptosystem has also linearity. If computation size is infinite, our cryptosystem is attacked becauseof i t s linearity. First we show the ciphertext only attack, and then we show why this attack does not
succeed to break our cryptmystem.
From the encryption function eq. (3), almost all xk are divided into the following two states, andthus almost a l l ciphertexts are divided into these states.
State 1 : a multiple of aState 2 : 1+ a multiple of a

[Proof]i) First, we think the case when xk is in state 1. If the sender chooses the left side of the tent map
which i s the next &, is in the state 1 because

a t this step, & - I ,xk-1 = a(aAl),(12)

where xk = aA1. If the sendcr chooses the right side of the tent map a t this step, x k - 1 is instate 2 because
xk-1= (a- l)a& + 1 = a(a - 1 ) A g + 1,

(13)

where X, = aA2.

ii) Second, we think the case when X,, is in state 2. Whichever the sender chooses, Xk-1 is in state
1 because+

XLI = @(&A3 I),
where xk = aA3+ 1, and

where xk = aA,

+ 1.

( 14)

iii) Finally, we think the first step of the encryption. Whatever plaintext p is, just after the senderchooses the kft side of the tent map, xk is in state 1. After this state, x k is in state 1 or state

2 as we mentioned above. The only one case which Xk is never in these two states is that thesender chooses the right side of the tent map during all the encryption steps. If the sender chooses
the side randomly, the provability of this is Y r 5Consequently,.
almost a l l ciphertexts are divided
into these states.

133This fact enables attackers the following attack. If an attacker can eavesdrop two ciphertexts CO

a n d Cl, he can obtain the key a after at most four times tests like

where bo and b1 are 1or 0. This is the ciphertext only attack.
Next we show why this attack does not succeed t o break our cryptosystem if we set computation

size. If a sender calculated a ciphertext whose size was infinite, it is described by
key size x n+ plaintext size = 1520 digits(17)

because key size and plaintext size are both 20 digits, and n = 75. If he sent the ciphertext of this size
to receiver and an attacker could eavesdrop it, the attacker can obtain the key ct because the linearity of
our cryptosystem still exists. However, ciphertext can be described by only 44 digits. This means thatthe attacker lacks the information to succeed the attack. In other words, although our cryptosystem is
described by linear functions, setting computation size saves our cryptosystem from the attack.

3.4

Other Chaotic Mapa

As we mentioned above, the ciphertext only attack is avoided by the setting computation size but
the tent map cryptosystem still has linearity. There will exist other types of attacks such as chosen
plaintext attack, known plaintext attack, and so on. We expect that these attack will be based on thecharacteristics of the linearity. We recommend other chaotic maps to avoid these attacks. For example,
a certain of non-linear onedimensional chaotic map meets this condition. Further research is necessary
for this aspect.

4

Conclusions

We have proposed a new secret key cryptosystem by iterating a chaotic map. In the case that we use
a tent map as a chaotic map, we determine the parameter sizes to prevent statistic attacks by xa test,
whose result is that the times of mapping should be larger than 73 if the key size and the plaintext sizeare both 20digits. We verify that correct decryption is achieved if the computation size is larger than

44 digits. We also verify that the computation size prevent the ciphertext only attack from breaking
our cryptosystem. In the proposed system, a plaintext has 2" ciphertexts and one of 2" ciphertexts issent t o the receiver. Even if the ciphertext is chosen by any arbitrary way, the receive: can obtain theplaintext only using the secret key.

Acknowledgement
The authors wish t o thank Dr. Tsutomu Matsumoto a t Yokohama National University for his
valuable suggestions and all the participants of EUROCRYPT 91 for their useful discussions.

134

References[lJ.
]M. T . Thompson and H. B. Stewart: “Nonlinear Dynamics and Chaos”, John Wiley and Sons,

Chichester. 1986.
[2] P. Collet and J. P. Eckmann: “Iterated Maps on the Interval as Dynamical Systems”, Birkhiuser,
Boston. 1980.
[3] S. Oishi and H. Inoue: “Pseudo-Random Number Generators and Chaos”, Trans. IECE Japan,
E65, 9, pp.534-541 (Sept. 1982)[4] G. K. Bhattacharyya and R. A. Johnson: ”Statistical Concepts and Methods”. John Wiley andSons, Tronto, 1977.
[5] T. Habutsu, Y. Nishio. I. Sasase. and S. Mori: “ A Secret Key Cryptosystem Using a Chaotic Map”,
Trans. IEICE Japan, E73.7, pp.1041-1044 (July 1990)

135

1
I
I
I

I

xk+l

i,
0

I
I
I
I

I
I
I
I
I

xk
(b)

Fig.1 (a) Tent map.
(b) Inverse tent map.

1

136

0

x-1

p

Xk
Fig.2 Encryption and Decryption.

---f: Encryption-.

: Decryption

1

137

300

0

50

0

F - lo (X o)

4 I
F-" (Xo)(b)

Fig. 3 The histogram of F-''(X,,)

in 20 intervals [i/2O, ( i+ 1)/20), i = 0,.. . ,19.

(a) a = 0.11 X, = 0.2356

1

1

138

50

1

0

F75(C)
Fig. 4 The histogram of plaintexts obtained from the same ciphertext
for 1000 keys (C = 0.3987):20 intervals [i/20, ( i+ 1)/20), i = 0,. .. ,19.

X

600 --"x

400 --

200 -124.3 -

X

X

X

--

X-x*

- -x x xx x

X X Tx7ir

x

xxX

0

1

n
Fig. 5 The results of xa test.
( ~ : ~ ( 0 . 0=
5 )124.3)

t

140

100

X

0
35

45

40

size (digits)

Fig. 6 The rate of correct decryption.
(Computer simulation : 1000 samples)50