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:
\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}
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{schneier1996}. 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{STMAZ01769371}.
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.
