From 081840755bb6cc5ba3843b7830061c00079cd58e Mon Sep 17 00:00:00 2001 From: qianxue Date: Fri, 14 Oct 2011 16:21:55 +0200 Subject: [PATCH] Add references. --- GeneralNotions.tex | 26 +- GeneralNotions.tex.backup | 201 +++++++--------- Introduction.tex | 2 +- Thesis.bib | 494 +++++++++++++++++++++++++++++++++++++- these.tex | 4 +- 5 files changed, 593 insertions(+), 134 deletions(-) diff --git a/GeneralNotions.tex b/GeneralNotions.tex index 4cdb2aa..83ddf02 100644 --- a/GeneralNotions.tex +++ b/GeneralNotions.tex @@ -5,29 +5,29 @@ Ce chapitre, faisant office de fondations pour cette thèse, introduit la terminologie et les notations utilisés dans le domaine des générateurs de nombres pseudo-aléatoires. \section{ Aléas} -Une suite aléatoire de bits peut s’interpréter comme le résultat de lancers d’une pièce équilibrée (non-biaisée). On assimiler "Pile" à "0" et "face" à "1", et l’on suppose que chaque lancer a une probabilité $1/2$ exactement de produire un "0", et parcellement pour "1". On suppose de plus que les lancers sont indépendants les uns des autres: le résultat n’importe quel précédent lancer n’affecte pas les lancers à venir. La pièce sans biais et équitable est alors l’image d’un générateur aléatoire de bits parfait, puisque les " 0 " et "1" seront aléatoirement distribués. Tous les éléments de la suite sont générés indépendamment les uns des autres, et la valeur de l'élément suivant dans la suite ne peut être prédite à partir de la suite des nombres déjà obtenus, et ce quelle que soit la grandeur de cette suite. Cependant, clairement, l'utilisation de pièces non biaisées à des fins cryptographiques est impraticable en pratique. Quai qu’il en soit, la sortie hypothétique d'un tel générateur idéal de suites réellement aléatoire sert de critère de comparaison (benchmark) pour l'évaluation des générateurs de nombres aléatoires et pseudo aléatoires~\cite{ANDREW2008}. +Une suite aléatoire de bits peut s’interpréter comme le résultat de lancers d’une pièce équilibrée (non-biaisée). On assimiler "Pile" à "0" et "face" à "1", et l’on suppose que chaque lancer a une probabilité $1/2$ exactement de produire un "0", et parcellement pour "1". On suppose de plus que les lancers sont indépendants les uns des autres: le résultat n’importe quel précédent lancer n’affecte pas les lancers à venir. La pièce sans biais et équitable est alors l’image d’un générateur aléatoire de bits parfait, puisque les " 0 " et "1" seront aléatoirement distribués. Tous les éléments de la suite sont générés indépendamment les uns des autres, et la valeur de l'élément suivant dans la suite ne peut être prédite à partir de la suite des nombres déjà obtenus, et ce quelle que soit la grandeur de cette suite~\cite{Deborah1998,Kallenberg1986}. Cependant, clairement, l'utilisation de pièces non biaisées à des fins cryptographiques est impraticable en pratique. Quai qu’il en soit, la sortie hypothétique d'un tel générateur idéal de suites réellement aléatoire sert de critère de comparaison (benchmark) pour l'évaluation des générateurs de nombres aléatoires et pseudo aléatoires~\cite{ANDREW2008}. \section{Différents types de générateurs de nombres aléatoires (RNG)} -Un RNG est un composant informatique ou physique, assemblé pour produire une suite de nombres ou de symboles qui semble aléatoires. +Un RNG est un composant informatique ou physique, assemblé pour produire une suite de nombres ou de symboles qui semble aléatoires~\cite{William2007}. Générer une bonne suite aléatoires est une tâche difficile. On peut bien évidemment obtenir une telle suite à partir d’un lancer de clés ou d’une pièce de monnaie, un tel procède mécanique n’est, on l’a dit, pas pratique. Il y a quelques temps de cela, les nombres aléatoires étaient générés à partir et tabulées en utilisant par exemple les procèdes mécaniques évoqués ci-dessus. Ces tables prêtes à l'emploi peuvent encore se trouver sur le web ou sur des CDs de données dédiés. -Cependant, du fait des besoins liés à Internet et aux problèmes de sécurité soulevés par cette approche, ces tables ne permettent plus de satisfaire les besoins en nombres aléatoires. C’est pourquoi de nouveaux types de RNG ont été introduits, notamment depuis l’apparition de l’informatique. +Cependant, du fait des besoins liés à Internet et aux problèmes de sécurité soulevés par cette approche, ces tables~\cite{Tippett1927} ne permettent plus de satisfaire les besoins en nombres aléatoires. C’est pourquoi de nouveaux types de RNG ont été introduits, notamment depuis l’apparition de l’informatique. Les RNG sont traditionnellement regroupés en deux classes, suivant leur source d’aléas: les générateurs de nombres vraiment aléatoires et les générateurs de nombres pseudo aléatoires. \subsection{ Les générateurs de nombres vraiment aléatoires (TRNGs)} -Un TRNG est un générateur produisant des bits statistiquement indépendants et sans biais. Ils s’agit de RNG non déterministes. En informatique, un TRNG est un appareil produisant des nombres aléatoires à partir d'un processus physique. De tels composants se basent souvent sur des phénomènes microscopiques génèrent un signal de bas niveau, un bruit statistiquement aléatoire. Les phénomènes peuvent être un "bruit thermal" utilisant les capteurs de température de l’ordinateur, peuvent utiliser l’effet photoélectrique ou tout autre phénomène quantique. En théorie, ces processus sont complètement imprévisible s; en pratique, une telle assertion se vérifie à l’aide de batteries tests statistiques. Un tel générateur quantique de type physique, consiste typiquement en un transducteur qui convertir un certains aspects d’un phénomène physique en un signal électrique. Ce transducteur est relié à un amplificateur et d'autres composant électroniques, dont le but est de porter la sortie du transducteur de l’échelle microscopique à l’échelle macroscopique. Enfin, un convertisseur analogique vers numérique permet de transformer a signal analogique en une suite de nombres, souvent de simples bits. On obtient ainsi une suite de bits en reproduisant le procédé tant que nécessaire. +Un TRNG est un générateur produisant des bits statistiquement indépendants et sans biais. Ils s’agit de RNG non déterministes. En informatique, un TRNG est un appareil produisant des nombres aléatoires à partir d'un processus physique~\cite{Pashley2010184}. De tels composants se basent souvent sur des phénomènes microscopiques génèrent un signal de bas niveau, un bruit statistiquement aléatoire. Les phénomènes peuvent être un "bruit thermal" utilisant les capteurs de température de l’ordinateur, peuvent utiliser l’effet photoélectrique ou tout autre phénomène quantique~\cite{Guler2011,WT198429,Danger2009,JarosawAdam2011}. En théorie, ces processus sont complètement imprévisible s; en pratique, une telle assertion se vérifie à l’aide de batteries tests statistiques. Un tel générateur quantique de type physique, consiste typiquement en un transducteur qui convertir un certains aspects d’un phénomène physique en un signal électrique. Ce transducteur est relié à un amplificateur et d'autres composant électroniques, dont le but est de porter la sortie du transducteur de l’échelle microscopique à l’échelle macroscopique. Enfin, un convertisseur analogique vers numérique permet de transformer a signal analogique en une suite de nombres, souvent de simples bits. On obtient ainsi une suite de bits en reproduisant le procédé tant que nécessaire. \subsection{ Les générateurs de nombres pseudo-aléatoires (PRNGs)} -Un PRNG, appelé aussi générateur déterministes de bits aléatoires (DRBG : Deterministic Random Bit Generator ) ~\cite{Barker05recommendationfor} est un algorithme générant une suite de nombres qui approximent les propriétés des nombres aléatoires. La suite n'est pas réellement aléatoire dans le sens où elle est complètement déterminée par un ensemble de valeurs initiales relativement petit, appelé l’état du PRNG. S’il est vrai que des suites proches d’un aléa pur peuvent être obtenues avec des générateurs physiques, cela ne signifie pas pour autant que les générateurs pseudo-aléatoires sont inutiles. Leur importance se matérialise lors de simulations, par exemple de systèmes physiques en utilisant la méthode de Monte Carlo. Ils sont de plus primordiaux en cryptographie et en génération procédurale~\cite{ }. Des classes bien connue de tels algorithmes sont les générateurs congruentiels linéaires, les Lagged Fibonacci générateurs, linéaire feedback shift registre, feedback with carry shift registers, and generalised feedback shift registers. Le Blum Blum Shub, le Fortuna, et le Mersenne Twister sont par exemple des instances récentes de ces classes d’algorithmes. +Un PRNG, appelé aussi générateur déterministes de bits aléatoires (DRBG : Deterministic Random Bit Generator ) ~\cite{Barker05recommendationfor} est un algorithme générant une suite de nombres qui approximent les propriétés des nombres aléatoires. La suite n'est pas réellement aléatoire dans le sens où elle est complètement déterminée par un ensemble de valeurs initiales relativement petit, appelé l’état du PRNG. S’il est vrai que des suites proches d’un aléa pur peuvent être obtenues avec des générateurs physiques, cela ne signifie pas pour autant que les générateurs pseudo-aléatoires sont inutiles. Leur importance se matérialise lors de simulations, par exemple de systèmes physiques en utilisant la méthode de Monte Carlo. Ils sont de plus primordiaux en cryptographie et en génération procédurale~\cite{Tan20091618,StDenis200691}. Des classes bien connue de tels algorithmes sont les générateurs congruentiels linéaires~\cite{Knuth1998_1}, les Lagged Fibonacci générateurs~\cite{Knuth1998_2}, linéaire feedback shift registre~\cite{tagkey2009407}, feedback with carry shift registers~\cite{Klapper1994}, and generalised feedback shift registers~\cite{Linardatos2002157,Klapper199961,Mykkeltveit1979202,Unjeng198461}. Le Blum Blum Shub~\cite{DBLP1986}, le Fortuna~\cite{DBLP2003}, et le Mersenne Twister~\cite{Matsumoto1998} sont par exemple des instances récentes de ces classes d’algorithmes. \section{ PRNGs cryptographiquement sûrs } -Un PRNG pouvant être utilisé en cryptographie est appelé un PRNG cryptographiquement sûr (CSPRNG). Une propriété importante que doit satisfaire un CSPRNG est qu’un adversaire, ne connaissant pas la graine, n'a qu'un avantage négligeable de pouvoir distinguer la séquence produite par le générateur d'une séquence réellement aléatoire. En d'autres termes, tandis que l’en se demande à un PRNG que de passer certains tests statistiques, un CSPRNG doit passer tous les tests statistiques ayant un temps d’ exécuter polynomial par rapport à la taille de la graine. Bien qu’une telle propriété ne peut pas être prouvée~\cite{ }, on peut cependant s’en approcher en réduisant ce problème pour un générateur à un problème NP-difficile tel que la factorisation des entiers. En général, des années d’étude sont requises avant de pouvoir certifier qu’un algorithme donné est un CSPRNG. +Un PRNG pouvant être utilisé en cryptographie est appelé un PRNG cryptographiquement sûr (CSPRNG). Une propriété importante que doit satisfaire un CSPRNG est qu’un adversaire, ne connaissant pas la graine, n'a qu'un avantage négligeable de pouvoir distinguer la séquence produite par le générateur d'une séquence réellement aléatoire. En d'autres termes, tandis que l’en se demande à un PRNG que de passer certains tests statistiques, un CSPRNG doit passer tous les tests statistiques ayant un temps d’ exécuter polynomial par rapport à la taille de la graine. Bien qu’une telle propriété ne peut pas être prouvée~\cite{Miller2010}, on peut cependant s’en approcher en réduisant ce problème pour un générateur à un problème NP-difficile tel que la factorisation des entiers. En général, des années d’étude sont requises avant de pouvoir certifier qu’un algorithme donné est un CSPRNG. Donnons maintenant quelques classes de CSPRNGs: @@ -49,7 +49,7 @@ Dans certaines applications spécifiques, les chiffrements par flots sont plus a \item Les chiffrements par flots sont généralement plus rapides que le chiffrements par bloc, surtout quand ces premiers sont produits au niveau matériel. \item Les chiffrements par flots ont une complexité matérielle plus faible, et nécessitent moins de mémoire, et ce que ce soit au niveau hardware ou software. \item Les chiffrements par flots opèrent sur le clair-texte caractère par caractère, et ainsi aucun tampon n.est nécessaire, il n’y a pas besoin d'accumuler un bloc complet du clair-texte (contrairement au chiffrement par bloc). -\item Les chiffrements par flots synchrones n'ont pas de propagation d’erreur~\cite{ }. +\item Les chiffrements par flots synchrones n'ont pas de propagation d’erreur~\cite{springerlink1994}. \end{enumerate} \section{Le chiffrement par flot} @@ -63,27 +63,27 @@ Le chiffrement de Vernam est un chiffrement par flot dans lequel on applique le Shannon a montré~\cite{Shannon-OTP} que le masque jetable fournit une sécurité parfaite. Cela veut dire que l'entropie conditionnelle du message $M$ connaissant le cryptogramme $ C $, est la même que l'entropie du message d'origine : $H(M|C) = H(M)$. Shannon a aussi montré que le masque jetable est optimale : la condition précédente ne peut être obtenue avec une clé de taille plus petite que le message $M$. -Le problème avec le masque jetable est que l’on doit avoir une clé de la faille du message, ce qui dans la plupart des cas est impossible en pratique. Les deux schémas suivants tentent de produire un keystream à l’allure aléatoire à partir d’une petite clé. Par allure aléatoire, il faut comprendre que l’on ne doit pas pouvoir faire la distinction entre le keystream et une suite aléatoire, en une complexité inférieure à celle intervenant quand on tente toutes les clés possibles. +Le problème avec le masque jetable est que l’on doit avoir une clé de la faille du message, ce qui dans la plupart des cas est impossible en pratique~\cite{PhysRevA2004}. Les deux schémas suivants tentent de produire un keystream à l’allure aléatoire à partir d’une petite clé. Par allure aléatoire, il faut comprendre que l’on ne doit pas pouvoir faire la distinction entre le keystream et une suite aléatoire, en une complexité inférieure à celle intervenant quand on tente toutes les clés possibles. \subsection{ chiffrements par flots synchrones} -Dans un chiffrement par flot synchrone, le flux de nombres pseudo-aléatoires est produit indépendamment du clair-texte et du cryptogramme, puis est ensuite combiné soit au clair-texte à chiffrer, soit au cryptogramme à déchiffrer. +Dans un chiffrement par flot synchrone, le flux de nombres pseudo-aléatoires est produit indépendamment du clair-texte et du cryptogramme, puis est ensuite combiné soit au clair-texte à chiffrer, soit au cryptogramme à déchiffrer~\cite{cusick2004stream}. Dans un chiffrement par flot synchrone, l'expéditeur et le récepteur doivent être exactement synchronisés pour que le déchiffrement puisse se faire sans encombre. Si des chiffres sont ajoutés ou enlevés du message pendant la transmission, alors la synchronisation sera perdue. Pour la restaurer, on peut effectuer différentes tentatives de déchiffrement à partir de keystream décalés jusqu’à obtenir un message intelligible. Une autre approche consiste à introduire des marqueurs dans le cryptogramme, comme autant de repères permettant une resynchronisation. -Si, cependant, un chiffre est corrompu durant la transmission, sans qu’il y ait décalage, alors seul un bit du clair-texte aura été affecté et l'erreur ne se propagera pas à d'autres parties du message. Cette propriété est utile quand le taux d'erreur de transmission est élevé ; mais dans ce cas les erreurs ont moins de chance d’être détectée. De plus, à cause de cette propriété, les chiffrements par flot synchrones sont fragiles face aux attaques actives : si un adversaire peut changer un bit dans le cryptogramme, alors il pourrait être en mesure de faire des changements prévisibles au niveau du clair-texte. En effet, changer un bit dans le cryptogramme entraîne le changement du bit du clair-texte situé au même endroit. provoque le même bit pour être retourné dans le texte clair. +Si, cependant, un chiffre est corrompu durant la transmission, sans qu’il y ait décalage, alors seul un bit du clair-texte aura été affecté et l'erreur ne se propagera pas à d'autres parties du message. Cette propriété est utile quand le taux d'erreur de transmission est élevé ; mais dans ce cas les erreurs ont moins de chance d’être détectée. De plus, à cause de cette propriété, les chiffrements par flot synchrones sont fragiles face aux attaques actives : si un adversaire peut changer un bit dans le cryptogramme, alors il pourrait être en mesure de faire des changements prévisibles au niveau du clair-texte. En effet, changer un bit dans le cryptogramme entraîne le changement du bit du clair-texte situé au même endroit. provoque le même bit pour être retourné dans le texte clair~\cite{Wu2008,Daemen1994}. \subsection{ chiffrements par flot auto-synchronisants} -Une autre approche utilise un certain nombre des $N$ derniers chiffres du cryptogramme pour calculer le keystream. De tels schémas sont aussi appelés chiffrements par flot asynchrones, ‘’cryptogramme autokey’’ (CTAK). L'idée de l’auto-synchronisation a été brevetée en 1946. Elle a l'avantage que le récepteur peut auto-matiquement se synchroniser avec le générateur keystream après avoir reçu $N$ chiffres du cryptogramme, rendant ainsi facile la resynchronisation en cas d’ajout ou de perte de chiffres lors de la transmission. Des erreurs portant sur un chiffre seul seront limités dans leurs protée, affectant seulement au plus $N$ chiffres du clair-texte. +Une autre approche utilise un certain nombre des $N$ derniers chiffres du cryptogramme pour calculer le keystream. De tels schémas sont aussi appelés chiffrements par flot asynchrones, ‘’cryptogramme autokey’’ (CTAK). L'idée de l’auto-synchronisation a été brevetée en 1946~\cite{schneier1996applied}. Elle a l'avantage que le récepteur peut auto-matiquement se synchroniser avec le générateur keystream après avoir reçu $N$ chiffres du cryptogramme, rendant ainsi facile la resynchronisation en cas d’ajout ou de perte de chiffres lors de la transmission. Des erreurs portant sur un chiffre seul seront limités dans leurs protée, affectant seulement au plus $N$ chiffres du clair-texte. -Un exemple de chiffrement par flot auto-synchronisation est un chiffrement par bloc en mode Cipher Feedback (CFB). +Un exemple de chiffrement par flot auto-synchronisation est un chiffrement par bloc en mode Cipher Feedback (CFB)~\cite{Meyer100035}. \section{ Générateurs de nombres aléatoires basés sur le chaos } -Depuis les années 70, l'utilisation de dynamiques chaotiques pour la génération de suites aléatoires et les applications cryptographiques a soulevé beaucoup d'intérêt. De nombreux ponts entre la théorie du chaos et la cryptographie ont été établis ces deux dernières décennies qui ont conduit à de nombreux travaux de recherche. +Depuis les années 70, l'utilisation de dynamiques chaotiques pour la génération de suites aléatoires et les applications cryptographiques a soulevé beaucoup d'intérêt. De nombreux ponts entre la théorie du chaos et la cryptographie ont été établis ces deux dernières décennies qui ont conduit à de nombreux travaux de recherche~\cite{STMAZ.01769371}. Les dynamiques chaotiques sont habituellement étudiées dans deux différents domaines. Dans le domaine des temps continus, dans lequel ces dynamiques sont produites à partir de systèmes chaotiques issus d’équations différentielles. Dans le domaine des temps discrets, dans lequel une fonction chaotique est utilisée dans une relation de récurrence. diff --git a/GeneralNotions.tex.backup b/GeneralNotions.tex.backup index 36ed6ed..4165b7a 100644 --- a/GeneralNotions.tex.backup +++ b/GeneralNotions.tex.backup @@ -1,176 +1,159 @@ -\chapter{General Notions} -\label{General Notions} +\chapter{Notions générales} +\label{Notions générales} \minitoc -This chapter, serving as the background of this thesis, is devoted to basic notations and terminologies in the fields of random number and its classification. +Ce chapitre, faisant office de fondations pour cette thèse, introduit la terminologie et les notations utilisés dans le domaine des générateurs de nombres pseudo-aléatoires. +\section{ Aléas} +Une suite aléatoire de bits peut s’interpréter comme le résultat de lancers d’une pièce équilibrée (non-biaisée). On assimiler "Pile" à "0" et "face" à "1", et l’on suppose que chaque lancer a une probabilité $1/2$ exactement de produire un "0", et parcellement pour "1". On suppose de plus que les lancers sont indépendants les uns des autres: le résultat n’importe quel précédent lancer n’affecte pas les lancers à venir. La pièce sans biais et équitable est alors l’image d’un générateur aléatoire de bits parfait, puisque les " 0 " et "1" seront aléatoirement distribués. Tous les éléments de la suite sont générés indépendamment les uns des autres, et la valeur de l'élément suivant dans la suite ne peut être prédite à partir de la suite des nombres déjà obtenus, et ce quelle que soit la grandeur de cette suite~\cite{Deborah1998,Kallenberg1986}. Cependant, clairement, l'utilisation de pièces non biaisées à des fins cryptographiques est impraticable en pratique. Quai qu’il en soit, la sortie hypothétique d'un tel générateur idéal de suites réellement aléatoire sert de critère de comparaison (benchmark) pour l'évaluation des générateurs de nombres aléatoires et pseudo aléatoires~\cite{ANDREW2008}. -\section{Randomness} -A random bit sequence could be interpreted as the result of the flips of an unbiased "fair" coin with sides -that are labeled "0" and "1," with each flip having a probability of exactly $1/2$ of producing a "0" or "1." -Furthermore, the flips are independent of each other: the result of any previous coin flip does not affect -future coin flips. The unbiased "fair" coin is thus the perfect random bit stream generator, since the "0" -and "1" values will be randomly distributed (and [0,1] uniformly distributed). All elements of the -sequence are generated independently of each other, and the value of the next element in the sequence -cannot be predicted, regardless of how many elements have already been produced. -Obviously, the use of unbiased coins for cryptographic purposes is impractical. Nonetheless, the -hypothetical output of such an idealized generator of a true random sequence serves as a benchmark for -the evaluation of random and pseudorandom number generators.~\cite{ANDREW2008} +\section{Différents types de générateurs de nombres aléatoires (RNG)} +Un RNG est un composant informatique ou physique, assemblé pour produire une suite de nombres ou de symboles qui semble aléatoires~\cite{William2007}. -\section{Types of Random Number Generators (RNGs)} -A RNG is a computational or physical device designed to generate a sequence of numbers or symbols that lack any pattern, i.e. appear random. -It is always a difficult task to generate good random number/sequence. Although it is accepted that rolling a dice or drawing cards is random these mechanical methods are not practical. in the past, random numbers are usually generated offline based on some dedicated setup or devices, and the sequences are stored in table ready for use. These random tables are still available in the world-wide-web or some data CDROMs. +Générer une bonne suite aléatoires est une tâche difficile. On peut bien évidemment obtenir une telle suite à partir d’un lancer de clés ou d’une pièce de monnaie, un tel procède mécanique n’est, on l’a dit, pas pratique. Il y a quelques temps de cela, les nombres aléatoires étaient générés à partir et tabulées en utilisant par exemple les procèdes mécaniques évoqués ci-dessus. Ces tables prêtes à l'emploi peuvent encore se trouver sur le web ou sur des CDs de données dédiés. -However, due to the online requirements and the security issues, random table becomes inappropriate, and hence different RNGs have been proposed, especially after the introduction of computer. -In general, RNGs can be grouped into two classes, namely true random number gernerators and pseudo random number generators, depending on their sources of randomness. -RNGs can be classified as: -\subsection{True Random Number Generators (TRNGs)} -A TRNG is one which generates statistically independent and unbiased bits. These are also -called as non-deterministic RNGs. In computing, a True random number generator is an apparatus that generates random numbers from a physical process. Such devices are often based on microscopic phenomena that generate a low-level, statistically random "noise" signal, such as thermal noise or the photoelectric effect or other quantum phenomena. These processes are, in theory, completely unpredictable, and the theory's assertions of unpredictability are subject to experimental test. A quantum-based hardware random number generator typically consists of a transducer to convert some aspect of the physical phenomena to an electrical signal, an amplifier and other electronic circuitry to bring the output of the transducer into the macroscopic realm, and some type of analog to digital converter to convert the output into a digital number, often a simple binary digit 0 or 1. By repeatedly sampling the randomly varying signal, a series of random numbers is obtained. +Cependant, du fait des besoins liés à Internet et aux problèmes de sécurité soulevés par cette approche, ces tables~\cite{Tippett1927} ne permettent plus de satisfaire les besoins en nombres aléatoires. C’est pourquoi de nouveaux types de RNG ont été introduits, notamment depuis l’apparition de l’informatique. -\subsection{Pseudo Random Number Generators (PRNGs)} -A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG),~\cite{Barker05recommendationfor} is an algorithm for generating a sequence of numbers that approximates the properties of random numbers. The sequence is not truly random in that it is completely determined by a relatively small set of initial values, called the PRNG's state. Although sequences that are closer to truly random can be generated using hardware random number generators, pseudorandom numbers are important in practice for simulations (e.g., of physical systems with the Monte Carlo method), and are central in the practice of cryptography and procedural generation. Common classes of these algorithms are linear congruential generators, Lagged Fibonacci generators, linear feedback shift registers, feedback with carry shift registers, and generalised feedback shift registers. Recent instances of pseudorandom algorithms include Blum Blum Shub, Fortuna, and the Mersenne twister. +Les RNG sont traditionnellement regroupés en deux classes, suivant leur source d’aléas: les générateurs de nombres vraiment aléatoires et les générateurs de nombres pseudo aléatoires. +\subsection{ Les générateurs de nombres vraiment aléatoires (TRNGs)} +Un TRNG est un générateur produisant des bits statistiquement indépendants et sans biais. Ils s’agit de RNG non déterministes. En informatique, un TRNG est un appareil produisant des nombres aléatoires à partir d'un processus physique~\cite{Pashley2010184}. De tels composants se basent souvent sur des phénomènes microscopiques génèrent un signal de bas niveau, un bruit statistiquement aléatoire. Les phénomènes peuvent être un "bruit thermal" utilisant les capteurs de température de l’ordinateur, peuvent utiliser l’effet photoélectrique ou tout autre phénomène quantique~\cite{Guler2011,WT198429,Danger2009,JarosławAdam2011}. En théorie, ces processus sont complètement imprévisible s; en pratique, une telle assertion se vérifie à l’aide de batteries tests statistiques. Un tel générateur quantique de type physique, consiste typiquement en un transducteur qui convertir un certains aspects d’un phénomène physique en un signal électrique. Ce transducteur est relié à un amplificateur et d'autres composant électroniques, dont le but est de porter la sortie du transducteur de l’échelle microscopique à l’échelle macroscopique. Enfin, un convertisseur analogique vers numérique permet de transformer a signal analogique en une suite de nombres, souvent de simples bits. On obtient ainsi une suite de bits en reproduisant le procédé tant que nécessaire. -\section{Cryptographically secure pseudo random number generators} +\subsection{ Les générateurs de nombres pseudo-aléatoires (PRNGs)} +Un PRNG, appelé aussi générateur déterministes de bits aléatoires (DRBG : Deterministic Random Bit Generator ) ~\cite{Barker05recommendationfor} est un algorithme générant une suite de nombres qui approximent les propriétés des nombres aléatoires. La suite n'est pas réellement aléatoire dans le sens où elle est complètement déterminée par un ensemble de valeurs initiales relativement petit, appelé l’état du PRNG. S’il est vrai que des suites proches d’un aléa pur peuvent être obtenues avec des générateurs physiques, cela ne signifie pas pour autant que les générateurs pseudo-aléatoires sont inutiles. Leur importance se matérialise lors de simulations, par exemple de systèmes physiques en utilisant la méthode de Monte Carlo. Ils sont de plus primordiaux en cryptographie et en génération procédurale~\cite{Tan20091618,StDenis200691}. Des classes bien connue de tels algorithmes sont les générateurs congruentiels linéaires~\cite{Knuth1998_1}, les Lagged Fibonacci générateurs~\cite{}, linéaire feedback shift registre~\cite{}, feedback with carry shift registers~\cite{}, and generalised feedback shift registers~\cite{}. Le Blum Blum Shub, le Fortuna, et le Mersenne Twister sont par exemple des instances récentes de ces classes d’algorithmes. -A PRNG suitable for cryptographic applications is called a cryptographically secure PRNG (CSPRNG). A requirement for a CSPRNG is that an adversary not knowing the seed has only negligible advantage in distinguishing the generator's output sequence from a random sequence. In other words, while a PRNG is only required to pass certain statistical tests, a CSPRNG must pass all statistical tests that are restricted to polynomial time in the size of the seed. Though such property cannot be proven, strong evidence may be provided by reducing the CSPRNG to a known hard problem in mathematics (e.g., integer factorization). In general, years of review may be required before an algorithm can be certified as a CSPRNG. -Some classes of CSPRNGs include the following: +\section{ PRNGs cryptographiquement sûrs } +Un PRNG pouvant être utilisé en cryptographie est appelé un PRNG cryptographiquement sûr (CSPRNG). Une propriété importante que doit satisfaire un CSPRNG est qu’un adversaire, ne connaissant pas la graine, n'a qu'un avantage négligeable de pouvoir distinguer la séquence produite par le générateur d'une séquence réellement aléatoire. En d'autres termes, tandis que l’en se demande à un PRNG que de passer certains tests statistiques, un CSPRNG doit passer tous les tests statistiques ayant un temps d’ exécuter polynomial par rapport à la taille de la graine. Bien qu’une telle propriété ne peut pas être prouvée~\cite{ }, on peut cependant s’en approcher en réduisant ce problème pour un générateur à un problème NP-difficile tel que la factorisation des entiers. En général, des années d’étude sont requises avant de pouvoir certifier qu’un algorithme donné est un CSPRNG. + + +Donnons maintenant quelques classes de CSPRNGs: \begin{itemize} -\item Stream ciphers -\item Block ciphers running in counter or output feedback mode. -\item PRNGs that have been designed specifically to be cryptographically secure, such as Microsoft's Cryptographic - Application Programming Interface function CryptGenRandom, the Yarrow algorithm (incorporated in Mac OS X and FreeBSD), and Fortuna. -\item Combination PRNGs which attempt to combine several PRNG primitive algorithms with the goal of removing any non-randomness. -\item Special designs based on mathematical hardness assumptions. Examples include Micali-Schnorr and the Blum Blum Shub algorithm, which provide a strong security proof. Such algorithms are rather slow compared to traditional constructions, and impractical for many applications. - +\item les chiffrements par flot (Stream ciphers). +\item les chiffrements par bloc fonctionnant en mode counter ou output feedback mode. +\item certains PRNGs produit expressément pour être cryptographiquement sûr, tels que la fonction CryptGenRandom de Microsoft, l'algorithme Yarrow (embarqué dans le Mac OS X et dans FreeBSD), et Fortuna. +\item la combinaison de PRNGs telle que le PRNG résultant ne possède plus aucune trace de non-aléas. +\item des PRNG spécialement conçus à partir de problèmes mathématiques difficiles, tels que les algorithmes Micali-Schnorr et Blum Blum Shub. Ces algorithmes sont livrés avec des preuves de sécurité rigoureuses. En contre partie, ces CSPRNGs sont lents, voire inutilisables pour un certain nombre d’applications. \end{itemize} -A stream cipher is a cryptographic technique that encrypts binary digits individually, using a transformation that changes with time. This is contrasted to a block cipher, where a block of binary data is encrypted simultaneously, with the transformation usually being constant for each block. -In specific applications, stream ciphers are more appropriate than block ciphers~\cite{Preneel03nessied20,Robshaw95streamciphers}: + +Le chiffrement par flot est technique cryptographique qui chiffre les bits individuellement, en utilisant une transformation qui change au cours du temps. A contrario dans un chiffrement par blocs, le clair-texte est découpé en blocs, et chaque bloc de bits est chiffré d’un coup, en simultané, la même transformation s’appliquant chacun des blocs. + + +Dans certaines applications spécifiques, les chiffrements par flots sont plus appropriés que les chiffrements par bloc ~\cite{Preneel03nessied20, Robshaw95streamciphers}: \begin{enumerate} -\item Stream ciphers are generally faster than block ciphers, especially in hardware. -\item Stream ciphers have less hardware complexity and less memory requirements for both hardware and software. -\item Stream ciphers process the plaintext character by character, so no buffering is required to accumulate a full plaintext block (unlike block ciphers). -\item Synchronous stream ciphers have no error propagation. +\item Les chiffrements par flots sont généralement plus rapides que le chiffrements par bloc, surtout quand ces premiers sont produits au niveau matériel. +\item Les chiffrements par flots ont une complexité matérielle plus faible, et nécessitent moins de mémoire, et ce que ce soit au niveau hardware ou software. +\item Les chiffrements par flots opèrent sur le clair-texte caractère par caractère, et ainsi aucun tampon n.est nécessaire, il n’y a pas besoin d'accumuler un bloc complet du clair-texte (contrairement au chiffrement par bloc). +\item Les chiffrements par flots synchrones n'ont pas de propagation d’erreur~\cite{ }. \end{enumerate} -\section{Stream Cipher} -A stream cipher generates successive elements of the keystream based on an internal state. This state is updated in essentially two ways: if the state changes independently of the plaintext or ciphertext messages, the cipher is classified as a synchronous stream cipher. By contrast, self-synchronising stream ciphers update their state based on previous ciphertext digits. +\section{Le chiffrement par flot} +Un chiffrement par flot génère le flux de sortie (cryptogramme) à partir d’un état interne. Cet état est mis à jour, essentiellement de deux manières différentes. Dans le premier cas de figure, l’état change indépendamment du clair-texte ou du cryptogramme. On parle alors de chiffrement par flot synchrone. Par contre, dans le cas des chiffrements par flot auto-synchronisant, l’état est mis à jour à partir des derniers bits du cryptogramme calculès. + + +\subsection{Les masque jetable( One-Time Pad, ou chiffrement Vernam)} +Le chiffrement de Vernam est un chiffrement par flot dans lequel on applique le XORshift entre chaque bit du clair-texte et le bit correspondant d’un flux de données aléatoire ou pseudo-aléatoire, appelé le keystream, ayant la même faille que le clair-texte. Si le keystream est réellement aléatoire et utilisé une seule fois, il s’agit alors du masque jetable (One-Time Pad) + + +Shannon a montré~\cite{Shannon-OTP} que le masque jetable fournit une sécurité parfaite. Cela veut dire que l'entropie conditionnelle du message $M$ connaissant le cryptogramme $ C $, est la même que l'entropie du message d'origine : $H(M|C) = H(M)$. Shannon a aussi montré que le masque jetable est optimale : la condition précédente ne peut être obtenue avec une clé de taille plus petite que le message $M$. + + +Le problème avec le masque jetable est que l’on doit avoir une clé de la faille du message, ce qui dans la plupart des cas est impossible en pratique. Les deux schémas suivants tentent de produire un keystream à l’allure aléatoire à partir d’une petite clé. Par allure aléatoire, il faut comprendre que l’on ne doit pas pouvoir faire la distinction entre le keystream et une suite aléatoire, en une complexité inférieure à celle intervenant quand on tente toutes les clés possibles. + -\subsection{One-Time Pad (Vernam Cipher)} -In modern terminology, a Vernam cipher is a stream cipher in which the plaintext is XORed with a random or pseudorandom stream of data (the keystream) of the same length to generate the ciphertext. If the keystream is truly random and used only once, this is effectively a one-time pad. +\subsection{ chiffrements par flots synchrones} +Dans un chiffrement par flot synchrone, le flux de nombres pseudo-aléatoires est produit indépendamment du clair-texte et du cryptogramme, puis est ensuite combiné soit au clair-texte à chiffrer, soit au cryptogramme à déchiffrer. -Shannon~\cite{shannon-otp} showed that the one-time pad provides perfect security. This means -that the conditional entropy of the message $M$ knowing the ciphertext $C$ is the same as the -entropy of the original message, i.e. $H(M|C) = H(M)$. He also showed that the one-time -pad is optimal in the sense that the previous conditions cannot be achieved with a key of -size smaller than the message. -The problem of the one-time pad is that we first have to agree on a key of the same -length as the message. For most applications this is not practical. The next two schemes -try to produce a ``random looking`` keystream from a short key and IV. By random looking, -we mean that we cannot distinguish the keystream from a random sequence in a complexity -less than trying all possible keys. +Dans un chiffrement par flot synchrone, l'expéditeur et le récepteur doivent être exactement synchronisés pour que le déchiffrement puisse se faire sans encombre. Si des chiffres sont ajoutés ou enlevés du message pendant la transmission, alors la synchronisation sera perdue. Pour la restaurer, on peut effectuer différentes tentatives de déchiffrement à partir de keystream décalés jusqu’à obtenir un message intelligible. Une autre approche consiste à introduire des marqueurs dans le cryptogramme, comme autant de repères permettant une resynchronisation. -\subsection{Synchronous stream ciphers} -In a synchronous stream cipher a stream of pseudo-random digits is generated independently of the plaintext and ciphertext messages, and then combined with the plaintext (to encrypt) or the ciphertext (to decrypt). In the most common form, binary digits are used (bits), and the keystream is combined with the plaintext using the exclusive or operation (XOR). This is termed a binary additive stream cipher. -In a synchronous stream cipher, the sender and receiver must be exactly in step for decryption to be successful. If digits are added or removed from the message during transmission, synchronisation is lost. To restore synchronisation, various offsets can be tried systematically to obtain the correct decryption. Another approach is to tag the ciphertext with markers at regular points in the output. +Si, cependant, un chiffre est corrompu durant la transmission, sans qu’il y ait décalage, alors seul un bit du clair-texte aura été affecté et l'erreur ne se propagera pas à d'autres parties du message. Cette propriété est utile quand le taux d'erreur de transmission est élevé ; mais dans ce cas les erreurs ont moins de chance d’être détectée. De plus, à cause de cette propriété, les chiffrements par flot synchrones sont fragiles face aux attaques actives : si un adversaire peut changer un bit dans le cryptogramme, alors il pourrait être en mesure de faire des changements prévisibles au niveau du clair-texte. En effet, changer un bit dans le cryptogramme entraîne le changement du bit du clair-texte situé au même endroit. provoque le même bit pour être retourné dans le texte clair. -If, however, a digit is corrupted in transmission, rather than added or lost, only a single digit in the plaintext is affected and the error does not propagate to other parts of the message. This property is useful when the transmission error rate is high; however, it makes it less likely the error would be detected without further mechanisms. Moreover, because of this property, synchronous stream ciphers are very susceptible to active attacks -- if an attacker can change a digit in the ciphertext, he might be able to make predictable changes to the corresponding plaintext bit; for example, flipping a bit in the ciphertext causes the same bit to be flipped in the plaintext. -\subsection{Self-synchronizing stream ciphers} -Another approach uses several of the previous N ciphertext digits to compute the keystream. Such schemes are known as self-synchronizing stream ciphers, asynchronous stream ciphers or ciphertext autokey (CTAK). The idea of self-synchronization was patented in 1946, and has the advantage that the receiver will automatically synchronise with the keystream generator after receiving N ciphertext digits, making it easier to recover if digits are dropped or added to the message stream. Single-digit errors are limited in their effect, affecting only up to N plaintext digits. +\subsection{ chiffrements par flot auto-synchronisants} +Une autre approche utilise un certain nombre des $N$ derniers chiffres du cryptogramme pour calculer le keystream. De tels schémas sont aussi appelés chiffrements par flot asynchrones, ‘’cryptogramme autokey’’ (CTAK). L'idée de l’auto-synchronisation a été brevetée en 1946. Elle a l'avantage que le récepteur peut auto-matiquement se synchroniser avec le générateur keystream après avoir reçu $N$ chiffres du cryptogramme, rendant ainsi facile la resynchronisation en cas d’ajout ou de perte de chiffres lors de la transmission. Des erreurs portant sur un chiffre seul seront limités dans leurs protée, affectant seulement au plus $N$ chiffres du clair-texte. -An example of a self-synchronising stream cipher is a block cipher in cipher feedback (CFB) mode. +Un exemple de chiffrement par flot auto-synchronisation est un chiffrement par bloc en mode Cipher Feedback (CFB). +\section{ Générateurs de nombres aléatoires basés sur le chaos } +Depuis les années 70, l'utilisation de dynamiques chaotiques pour la génération de suites aléatoires et les applications cryptographiques a soulevé beaucoup d'intérêt. De nombreux ponts entre la théorie du chaos et la cryptographie ont été établis ces deux dernières décennies qui ont conduit à de nombreux travaux de recherche. -\section{Chaos-based random number generators} -Since the seventies, the use of chaotic dynamics for the generation of random sequences and cryptographical applications has raised a lot of interests. It is clearly pointed out by some researchers that there exists a close relationship between chaos and cryptography, and many research works have been witnessed in the last two decades. -chaotic dynamics are usually studied in two different domains, the continuous time domain where the dynamics are generated from a chaotic system specified in differential equations, or a chaotic map quoted with recurrence relationship in the discrete time domain. +Les dynamiques chaotiques sont habituellement étudiées dans deux différents domaines. Dans le domaine des temps continus, dans lequel ces dynamiques sont produites à partir de systèmes chaotiques issus d’équations différentielles. Dans le domaine des temps discrets, dans lequel une fonction chaotique est utilisée dans une relation de récurrence. -chaos possesses several distinct propertie, including sensitivity to initial conditions, ergodicity and wide band spectrum. contributing its unpredictable and random manner in practice. Although it is still controversy to equate these properties with randomness and claim a chaos-based random number generator to be good enough, a lot of designs and applications, in particularly, related with the secure communications have been proposed. -It is common to use a chaotic map for pseudo-random number generation. Due to the recent design of electonic circuits for the realization fo chaotic systems, it is also possible to generate the bit sequence by observing such dynamics, as a replacement of those physical random sources. +Le chaos fait référence à un certain nombre de propriétés distinctes, incluant la sensibilité aux conditions initiales, l’ergodicité et le spectre large bande, contribuant toutes au caractère imprévisible et semblant aléatoire du système considéré. Assimiler ces propriétés, ou du moins les relier, à une forme d’aléas en affirmant que les générateur basés sur du chaos, sont de bons générateurs aléatoires, même à la controverse. Toutefois il est indéniable qu’un certain nombre de ces générateurs ont été proposés dans dévases applications, notamment dans la sécurisation de communications, et avec un certain succès. -\section{Continuous Chaos in Digital Computers} -In the past two decades, the use of chaotic systems in the design of cryptosystems, PRNG, and hash functions, has become more and more frequent. -Generally speaking, the chaos theory in the continuous field is used to analyze performances of related systems. +Il est dorénavant commun d'utiliser des fonctions chaotiques pour la génération de nombres pseudo-aléatoires. Et du fait de la Grâce à la construction récente de circuits électroniques pour la réalisation des systèmes chaotiques, il est aussi dorénavant possible de générer la suite de bits en observant de telle dynamique, apportant ainsi une méthode complémentaire pour la génération matérielle d’aléas. -However, when chaotic systems are realized in digital computers with finite computing precisions, it is doubtful whether or not they can still preserve the desired dynamics of the continuous chaotic systems. Because most dynamical properties of chaos are meaningful only when dynamical systems evolve in the continuous phase space, these properties may become meaningless or ambiguous when the phase space is highly quantized (i.e., latticed) with a finite computing precision (in other words, dynamical degradation of continuous chaotic systems realized -in finite computing precision). -The quantization errors, which are introduced into iterations of digital chaotic systems for every iteration, will make pseudo orbits depart from real ones with very complex and uncontrolled manners. Because of the sensitivity of chaotic systems on initial conditions, even ''trivial'' changes of computer arithmetic can definitely change pseudo orbits' structures. +\section{ Chaos continu dans les ordinateurs} +Au cours les deux dernières décennies, l'utilisation de systèmes chaotiques pour concevoir de nouveaux cryptosystèmes, des PRNG, voire des fonctions de hachage, est devenu de plus en plus fréquentes. D’une manière générale, la théorie du chaos sur des espaces continu est utilisée dans le but d’analyser les performances des systèmes considèrés. -Although all quantization errors are absolutely deterministic when the finite precision and the arithmetic are fixed, it is technically impossible to know and deal with all errors in digital iterations. Some random perturbation models have been proposed to depict quantization errors in digital chaotic systems, but they cannot exactly predict the actual dynamics of studied digital chaotic systems and has been criticized because of their essentially deficiencies +Cependant, quand des systèmes chaotiques sont mis en œuvre dans des ordinateurs ayant une précision finie, il est naturel de se demander si la dynamique désirée présente dans le système continu est préservée sur la machine. En fait la plupart des propriétés de chaos n’ont de sens que quand les systèmes dynamiques évoluent sur la droite réelle, et ces propriétés peuvent perdre tout leur sens, ou tout le moins devenir ambiguës, quand l'espace sur lequel on itère est fortement quantifié, ou lorsque l’on travaille à précision finie (en d'autres termes, la dynamique chaotique d’un systèmes continu se dégrade lorsque l’en effectue des calculs à précision finie). -When chaotic systems are realized in finite precision, their dynamical properties will be deeply different from the properties of continuous-value systems and some dynamical degradation will arise, such as short cycle length and decayed distribution. This phenomenon has been reported and analyzed in various situations~\cite{Binder1986,Wheeler1989,Palmore1990,Blank1997,Li2005}. +Les erreurs de quantification, qui sont introduites à chaque itération d’un système chaotique numérique, produiront des pseudo orbites qui s’éloigneront des orbites réelles d’une manière complexe et incontrôlé. Du fait de la sensibilité aux conditions initiales des systèmes chaotiques, même des changements élémentaires introduits par l'arithmétique des ordinateurs peuvent définitivement changer les structures des pseudo orbites. -Therefore, continuous chaos may collapse into the digital world and the ideal way to generate pseudo-random sequences is to use Chaotic iterations. +Même si ces erreurs de quantification sont complètement déterministes quand l'arithmétique et sa précision sont fixes, il est techniquement impossible de connaître et de traiter toutes les erreurs intervenant dans les itérations numériques. Des modèles de perturbation aléatoire ont bien été proposés pour représenter les erreurs de quantification dans les systèmes chaotique numériques, mais ils ne peuvent pas prévoir exactement la dynamique réelle de systèmes dynamiques numériques étudiées, et ces modèles ont de ce fait été critiqué pour leur manque de réalité. +Quand des systèmes chaotiques sont mis en œuvre sur des machines à précision finie, leurs propriétés dynamiques seront profondément différentes des propriétés des systèmes à valeurs continues. Des dégradations vont apparaître, telles que l’apparition de cycles de petite longueur et des distributions decayed. Ce phénomène a été rapporté et analysé dans diverses situations~\cite{Binder1986,Wheeler1989,Palmore1990,Blank1997,Li2005}. -\section{Chaos for Discrete Dynamical Systems} -Consider a metric space $(\mathcal{X},d)$ and a continuous function $f:\mathcal{X}\longrightarrow \mathcal{X}$, for one-dimensional dynamical systems of the form: +Par conclure, un système chaotique continu peut perdre ses propriétés quand on le porte sur ordinateur. C’est pourquoi, à notre sens, le meilleur moyen de concevoir un générateur de nombres pseudo-aléatoires chaotiques consiste à utiliser les itérations chaotiques. + +\section{ Chaos pour des systèmes dynamiques discrets} +On considère espace métrique $(\mathcal{X},d)$ et une fonction continue $f:\mathcal{X}\longrightarrow \mathcal{X}$. Soit le systèmes dynamiques: \begin{equation} x^0 \in \mathcal{X} \textrm{ and } \forall n \in \mathds{N}^*, x^n=f(x^{n-1}), \label{Devaney} \end{equation} -the following definition of chaotic behavior, formulated by Devaney~\cite{Dev89}, is widely accepted: + +La définition suivante d’un comportement chaotique, formulée par Devaney~\cite{Dev89}, est largement accepté: \begin{definition} - A dynamical system of form~\ref{Devaney} is said to be chaotic if the following conditions hold. + Un système dynamique de la forme ~\ref{Devaney} est dit chaotique s’il vérifie les propriétés suivantes : \begin{itemize} -\item Topological transitivity: +\item Transitivité topologique: \begin{equation} -\forall U,V \textrm{ open sets of } \mathcal{X}, ~\exists k>0, f^k(U) \cap V \neq \varnothing +\forall U,V \textrm{ ouverts de } \mathcal{X}, ~\exists k>0, f^k(U) \cap V \neq \varnothing \end{equation} - -Intuitively, a topologically transitive map has points which eventually move under iteration from one arbitrarily small neighborhood to any other. Consequently, the dynamical system can not be decomposed into two disjoint open sets which are invariant under the map. Note that if a map possesses a dense orbit, then it is clearly topologically transitive. -\item Density of periodic points in $\mathcal{X}$: - -Let $P=\{p\in \mathcal{X}|\exists n \in \mathds{N}^{\ast}:f^n(p)=p\}$ the set of periodic points of $f$. Then $P$ is dense in $\mathcal{X}$: - +Intuitivement, une fonction topologiquement transitive est telle que deux points aussi proches que l’om veut peuvent finir par se retrouver en des lieux complètement différents. D’autre part, le système dynamique est intrinsèquement compliqué et ne peut être décomposé en deux ouverts disjoints invariants sous les itérations de $f$. Enfin, signalons que si le système possède une orbite dense, alors il est clairement transitif. +\item Densité de points périodiques dans $\mathcal{X}$: +Soit $P=\{p\in \mathcal{X}|\exists n \in \mathds{N}^{\ast}:f^n(p)=p\}$ l'ensemble des points périodiques de $f$. Alors $P$ est dense dans $\mathcal{X}$: \begin{equation} \overline{P}=\mathcal{X} \end{equation} - -Intuitively, Density of periodic orbits means that every point in the space is approached arbitrarily closely by periodic orbits. Topologically mixing systems failing this condition may not display sensitivity to initial conditions, and hence may not be chaotic. -\item Sensitive dependence on initial conditions: - +Intuitivement, cette densité signifie que chaque point de l’espace est proche autant que l’on veut de points périodiques. Les systèmes transitifs ne présentant pas cette propriété peuvent ne pas être sensibles à la condition initiale, ce qui justifie en partie cette introduction d’un élément de régularité dans une définition de chaos. +\item Sensibilité à la condition initiale: $\exists \varepsilon>0,$ $\forall x \in \mathcal{X},$ $\forall \delta >0,$ $\exists y \in \mathcal{X},$ $\exists n \in \mathbb{N},$ $d(x,y)<\delta$ and $d\left(f^n(x),f^n(y)\right) \geqslant \varepsilon.$ - -Intuitively, a map possesses sensitive dependence on initial conditions if there exist points arbitrarily close to $x$ which eventually separate from $x$ by at least $\varepsilon$ under iteration of $f$. Not all points near $x$ need eventually separate from $x$ under iteration, but there must be at least one such point in every neighborhood of $x$. If a map possesses sensitive dependence on initial conditions, then for all practical purposes, the dynamics of the map defy numerical computation. Small errors in computation which are introduced by round-off may become magnified upon iteration. The results of numerical computation of an orbit, no matter how accurate, may bear no resemblance whatsoever with the real orbit. +Un système donc sensible aux conditions initiales, si il existe des points arbitrairement proches de $x$ qui s’éloignent à terme d’au moins $\varepsilon$ de $x$. Tous les points voisins de $x$ ne s’éloigneront pas forcément de $\varepsilon$: il faut qu’il s’en trouve au moins un dans chaque voisinage de $x$. Si une fonction possède cette dépendance aux conditions initiales, alors pour toutes les applications pratiques, la dynamique de la fonction défie tous les calculs numériques. De petites erreurs au cours du calcul, introduites par exemple du fait des erreurs d’arrondi, peuvent devenir non négligeables au cours des itérations. Le résultat du calcul numérique d'une orbite peut n’avoir aucune ressemblance avec l'orbite originale. \end{itemize} - \end{definition} -When $f$ is chaotic, then the system $(\mathcal{X}, f)$ is chaotic and quoting Devaney: ``it is unpredictable because of the sensitive dependence on initial conditions. It cannot be broken down or decomposed into two subsystems which do not interact because of topological transitivity. And, in the midst of this random behavior, we nevertheless have an element of regularity.'' Fundamentally different behaviors are consequently possible and occur in an unpredictable way. +Quand le système $(\mathcal{X}, f)$ est chaotique, on peut dire, en citant Devaney: `` il est imprévisible du fait de la dépendance aux conditions initiales. Il ne peut pas être cassé ou décomposé en deux sous-systèmes qui n'interagissent pas du fait de la transitivité topologique. Et en dépit de a comportement aléatoire, on a cependant un élément de régularité. `` Des comportements fondamentalements différents sont possibles et ils interviennent de manière imprévisible. - -\section{Chaotic iterations} -\label{subsection:Chaotic iterations} +\section{ Les itérations chaotiques} +\label{ Les itérations chaotiques } \begin{definition} \label{Chaotic iterations} -The set $\mathds{B}$ denoting $\{0,1\}$, let $f:\mathds{B}^{\mathsf{N}% -}\longrightarrow \mathds{B}^{\mathsf{N}}$ be an ``iteration'' function and $S\in \mathbb{S} -$ be a chaotic strategy. Then, the so-called \emph{chaotic iterations} are defined by~\cite{Robert1986}: +L’ensemble $\mathds{B}$ désignant $\{0,1\}$, soit $f:\mathds{B}^{\mathsf{N}% +}\longrightarrow \mathds{B}^{\mathsf{N}}$ une ``fonction d’itération'' et $S\in \mathbb{S} +$ une stratégie chaotique. Les \emph{ itérations chaotiques } sont définies par~\cite{Robert1986}: \begin{equation} \left\{\begin{array}{l} @@ -187,16 +170,8 @@ f(x^{n-1})_{S^n} & \text{if}~S^n=i. \right. \end{equation} \end{definition} +En d'autres termes, à la $n$-ième itérée, seule la $S^{n}$-ième cellule est mise à jour. Signalons que l’on peut fournir une définition plus générale, soit en considérant que $S^{n}$ est un sous-ensemble de $\llbracket 1;\mathsf{N} \rrbracket$, soit en remplaçant $f(x^{n-1})_{S^{n}}$ par $f(x^{k})_{S^{n}}$, où$k < n$, pour décrire par exemple des retards à la transmission des celleles ~\cite{Bahi2000}. Pour la définition générale de telles itérations chaotiques, on pourra se rapporter à~\cite{Robert1986}. +Les itérations chaotiques engendrent un ensemble de vecteurs de bits. Elles sont définies par un état initial $x^{0}$, une fonction d'itération $f$, et une stratégie chaotique $ S $. -In other words, at the $n^{th}$ iteration, only the $S^{n}-$th cell is -\textquotedblleft iterated\textquotedblright . Note that in a more general -formulation, $S^n$ can be a subset of components and $f(x^{n-1})_{S^{n}}$ can -be replaced by $f(x^{k})_{S^{n}}$, where $k < n$, describing for -example delays transmission (see \emph{e.g.}~\cite{Bahi2000}). For the -general definition of such chaotic iterations, see, e.g.~\cite{Robert1986}. - -Chaotic iterations generate a set of vectors (boolean vector in this paper), -they are defined by an initial state $x^{0}$, an iteration function $f$, and a chaotic strategy $S$. -The next subsection gives the outline proof that chaotic iterations satisfy Devaney's topological chaos property. Thus they can be used to define a new pseudo-random bit generator. - +Le paragraphe suivant donne l’aperçu preuve que itérations chaotiques de satisfaire la propriété de chaotique topologique par Devaney. Ainsi, ils peuvent être utilisés pour définir un nouveaux générateurs de nombres pseudo-aléatoires. diff --git a/Introduction.tex b/Introduction.tex index c8923b2..6311035 100644 --- a/Introduction.tex +++ b/Introduction.tex @@ -41,7 +41,7 @@ systems in the first case or because machine precision in the second case~\cite{ Pseudo Random Number Generators (PRNGs) are widely used in science and technology, it is a critical component in modern cryptographic systems, communication systems, statistical simulation systems and any scientific area incorporating Monte Carlo methods~\cite{Vadim2011692,Marchi20093328,citeulike:867581,thecolourblue:1046} and many others. By the way, the Monte Carlo method appeared on the scientific scene in the late 1940s, for problems involving particle scattering in nuclear physics~\cite{Dyadkin1997258}. In the present era, there are few scientific fields that do not use random number. One of the most important applications of PRNGs is in cryptography to generate cryptographic keys, and to randomly initialize certain variables in cryptographic protocols. -Moreover, the idea o f applying chaos theory to randomness has produced important works very recently ~\cite{james1995,Gonzalez1999109,Ergun2007235,Zhou20093442,Gonzalez2002259,Behnia20113455}. Chaos theory has been established since 1970s by many different research areas, such as physics, mathematics, engineering, and biology, etc. ~\cite{Hao1993}. Since 1990s, many researchers have noticed that there exists the close relationship between chaos and cryptography ~\cite{Brown1996,Fridrich98symmetricciphers}; many properties of chaotic systems have their corresponding counterparts in traditional cryptosystems. Chaotic systems have several significant features favorable to secure communications, such as ergodicity, sensitivity to initial condition, control parameters and random like behaviour, which can be connected with some +Moreover, the idea o f applying chaos theory to randomness has produced important works very recently ~\cite{james1995,Gonzalez1999109,Ergun2007235,Zhou20093442,Gonzalez2002259,Behnia20113455}. Chaos theory has been established since 1970s by many different research areas, such as physics, mathematics, engineering, and biology, etc. ~\cite{Hao1993}. Since 1990s, many researchers have noticed that there exists the close relationship between chaos and cryptography ~\cite{Brown1996,Fridrich98symmetricciphers,Zaher20113721,Wong200367,Roland2001429,MS199850}; many properties of chaotic systems have their corresponding counterparts in traditional cryptosystems. Chaotic systems have several significant features favorable to secure communications, such as ergodicity, sensitivity to initial condition, control parameters and random like behaviour, which can be connected with some conventional cryptographic properties of good ciphers, such as confusion/diffusion. With all these advantages scientists expected to introduce new and powerful tools of chaotic cryptography. Cryptography is the art of achieving security by encoding messages to make them non-readable. Nowaday, some efficient techniques for encoding based on discrete time chaotic systems are presented in ~\cite{Djema2009,Belmouhoub2005}. A good random number generation improves the cryptographic security ~\cite{Behnia2008408}. diff --git a/Thesis.bib b/Thesis.bib index 3836d5b..425a13a 100644 --- a/Thesis.bib +++ b/Thesis.bib @@ -7,7 +7,77 @@ year = "2008", crossref = "DBLP:conf/seta/2008", bibsource = "DBLP, http://dblp.uni-trier.de", - ee = "http://dx.doi.org/10.1007/978-3-540-85912-3\\\\\\\\\\\\_1" + ee = "http://dx.doi.org/10.1007/978-3-540-85912-3\\\\\\\\\\\\\_1" +} + +@Article{ Zaher20113721, + title = "On the design of chaos-based secure communication systems", + journal = "Communications in Nonlinear Science and Numerical Simulation", + volume = "16", + number = "9", + pages = "3721--3737", + year = "2011", + note = "", + issn = "1007-5704", + doi = "10.1016/j.cnsns.2010.12.032", + url = "http://www.sciencedirect.com/science/article/pii/S1007570411000037", + author = "Ashraf A. Zaher and Abdulnasser Abu-Rezq", + keywords = "Chaos-based secure communication", + keywords1 = "Chaos synchronization", + keywords2 = "Cryptography", + keywords3 = "Parameter identification", + keywords4 = "Lyapunov functions" +} + +@Article{ Wong200367, + title = "A chaotic cryptography scheme for generating short ciphertext", + journal = "Physics Letters A", + volume = "310", + number = "1", + pages = "67--73", + year = "2003", + note = "", + issn = "0375-9601", + doi = "10.1016/S0375-9601(03)00259-7", + url = "http://www.sciencedirect.com/science/article/pii/S0375960103002597", + author = "Kwok-Wo Wong and Sun-Wah Ho and Ching-Ki Yung", + keywords = "Chaos", + keywords1 = "Cryptography", + keywords2 = "Logistic map" +} + +@Article{ Roland2001429, + title = "Use of chaotic dynamical systems in cryptography", + journal = "Journal of the Franklin Institute", + volume = "338", + number = "4", + pages = "429--441", + year = "2001", + note = "", + issn = "0016-0032", + doi = "10.1016/S0016-0032(00)00087-9", + url = "http://www.sciencedirect.com/science/article/pii/S0016003200000879", + author = "Roland and Schmitz", + keywords = "Cryptography", + keywords1 = "Chaos" +} + +@Article{ MS199850, + title = "Cryptography with chaos", + journal = "Physics Letters A", + volume = "240", + number = "1-2", + pages = "50--54", + year = "1998", + note = "", + issn = "0375-9601", + doi = "10.1016/S0375-9601(98)00086-3", + url = "http://www.sciencedirect.com/science/article/pii/S0375960198000863", + author = "M.S. and Baptista", + keywords = "Chaos", + keywords1 = "Cryptography", + keywords2 = "Message", + keywords3 = "Security" } @Article{ DeMicco20083373, @@ -145,6 +215,20 @@ keywords2 = "Random number generators" } +@Article{ WT198429, + title = "The design of a truly random monolithic noise generator", + journal = "Microelectronics Journal", + volume = "15", + number = "4", + pages = "29--40", + year = "1984", + note = "", + issn = "0026-2692", + doi = "10.1016/S0026-2692(84)80068-3", + url = "http://www.sciencedirect.com/science/article/pii/S0026269284800683", + author = "W.T. and Penzhorn" +} + @Article{ Vadim2011692, title = "Pseudo-random number generators for Monte Carlo simulations on ATI Graphics Processing Units", journal = "Computer Physics Communications", @@ -186,16 +270,16 @@ @Misc{ Frick, title = "The Frick Collection, http://www.frick.org/", - comment = "http://www.frick.org/", type = "web page", - url = "http://www.frick.org/" + url = "http://www.frick.org/", + comment = "http://www.frick.org/" } @Misc{ Delicious, title = "Delicious social bookmarking, http://delicious.com/", - comment = "http://delicious.com/", type = "web page", - url = "http://delicious.com/" + url = "http://delicious.com/", + comment = "http://delicious.com/" } @Book{ ita09, @@ -500,6 +584,112 @@ timestamp = "2010.02.05" } +@InBook{ Knuth1998_2, + title = "The Art of Computer Programming, Volume 2: Seminumerical Algorithms", + author = "D. E. Knuth", + editor = "Reading and Mass and {third edition}", + publisher = "Addison-Wesley", + year = "1998", + pages = "29", + chapter = "3", + volume = "2", + owner = "qianxue", + timestamp = "2010.02.05" +} + +@InCollection{ tagkey2009407, + title = "Appendix E - Linear Feedback Shift Registers (LFSRs)", + editor = "", + booktitle = "Bebop to the Boolean Boogie (Third Edition)", + publisher = "Newnes", + edition = "Third Edition", + address = "Boston", + year = "2009", + pages = "407--422", + isbn = "978-1-85617-507-4", + doi = "10.1016/B978-1-85617-507-4.00033-4", + url = "http://www.sciencedirect.com/science/article/pii/B9781856175074000334", + key = "tagkey2009407", + author = "noname noname" +} + +@Article{ Linardatos2002157, + title = "Synthesis of minimal cost nonlinear feedback shift registers", + journal = "Signal Processing", + volume = "82", + number = "2", + pages = "157--176", + year = "2002", + note = "", + issn = "0165-1684", + doi = "10.1016/S0165-1684(01)00172-4", + url = "http://www.sciencedirect.com/science/article/pii/S0165168401001724", + author = "D. Linardatos and N. Kalouptsidis", + keywords = "Nonlinear feedback shift registers", + keywords1 = "Berlekamp--Massey algorithm", + keywords2 = "FIA" +} + +@Article{ Klapper199961, + title = "Algebraic feedback shift registers", + journal = "Theoretical Computer Science", + volume = "226", + number = "1-2", + pages = "61--92", + year = "1999", + note = "", + issn = "0304-3975", + doi = "10.1016/S0304-3975(99)00066-3", + url = "http://www.sciencedirect.com/science/article/pii/S0304397599000663", + author = "Andrew Klapper and Jinzhong Xu", + keywords = "Cryptography", + keywords1 = "Feedback shift register", + keywords2 = "Complete ring", + keywords3 = "Stream cipher", + keywords4 = "Pseudo-random number generator" +} + +@Article{ Mykkeltveit1979202, + title = "On the cycle structure of some nonlinear shift register sequences", + journal = "Information and Control", + volume = "43", + number = "2", + pages = "202--215", + year = "1979", + note = "", + issn = "0019-9958", + doi = "10.1016/S0019-9958(79)90708-3", + url = "http://www.sciencedirect.com/science/article/pii/S0019995879907083", + author = "Johannes Mykkeltveit and Man-Keung Siu and Po Tong" +} + +@Article{ Unjeng198461, + title = "On the cycle structure of certain classes of nonlinear shift registers", + journal = "Journal of Combinatorial Theory, Series A", + volume = "37", + number = "1", + pages = "61--68", + year = "1984", + note = "", + issn = "0097-3165", + doi = "10.1016/0097-3165(84)90019-0", + url = "http://www.sciencedirect.com/science/article/pii/0097316584900190", + author = "Unjeng and Cheng" +} + +@Book{ Knuth1998_1, + title = "The Art of Computer Programming, Volume 2: Seminumerical Algorithms", + author = "D. E. Knuth", + editor = "Reading and Mass and {third edition}", + publisher = "Addison-Wesley", + year = "1997", + series = "Section 3.2.1: The Linear Congruential Method", + edition = "Third Edition", + volume = "2: Seminumerical Algorithms", + owner = "qianxue", + timestamp = "2010.02.05" +} + @Article{ Gonzalez2005281, title = "Statistical complexity measure of pseudorandom bit generators", journal = "Physica A: Statistical Mechanics and its Applications", @@ -892,3 +1082,297 @@ year = "1996" } +@Book{ Deborah1998, + title = "Randomness", + author = "Deborah J. Bennett", + publisher = "Harvard University Press", + year = "1998" +} + +@Book{ Kallenberg1986, + title = "Random Measures, 4th ed.", + author = "Olav Kallenberg", + publisher = "Academic Press", + address = "New York, London; Akademie-Verlag, Berlin,", + edition = "MR0854102", + year = "1986" +} + +@Book{ William2007, + title = "Numerical Recipes: The Art of Scientific Computing (3rd ed.)", + series = "Chapter 7. Random Numbers", + author = "William H. Press", + publisher = "New York: Cambridge University Press", + year = "2007" +} + +@InCollection{ Pashley2010184, + title = "Generating Random Numbers", + editor = "Editors-in-Chief: Penelope Peterson and Eva Baker and Barry McGaw", + booktitle = "International Encyclopedia of Education (Third Edition)", + publisher = "Elsevier", + edition = "Third Edition", + address = "Oxford", + year = "2010", + pages = "184--189", + isbn = "978-0-08-044894-7", + doi = "10.1016/B978-0-08-044894-7.01375-0", + url = "http://www.sciencedirect.com/science/article/pii/B9780080448947013750", + author = "P.J. Pashley and A. Amodeo", + keywords = "Composite generator", + keywords1 = "Deterministic generation", + keywords10 = "Shuffling", + keywords11 = "Simulation", + keywords12 = "Tests of randomness", + keywords13 = "Uniform variates", + keywords2 = "Generation efficiency", + keywords3 = "Multiplicative congruential generator", + keywords4 = "Physical generation", + keywords5 = "Portability", + keywords6 = "Random number generator", + keywords7 = "Random sequences", + keywords8 = "Reproducibility", + keywords9 = "Sequence period" +} + +@Book{ Tippett1927, + title = "Random Sampling Numbers", + author = "L.H.C. Tippett", + publisher = "CUP", + year = "1927", + address = "London" +} + +@Article{ Danger2009, + title = "High speed true random number generator based on open loop structures in FPGAs", + author = "J.-L. Danger and S. Guilley and P. Hoogvorst", + publisher = "Microelectronics Journal", + journal = "Microelectronics Journal", + pages = "1650--1656", + volume = "40", + number = "11", + year = "November 2009" +} + +@Article{ JarosawAdam2011, + title = "Generating and using truly random quantum states in Mathematica", + journal = "Computer Physics Communications", + volume = "", + number = "0", + pages = "--", + year = "2011", + note = "", + issn = "0010-4655", + doi = "10.1016/j.cpc.2011.08.002", + url = "http://www.sciencedirect.com/science/article/pii/S0010465511002748", + author = "Jaros{\l}aw Adam and Miszczak", + keywords = "Random density matrices", + keywords1 = "Quantum information", + keywords2 = "Quantum random number generators" +} + +@Article{ Tan20091618, + title = "Randomness quality of permuted pseudorandom binary sequences", + journal = "Mathematics and Computers in Simulation", + volume = "79", + number = "5", + pages = "1618--1626", + year = "2009", + note = "", + issn = "0378-4754", + doi = "10.1016/j.matcom.2008.07.012", + url = "http://www.sciencedirect.com/science/article/pii/S0378475408002486", + author = "Syn Kiat Tan and Sheng-Uei Guan", + keywords = "Pseudorandom number generation", + keywords1 = "DIEHARD testing", + keywords2 = "Linear finite state machine", + keywords3 = "Cellular automata" +} + +@InCollection{ StDenis200691, + title = "Chapter 3 - Random Number Generation", + editor = "", + booktitle = "Cryptography for Developers", + publisher = "Syngress", + edition = "", + address = "Burlington", + year = "2006", + pages = "91--137", + isbn = "978-1-59749-104-4", + doi = "10.1016/B978-159749104-4/50006-6", + url = "http://www.sciencedirect.com/science/article/pii/B9781597491044500066", + author = "Tom St Denis and Simon Johnson" +} + +@InBook{ Klapper1994, + title = "2-adic shift registers, in: R. Anderson (Ed.) +, Fast Software Encryption", + author = "Klapper +A. and Goresky +M.", + publisher = "Lecture +Notes in Computer Science +", + pages = "174--178", + volume = "809", + year = "1994" +} + +@Article{ DBLP1986, + author = "Lenore Blum and Manuel Blum and Mike Shub", + title = "A Simple Unpredictable Pseudo-Random Number Generator", + journal = "SIAM J. Comput.", + volume = "15", + number = "2", + year = "1986", + pages = "364--383", + bibsource = "DBLP, http://dblp.uni-trier.de", + ee = "http://dx.doi.org/10.1137/0215025" +} + +@Book{ DBLP2003, + author = "Niels Ferguson and Bruce Schneier", + title = "Practical cryptography", + publisher = "Wiley", + year = "2003", + isbn = "978-0-471-22357-3", + pages = "I--XX, 1--410", + bibsource = "DBLP, http://dblp.uni-trier.de" +} + +@Article{ Matsumoto1998, + author = "Makoto Matsumoto and Takuji Nishimura", + title = "Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator", + journal = "ACM Trans. Model. Comput. Simul.", + volume = "8", + month = "January", + year = "1998", + issn = "1049-3301", + pages = "3--30", + url = "http://doi.acm.org/10.1145/272991.272995", + doi = "http://doi.acm.org/10.1145/272991.272995", + publisher = "ACM", + address = "New York, NY, USA", + keywords = "finite fields, GFSR, incomplete array, inversive-decimation method, k-distribution, Mersenne primes, Mersenne twister, m-sequences, MT19937, multiple-recursive matrix method, primitive polynomials, random number generation, tempering, TGFSR", + acmid = "272995", + issue = "1", + numpages = "28" +} + +@Book{ Miller2010, + author = "Frederic P. Miller and Agnes F. Vandome and John McBrewster", + title = "Cryptographically Secure Pseudorandom Number Generator", + year = "2010", + isbn = "6130875185, 9786130875183", + publisher = "Alpha Press" +} + +@InCollection{ springerlink1994, + author = "Joan Daemen and Ren{\'e} Govaerts and Joos Vandewalle", + title = "Resynchronization Weaknesses in Synchronous Stream Ciphers", + booktitle = "Advances in Cryptology — EUROCRYPT ’93", + series = "Lecture Notes in Computer Science", + editor = "Tor Helleseth", + publisher = "Springer Berlin / Heidelberg", + isbn = "978-3-540-57600-6", + pages = "159--167", + volume = "765", + url = "http://dx.doi.org/10.1007/3-540-48285-7_14", + note = "10.1007/3-540-48285-7\_14", + year = "1994", + affiliation = "Katholieke Universiteit Leuven Laboratorium ESAT Kardinaal Mercierlaan 94 B-3001 Heverlee Belgium", + keyword = "Computer Science" +} + +@Article{ PhysRevA2004, + title = "Secure direct communication with a quantum one-time pad", + month = "May", + journal = "Phys. Rev. A", + doi = "10.1103/PhysRevA.69.052319", + author = "Fu-Guo Deng and Gui Lu Long", + year = "2004", + url = "http://link.aps.org/doi/10.1103/PhysRevA.69.052319", + publisher = "American Physical Society", + pages = "052319", + volume = "69", + issue = "5", + numpages = "4" +} + +@InProceedings{ Wu2008, + author = "Keke Wu and Huiyun Li and Bo Peng and Fengqi Yu", + title = "Correlation Power Analysis Attack against Synchronous Stream Ciphers", + booktitle = "Proceedings of the 2008 The 9th International Conference for Young Computer Scientists", + year = "2008", + isbn = "978-0-7695-3398-8", + pages = "2067--2072", + numpages = "6", + url = "http://dl.acm.org/citation.cfm?id=1491263.1492074", + doi = "10.1109/ICYCS.2008.8", + acmid = "1492074", + publisher = "IEEE Computer Society", + address = "Washington, DC, USA", + keywords = "Correlation coefficient, CPA, DPA, Synchronous stream ciphers, Side channel analysis" +} + +@InProceedings{ Daemen1994, + author = "Joan Daemen and Ren{\'e} Govaerts and Joos Vandewalle", + title = "Resynchronization weaknesses in synchronous stream ciphers", + booktitle = "Workshop on the theory and application of cryptographic techniques on Advances in cryptology", + series = "EUROCRYPT '93", + year = "1994", + isbn = "3-540-57600-2", + location = "Lofthus, Norway", + pages = "159--167", + url = "http://dl.acm.org/citation.cfm?id=188307.188337", + publisher = "Springer-Verlag New York, Inc.", + address = "Secaucus, NJ, USA", + acmid = "188337", + numpages = "9" +} + +@Book{ cusick2004stream, + title = "Stream ciphers and number theory", + author = "T.W. Cusick and C. Ding and A. Renvall", + isbn = "9780444516312", + series = "North-Holland mathematical library", + url = "http://books.google.com/books?id=Q2IncJ99wacC", + year = "2004", + publisher = "Elsevier", + lccn = "2004040484" +} + +@Book{ Meyer100035, + author = "Carl H Meyer and Stephen M Matyas", + title = "Cryptography: a new dimension in computer data security; a guide for the design and implementation of secure systems", + publisher = "Wiley", + address = "New York, NY", + year = "1982" +} + +@Book{ schneier1996applied, + title = "Applied cryptography: protocols, algorithms, and source code in C", + author = "B. Schneier", + isbn = "9780471128458", + url = "http://books.google.com/books?id=6NdQAAAAMAAJ", + year = "1996", + publisher = "Wiley", + lccn = "95012398" +} + +@Article{ STMAZ.01769371, + author = "Toni Stojanovski and Johnny Pihl and Ljup\u{c}o Kocarev", + title = "Chaos-based random number generators.", + year = "2001", + journal = "IEEE Transactions on Circuits and Systems. I: Fundamental Theory and Applications", + volume = "48", + number = "3", + issn = "1057-7122", + pages = "382--385", + publisher = "Institute of Electrical and Electronics Engineers, Inc., New York, NY", + doi = "10.1109/81.915396", + abstract = "Summary: This paper and its companion [Part I, {\it T. Stojanovski} and {\it L. M. Kocarev}, ibid. 48, No. 3, 281-288 (2001; reviewed above)] are devoted to the analysis of the application of a chaotic piecewise-linear one-dimensional (PL1D) map as random number generator (RNG). In Part I, we have mathematically analyzed the information generation process of a class of PL1D maps. In this paper, we find optimum parameters that give an RNG with lowest redundancy and maximum margin against parasitic attractors. Further, the map is implemented in a 0.8 $\mu$m standard CMOS process utilizing switched current techniques. Post-layout circuit simulations of the RNG indicate no periodic attractors over variations in temperature, power supply and process conditions, and maximum redundancy of $0.4\%$. We estimate that the output bit rate of our RNG is 1 Mbit/s, which is substantially higher than the output bit rate of RNGs available on the market.", + identifier = "0997.65003", + msc2010 = "65C10 (94C05 62P20 94A15 62B10)" +} + diff --git a/these.tex b/these.tex index a5466f3..7946946 100644 --- a/these.tex +++ b/these.tex @@ -740,8 +740,8 @@ %------------------------------------------------------------------- -\bibliographystyle{alpha} -% \bibliographystyle{plain} +% \bibliographystyle{alpha} +\bibliographystyle{plain} \bibliography{Thesis} -- 2.39.5