An FPGA Implementation of a Chaotic Encryption Algorithm

Introduction 2
cope with these requirements, the couple VHDL-FPGA has been chosen, along with
a divide-and-conquer approach and a software suite provided by Mentor Graphics,
as rapid and ef cient development tools.
1.1. Chapter Organization
The main structure of the present work is divided in four parts.
The  rst chapter gives a general overview of cryptography science, introducing
some basic terminology, the concept of cryptosystems and two fundamental encryp-
tion techniques, permutation and substitution. The chapter continues with general
remarks about chaos which are the background for Kolmogorov chaotic systems and
pseudo-random sequences. Only topics that are needed for the subsequent Scharin-
ger’s algorithm description are presented.
The topic of chapter 3 is related to tools and method adopted in this thesis. A
brief description of what an FPGA is constitutes the  rst section which in turn is
followed by an explanation of concepts of entity, architecture, con guration and
generic parameter proper to the VHDL language. The  nal discussion is for the
used development suite and other chosen software tools, along with the adopted
methodology.
Chapter 4 forms the main part of the corpus. Here the fundamental ideas that
have been used to implement in hardware the encryption algorithm are treated. The
chapter opens with a description of the chief components constituting the  rst real-
ization that aimed to demonstrate the algorithm feasibility. Limits analysis and in-
verse Kolmogorov  ow study represent the starting point for a new approach called
one-shot and discussed in the subsequent section. The possibility offered by using
more than one memory bank concludes the chapter.
The last chapter is devolved to performance evaluation. For both  rst and one-
shot implementation, consume of physical resources and throughput capacity are
reported and summarized in two tables.
2 Description of a ChaoticCipher
Background and description of the cryptographic algorithm presented in this work
are the main subjects to which this chapter is devolved. The  rst section is an
introduction of cryptology science, its terminology and a brief de nition and clas-
si cation of cryptosystems, whereas the next one is related to chaos and chaotic
systems, particularly Kolmogorov  ows. At the end of the chapter, these two topics
will be joint together to describe in detail the actual algorithm.
2.1. General Remarks About Cryptography
In this section rudimentary concepts of cryptology science are introduced. The  rst
subsection de nes technical terms common in this discipline and used throughout
the rest of the work, while subsection 2.1.2 distinguishes different points of view
from which a cryptosystem can be seen. The objective of this section is to  nd a col-
location in the cryptography panorama for the algorithm implemented in hardware
for this work.
2.1.1. Basic Terminology
The word cryptography refers to the science of keeping secrecy of messages ex-
changed between a sender and a receiver over an insecure channel. The objective is
achieved by encoding data so that it can only be decoded by speci c individuals.
The original message M being wanted to be sent is called plaintext since it is
clearly intelligible, whereas the term used to refer to the message C being transited
over an insecure channel is ciphertext. The process E of transforming a plaintext
into a ciphertext is called encryption, while the opposite procedure D that turns a
ciphertext into a plaintext at the receiver’s side is said decryption. In symbols
E(M) = C
D(C) = M
Description of a Chaotic Cipher 4
M C M
E D
ke kd
Figure 2.1: Encryption and decryption with a key.
A cryptographic algorithm is composed of the mathematical function used for
encryption and its related inverse-function for decryption. A cryptographic algo-
rithm is some times referred as cipher. The security of an algorithm can rely on the
secrecy of its function, when quality, standardization and mass utilization is not a
concern [12]. Where these restrictions can not be tolerated (basically in any prac-
tical situation), the problem is solved by means of a key, denoted with k. This key
might be any one of a large number of values, which all together form the keyspace
K. Two different keys ke and kd for encryption and decryption respectively might
be used. Once more in symbols:
Eke(M) = C
Dkd(C) = M
Finally, a cryptosystem is an algorithm plus all possible plaintexts, ciphertexts
and keys.
2.1.2. Classi cation of Cryptosystems
As seen, de nitions and symbology introduced in the previous section can be sum-
marized by the general concept of cryptosystem, whose picture is shown in  g-
ure 2.1. In regard to the kind of distribution method established for the keys, the
way a cipher treats the plaintext and the type of implementation support chosen, a
cryptosystem can be seen under several points of view. A look at them will allow
us to have an idea of the collocation of the present algorithm within the vast  eld of
cryptography.
Distribution of the Secret Key
The  rst big classi cation to which cryptographic algorithms might be undertaken
is the distinction between the methods with which keys are distributed. When en-
cryption key ke and decryption key kd are identical, i.e. ke ≡ kd, sender and receiver
Description of a Chaotic Cipher 5
must agree on a secure channel through which transmitting the key without anybody
else  nding out. This is the most extensively used method and is often accompanied
by the adjective symmetric because of the equivalence of the keys. Contrarily, the
asymmetric method makes use of a pair of keys for each individual  one public
and the other private1.
Block and Stream Cipher
Another big classi cation for cryptographic algorithms consists of subdividing ci-
phers into two categories: stream ciphers and block ciphers. A stream cipher is so
called because it works on a stream of data, normally one bit (but some time also
one byte or 32 bit) at a time: as soon as a new value of plaintext arrives, the corre-
spondent cipher value is computed. On the other side, a block cipher operates on
the plaintext one block at a time: a new block of ciphertext can not be evaluated
until the previous block is  nished. Moreover, a block cipher will encrypt the same
plaintext with the same key always to the same ciphertext, while for a stream cryp-
tosystem the output depends also on the history of the cipher  this leads to the
problem of synchronization between encryption and decryption processes.
A cipher can operate in several cryptographic modes in regard to the way the
plaintext, key and ciphertext interact with each other. Electronic Codebook (ECB)
mode represents the more straightforward and simple solution for a block cipher.
Once the key is  xed, the system will always encrypt the same block of plaintext
into the same block of ciphertext, without regard to other parameters. This mode
can be thought of as a double entry look-up table. While implementations can be
extremely fast, this mode is also very memory demanding since a table is necessary
for every couple of plain- and ciphertext and for each key k ∈ K. The counterpart
of ECB is the Cipher Block Chaining (CBC) mode in which new ciphertext blocks
depend, by means of a sort of feedback mechanism on previous outputs.
Besides ECB and CBC, Ciphertext Feedback (CFB) represents a mode to run
block ciphers as stream ciphers. This statement means that output values from a
cryptosystem are serialized as in a stream cipher, but rely somehow on the pre-
vious computed values as in a block cipher. The mechanism used to realize this
mode generally consists of a shift register into which new values are pushed and
on which the encryption algorithm depends. Another solution consists of using a
Pseudo-Random Number Generator (PRNG). It is worth noticing that in any case
the mechanism has to be initialized with an initialization vector which concurs, be-
sides the key, to effect the encipherment output for a given sequence of plaintext’s
data. This means that the ciphertext depends on previous blocks such as a stream
cipher. Nevertheless, if the initialization vector depends on the key and the keys ke
1For further reference see W. Dif e and M. E. Hellman,  New Directions in Cryptography ,
IEEE Transactions on Information Theory, v. IT-22, n. 6, Nov. 1976, pp. 644-654.
Description of a Chaotic Cipher 6
and kd match, there are no synchronization problems and ciphertext can be correctly
deciphered.
Hardware Versus Software Implementation
The kind of algorithm classes being explained in this subsection do not have well-
de ned boundaries, that is, an algorithm can be moved from a class to another due
to a technological improvement or a smarter implementation. In fact, any crypto-
graphic algorithm might potentially be designed either for an hardware project and
for a software program, but many times the involved operations render one of the
two solutions (and sometimes both) impracticable or inconvenient.
A software implementation has, on its side,  exibility throughout different ap-
plications, portability from one platform to another, ease of use and ease of upgrade
of the binary or source code. The disadvantages are in speed  especially if the
algorithm belongs to the category of stream ciphers  ease of modi cation and
manipulation by third party.
On the other side, a hardware implementation suffers mainly of de ciency in
mathematical abilities, since operations as multiplications and divisions are nor-
mally dif cult or cost prohibitive for realization. Nonetheless, the advantages abun-
dantly overcome the inadequacies. The  rst is speed. Dedicated hardware  pos-
sibly another chip beside the main CPU  will always win a speed race against
a general-purpose processor, especially if the cryptographic algorithm is a sort of
stream cipher.
Besides speed, security reasons play a great role. A dedicated hardware has got
a physical barrier to be surmounted before reading internal variables. Codes can
be burned into the chip and tamper-proof can prevent someone from modifying a
hardware encryption device [12]: chemical substances can be used to destruct the
chip’s logic in case a third party accesses the interior.
A  nal reason relies on ease installation as simple device between two existent
peripherals.
2.1.3. Confusion and Diffusion
The main objective of cryptology is to achieve the perfect secrecy [12] by which no
information of the plaintext can be extracted from the ciphertext. The only crypto-
graphic algorithm able of such a performance is called one-time pad2 where each
character of the plain-message is ciphered with exactly one random number picked
out from a truly random sequence which can be used only once for only one mes-
sage.
2See for example D. Kahn, The Codebreakers: The Story of Secret Writing, New York, Macmil-
lan Publishing Co., 1967
Description of a Chaotic Cipher 7
Since the one-time pad only has a theoretical validity and any other cipher is
an approximation of it, every ciphertext unavoidably yields some information about
the corresponding plaintext. In part this is also due to the redundancy to which a
natural language is subjected, i.e. the fact that a plaintext contains more symbols
than those necessary to provide the same amount of information. A good algorithm
will tend to reduce redundancy to a minimum.
According to [12] who cites Shannon3 the two basic techniques for conceiving
redundancies, beside using a compression algorithm, are called confusion and diffu-
sion. Confusion seeks to reduce the correlation between the input plaintext and the
output ciphertext. The task is generally accomplished substituting every fundamen-
tal block of data for another one according to the rules dictated by the cryptographic
algorithm. Despite this, repetitions or well-known sequence of blocks in the plain-
text are still kept at the output. This problem is addressed by diffusion: a data on the
input block is transposed to other coordinates on the output block. Put in another
way, diffusion changes the position of data, while, during a confusion process, the
data itself is modi ed. It is to be observed that diffusion implies a block cipher,
whereas confusion can deal with streams of data, as well.
2.2. Chaos and Kolmogorov Flows
This section is opened by a simple introduction to chaos theory which is followed
by a brief de nition of two characteristics that distinguish some chaotic systems:
ergodicy and mixing-property. A discussion about Kolmogorov  ows related to the
application for this work closes the section.
2.2.1. Basic Introduction to Chaos
Uncountable de nitions have been given in seeking to formally describe chaos and
chaos theory as a branch of mathematics. In this ambit, only a qualitative descrip-
tion suitable for comprehension of the algorithm highlighted in section 2.3 is faced.
Let’s start this introduction to chaos speaking about the mathematical problem
of having two bodies in space. Solving the system of differential equations that
arise from the application of Newton’s law, the trajectories of the two bodies are
completely described in terms of space and time by the well-known gravity law.
This means that, given the initial conditions, all the parameters that govern the
system  i.e. position, velocity and acceleration  can be determined for each of
the two bodies at any time. Because of this, the system is said to be deterministic.
When a third body is introduced into the system, the property of the system of
having a closed solution no longer holds to be true. The system of differential equa-
3C. E. Shannon,  Communication Theory of Secrecy Systems , Bell System Technical Journal,
v. 28, n. 4, 1949, pp. 656-715
Description of a Chaotic Cipher 8
Figure 2.2: Divergence due to sensitive dependence to initial conditions.
tions still describe completely the behaviour of the three bodies, but the knowledge
of the position of each element in the system at a given time t can be calculated
only by iterating the differential equations written in discrete form starting from the
initial condition up to time t. In other words, the output from the previous step is
the input of the next iteration and a general solution can not be expressed using only
one equation. The system belongs to the category of non-linear systems.
A third characteristic distinguishes the system of three bodies in space: density.
A system is dense when, without regard to the distance between two legal points in
the system, there always exists a third point between them.
These properties lead, for a reason that will not be discussed here, to another
proposition by which chaotic systems are referred  sensitive dependence on initial
conditions. To provide a general idea of such dependence without entering into the
mathematical realm, let’s suppose to record the trajectory followed by the system
starting with the initial condition t0. Let’s also suppose to choose another condition
t1 very close, thank the denseness property, to t0. If the trajectory of t1 diverges
sensitively from the one of t0 (see  gure 2.2), it is impossible, chosen a third initial
condition t2, to predict what trajectory the system will follow. In this sense, the
system appears to behave randomly.
Summarizing the notions so far introduced, a chaotic system might be de ned
as a non-linear deterministic system so sensitive to initial conditions that it appears
random. It is remarkable observing that here two antonyms as deterministic and
random are used in the same sentence, since chaos theory effectively forms a bridge
between two dissimilar sciences  mathematics and probability.
2.2.2. Kolmogorov Chaotic Systems
In the prior subsection a general view of what a chaotic system represents has been
outlined. Here the discussion is going ahead showing that the Kolmogorov  ows
belong to a hierarchy of chaotic systems with speci c characteristics.
Description of a Chaotic Cipher 9
(a) (b) (c)
Figure 2.3: The remarkable differences in behaviour in  phase space between a
simple system (a), a so-called ergodic system (b) and a mixed ergodic system (c)
which is chaotic.
Ergodic- and Mixing-Properties
It is possible to imagine a chaotic system as a point tracing a trajectory in space.
The rules governing the system often keep the point within a region E that is called
the phase space of the system. In general, the function that describes the system
maps values taken from E in itself, but not necessarily all values from the phase
space are mapped so that all E is covered. If the set of chaotic system is restricted
to systems whose output coincides with the whole phase space E, we are working
with a subset that takes the name of ergodic systems.
At a higher level of the hierarchy, there exists another class of chaotic systems
which possesses a new property called mixing property. This name refers to the par-
ticular characteristic that some ergodic systems show to have. Exploiting a simple
comparison to clear the idea, it can be said that a system is mixing when it spreads
out into ever  ner  bres until it covers the entire phase space such as a drop of ink
spreads out chaotically in water (see  gure 2.3(c)). This behaviour is due to the fact
that trajectories diverge from each other exponentially fast.
K-Flows
Continuing to go up the hierarchy of the randomness, a smaller subset of systems
showing mixing and ergodic properties can be identi ed. This new sort of systems
are called K- ows . The  K stands for Kolmogorov 4, a Russian mathematician
whose work in uenced several branches of modern mathematics, while the noun
  ow comes out from the fact that this kind of systems are widely spread among
