1 \documentclass[nofrench, 11pt]{thloria}
3 %----------------------------------------------------------------------
4 % Chargement de quelques packages
5 %----------------------------------------------------------------------
7 % Si l'on veut produire une version PDF avec distiller ou pdflatex :
8 \usepackage[pageanchor=false]{tlhypref}
9 % Si l'on produit le PDF avec pdflatex, ceci remplace la plupart
10 % des polices EC par des polices CM, plus adaptées a la génération de PDF,
11 % car ayant des équivalents PS :
14 % Pour tout savoir sur les polices
15 % (cette ligne n'est pas nécessaire au traitement du fichier)
16 \usepackage[infoshow]{tracefnt}
18 % Pour les figures PS :
21 % Si on veut des mini-tables des matières (utiliser minitoc-hyper
22 % en conjonction avec tlhypref) :
23 \usepackage[french]{minitoc}
26 % Pour mathds : les ensembles IR, IN, etc.
29 % Pour une police à casse fixe
32 % Pour suspendre et reprendre des énumérations
35 % Pour avoir des intervalles d'entiers
38 % Pour avoir de la couleur
41 % Pour divers symboles de math
47 % Pour redéfinir les théorèmes (ci-dessous)
49 \usepackage[amsmath,thmmarks,thref,framed]{ntheorem}
52 \usepackage[french]{babel}
53 \usepackage[T1]{fontenc}
55 \usepackage[utf8]{inputenc}
58 % Pour avoir de belles têtes de chapitres
59 \usepackage[Sonny]{fncychap}
63 \usepackage{algorithm2e,algorithmic}
68 % Pour avoir des citations au début des chapitres
70 % Redéfinition de la largeur des citations
71 \setlength{\epigraphwidth}{8.25cm}
72 \renewcommand{\textflush}{flushepinormal}
74 % Pour les listings des codes python
77 \lstset{% general command to set parameter(s)
78 basicstyle=\small, % print whole listing small
79 keywordstyle=\color{black}\bfseries,
80 % underlined bold black keywords
81 identifierstyle=, % nothing happens
82 commentstyle=\color{white}, % white comments
83 stringstyle=\ttfamily, % typewriter type for strings
85 showstringspaces=false,% no special string spaces
89 % Pour faire des sous-figures dans les figures
90 \usepackage{subfigure}
100 %-------------------------------------------------------------------
101 % Corrections pour les imprimantes recto-verso
103 %-------------------------------------------------------------------
105 %\ShiftOddPagesRight{-1mm}
106 %\ShiftOddPagesDown{2.5mm}
107 %\ShiftEvenPagesRight{0mm}
108 %\ShiftEvenPagesDown{0mm}
111 %-------------------------------------------------------------------
113 %-------------------------------------------------------------------
115 % pour positionner les vraies marges:
116 %\SetRealMargins{1mm}{1mm}
118 %-------------------------------------------------------------------
120 %-------------------------------------------------------------------
122 % Les en-tetes: quelques exemples
125 %\newcommand\bfheadings[1]{{\bf #1}}
126 %\FormatHeadingsWith{\bfheadings}
127 %\FormatHeadingsWith{\uppercase}
128 %\FormatHeadingsWith{\underline}
129 \newcommand\upun[1]{\uppercase{\underline{\underline{#1}}}}
130 \FormatHeadingsWith\upun
132 \newcommand\itheadings[1]{\textit{#1}}
133 \FormatHeadingsWith{\itheadings}
135 % pour avoir un trait sous l'en-tete:
136 \setlength{\HeadRuleWidth}{0.4pt}
138 %-------------------------------------------------------------------
140 %-------------------------------------------------------------------
143 \NoChapterNumberInRef
148 % CREATION DE NOUVELLES COULEURS : gris5
149 \definecolor{gris}{gray}{0.35}
152 %REDEFINITION DU STYLE DES PROPOSITIONS
154 \theoremprework{\medskip}
155 \theoremheaderfont{\bfseries \scshape}
156 %\theorembodyfont{\scshape \bfseries}
157 \theoremseparator{ :}
158 %\theorempostwork{\hrulefill}
160 \newtheorem{Prop}{Proposition}[part]
164 %REDEFINITION DU STYLE DES COROLLAIRES
166 \theoremprework{\medskip}
167 \theoremheaderfont{\bfseries \scshape}
168 %\theorembodyfont{\scshape \bfseries}
169 \theoremseparator{ :}
170 %\theorempostwork{\hrulefill}
172 \newtheorem{Cor}{Corollaire}[part]
175 %REDEFINITION DU STYLE DES THEOREMES
177 %\theoremprework{\medskip}
178 \theoremheaderfont{\bfseries \scshape}
179 %\theorembodyfont{\scshape \bfseries}
180 \theoremseparator{ :}
181 %\theorempostwork{\hrulefill}
183 \newframedtheorem{Th}{Théorème}[part]
186 %REDEFINITION DU STYLE DES PREUVES
187 \theoremheaderfont{\bfseries \scshape}
188 \theoremstyle{nonumberplain}
189 \theoremseparator{ :}
190 \theorembodyfont{\slshape}
191 \theoremprework{\begin{color}{gris}}
192 \theorempostwork{\end{color}}
193 %\theoremsymbol{\openbox}
195 \newtheorem{Pre}{Preuve}[chapter]
198 %REDEFINITION DU STYLE DES REMARQUES
199 \theoremstyle{nonumberplain}
200 \theoremheaderfont{\bfseries \scshape}
201 \theorembodyfont{\upshape}
202 \theoremsymbol{\ensuremath{}}
203 \theoremseparator{. }
205 \newtheorem{Rem}{Remarque}[chapter]
209 %REDEFINITION DU STYLE DES NOTATIONS
211 \theoremheaderfont{\bfseries \scshape}
212 \theorembodyfont{\upshape}
213 \theoremsymbol{\ensuremath{}}
214 \theoremseparator{. }
216 \newtheorem{Notation}{Notation}[part]
222 %REDEFINITION DU STYLE DES LEMMES
224 \theoremsymbol{\ensuremath{\diamond}}
226 \theoremnumbering{arabic}
227 \newtheorem{Lemma}{Lemme}[chapter]
232 %%%%%%%% REDEFINITION DES LISTES %%%%%%%%
234 %\setlength{\leftmargini}{2.25cm}
236 % Redéfinition des items
238 \renewenvironment{itemize}{%
239 \begin{list}{\begin{scriptsize}$\bullet$\end{scriptsize}}{%
240 \setlength{\leftmargin}{1.8cm}%
244 % Redéfinition des enumerate
247 \renewenvironment{enumerate}{%
248 \begin{list}{\large{\oldstylenums{\arabic{numero}}}. }{%
250 \setlength{\leftmargin}{2cm}%
254 % Redéfinition des descriptions
255 \newcommand{\entree}[1]{\mbox{\itshape\textbf{#1}}\hfil}
257 \renewenvironment{description}{%
259 \renewcommand{\makelabel}{\entree}
260 \setlength{\leftmargin}{1.75cm}%
261 \setlength{\labelwidth}{1cm}
267 %%%%%%%% REDEFINITION DU STYLE DES TITRES DES SECTIONS %%%%%%%%
268 \usepackage{titlesec}
269 \setcounter{secnumdepth}{5}
270 %% REDEFINITION DU STYLE DES CHAPITRES
271 %% Fait par le package fncychap
273 % REDEFINITION DU STYLE DES SECTIONS
275 \titleformat{\section}
277 {\Large\bfseries\scshape} % Le style des caractères :
278 % tt (police), LARGE (très grand),
279 % scshape (en majuscule), bfseries (en gras)
280 {\Roman{section}. } % Numérotation : I. II. etc.
281 {0cm} % Espace entre le numéro et le titre
282 {} % Commandes à exécuter avant
284 % Commandes à exécuter après : arrêt du soulignement
286 \titlespacing*{\section}
288 {3.5ex plus 1ex minus .2ex}
291 % REDEFINITION DU STYLE DES SOUS-SECTIONS
293 \titleformat{\subsection}
295 {\normalfont\large\bfseries}
296 {\arabic{subsection}. } % Numérotation : 1. , 2., etc.
297 % On impose en plus le soulignement du numéro.
298 {0cm} % Espace entre le numéro et le titre
299 {} % Commandes à exécuter avant
301 % Commandes à exécuter après : arrêt du soulignement
303 \titlespacing*{\subsection}
304 {50pt} % On décale de 50pt devant le titre
305 {3.25ex plus 1ex minus .2ex}
308 % REDEFINITION DU STYLE DES SOUS-SOUS-SECTIONS
310 \titleformat{\subsubsection}
311 {\normalfont\normalsize\itshape\bfseries}
312 {\alph{subsubsection}. }
317 \titlespacing*{\subsubsection}
318 {70pt} % On décale de 70pt devant le titre
319 {3.25ex plus 1ex minus .2ex}
322 %% REDEFINITION DU STYLE DES PARAGRAPHES
324 \titleformat{\paragraph}[runin]
325 {\normalfont\normalsize\bfseries}
326 {\roman{paragraph}. }
331 \titlespacing*{\paragraph}
333 {3.25ex plus 1ex minus .2ex}
335 %% REDEFINITION DU STYLE DES SOUS-PARAGRAPHES
337 %\titleformat{\subparagraph}[runin]
338 % {\normalfont\normalsize\bfseries}
343 % \titlespacing*{\subparagraph}
345 % {3.25ex plus 1ex minus .2ex}
347 %%%%%%%%%%%%%%%%%%% FIN DE LA REDEFINITION DES TITRES %%%%%%%%%%%%
351 %-------------------------------------------------------------------
352 % POUR LES INFOS ET LES LIENS DES PDFs
353 %-------------------------------------------------------------------
354 \usepackage{hyperref}
357 %backref=true, %permet d'ajouter des liens dans...
358 %pagebackref=true,%...les bibliographies
359 %hyperindex=true, %ajoute des liens dans les index.
360 colorlinks=true, %colorise les liens
361 breaklinks=true, %permet le retour à la ligne dans les liens trop longs
362 urlcolor= black, %couleur des hyperliens
363 linkcolor= blue, %couleur des liens internes
364 %bookmarks=true, %créé des signets pour Acrobat
365 bookmarksopen=true, %si les signets Acrobat sont créés,
366 %les afficher complÚtement.
367 citecolor=blue, % Couleur des références citées
368 pdftitle={Générateurs de nombres pseudo-aléatoires. Applications en cryptologie}, %informations apparaissant dans
369 pdfauthor={Christophe Guyeux}, %dans les informations du document
370 pdfsubject={Thèse} %sous Acrobat.
374 %-------------------------------------------------------------------
376 %-------------------------------------------------------------------
377 % On inclus le fichier contenant le glossaire :
379 %\include{Autre/Glossaire}
383 %-------------------------------------------------------------------
384 % Césure des mots problématiques
385 %-------------------------------------------------------------------
387 \hyphenation{dy-na-mi-que}
388 \hyphenation{nom-bre}
389 \hyphenation{pé-rio-di-que}
390 \hyphenation{ca-rac-té-ri-sa-tion}
391 \hyphenation{con-crè-tes}
392 \hyphenation{con-ver-ge}
393 \hyphenation{con-trai-re}
394 %-------------------------------------------------------------------
396 %-------------------------------------------------------------------
399 \newcommand{\X}{\mathcal{X}}
400 \newcommand{\Go}{G_{f_0}}
401 \newcommand{\B}{\mathds{B}}
402 \newcommand{\N}{\mathds{N}}
403 \newcommand{\BN}{\mathds{B}^\mathsf{N}}
405 %-------------------------------------------------------------------
407 %-------------------------------------------------------------------
409 % ceci ajoute une marque `brouillon' et la date
412 %-------------------------------------------------------------------
413 % Pour collecter un glossaire et un index
414 %-------------------------------------------------------------------
436 \OddHead={{\leftmark\rightmark}{\hfil\slshape\rightmark}}
437 \EvenHead={{\leftmark}{{\slshape\leftmark}\hfil}}
438 \OddFoot={\hfil\thepage}
439 \EvenFoot={\thepage\hfil}
440 \pagestyle{ThesisHeadingsII}
442 %-------------------------------------------------------------------
444 %-------------------------------------------------------------------
446 % encadre les chapitres dans la table des matières:
447 % (ces commandes doivent figurer après \begin{document}
453 %-------------------------------------------------------------------
454 % Re initialisation de la numérotation des chapitres
455 %-------------------------------------------------------------------
457 % Si la commande suivante est présente,
458 % elle doit figurer APRÈS \begin{document}
459 % et avant la première commande \part
460 \ResetChaptersAtParts
462 %-------------------------------------------------------------------
463 % mini-tables des matières par chapitre
464 %-------------------------------------------------------------------
466 % préparer les mini-tables des matières par chapitre.
467 % (commande de minitoc.sty)
470 %-------------------------------------------------------------------
472 %-------------------------------------------------------------------
476 \ThesisTitle{Générateurs de nombres pseudo-aléatoires. Applications en cryptologie}
478 \ThesisDate{13 décembre 2010}
480 \ThesisAuthor{Christophe Guyeux}
483 % Type de la thèse (autres solution: \ThesisINPL, \ThesisNancyII)
489 % (ne pas mettre de \\ après la dernière entrée)
491 % Exemple de création d'une nouvelle catégorie dans le jury:
493 \NewJuryCategory{Directeur}{\it Directeur :}
496 \def\blanc{\hspace*{1cm}}
498 \President = {Michel de Labachelerie}
500 \Rapporteurs = {Pascale Charpin, \emph{Directrice de Recherche, INRIA-Rocquencourt}\\
501 Éric Filiol, \emph{Professeur, ESIEA - Laval}\\
502 Pierre Spitéri, \emph{Professeur Émérite, IRIT-ENSEEIHT}
506 Michel de Labachelerie, \emph{Directeur de Recherche CNRS, Université de Franche-Comté}\\
507 Laurent Larger, \emph{Professeur, Université de Franche-Comté}\\
508 Jean-Claude Miellou, \emph{Professeur, Université de Franche-Comté}\\
509 Congduc Pham, \emph{Professeur, Université de Pau}
512 \Directeur = {Jacques M. Bahi, \emph{Professeur, Université de Franche-Comté}}
514 % Creation de la page de titre:
517 % on peut en faire plusieurs:
518 %\MakeThesisTitlePage
521 %\MakeThesisTitlePage
523 %-------------------------------------------------------------------
526 %-------------------------------------------------------------------
528 %-------------------------------------------------------------------
531 \begin{ThesisAcknowledgments}
532 Je souhaite avant toutes choses remercier mon directeur de thèse, le Professeur Jacques M. Bahi, pour son encadrement, sa disponibilité et son amitié. Il a su, malgré un emploi du temps bien chargé, toujours être présent à mes côtés, et me faire profiter de son expérience, son intelligence, et sa connaissance si fine des objets de ma recherche. Le travail que j'ai pu mener et ce document ne seraient pas ce qu'ils sont sans sa motivation et ses encouragements, sa patience, son recul, son regard critique, et la pertinence de ses conseils. Ce fut un grand plaisir de travailler avec lui, et j'espère pouvoir continuer à le faire longtemps encore.
536 Je tiens également à remercier Pascale Charpin, \'Eric Filiol, Pierre Spitéri, Michel de Labachelerie, Laurent Larger, Jean-Claude Miellou et Congduc Pham, qui ont bien voulu être membres de mon jury de thèse. Et plus particulièrement, merci à P. Charpin, \'E. Filiol et P. Spitéri qui m'ont fait l'honneur d'être les rapporteurs de cette thèse. Merci pour leurs suggestions et leurs conseils précieux, qui m'ont aidé à améliorer et clarifier ce mémoire.
540 Je tiens aussi à remercier tous les membres de l'équipe AND pour leur amitié et la bonne ambiance qu'ils contribuent à créer. Je remercie notamment Jean-François Couchot et Michel Salomon pour leurs relectures de qualité et leurs conseils.
544 Je ne remercierai jamais assez mon frère et mes parents, pour avoir toujours été présents, m'avoir toujours aidé et soutenu, et pas seulement durant mes études. Sans eux, leur gentillesse, leurs encouragements et leur dévouement, je n'en serais pas là. Malgré la distance, ils sont toujours présents à mes côtés.
548 Et surtout, merci à Nathalie, pour tout.
549 \end{ThesisAcknowledgments}
552 %-------------------------------------------------------------------
554 %-------------------------------------------------------------------
556 \begin{ThesisDedication}
562 \`A mes parents et ma filleule,\\en souvenir de mon grand-père.
563 \end{ThesisDedication}
567 %-------------------------------------------------------------------
568 % Écriture de `Chapitre' et `Partie'
569 % dans la table des matières
570 %-------------------------------------------------------------------
573 \WriteChapterLabelInToc
575 %-------------------------------------------------------------------
577 %-------------------------------------------------------------------
581 %\DontNumberThisInToc
584 % Pour ne pas avoir le mot `Chapitre' au début de chaque chapitre.
588 %-------------------------------------------------------------------
589 % Introduction générale et notation
590 %-------------------------------------------------------------------
592 \SpecialSection{Introduction g\'en\'erale}
600 %\include{Autre/IntroductionGenerale}
606 %\part*{Introduction générale}
607 \label{Contexte et rappels}
610 %REDEFINITION DU STYLE DES DEFINITIONS
612 \theoremheaderfont{\bfseries \scshape}
613 %\theorembodyfont{\em}
614 \theoremsymbol{\ensuremath{\diamondsuit}}
615 %\theoremprework{\medskip}
616 \theoremseparator{ : }
618 \newtheorem{Def}{Définition}
622 %REDEFINITION DU STYLE DES EXEMPLES
623 \theoremstyle{numberplain}
624 \theoremheaderfont{\bfseries \scshape\slshape}
625 \theorembodyfont{\upshape}
626 \theoremsymbol{\ensuremath{}}
627 \theoremseparator{ : }
628 %\theoremprework{\hrulefill}
629 %\theorempostwork{\hrulefill\newline}
630 \newtheorem{Ex}{Exemple}
635 %\include{Rappels_ICs/historique}
636 %\include{Objectifs/cryptosys}
638 % La commande \mainmatter (nouvelle commande LaTeX2e) permet de passer
639 % a la numérotation arabe (ce que fait \pagenumbering{arabic})
640 % et de faire commencer la nouvelle page 1 sur une page impaire.
641 % On évitera donc d'utiliser directement \pagenumbering{arabic}.
647 %REDEFINITION DU STYLE DES DEFINITIONS
649 \theoremheaderfont{\bfseries \scshape}
650 %\theorembodyfont{\em}
651 \theoremsymbol{\ensuremath{\diamondsuit}}
652 %\theoremprework{\medskip}
653 \theoremseparator{ : }
655 \renewtheorem{Def}{Définition}[part]
657 \newtheorem{definition}{Definition}
658 \newtheorem{proposition}{Proposition}
659 \newtheorem{theorem}{Theorem}
660 \newtheorem{proof}{Proof}
661 \newtheorem{remark}{Remark}
665 %REDEFINITION DU STYLE DES EXEMPLES
666 \theoremstyle{numberplain}
667 \theoremheaderfont{\bfseries \scshape\slshape}
668 \theorembodyfont{\upshape}
669 \theoremsymbol{\ensuremath{}}
670 \theoremseparator{ : }
671 %\theoremprework{\hrulefill}
672 %\theorempostwork{\hrulefill\newline}
673 \renewtheorem{Ex}{Exemple}[part]
687 \include{Introduction}
688 \include{GeneralNotions}
693 \include{DesignofCIPRNG}
696 \include{StatisticalTestsforRandomness}
699 \include{Securityanalysis}
702 \include{ThefamilyofCIPRNG}
705 \part{Application aux techniques de la dissimulation d'information}
706 \label{Applications aux techniques de dissimulation d'information}
708 \include{ApplicationofRNG}
710 \part*{Conclusions et Annexes}
711 \label{part:Conclusions}
713 \include{FinalConclusion}
721 %------------------------------------------------------------------
723 %-----------------------------------------------------------------
727 %-------------------------------------------------------------------
728 % L'index (toujours sur deux colonnes)
729 %-------------------------------------------------------------------
730 %\BeginIndWith{Les numéros de pages auxquelles font références les entrées de cet index ne sont pas celles du fichier pdf, mais celles que l'on trouve en bas de chaque page. En effet, les premières pages du document sont numérotées en chiffres romains.}
736 %-------------------------------------------------------------------
738 %-------------------------------------------------------------------
741 \bibliographystyle{alpha}
742 \bibliography{Thesis}
745 %-------------------------------------------------------------------
747 %-------------------------------------------------------------------
748 % (si le resume' apparait sur une colonne etroite, avec la
749 % bibliographie a gauche, c'est sans doute parce que vous avez
750 % oublie' de generer les fichiers d'index et de glossaire...)
753 \begin{ThesisAbstract}
754 \begin{FrenchAbstract}
756 \KeyWords{Théorie du Chaos; Systèmes Dynamiques Discrets; Itérations Chaotiques; Sécurité; Fonctions de Hachage; Stéganalyse; Réseaux de Capteurs.}
758 \begin{EnglishAbstract}
759 Due to the rapid development of the Internet in recent years, the need to find new tools to reinforce trust and security through the Internet has became a major concern. The discovery of new pseudo-random number generators with a strong level of security is thus becoming a hot topic. Although some mechanical ways, such as tossing a coin or roling a dice, are commonly accepted as good random sources, they are obviously not be able to fulfill the requirements of most of the real-world applications, in wich high throughput and good quality are generally required.\\
760 For more than half century, different random generators have been proposed. Recently, we have witnessed an active involvement of another branch of sciences in this topic, in particularly, aiming for cryptographical applications. Due to the distinct properties of chaos, including random-like dynamics, high sensitivity on initial conditions and system parameters, etc, the use of chaos in random number generation and crytographical applications has aroused tremendous interests.\\
761 However, the actual realization environment is usually ignored in most of the chaos-designs, for which an infinite precision is commonly assumed.as pinted out by some researchers, if a chaotic system is to be implemented in finite precision, its dynamics will be greatly deviated from its original one, and hence some nice properties will be vanished.\\
762 In this thesis, a new scheme to generate pseudo random number is presented, the generators are based on discrete chaotic iterations which satisfy Devaney's definition of chaos. A rigorous framework is introduced, where topological chaotic properties of the generator are shown. Two practical designs of these chaos-based random number generators are showed. With such chaotic iterations, the statistical quality of the generated random sequence can be greatly improved and fulfil the up-to-date standards. From the experiments, the comparison between these two designs are investigated in details. The second designed technique outperforms the first one, both in terms of performance and speed.\\
763 In the above research, the iteration function for chaotic iterations is the vectorial Boolean negation as a prototype. we propose a method using Graph with strongly connected components as a selecton criterion and modifying the iteration function without deflating the good properties of the associated generator.
764 Simulation results and basic security analysis are then presented
765 to evaluate the randomness of this new family of generators.\\
766 Finally, an illustration in the field of data hiding is presented and the robustness of the obtained data hiding algorithm against attacks is evaluated.
768 \KeyWords{Internet security; Chaotic sequences; Statistical tests; Discrete chaotic iterations; Information hiding.}
769 \end{EnglishAbstract}