Multiobjective Evolutionary Random Binary Sequences for

Cryptography
Boulahiat Bouchra, Omary Fouzia

Mohammed V university, Faculty of Sciences- Rabat

Computer Science Departement
Computer Science Research Laboratory

Abstract:

This paper presents a new approach of random number generator based on multi-objective
evolutionary computation. Random number generators are very useful in different area such
as computer simulations and cryptography. Evolutionary algorithms resolve a lot of
optimization problems.

Our goal is to show that our generator can generate sequences of random numbers, while also
respecting the characteristics of a generator as the period, independence and uniform
distribution of binary sequences.

Le choix du PRGN et sa performance

Experiences+ NIST tests : (Statistical tests are applied to the keystream in compliance with the National
Institute of Standards and Technology (NIST) and Diehard test suites in order to ensure the quality of bitstream
produced by the generator.à modifier , Further validation of the TRBG stochastic properties is provided via the
Diehard test suite. The binary sequence obtained from this structure passed the FIPS set of tests,)

Keywords: Generator numbers, Random Binary Sequences, Multiobjective

optimization, evolutionary algorithms, cryptography.
 1. INTRODUCTION

- Introduire le développement de la technologie

- Le besoin fort des nombres aléatoires
- Introduire les générateurs des nombres, les types, l’usage de chacun
- Petit résumé su nouveau système
- The remainder of this paper is organized as follows. Section II presents a brief introduction to
multi-objective optimization. In Section III, we propose a taxonomy of applications. In Section
IV, we review the use of MOEAs in investment portfolio optimization. In Section IX, we
describe some of the future applications that remain to be done using MOEAs. Finally, Section
X contains our conclusions.

In today’s world of modern computers and ubiquitous networks most security

solutions rely on the use of cryptography. Generation high-quality randomness is
a vital (and maybe most difficult) cornerstone of many cryptographic operations
and the importance of a careful design of cryptographic (pseudo)random data
generators cannot be underestimated.
Following the second Kerckhoffs’ principle – the security of a cryptosystem shall
not be based on keeping the algorithm secret but solely on keeping the key secret
– the quality and unpredictability of secret data (e.g., cryptographic keys,
padding values or per-message secrets) is critical to securing communication by
modern cryptographic techniques. Generation of such data for cryptographic purposes
typically requires an unpredictable physical source of random data, secure
mechanisms for its digital post-processing and/or secure and robust methods for
gathering random data from one or several distributed systems.( à utiliser)[8]

 Dans son sens le plus général, l’aléa est le caractère de tout ce qui ne peut pas être
prédit. Cette notion d’aléa est difficile à définir et il est plus facile de dégager des loi
qui permettent de dire si un générateur est mauvais que d’énoncer des lois définissant
un bon générateur.
 En effet, la production d’un événement vraiment aléatoire est insoluble par les
ordinateurs qui ne répondent en principe qu’à des procédures et lois déterministes.
 Mais on peut tout de même obtenir des valeurs qui sont le fruit du vrai hasard en
faisant appel à des phénomènes physiques réputés imprévisible (exemple : variation de
la température ambiante ;…..). Cela dit, ces techniques sont généralement coûteuses
en termes de temps et de moyens.

2. RELATED WORK

-les générateurs qui ont utilisé les EA avant

-les travaux sur MOEA: Fonseca, golberdg…

-
 3. EVOLUTIONARY ALGORITHMS
3.1 Definition

Evolutionary Algorithm (EAs) are inspired by biological processes of evolution, and they
form a family of metaheuristics which consist to evolve a set of solutions (populations) to
solve an optimization problem, generally a combinatorial optimization one, by using
stochastic processes.
Evolutionary algorithms constitute an original approach: their goal is not to find an exact
solution, or a good numerical approximation, but to find solutions satisfying different criteria.
It can be seen that the solutions provided are generally better than those obtained by classical
methods for the same computation time.
The three most popular types of evolutionary algorithms have been developed almost
simultaneously by different scientists: Evolutionary Programming (L. Fogel 1966),
Evolutionary Strategies ( J. Rechenberg 1973 ) and the Genetic algorithms (J. Holland 1975).
So each type has numerous variants due to different parameter settings and implementations.

3.2 Algorithm
The basic structure of any evolutionary method is represented in “Fig.1”:

Initial Population Evaluation Fitness Assignment

Create an initial population of Calculate the objective values Use the objective values to
random individuals of candidate solutions determine fitness values

Reproduction Selection
Create new individuals from Select the fittest individuals for
mating pool by crossover and reproduction
mutation

Fig.1 : The basic cycle of evolutionary algorithms

And the algorithm is as follow:

