Brevet FR2787898A1 — publié le 20000630

PROCEDE D'AMELIORATION D'UN TEST STATISTIQUE L'invention concerne une amélioration d'un procédé de test statistique de générateurs de nombres aléatoires appelés aussi sources générant des nombres aléatoires, en particulier des sources mises au point dans le cadre de systèmes cryptographiques tels que les générateurs de nombres aléatoires embarqués à bord de cartes à puce. Elle est particulièrement destinée à être mise en oeuvre dans le test et la validation de dispositifs électroniques du type carte à puce, o PCMCIA ("Personal Computer Memory Card International Association", 1030 B East Duane Avenue Sunnyvale, California) badges, cartes sans contact ou tout autre appareil portable. La plupart des systèmes de cryptographie à clé publique (dite aussi cryptographie asymétrique) et clé secrète (dite aussi cryptographie symétrique) nécessitent le tirage d'aléas secrets. Il est primordial que de tels aléas, ou nombres, destinés à servir comme clés ultérieurement, soient à priori imprévisibles et ne présentent pas de régularités permettant de les retrouver par des stratégies de recherche exhaustive ou exhaustive améliorée pour laquelle les clés les plus probables sont cherchées en premier lieu. A ce titre, il existe plusieurs procédés permettant de tester les aléas générés par une source aléatoire et de s'assurer que ladite source fonctionne correctement et ne présente pas de dérive suite à des changements de paramètres externes d'origine malveillante telle qu'une altération par des radiations induites. Chacun de ces procédés s'applique à une suite, appelée aussi séquence, de nombres entiers compris entre 0 et une valeur d, ladite suite étant générée par la source aléatoire. Le procédé de test le plus connu est le test dit de "fréquence". Il s'agit de compter le nombre d'apparitions de chaque entier compris entre 0 et une valeur d dans ladite séquence. Le nombre d'apparitions de chaque entier est ensuite évalué statistiquement. Un second procédé de test dit de "séries" consiste en un comptage et une évaluation statistique du nombre d'apparitions de tous les couples possibles d'entiers compris entre 0 et une valeur d. Ce procédé de test peut être généralisé au comptage des triplets, quadruplets d'entiers, etc... Un troisième procédé de test dit de "trou" existe. Un trou dans une séquence est une suite de nombres à l'extérieur d'un intervalle prédéterminé. Il s'agit d'une évaluation statistique de la longueur desdits trous dans la séquence. Un quatrième procédé de test, dit test du "poker", existe. Le test consiste à grouper les nombres de la séquence par groupe de cinq o nombres et à compter dans chaque quintuplet combien de valeurs différentes apparaissent. Un cinquième procédé de test dit de "collecte de coupons" consiste à évaluer statistiquement la taille de séquence nécessaire pour que toutes les valeurs entières comprises entre 0 et d apparaissent dans ladite séquence. Le détail de ces procédés se trouve dans l'ouvrage intitulé: "Knuth, The art of computer programming, vol. 2, Seminumerical algorithms ". Un autre procédé de test populaire est le test universel de Maurer décrit dans l'ouvrage "Journal of Cryptology, vol. 5, n 2, 1992, pp. 89- ". Ce test présente l'avantage de révéler tous les défauts décelables par les procédés de tests précédemment cités ainsi que d'autres défauts statistiques non détectés par ces mêmes procédés de test. Le procédé de test, dit de Maurer, également dénommé universel, comprend les étapes suivantes: Première étape: Génération d'une séquence de (Q+K)*L bits par la source aléatoire. Q, K et L sont des paramètres d'entrée. Les bits de la séquence sont groupés par bloc de L bits, formant une séquence d'entiers compris entre 0 et 2L-1 de longueur Q+K. La longueur est mémorisée dans le tableau block[n], o n est compris entre 1 et Q+K. Deuxième étape: Calcul du paramètre du test, noté fTU; cette deuxième étape comprenant les étapes suivantes, appelées sous-étapes 2.1 à 2.5, Sum étant une variable utilisée à partir de l'étape 2.3: 2.1 Création et initialisation d'un tableau tab [i] de taille 2L; 2.2 Pour n variant de 1 à Q, faire le calcul: tab[block[n]]=n; 2.3 Initialiser le nombre Sum à 0; 2.4 Pour n variant de Q+1 à Q+K, exécuter le calcul: Ajouter log(n-tab[block[n]] à Sum; Faire le calcul: tab[block[n]]=n; s 2.5 Le paramètre fTU du test est donné par: fTU=(Sum/K)/Log(2); Troisième étape: Calcul de la variance par block de paramètre du test, notée Var. Son expression précise est donnée dans l'article publié par Maurer dans l'ouvrage "Journal of Cryptology, vol. 5, n 2, 1992, pp. io 89-105 ", qui est: Var= (1-z)* E log2(i)2*zi-1 - ((1-z)*E log2(i)*zi-1)2, i =1 i=1 avec log2(z)=log(z)/log(2) et z=1-2' Quatrième étape: Calcul de la fonction c(L,K). Une expression approchée de cette fonction est donnée dans l'article de l'ouvrage précédent, qui est: c(L,K)=0,7-0,8/L+(1,6+12,8/L)*K(4/L); Cinquième étape: Calcul de l'écart type du paramètre de test, noté a: G=c(L,K)*M(Var/K); Sixième étape: Calcul du paramètre y; y est déterminé à partir du taux de rejet du test fixé en entrée, noté p. y doit vérifier l'équation: N(- y)= p. N est la fonction de densité normale décrite dans l'ouvrage "R. Langley, Practical statistics, Dover publications, New-York, 1968 ". L'équation N(-y)= p peut être résolue en utilisant une table de valeurs de N. Une telle table est fournie dans l'article précédent; Septième étape: Calcul de la valeur moyenne du test, notée E[fTU]. Son expression est donnée dans l'article publié par Maurer dans I'ouvrage " Journal of Cryptology, vol. 5, n 2, 1992, pp. 89-105 ", et vaut: z O E[f-U]= (1-z)* Z Iog2(i)*zi-1 avec log2(z)=log(z)/log(2) et z=1-2L Huitième étape: Calcul des bornes tl et t2. Elles sont données par l'équation: t1=E[fTU]- y*c et t2=E[fTU]+y*o; Neuvième étape: Résultat du test: Si le paramètre du test fTU est compris entre tl et t2, alors le générateur de nombre aléatoire est accepté. Dans le cas contraire, il est refusé. L'intérêt de ce procédé de test universel est que le paramètre du test fTU est relié de façon asymptotique à l'entropie de la source aléatoire o testée. L'entropie d'une source aléatoire mesure la qualité cryptographique de cette source. Il est possible d'établir la relation asymptotique suivante entre le paramètre du test fTU et l'entropie par blocks de taille L de la source notée K(L), qui est: E[fTU] - K(L) converge vers C quand L tend vers l'infini, o C est une constante calculable. La présente invention a pour objet un procédé de test amélioré permettant d'atteindre une meilleure précision dans l'estimation de l'entropie. Soit fTM la fonction de test améliorée décrite dans la suite de ce document, il est possible d'établir que: E[fTM]=K(L) Contrairement au test de Maurer original pour lequel il existe seulement une relation asymptotique entre la fonction du test fTU et l'entropie de la source K(L), I'avantage du procédé de test amélioré est que la fonction du test amélioré fTM est exactement égale à l'entropie de la source K(L). En conséquence, tout défaut statistique induisant une variation de l'entropie de la source sera détecté de manière plus fiable par le procédé de test amélioré. Ce test amélioré sert notamment à évaluer la sécurité de dispositifs portables du type carte à puce Le procédé de test amélioré comprend les étapes suivantes: Première étape: Elle consiste en une génération d'une séquence de (Q+K)*L bits par la source aléatoire, Q, K et L étant des paramètres d'entrée; les bits de la séquence sont groupés par bloc de L bits, formant une séquence d'entiers compris entre O et 2L-1 de longueur Q+K; la longueur est mémorisée dans le tableau block[n], o n est compris entre 1 et Q+K. Deuxième étape: elle consiste en un calcul du paramètre du test amélioré, noté fTM qui comprend les étapes suivantes, appelées sous- io étapes 2.1 à 2.5: 2.1 Création et initialisation d'un tableau tab [i] de taille 2L; 2.2 Pour n variant de 1 à Q, calcul de: tab[block[n]]=n; 2.3 Initialisation du nombre Sum à O; 2.4 Pour n variant de Q+1 à Q+K, exécution du calcul suivant: Calcul de j=n-tab[block[n]]. Si j est inférieur ou égal à 23 alors exécuter le calcul Pour k variant de 1 à j-1 Ajouter 1/(k*Log(2)) à Sum Sinon, pour j supérieur à 23, exécuter le calcul Ajouter log(j-1)/Iog(2)+0. 8327462+1/(2*(j-1))/log(2) à Sum, Exécution du calcul: tab[block[n]]=n; 2.5 Le paramètre fTM du test est donné par: fTM=Sum/K Troisième étape: elle consiste en un calcul de la variance par block de paramètre du test, notée Var; son expression précise est donnée par l'expression suivante: Var= (1 -z)* g(i)2*zi-1 - L2 i =1 avec z=1-2'L et g(i) une fonction définie de la manière suivante: i-1 g(i)= E 1/k k =1 Quatrième étape: elle consiste en un calcul de la fonction c(L, K); une expression approchée de cette fonction est donnée par la formule c(L,K)=0,7-0,8/L+(1,6+12,8/L)*K(-4/L); Cinquième étape: elle consiste en un calcul de l'écart type du paramètre de test, noté cy: =c(L,K)*,(Var/K); Sixième étape: elle consiste en un calcul du paramètre y; y est déterminé à partir du taux de rejet du test fixé en entrée, noté p. y doit vérifier l'équation: o0 N(-y)= p. N est la fonction de densité normale décrite dans l'ouvrage " R. Langley, Practical statistics, Dover publications, New-York, 1968 " qui est: N(-y)= J 1/(2*7t)*exp(-x2/2) dx -O L'équation N(-y)= p peut être résolue en utilisant une table de valeurs de N. Une telle table est fournie dans l'article précédent; Septième étape: elle consiste en un calcul des bornes tl et t2. Elles sont données par l'équation: t1 =L-y*a et t2=L+y*c; Huitième étape: elle consiste à donner le résultat du test: Si le paramètre du test fTM est compris entre tl et t2, alors le générateur de nombre aléatoire est accepté; dans le cas contraire, il est refusé. Par conséquent, le procédé de l'invention consiste en un calcul modifié de la fonction du test de Maurer fTM. L'intérêt de ce calcul modifié est qu'il permet d'avoir une estimation beaucoup plus précise de l'entropie K(L) de la source, puisque la valeur moyenne de la fonction de test modifiée E[fTM] est égale à K(L). Grâce à cette estimation plus précise de l'entropie de la source, le procédé de l'invention permet une détection plus fiable des éventuels défauts statistiques de la source aléatoire testée. La présente invention concerne également, comme cela a été dit au début de la description un dispositif électronique représenté à la figure unique jointe à la présente description. Ce dispositif électronique 10 est un dispositif d'auto-vérification d'intégrité physique d'un circuit intégré s'auto-vérifiant et contrôlant l'intégrité de son générateur aléatoire 40 produisant des nombres aléatoires 30 à partir du procédé de test amélioré 20 décrit précédemment, ceci afin de s'assurer que ledit générateur 40 fonctionne correctement en général et ne présente pas de dérive suite à des io changements de paramètres externes d'origine malveillante telle qu'une altération par des radiations induites en particulier. De manière préférentielle, le dispositif électronique effectuant le test est un dispositif portable, plus particulièrement il consiste, par exemple, en une carte à puce, une carte sans contact, une carte PCMCIA ("Personal Computer Memory Card International Association", 1030 B East Duane Avenue Sunnyvale, California), un badge, une montre "intelligente". Enfin, le dispositif électronique de l'invention peut être un dispositif extérieur constitué d'une machine ou installation destinée à tester le bon fonctionnement de générateurs aléatoires embarqués à bord desdits dispositifs portables. Ce dispositif extérieur permet un échange d'informations avec le dispositif portable de manière à vérifier que le générateur aléatoire fonctionne correctement. Le dispositif extérieur inter- agit avec le dispositif portable pour vérifier l'intégrité de son générateur aléatoire. REVENDICATIONS 1. Procédé de test de sources de nombres aléatoires embarqué à bord d'un système cryptographique, du type carte à puce, comprenant les étapes suivantes: Première étape: Génération d'une séquence de (Q+K)*L bits par la source aléatoire, Q, K et L étant des paramètres d'entrée; les bits de la séquence étant groupés par bloc de L bits, formant une séquence d'entiers compris entre O et 2L-1 de longueur Q+K; la longueur étant io mémorisée dans le tableau block[n], o n est compris entre 1 et Q+K, ledit procédé de test de source étant caractérisé en ce que les étapes deux à huit sont les suivantes: Deuxième étape: Calcul du paramètre du test amélioré, noté fTM; cette deuxième étape comprenant les étapes suivantes, appelées sous- i5 étapes 2.1 à 2.5, Sum étant une variable utilisée à partir de l'étape 2.3, 2.1 Création et initialisation d'un tableau tab [i] de taille 2L; 2. 2 Pour n variant de 1 à Q, calcul de tab[block[n]]=n; 2.3 Initialisation du nombre Sum à O; 2.4 Pour n variant de Q+1 à Q+K, exécution du calcul: Calculer j=n-tab[block[n]]. Si j est inférieur ou égal à 23 alors exécution du calcul Pour k allant de 1 à i-1 Ajouter 1/(k*Log(2)) à Sum Sinon, pour j supérieur à 23, exécution du calcul Ajouter log(j-1)/Iog(2)+0. 8327462+1/(2*(j-1))/log(2) à Sum Faire le calcul: tab[block[n]]=n; 2.5 Le paramètre fTM du test est donné par: fTM=Sum/K Troisième étape: Calcul de la variance par block de paramètre du test, notée Var; son expression précise étant donnée par l'expression suivante: Var= (1- z)* z g(i)2*zi-1 - LA2 i = avec z=1-2'L et g(i) qui est une fonction définie de la manière suivante: i-1 g(i)= Z 1/k k=1 Quatrième étape: Calcul de la fonction c(L,K); son expression approchée étant donnée par la formule: c(L,K)=0,7-0,8/L+(1,6+ 1 2,8/L)*K(-4/L); Cinquième étape: Calcul de l'écart type du paramètre de test, noté cy, donné par la formule o=c(L,K)*I(Var/K); Sixième étape: Calcul du paramètre y; y état déterminé à partir du taux de rejet du test fixé en entrée, noté p; y devant vérifier l'équation: N(-y)= p; N étant la fonction de densité normale sous la forme: N(-y)=J 1/J(2*7t)*exp(-x2/2) dx - Septième étape: Calcul des bornes tl et t2 qui sont données par l'équation: t1=L-y*cy et t2=L+y*c; Huitième étape: Résultat du test: Si le paramètre du test fTM est compris entre tl et t2, alors le générateur de nombre aléatoire est accepté et dans le cas contraire, il est refusé. 2. Dispositif électronique d'auto-vérification d'intégrité physique d'un circuit intégré s'auto-vérifiant et contrôlant l'intégrité de son générateur aléatoire, afin de s'assurer que ce dernier fonctionne correctement en général et ne présente pas de dérive suite à des changements de paramètres externes d'origine malveillante telle qu'une altération par des radiations induites en particulier, caractérisé en ce que ledit dispositif met I0 en oeuvre le procédé de test amélioré selon la revendication 1. 3. Dispositif électronique selon la revendication 2 caractérisé en ce que le dispositif effectuant le test est un dispositif portable. 4. Dispositif électronique selon la revendication 3 caractérisé en ce que le dispositif est une carte à puce. 5. Dispositif électronique selon la revendication 3 caractérisé en ce que le dispositif est une carte sans contact. 6. Dispositif électronique selon la revendication 3 caractérisé en ce que le dispositif est une carte PCMCIA ("Personal Computer Memory Card International Association", 1030 B East Duane Avenue Sunnyvale, Califomia). 7. Dispositif électronique selon la revendication 3 caractérisé en ce que le dispositif est un badge. 8. Dispositif électronique selon la revendication 3 caractérisé en ce que le dispositif est une montre. 9. Dispositif électronique selon la revendication 1 caractérisé en ce qu'un dispositif extérieur effectuant le test est constitué d'une machine ou installation destinée à tester le bon fonctionnement de générateurs aléatoires embarqués à bord desdits dispositifs portables.