IBTS-77-RP-1000
Nombres aléatoires
L’aléa ou l’observation du phénomène aléatoire est utilisé dans le cadre de nombreuses applications et cela depuis plusieurs siècles déjà.
Initialement l’aléa était utilisé pour départager les Hommes de manière incontestable. C’est pour cette raison qu’il est l’ingrédient le plus important dans les jeux de hasard. C’est également pour cette raison que l’aléa est depuis des siècles utilisé dans les processus de gestions publiques. En effet rappelons que dans l’antique démocratie athénienne certaines fonctions politiques étaient confiées à des citoyens choisis aléatoirement ou encore qu’aujourd’hui en France les jurés d’assises sont tirés au sort à partir des listes électorales.
À partir du milieu du vingtième siècle, les nombres aléatoires ont été utilisés pour résoudre des problèmes mathématiques complexes. C’est à cette époque que les méthodes de Monte-Carlo sont inventées. Il s’agit de méthodes permettant à l’aide de processus aléatoires de calculer la valeur numérique d’une intégrale dont le calcul formel est quasi-impossible. Cette valeur numérique est le résultat d’un système d’équations complexe, qui permet par exemple de modéliser une particule physique dont le comportement est difficile à décrire de manière déterministe.
Les caractéristiques demandées à un nombre aléatoire peuvent différer d’une application à l’autre. Par exemple, contrairement à certaines applications cryptographiques, les méthodes de Monte Carlo n’exigent pas que la séquence de nombres aléatoires soit imprédictible.
Propriétés fondamentales des nombres aléatoires
Dans une première approche nous pouvons dire qu’un nombre imprédictible est un nombre qui ne peut pas être prédit. Dans ce cas pour définir « l’imprédictibilité d’un nombre » il est plus simple de d’abord définir ce qu’est « la prédiction d’un nombre ». Une prédiction est l’annonce d’événements futurs par la connaissance qu’on a de leurs causes. Ainsi pouvoir prédire un nombre c’est pouvoir l’annoncer à l’avance en se basant sur la connaissance qu’on a du processus dont il est issu.
Par opposition à ce dernier énoncé, nous pouvons conclure qu’un nombre imprédictible est un nombre que l’on ne peut pas annoncer à l’avance, et cela même en se basant sur l’ensemble des connaissances que l’on a du processus servant à le générer et des nombres déjà produits.
L’ensemble des connaissances qu’on a du processus générant un nombre est donc très important pour évaluer l’imprédictibilité de ce nombre, en effet il est tout à fait envisageable que l’ajout d’un seul élément à cet ensemble de connaissances rende possible la prédiction du nombre.
Dans le contexte des applications cryptographiques il faut également que les nombres qui ont déjà été utilisé ne puissent pas être reproduits. En effet, si Oscar arrive à retrouver la clé, il ne doit pas être capable d’en déduire les clés précédemment utilisées.
Cela signifie que même en se basant sur l’ensemble des connaissances que l’on a des derniers nombres produits et du processus générateur il doit être impossible de retrouver un autre nombre déjà généré.
Remarquons qu’en anglais on parle pour cela de « postdiction » : un mot qui tire son origine du remplacement dans le mot « prédiction » du préfixe « pre- » par le préfixe « post-« . Ainsi dans la suite du manuscrit nous réalisons un anglicisme et nous parlons de l’impostdictibilité des nombres pour évoquer cette propriété.
Générateurs physiques de nombres réellement aléatoires
Contrairement aux TRNG non physiques, les P-TRNG sont des dispositifs uniquement dédiés à la génération des nombres aléatoires. Ainsi aucun des éléments participant à la génération de l’aléa n’est ici partagé avec une autre fonctionnalité du circuit. un P-TRNG se décompose en trois entités:
La source d’aléa, il s’agit d’un circuit électronique générant un signal analogique bruité. Le numériseur, il s’agit d’un dispositif transformant le signal bruité en une séquence numérique (habituellement binaire) : la séquence aléatoire brute.
La qualité statistique de cette séquence est souvent trop faible, il est donc nécessaire de l’améliorer.
Le post-traitement, il s’agit de la mise en œuvre d’un algorithme s’appliquant sur la séquence aléatoire brute et permettant ainsi d’en augmenter la qualité statistique.
Le signal bruité peut être vu comme la somme de deux signaux : le signal idéal qui correspond au comportement déterministe du circuit et le signal de bruit qui traduit l’impact des bruits électroniques.
Pour illustrer cette définition prenons l’exemple d’un P-TRNG composé d’une résistance dont la tension est mesurée avec un voltmètre numérique. Nous pouvons alors dire que la résistance est la source d’aléa, que le voltmètre est le numériseur et que les tensions affichées sur le voltmètre sont les éléments de la séquence aléatoire brute. Dans le cas de cet exemple, le signal bruité est la tension aux bornes de la résistance, le signal idéal est la valeur moyenne de cette tension et le signal de bruit est la variation du signal bruité autour de cette valeur moyenne.
Dans ce cas, nous pouvons dire que si Oscar est capable de prédire et de postdire la valeur de la tension aux bornes de la résistance alors il est capable de déterminer la séquence aléatoire brute. Toujours dans le cadre de cet exemple, il est important que la sensibilité du voltmètre ne soit pas trop grande par rapport aux variations du signal bruité ou que le signal idéal ne soit pas trop éloigné d’un des seuils du voltmètre. En effet, si ces deux conditions ne sont pas respectées, les variations du signal de bruit ne sont pas détectées par le voltmètre numérique et n’impactent donc pas la séquence aléatoire brute.
APPROCHE MODERNE D’ÉVALUATION DES P-TRNG : LA MODÉLISATION
défauts statistiques dans une séquence produite par un P-TRNG, qui est lui même utilisé dans un environnement donné. Ils ne permettent surtout pas de garantir l’imprédictibilité ou l’impostdictibilité de la séquence produite par un P-TRNG.
Ces tests ne prennent pas non plus en compte l’environnement dans lequel le générateur est implanté, c’est à dire la technologie du circuit cible (ASIC ou FPGA), la stabilité de l’alimentation, la température, ou tout autre perturbation involontaire. Pourtant dans la majorité des publications présentes dans la frise 2.21, le seul succès des tests a permis à leurs auteurs de juger de la qualité du générateur.
De plus, en 2012, Hochberger et al. ont montré [HLRV12] que les performances d’un générateur peuvent se dégrader lorsque son environnement change. Hochberger et al. mettent ainsi en évidence que la qualité de la séquence aléatoire dépend fortement de l’environnement de test, c’est à dire de la température, de la tension d’alimentation et de la famille du FPGA cible utilisé. Ainsi rien ne garantit qu’un P-TRNG réussissant des tests statistiques sous un environnement les réussira également sous un autre environnement.
En analysant l’ensemble des implantations matérielles de la frise 2.21, nous remarquons que ces P-TRNG sont implantés dans des conditions environnementales différentes. Il n’est donc pas rigoureux d’utiliser comme éléments de comparaisons les performances proclamées dans ces articles.
Comme introduit précédemment, ces tests statistiques ne permettent de garantir ni l’imprédictibilité ni l’impostdictibilité de la séquence produite par un P-TRNG. A titre d’exemple, Bochard et al. ont montré que dans le cas du P-TRNG proposé par dans [WT08], qu’en l’absence de jitter, la seule différence des fréquences moyennes des oscillateurs suffit pour que la séquence aléatoire brute passe avec succès des tests statistiques.
L’imprédictibilité et l’impostdictibilité de la séquence produite par un P-TRNG sont deux propriétés importantes pour les applications cryptographiques. Ainsi face à l’incapacité des tests statistiques à garantir ces propriétés, une nouvelle approche d’évaluation est apparue comme plus pertinente au yeux de la communauté scientifique. Cette dernière est basée sur la compréhension et la modélisation du fonctionnement du générateur.
|
Table des matières
1 Introduction
1.1 Introduction à la cryptologie
1.2 Nombres aléatoires
1.2.1 Nombres aléatoires en cryptographie
1.2.2 Propriétés fondamentales des nombres aléatoires
1.2.3 D’autres utilisations cryptographiques
1.3 Différents types de générateurs de nombres aléatoires
1.3.1 Générateurs de nombres aléatoires déterministes
1.3.2 Générateurs de nombres réellement aléatoires
1.3.3 Générateurs physiques de nombres réellement aléatoires
1.4 Contribution et organisation du manuscrit
2 État de l’art
2.1 État de l’art des sources d’aléa
2.1.1 Sources oscillantes d’aléa
2.1.2 Sources d’aléa non-oscillantes
2.2 État de l’art des P-TRNG
2.2.1 Générateur de Fairfield et al. [FMC85]
2.2.2 Variantes du générateur de Fairfield et al
2.2.3 Générateur de Danger et al
2.3 Historique des P-TRNG
2.4 Approche historique d’évaluation des P-TRNG : les tests statistiques
2.5 Approche moderne d’évaluation des P-TRNG : la modélisation
2.6 Norme AIS 31
2.6.1 Qualité statistique
2.6.2 Évaluation de l’entropie
2.6.3 Tests embarqués
2.6.4 Classes de la norme AIS 31
2.7 Modélisations dans la génération de nombres aléatoires
2.7.1 Modèles de bruits à l’échelle du transistor
2.7.2 Modèles de sources d’aléa
2.7.3 Modèles de P-TRNG
2.7.4 Étapes de la modélisation
2.8 Conclusion
3 Caractérisation du jitter pour la génération de nombres aléatoires
3.1 Introduction
3.2 Mesure du jitter dans les anneaux à inverseurs
3.2.1 Partie théorique et définitions
3.2.2 Dispositif de mesure du jitter dans les anneaux oscillants à inverseurs
3.3 Bruit de scintillement et les modélisations
3.3.1 Bruit de scintillement et indépendance du jitter
3.3.2 Modélisation des dépendances
3.3.3 Conclusion
3.4 Tests embarqués basés sur la mesure du jitter dans les anneaux oscillants à inverseurs
3.4.1 Test en ligne sous l’hypothèse d’absence du bruit de scintillement
3.4.2 Test en ligne en présence de bruit thermique et de bruit de scintillement
3.4.3 Test d’échec total de la source d’entropie
3.4.4 Conclusion
3.5 Tests embarqués d’un P-TRNG basé sur l’échantillonnage cohérent
3.5.1 Mesure du jitter dans les PLL : partie théorique et modélisation
3.5.2 Mesure du jitter dans les PLL : mise en œuvre
3.5.3 Tests embarqués basés sur les dispositifs de mesure
3.6 Conclusion
4 Modélisation et caractérisation du P-TRNG basé sur le TERO
4.1 Présentation du TERO based RNG
4.2 Modélisation du P-TRNG
4.2.1 Modélisation du nombre d’oscillations avant stabilisation
4.2.2 Validation expérimentale du modèle
4.2.3 Modélisation de la séquence aléatoire
4.2.4 Conclusion
4.3 Sensibilité aux attaques par injection harmonique
4.3.1 Le dispositif de perturbation
4.3.2 Le lien avec la modélisation
4.3.3 Conclusion
4.4 Conclusion
5 Résumé des contributions et perspectives
5.1 Principales contributions
5.2 Perspectives
Liste des publications
Bibliographie
Variance du jitter de phase dans les PLL
.1 Convergence de Ith
.2 Convergence de If l
.3 Conclusion
Télécharger le rapport complet