Evolutionary Algorithm:
INPUTS: certain parameter µ, λ, ….., fitness function f: Ω
PARAMETERS: population size µ, number of offspring λ, genotype G, decoding
function
g
t 0
P(t) create a population of size µ
Evaluate individuals in P(t) using g and f
While termination criteria not fulfilled do
E select parents for offspring from P(t)
P’ create offspring by recombination of individuals in E
P’’ mutate individuals in P’
 evaluate individuals in P’’ using g and f
t t+1
P(t) select µ individuals from P’’ ( and P(t-1))
end while
OUTPUTS: best individuals in P(t)

4. MULTIOBJECTIVE OPTIMIZATION
4.1 Definition
Optimization is a procedure of finding and comparing possible solutions, which
are termed good or bad in terms of a determined objective. The majority of
research and application in optimization field considers a single objective, while
the most real-world optimization problems (including) are depending of different
constraints and shall satisfying several objectives.
On the other hand, evolutionary algorithms (EAs) are ideal candidates for solving
multi-objective optimization problems, since they can find multiple solutions as a
result to their population scheme.
Two major problems must be considered when an evolutionary algorithm is applied to
multi-objective optimization problem:
1. How to accomplish fitness assignment and selection, respectively, in order
to guide the search towards the optimal solutions set.
2. How to maintain a diverse population in order to prevent premature
convergence

3.2 Classifying MOEAs

There are several types of MOEAs. The most simple ones are based on the type of
selection mechanism and are (we cite):
 Aggregating Functions
 Population-based Approaches
 Pareto-based Approaches

Our algorithm conception is based on this following type:

1.4.1. Aggregating Functions

Perhaps the most straightforward approach to deal with multi-objective
problems is to combine them into a single scalar value (e.g., adding them
together). These techniques are normally known as "aggregating functions",
because they combine (or "aggregate") all the objectives of the problem into
a single one. An example of this approach is a fitness function in which we
aim to solve the following problem:
 Where ωi > 0 are the weighting coefficients representing the relative importance of the
k objective functions of our problem.

It is usually assumed that:

Aggregating functions may be linear (as the previous example) or nonlinear. Aggregating
functions have been largely underestimated by MOEA researchers mainly because of the
well-known limitation of linear aggregating functions (i.e., they cannot generate non-convex
portions of the Pareto front regardless of the weight combination used). Note however that
nonlinear aggregating functions do not necessarily present such limitation, and they have been
quite successful in multi-objective combinatorial optimization [6].

figure à partir de [7].

Performance of Multiobjective Evolutionary Algorithms

Basically, there are two ways to assess the performance of MOEAs: i) theoretically
by analysis or ii) empirically by simulation. In the following, we will present
some recent results with respect to both approaches. On the one hand, we will
discuss the limit behavior of MOEAs and provide a run-time analysis of two simple
MOEAs. On the other hand, we will address the question of how to assess
the quality of the outcome of a MOEA from a theoretical perspective.
5. RANDOM GENERATORS
The random data is produced by a random bit generator, which is a device whose
output is a bit sequence which must be independent and uniformly distributed.
A random bit generator is composed of two parts:
1. A non-deterministic noise source from physical phenomena whose behavior is
at least partially random
2. A deterministic part that takes as input the outgoing bit stream from the noise
source and returns a totally unpredictable binary sequence.
Random numbers make significant use in various application areas such as computer
simulation, statistical sampling, cryptography, and other areas where producing an
unpredictable result is desirable.
For example in cryptography, they can be used in the generation of secret keys, and
therefore, they can constitute a real flaw in the system according to the quality of the
generated random bit sequences. Currently, techniques for generating random numbers
become complex because the current cryptography demand truly random bit
sequences and cannot always be satisfied with pseudo random bit sequences for its
operation. The relevant question is: how to get a truly random bit sequences?
And we can distinguish two types of random generators:
- True random number generator (TRNG)
- Pseudo random number generator (PRNG)
5.1 Pseudo Random Number Generator (PRNG)
5.1.1 Definition
Pseudo Random Generator is a deterministic algorithm used to generate numbers
that must appear random.
It takes as input a random seed of n bits, and returns a sequence of N bits as output
( with N>>n) which look at a random bits sequence. This sequence is called
Pseudo Random Sequence.
The pseudo random generators are used in the stream cipher, the generated
sequence is xored with the plaintext to obtain the ciphertext.
Many constructions from cryptographically secure pseudo-random generators are
proposed like Micali and blum or blum blum shub. However, these generators are
very slow and are used in practice only when the evidence from output sequence
security is explicitly requested.

5.2 True Random Generator

 F

 First example of TRG



 Second example of TRG
 Third example of TRG
5.3 Hybrid Random Generator
 6. OUR EVOLUTIONARY RANDOM GENERATOR