researches where collisions between particles dominate the dynamics. K- ows dis-
tinguish from other chaotic systems since they possess the remarkable property that
4Born April 25, 1903, in Tambov, Russia and died October 20, 1987, in Moscow.
Description of a Chaotic Cipher 10
y’
x x’
y
11/4 1
y3/4
y1/4
y1y1
3/4
Figure 2.4: Some sample points mapped by Tpi.
their next measurement can not be predicted even after an in nite number of prior
measurements.
For this work the Kolmogorov  ows described in [10] and [11] will be used.
The continuous version Tpi of this system can be expressed using the following
mathematical notation. Let pi = (p1, p2, . . . , pk) be a sequence of numbers with the
properties that pi ∈ R, 0 < pi < 1 and
∑
i
pi = 1, where i = 1, . . . , k. Let also
the unit-square E = [0, 1) × [0, 1) denote the phase space of the system and Fs be
de ned as follow
Fs =
{
0 for s = 1
p1 + . . .+ ps−1 for s = 2, . . . , k (2.1)
Then the application Tpi : E→ E on (x, y) ∈ [Fs, Fs + ps)× [0, 1) is expressed by
the following relation
Tpi(x, y) =
(
1
ps
(x− Fs) , yps + Fs
)
(2.2)
and Tpi(x, y) ∈ [0, 1)× [Fs, Fs + ps).
In other words, the phase space E is divided into horizontal strips of dimensions
1 × ps and bounded on the left and on the right by Fs and Fs + ps, respectively.
Every point (x, y) of each strip is mapped according to Tpi into a vertical strip of
size ps × 1 (see  gure 2.4).
In order to deal with a digital circuit, the application Tpi just de ned has to
be modi ed in a way that works with discrete values. This task can be accom-
plished thinking about the phase space as a subset of natural numbers, i.e. En =
Description of a Chaotic Cipher 11
[0, n) × [0, n) ⊆ N2, where n is the dimension of the square phase space. If δ =
(n1, n2, . . . , nk) is a list of positive integers that holds the properties 0 < ni < n
and
∑
i
ni = n, where i = 1, . . . , k, then the discrete version of the K- ow de ned
by eq. (2.2) will be identi ed by Tn,δ.
To be suitable for our purposes, the application Tn,δ : En → En just introduced
has to possess another property. In order to avoid a generic division operation in-
duced by the term 1/ps, ni must divide n without any reminder. Thus, a new se-
quence of positive integers can be de ned as qs = n/ns, where s = 1, 2, . . . , k. If
Ns is still the left border of the s-th vertical strip
Ns =
{
0 for s = 1
n1 + . . .+ ns−1 for s = 2, . . . , k (2.3)
then the application on (x, y) ∈ [Ns, Ns + ns) × [0, 1) that approximates the best
the corresponding chaotic continuous system is given, according to [10], by the
following relation
Tn,δ(x, y) =
(
qs(x−Ns) + (y mod qs) , (y div qs) +Ns
)
(2.4)
and Tn,δ(x, y) ∈ [0, 1)× [Ns, Ns + ns).
As we are concerned of security purpose, the dimension of the square phase
space must be as big as possible. In fact, increasing n results in a greater number of
different valid parameters δ from which it is possible to choose.
The operations division and modulus of eq. (2.4) are between integer numbers.
Their de nition is as follow
a = b · d+ r ⇒
{
a div b = d
a mod b = r (2.5)
where a, b, d and r are natural numbers, r < b and b 6= 0.
Finally, it can be observed that the K- ow Tn,δ is bijective. De ning the upper
border of the s-th horizontal strip
Ms =
{
0 for s = 1
n1 + . . .+ ns−1 for s = 2, . . . , k (2.6)
points (x′, y′) ∈ [0, 1)×[Ms,Ms+ns) can be mapped back to [Ms,Ms+ns)×[0, 1)
by the inverse T−1n,δ given by
T−1n,δ (x
′
, y′) =
(
(x′ div qs) +Ms , qs(y′ −Ms) + (x′ mod qs)
)
(2.7)
Description of a Chaotic Cipher 12
2.2.3. Pseudo-Random Sequences
The ciphering algorithm that is going to be described in section 2.3 uses random
numbers in two parts of the process. Therefore, it is worth spending some words on
what pseudo-random-sequence generation is without going too much into details.
A real random sequence is a sequence of numbers which shows a property of
real randomness (i.e. without any correlation among the generated numbers) and
which cannot be reliably reproduced [12]. The nature offers a vast variety of real
random sequences. Unfortunately, these sequences cannot be exploited since com-
puters and digital systems in general are deterministic. In fact, any  nite state ma-
chine can only be in a  nite number of states. This implies that no random number
generator can produce a real random sequence, but only pseudo-random sequences.
A pseudo-random sequence is a sequence where random numbers repeat after a
certain number of generations, called period. The  nite state machine has its initial
state set by a key, frequently referred to as a seed. Such  nite state machines are
named Pseudo-Random Number Generator (PRNG).
In order to be suitable for cryptographic applications, a PRNG should possesses
two properties. The  rst property is related to randomness. The PRNG should have
a period long enough to pass all the statistical tests of randomness available. The
second property relies on unpredictability. It should be computationally infeasible
to calculate the next pseudo-random number given the entire previous produced
sequence.
2.3. Algorithm Behavioural Description
This section describes, with the auxil of the concepts introduced in the prior sec-
tions, the cryptographic algorithm related to this work.
The general block diagram of the cipher under consideration is shown in  g-
ure 2.5 on the following page. The passphrase of 6, 400 bit is unique for both en-
cryption and decryption, so that, according to what exposed in section 2, the algo-
rithm is symmetric. More interestingly, the algorithm works on square plaintexts
(formally images) and therefore it belongs to the category of block ciphers. The
only constraint to which images are subjected is that the block length has to be an
integral power of 2. The cipher performs an encryption iterating the same algorithm
for r rounds. According to the author [11], a number of rounds at least equal to 12
is recommended.
Permutation
The permutation component is responsible for the actualization of the concept dif-
fusion outlined in section 2.1.3. Each data which composes the plainblock at the
input is transposed to a new position at the output. This transformation follows the
Description of a Chaotic Cipher 13
plain
text
cipher
text
C1=P1
internal key management
P0
KS1KP1 KS2KP2
Per Sub Per Sub
C2=P2 Cr-1=Pr-1 Cr
KSrKPr
Per Sub
passphrase
Figure 2.5: General block diagram of the cipher algorithm.
rules dictated by the chaotic Kolmogorov  ow Tn,δ formalized by eq. (2.4) on page
11.
It is opportune to remember that the K- ow Tn,δ just mentioned depends on
two parameters. The  rst parameter is n which represents in this context the size
of the image. The second parameter is the sequence δ = {n1, n2, . . . , nk} into
which the image is partitioned. Because n is a power of 2 and because each ns
(s = 1, . . . , k) must divide n without any reminder, the two major operations of
division and modulo that compose the application Tn,δ are between a natural number
in the range [0 . . . n) and a number that is a power of two, i.e. qs. Common partitions
are on the form {1/2, 1/2}, {1/4, 1/2, 1/4} and so on, which, for the discrete case,
translate to {2, 2}, {4, 2, 4}.
Substitution
Confusion is accomplished by the substitution component. Each data p(i) coming
from the permutation block at time i is combined with the previous values to com-
pute a new cipherdata c(i) that will constitute the output encrypted block Ci. Since
no re-arrangement of the position each data takes within blocks are performed, but
only a change in the value of data, substitution component clearly belongs to the
category of stream ciphers de ned in section 2.1.2.
The mathematical operation that copes with the confusion is formalized by the
following equation
c(i) = (p(i) + prsp(i) + prsc(i)) mod 232 (2.8)
The quantities prsp(i) and prsp(i) represent the pseudo-random sequences for plain-
text and ciphertext, respectively. Their values are computed by means of the follow-
Description of a Chaotic Cipher 14
ing relations
prsp(i) = (p(i− 24)− p(i− 37)− cp(i)) mod 232 (2.9)
cp(i+ 1) =
{
1 if p(i− 24)− p(i− 37)− cp(i) < 0
0 otherwise (2.10)
prsc(i) = (c(i− 24)− c(i− 37)− cc(i)) mod 232 (2.11)
cc(i+ 1) =
{
1 if c(i− 24)− c(i− 37)− cc(i) < 0
0 otherwise (2.12)
These expressions reassemble a type of PRNG (see section 2.2.3) described in [8].
Speci cally, the author of the present algorithm chose the recommended Subtract
With Borrow (SWB) pseudo-random number generator whose characteristic equa-
tion is given by xn = xn−24 − xn−37 − c mod 232.The integer numbers 24 and 37
clarify the constant present in eq.s (2.9) to (2.12).
It is important to notice that the considered SWB generator uses a seed vector
x = (x1, . . . , x37, c) constituted of 37 elements of 32 bit each and one element of
1 bit. This vector seed has to be initialized with a not-null vector in order for the
pseudo-random generator to work properly.
Key Management
The passphrase in  gure 2.5 on the page before represents the input key with which
the sensitive data are protected. As indicated by the author of the algorithm, the
passphrase is limited to at most 200 · 32 = 6, 400 bit that directly feed a 250 32-
bit element vector. Therefore, the remaining 50 cells are initialized with random
values.
The above-mentioned vector belongs to a PRNG called  R250 [6]. This com-
ponent is responsible of delivering on demand pseudo-random numbers to the prior
two components. Precisely, since the author of the algorithm did not exactly spec-
ify the procedure, it has been decided that the  rst number serves to chose the
δ-partition for the permutation and the next 2 · 37 numbers  ll up the substitution’s
vectors.