Brevet FR3006781A1 — publié le 20141212

PROCEDE DE CALCUL DE FREQUENCE RELATIVE ET PROCEDE DE CALCUL DE DISTRIBUTION DE PROBABILITE DE LA GIGUE DE PHASE DANS UN GENERATEUR DE NOMBRES VRAIMENT ALEATOIRES La présente invention concerne le domaine de la cryptographie, et porte plus particulièrement sur un procédé de calcul de la distribution de probabilité de la gigue de phase g dans un générateur de nombres vraiment aléatoires (TRNG), mis en oeuvre sur un circuit logique programmable. La publication « Sur la sécurité des générateurs de nombres aléatoires basés sur oscillateurs » (On the security of oscillator-based random number generators), M. Baudet et al., Journal of Cryptology, 24 :398-425, 2011 est également incorporé par référence dans son intégralité à la présente description. Les générateurs de nombres aléatoires (Random Number Generators - RNG) sont des composants cruciaux des systèmes cryptographiques. Ils sont utilisés typiquement pour la génération de clés, l'initialisation de vecteurs et en tant que contre-mesures à l'encontre d'attaques par canal auxiliaire. En plus de produire un flux binaire en sortie avec de bonnes propriétés statistiques, les RNG pour applications cryptographiques doivent satisfaire des exigences de sécurité supplémentaires : ils doivent pouvoir être testés en temps réel et leur sécurité doit être prouvée sous une hypothèse physique minutieusement testée. Les RNG cryptographiques classiques sont constitués de deux niveaux : un générateur de nombres vraiment aléatoires (True Random Number Generator - TRNG) qui produit l'entropie, et un post-traitement cryptographique pour obtenir un certain niveau de sécurité, même dans le cas d'une défaillance non détectée du TRNG sous-jacent. Pour des applications cryptographiques, la 5 sécurité d'un TRNG dépend de son taux d'entropie qui mesure le temps d'exécution d'une attaque par force brute sur une clé par échantillonnage de la distribution du TRNG. Le taux d'entropie du TRNG dépend d'un modèle statistique de celui-ci qui décrit la distribution de sa 10 séquence de sortie à partir de la connaissance de paramètres physiques. Le taux d'entropie ne peut en conséquence pas être trouvé uniquement à partir de la seule connaissance d'une séquence de sortie du TRNG, aussi importante soit-elle. Par approximation de cette 15 distribution par une source ergodique stationnaire, il est possible de trouver le taux d'entropie d'un TRNG. Une source de caractère aléatoire couramment utilisée dans les mises en oeuvre de TRNG par matrice prédiffusée programmable par l'utilisateur (FPGA) ou 20 circuit intégré spécifique (ASIC) est l'instabilité du temps de propagation des signaux à travers les portes logiques. Cette instabilité est typiquement accumulée dans des oscillateurs en anneau, qui consistent en une série d'inverseurs ou d'éléments de retard connectés en anneau, 25 dont le signal boucle sur lui-même. Un tel anneau d'oscillateurs produit spontanément un signal presque périodique. Deux anneaux d'oscillateurs implémentés sur le même circuit vont avoir tendance à se déphaser du fait d'un 30 phénomène appelé gigue de phase (« phase jitter » en anglais). La loi décrivant ce déphasage (au moins sur des temps de l'ordre de la milliseconde) est une marche aléatoire qui permet de fabriquer la distribution qui sera utilisée pour produire des nombres aléatoires. Cette gigue de phase peut être extraite par une unité d'échantillonnage. Cette structure simple est appelée dans ce qui suit un TRNG élémentaire. La gigue de phase est un phénomène complexe en ce qu'elle est constituée par la superposition de différentes sources de bruit. On distingue la composante locale de la gigue de phase, elle-même constituée d'une combinaison de différents types de bruits avec différentes propriétés statistiques et correspondant à la source d'entropie du TRNG, des bruits déterministes globaux qui peuvent être manipulés depuis l'extérieur du TRNG. Dans le document « Sur la sécurité des générateurs de nombres aléatoires à base d'oscillateurs » (On the security of oscillator-based random number generators), M. Baudet et al., Journal of Cryptology, 24 :398-425, 2011, il est proposé un modèle statistique pour un TRNG élémentaire qui calcule le taux d'entropie provenant du bruit de phase de marche aléatoire. Une manière habituelle de caractériser la gigue de phase est d'émettre en sortie le signal produit par un oscillateur en anneau et de l'analyser avec un oscilloscope ou avec un analyseur de spectre, cette technique étant décrite par exemple dans « Mesures de temporisation numérique : des oscilloscopes et sondes à la temporisation et à la gigue » (Digital Timing Measurements : From Scopes and Probes to Timing and Jitter), W. Maichen, Frontières en test électronique (Frontiers in Electronic Testing), Springer, 2010. Le problème avec cette technique est qu'elle introduit une gigue de phase supplémentaire ainsi que des distorsions sur le signal mesuré issu de la chaîne d'acquisition de données. En outre, cette technique ne permet pas de qualifier chaque puce comportant un TRNG sur une ligne de production et ne permet pas de vérifier correctement le fonctionnement du dispositif. La présente invention vise à surmonter ces inconvénients et porte sur un procédé permettant de mesurer la gigue de phase à l'intérieur de la puce, de façon simple et facile à mettre en oeuvre. Le procédé peut facilement être mis en oeuvre sur un FPGA ou un ASIC, et peut être utilisé pour étalonner un TRNG élémentaire ou pour certifier le taux d'entropie d'un TRNG élémentaire en fonctionnement. Le procédé est mis en oeuvre par l'intermédiaire d'un TRNG élémentaire, à savoir un anneau d'oscillateurs qui échantillonne un autre anneau d'oscillateurs par l'intermédiaire d'une bascule D. Pour obtenir une distribution satisfaisante, il est nécessaire d'accumuler la gigue de phase, par diminution de la fréquence de l'anneau d'oscillateurs qui échantillonne, par exemple grâce à un compteur. Le procédé de l'invention permet de calculer la distribution de probabilité de la gigue de phase g dans un générateur de nombres vraiment aléatoires (TRNG), afin de calculer à partir de celle-ci le taux d'entropie d'un TRNG par utilisation de la technique décrite dans le document précité « Sur la sécurité des générateurs de nombres aléatoires à base d'oscillateurs » (On the security of oscillator-based random number generators), M. Baudet et al., Journal of Cryptology, 24 :398-425, 2011. Dans la présente spécification, on notera : x mod T= Zlx nn > 0}T. Pour I un intervalle et teR, I+t est l'intervalle L'invention a pour objet un procédé de calcul de la fréquence relative entre deux anneaux d'oscillateurs 01 5 et 02, mis en oeuvre sur un circuit logique programmable, caractérisé par le fait qu'il comprend les étapes consistant à : - générer une séquence binaire [b1, bn] de n bits, n étant un entier naturel supérieur à 1, en sortie d'une 10 bascule D ayant en entrée la sortie du premier anneau d'oscillateurs 01 de période moyenne T1 et en signal d'horloge la sortie du deuxième anneau d'oscillateurs 02 de période moyenne T2 ; - calculer la distance statistique dR entre les bits de la 15 séquence binaire [b1, bn] séparés de R positions, R1, dans la séquence, la distance statistique dR étant définie comme la probabilité que le bit bi soit différent du bit bi-FR - calculer, à partir de la distance statistique d 20 calculée, = dR/2. La distance statistique dR peut être calculée, en partant d'une valeur S égale à O, en ajoutant 1 à S à chaque fois que bi est différent de bi+R, pour tout entier i compris entre 1 et (n-M), la distance statistique d étant 25 égale à la valeur finale de S divisée par (n-M). La distance statistique dR donne une évaluation de R*T2 mod T1, pour R1. L'invention a également pour objet un procédé de calcul d'une valeur approchée de la distribution de 30 probabilité de la gigue de phase g dans un générateur de nombres vraiment aléatoires (TRNG), mis en oeuvre sur un circuit logique programmable, caractérisé par le fait qu'il comprend les étapes consistant à : - calculer la fréquence relative entre deux anneaux d'oscillateurs 01 et 02, mis en oeuvre sur ledit circuit logique programmable, par le procédé tel que décrit ci- dessus, avec T1 et T2 étant supérieurs à l'écart-type de la gigue de phase g entre lesdits deux anneaux d'oscillateurs 01, 02 ; - déterminer un entier naturel M tel que, pour tout entier naturel i, les instants ti représentant les fronts montants de la sortie du deuxième anneau d'oscillateurs 02, la gigue de phase g est négligeable sur la période de temps [ti, ; - calculer l'unique permutation p telle que, N 4*N et la notation wi représentant l'expression (iT2 mod T1), quels que soient i, j appartenant à {0, N} avec i La distribution de probabilité P de la gigue de phase g peut être calculée par calcul de la liste L telle que, iu étant l'indice tel que bk+p(iu)=0 et bk+p((iu+1) mod(N+1))=1 et ju étant l'indice tel que bk-Fm+p(iu)=0 et bk+M-kotju+1) 5 mod(N+1)>=1, avec k=0 et L étant la liste vide comme conditions initiales, on complète à chaque itération la liste L par l'élément DA/G(ju)-w,0_,0] et on ajoute M à k, tant que k(n-M-N), la liste L finale représentant un échantillon de points tiré selon la distribution de 10 probabilité P de la gigue de phase g. L'invention a également pour objet un circuit logique programmable sur lequel est programmé un générateur de nombres vraiment aléatoires (TRNG), caractérisé par le fait qu'il comprend en outre des circuits programmés pour 15 mettre en oeuvre le procédé tel que défini ci-dessus. Ledit circuit logique programmable peut être une matrice prédiffusée programmable par l'utilisateur (FPGA) ou un circuit intégré spécifique (ASIC). 20 Exemple On a testé le procédé sur un démonstrateur, qui consiste en un FPGA dédié à l'évaluation d'un TRNG élémentaire constitué de deux éléments : une carte mère qui 25 contient une interface USB alimentée par une alimentation à faible bruit isolée et un module auxiliaire contenant le composant FPGA et branché sur la carte mère. Le TRNG élémentaire est implémenté sur le module auxiliaire et la séquence binaire de sortie est transmise 30 par l'intermédiaire de l'interface USB à la carte mère pour être analysée par un ordinateur externe sur lequel l'algorithme a été implémenté en Python (marque enregistrée). Le FPGA utilisé dans cet exemple est un Altera (marque enregistrée), mais le procédé de l'invention peut être mis en oeuvre sur un autre type de FPGA ou un ASIC. Les périodes moyennes des anneaux d'oscillateurs 5 du TRNG élémentaire de cet exemple, mesurées par un oscilloscope, sont respectivement T1-11,335ns et T2=8, 712ns. On a obtenu une séquence de 819200 bits en sortie du TRNG. On choisit M=1. 10 On calcule alors la distance statistique d entre deux bits consécutifs (M=1) dans cette séquence binaire et l'on obtient d=0,46288, d'où l'on peut déduire ---(J/(2*M)=d/2=0,23144. A partir de on calcule la permutation p, pour 15 une longueur N=64, la permutation p étant donnée par la liste L suivante (L[i]=p(i)) : 0 13 26 39 52 9 22 35 48 61 5 18 31 44 57 1 14 27 40 53 10 23 36 49 62 6 19 32 45 58 2 15 28 41 54 11 24 37 50 63 7 20 33 46 59 3 29 42 16 55 12 25 38 51 8 21 34 47 60 4 17 30 43 56 Les premiers 64 bits de la séquence ME/ sont: 00 00 00011001 1001100111001100 0011001100011001 1001100111001100 20 L'application de la permutation p à ces 64 premiers bits donne la séquence suivante : 0000000000000000 0000011111111111 111111111 111111 1111'000000000000 On remarque que les bits 0 et 1 sont groupés ensemble. 25 On calcule alors la distribution de probabilité de la gigue de phase g, par calcul de la liste L' telle que, iu étant l'indice tel que bk_koi3O=0 et bk+p((iu+1) mod (N+1) ) =1 et ju étant l' indice tel que bk+m-Fp(iu)=0 et bk+M+p ( (ju+1) mod (N+1) ) =1, avec k=0 et L' étant la liste vide comme 30 conditions initiales, on complète à chaque itération la liste L' par l'élément [1,/6(i,)-w,u-o] et on ajoute M à k, tant que k REVENDICATIONS1 - Procédé de calcul de la fréquence relative entre deux anneaux d'oscillateurs 01 et 02, mis en oeuvre sur 5 un circuit logique programmable, caractérisé par le fait qu'il comprend les étapes consistant à : - générer une séquence binaire [b1, bn] de n bits, n étant un entier naturel supérieur à 1, en sortie d'une bascule D ayant en entrée la sortie du premier anneau 10 d'oscillateurs 01 de période moyenne T1 et en signal d'horloge la sortie du deuxième anneau d'oscillateurs 02 de période moyenne T2 ; - calculer la distance statistique dR entre les bits de la séquence binaire [b1, bn] séparés de R positions, R1, 15 dans la séquence, la distance statistique dR étant définie comme la probabilité que le bit b/ soit différent du bit bi-ER - calculer, à partir de la distance statistique d calculée, dR/2. 20 2 - Procédé selon la revendication 1, caractérisé par le fait que la distance statistique dR est calculée, en partant d'une valeur S égale à O, en ajoutant 1 à S à chaque fois que bi est différent de bi+R, pour tout entier i compris entre 1 et (n-M), la distance statistique d étant 25 égale à la valeur finale de S divisée par (n-M). 3 - Procédé de calcul d'une valeur approchée de la distribution de probabilité de la gigue de phase g dans un générateur de nombres vraiment aléatoires (TRNG), mis en oeuvre sur un circuit logique programmable, caractérisé par 30 le fait qu'il comprend les étapes consistant à : - calculer la fréquence relative entre deux anneaux d'oscillateurs 01 et 02, mis en oeuvre sur ledit circuit logique programmable, par le procédé selon l'unequelconque des revendications 1 et 2, avec T1 et T2 étant supérieurs à l'écart-type de la gigue de phase g entre lesdits deux anneaux d'oscillateurs 01, 02 - déterminer un entier naturel M tel que, pour tout entier naturel i, les instants ti représentant les fronts montants de la sortie du deuxième anneau d'oscillateurs 02, la gigue de phase g est négligeable sur la période de temps [ti, tilm] ; - calculer l'unique permutation p telle que, N 4*N et la notation Wi représentant l'expression (iT2 mod T1), quels que soient i, j appartenant à {0, N} avec i 4 - Procédé selon la revendication 3, caractérisé par le fait que l'unique permutation p est calculée par calcul de la liste L = [(O, 0), (, 1), (k* mod 1, k), (N* mod 1, N)], p correspondant à la liste L triée sur la première colonne. 5 - Procédé selon l'une des revendications 3 et 4, caractérisé par le fait que la distribution de probabilité P de la gigue de phase g est calculée par calcul de la liste L telle que, iu étant l'indice tel que bk+p(1u)=0 et bk+o(iu+i) mod(N+1))=1 et ju étant l'indice tel que bk-km+p (iti) =0 et bk+m+o(iu+i) mod(N+1))=1, avec k=0 et L étant la liste vide comme conditions initiales, on complète à chaque itération la liste L par l'élément [wo(ju)-w0(iu)] et on ajoute M à k, tant que k 6 - Circuit logique programmable sur lequel est programmé un générateur de nombres vraiment aléatoires (TRNG), caractérisé par le fait qu'il comprend en outre des circuits programmés pour mettre en oeuvre le procédé de l'une quelconque des revendications 1 à 5. 7 - Circuit logique programmable selon la revendication 6, caractérisé par le fait que ledit circuit logique programmable est une matrice prédiffusée programmable par l'utilisateur (FPGA) ou un circuit intégré spécifique (ASIC).