6.1 Description
Les algorithmes évolutionnistes sont des métaheuristiques qui se basent sur des processus
stochastiques, donc des processus aléatoires comme les opérateurs de croisement et de
mutation. Bien qu’ils peuvent être une source d’aléatoire très efficace pour les systèmes
actuels, il suffit que nous puissions bien définir ses paramètres afin d’aboutir aux résultats
voulus (attendus).
L’objectif principale des algorithmes évolutionnistes multiobjectifs est de créer un
algorithme efficace afin de trouver les meilleures solutions au problème posé. Mais afin
d’aboutir à cet objectif, il faut vérifier les differentes contraintes liés à la résolution de ce
problème.
- The main goal of MOEA research is the creation of an effective and efficient
algorithm that renders good solutions. But to achieve that goal, several smaller goals
need to be addressed. These goals can be classified under two categories:
effectiveness goals and efficiency goals.

Notre idée de conception d’un nouveau générateur de nombres vraiment aléatoires

(TRNG) se base principalement sur le squelette de l’algorithme évolutionniste
multiobjectif, avec une redéfinition de tous ses paramètres en respectant toutes les
conditions pour aboutir à un bon (TRNG) générateur.
La qualité de notre générateur va être la réponse sur la question qui suit :
Partant d’un ensemble de données X quelconque et en se basant sur le processus d’un
algorithme évolutionniste multiobjectif, est ce qu’on peut générer des suites de nombres
vraiment aléatoires : des suites totalement différentes (càd : très grande période),
uniformément distribuées (càd : corrélation =0), et indépendantes (càd : une grande valeur
d’entropie) ?
Afin de répondre à cette question multicritères, on peut facilement déduire que notre
algorithme évolutionniste doit répondre à ces trois critères simultanément. Donc, nous
avons besoin de concevoir un algorithme évolutionniste multiobjectif, et par conséquent,
nous devons définir notre fonction objective multicritères.

En réalité, seulement les tests statistiques peuvent juger la performance de notre

générateur évolutionniste multiobjectif. C’est pourquoi nous avons appliquer plusieurs
tests statistiques à notre générateur, comme ( Entropie test, Diehard test suite, Corrélation,
NIST tests,…) afin d’assurer la qualité des suites de nombres générées.

-Verification of the statistical quality of (pseudo)random data by detecting deviations from

true randomness (known a priori) is based on statistical testing.

- The problem of insufficient amount of truly random data can be effectively

- Verification of the statistical quality of (pseudo)random data by detecting deviations from

true randomness (known a priori) is based on statistical testing. These tests may be useful
as the first step in determining whether or not a generator is suitable for a particular
cryptographic application. However, no set of statistical tests can surely point out a
generator as appropriate for usage in a particular application, i.e., statistical testing cannot
serve as a substitute for cryptanalysis. In addition, the results of statistical testing must be
interpreted with some care and caution to avoid incorrect conclusions about a specific
generator.[8]
6.2 Algorithm
7. EXPERIENCES & RESULTS
7.1 Test d’entropie
L’entropie et shanon( facteur/ qualité de l’aléa)
7.2 Test de corrélation
7.3 Diehard Test suit
Dans cette section, nous allons décrire les résultats de l’application de Diehard test
suit. Diehard est tres utilisé pour tester l’aléatoire dans les générateurs ces dernières
années.

7.4 NIST test

8. CONCLUSION & FUTURE WORK

Utilisation de SEC comme generateur de clé de session
9. REFERENCES
1. Sensitiveness of Evolutionary Algorithms to the Random Number Generator:Miguel
Cárdenas-Montes, Miguel A. Vega-Rodríguez, Antonio Gómez-Iglesias
2. Interactive Random Graph Generation with Evolutionary Algorithms:Benjamin Bach,
Andre Spritzer, Evelyne Lutton, and Jean-Daniel Fekete

3. W.Schindler, W.Killmann : Evaluation Criteria for True (Physical) Random Number

Generators Used in Cryptographic Applications. Cryptographic Hardware and
Embedded Systems - CHES 2002 Lecture Notes in Computer Science Volume
2523, 2003, pp 431-449.
4. Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone : Handbook of Applied
Cryptography. CRC Press , ISBN: 0-8493-8523-7 October 1996, 816 pages.
5. Eckart Zitzler and Lothar Thiele:Multiobjective Evolutionary Algorithms:A
Comparative Case Study and the Strength Pareto Approach. IEEE TRANSACTIONS
ON EVOLUTIONARY COMPUTATION, VOL. 3, NO. 4, NOVEMBER 1999
6. C. A. Coello Coello and G. B. Lamont, Eds., Applications of Multi-Objective
Evolutionary Algorithms. Singapore: World Scientific, 2004, iSBN 981-256-106-4.
7. Eckart Zitzler, Marco Laumanns, and Stefan Bleuler. “A Tutorial on Evolutionary
Multiobjective Optimization” Metaheuristics for Multiobjective Optimisation, Volume
535, 2004, pp 3-37
8. Thesis : Jan Krhovjàk, Cryptographic random and pseudorandom data generators.2009