Brevet FR2861518A1 — publié le 20050429

PROCEDE ET DISPOSITIF ASSOCIE DE GENERATION DE NOMBRES ALEATOIRES DANS UN INTERVALLE DONNE L'invention concerne un procédé d'obtention d'un nombre aléatoire compris entre A et B à partir d'un générateur produisant des nombres aléatoires compris entre 0 et W-1, avec N la taille des nombres produits par le générateur, W-1 la valeur maximale prise par les nombres aléatoires produits, avec par exemple W = 21'1, et A, B des nombres entiers quelconques, inférieurs ou supérieurs au nombre W. Une telle situation se produit par exemple dans un composant électronique adapté pour réaliser des calculs cryptographiques et comprenant un générateur de nombres aléatoires de N bits, par exemple N = 8. Les nombres aléatoires qu'il peut produire sont ainsi compris entre 0 et W-1 = 255, alors qu'il serait souhaitable de disposer de nombres aléatoires compris par exemple entre 0 et 100 ou entre 300 et 10000. A noter qu'il suffit de déterminer des nombres entre 0 et 9700 puis d'ajouter ensuite 300 au nombre obtenu pour obtenir finalement un nombre entre 300 et 10000. Une telle situation se retrouve dans la pratique dans la plupart des applications cryptographiques, par exemple la signature DSA, la signature ou le chiffrement d'El Gamal, le développement de contremesures contre diverses attaques, etc. Plusieurs procédés sont déjà connus pour produire des nombres aléatoires R compris entre 0 et K à partir de nombres compris entre 0 et W-1. Ces procédés sont en général mis en oeuvre par des moyens logiciels utilisés pour piloter d'une part un générateur hardware qui produit des nombres aléatoires de taille N et d'autre part des moyens de calcul réalisant notamment des opérations de multiplications, d'additions, etc. Un premier procédé connu comprend les étapes suivantes a) déterminer le plus petit nombre entier p tel que K WP - 1, b) produire p nombres aléatoires S0, S1, Sp_1 et p-1 former la variable S = E Si * Wl i=0 c) si S > K, alors retourner à l'étape b), sinon poser R = S R est le nombre aléatoire recherché, compris entre 0 et p-1 K. L'équation S = E Si * Wl est une représentation de la i=0 variable S décomposée / recomposée dans la base (WP-1, ..., W1, w0). On pourrait également noter S = Sp_1Sp_2...S1S0, notation couramment utilisée. Un deuxième procédé connu comprend les étapes suivantes: a) déterminer le plus petit nombre entier p tel que 20 K S WP - 1, b) produire p nombres aléatoires Sa, S1, Sp_1 et p-2 former la variable T = E S, etS = T + Sp_1*Wp 1 r=o c) si S > K, poser R = T, sinon poser R = S. Un troisième procédé connu comprend les étapes 25 suivantes: a) déterminer le plus petit nombre entier p tel que K Ces trois procédés peuvent être résumés par les étapes suivantes: a) produire p nombres aléatoires S0r S1, Sp_1, p étant le plus petit nombre entier tel que K A noter que, dans les trois procédés, si un nombre compris entre A et K+A est souhaité, il suffit d'ajouter 20 A au nombre R obtenu compris entre 0 et K. Le premier procédé a pour principal inconvénient un temps de calcul particulièrement long et surtout imprévisible: l'étape de production des p nombres aléatoires peut être répétée de nombreuses fois sans qu'il soit possible de prévoir au départ le nombre de répétitions de cette étape. Le 2ème et le 3ème procédés ont pour principal inconvénient de produire des nombres aléatoires présentant un biais: parmi les nombres R produits dans l'intervalle [0, K], 2861518 4 certaines valeurs sont plus probables que d'autres. Dit autrement, les nombres R produits ne sont pas parfaitement aléatoires (distribution non uniforme). Ce biais peut avoir des conséquences importantes sur la sécurité des systèmes cryptographiques susceptibles de mettre en oeuvre ces procédés. La sécurité des systèmes cryptographiques suppose en effet que les nombres aléatoires qu'ils utilisent soient uniformément distribués (ou au moins proches d'une distribution uniforme) dans l'intervalle [0, K] ou [A, K+A] souhaité. Enfin, les trois procédés sont globalement lents parce qu'ils mettent en oeuvre des opérations sur des grands nombres, de taille N (au sens nombre de bits) supérieure à la taille des circuits utilisés pour la mise en uvre. En effet, le nombre K notamment, est quelconque et peut être supérieur à w et donc de taille supérieure à N. La variable S peut également être de grande taille. Or, la mise en oeuvre d'opérations sur des grands nombres nécessite la mise en oeuvre de procédés complexes et coûteux en termes de temps de calcul. Un objet essentiel de l'invention est de proposer un procédé de construction d'un nombre aléatoire R particulièrement rapide. Ainsi, l'invention propose un procédé cryptographique, au cours duquel on utilise un générateur de nombres aléatoires produisant des nombres aléatoires Si de taille N fixée compris entre 0 et W-1, avec par exemple mais non nécessairement W = 2N, pour produire un nombre aléatoire R compris entre 0 et une borne K prédéfinie. Les étapes essentielles d'un procédé selon l'invention sont les suivantes: E31: on produit une variable aléatoire Si comprise entre 0 et W-1, E32. si la variable aléatoire Si est strictement inférieure à un coefficient Ki de la borne K dans la base W, alors le coefficient Ri de rang i du nombre aléatoire R est égal à la variable aléatoire Si puis, pour tout rang j inférieur à i, on produit une variable aléatoire Sj entre 0 et W-1 et on pose Rj = Sj E33 sinon, si la dite variable aléatoire est supérieure au coefficient Ki de rang i de la borne K dans la base W, alors on détermine le dit coefficient Ri à partir de la variable aléatoire Si de rang i selon une fonction prédéfinie, puis on détermine le coefficient Ri_1 du nombre aléatoire R de rang i-1 immédiatement inférieur en répétant les étapes E31 à E33. Ainsi, dans un procédé selon l'invention, on recherche un à un les coefficients Ri du nombre aléatoire R souhaité, en commençant par le coefficient Rp_1 le plus significatif. Le générateur physique de nombres aléatoires utilisés produit ainsi des variables aléatoires Si une à une, une variable à chaque itération. De plus, le procédé est rapide car l'étape E33 est exécutée un nombre restreint de fois. En effet, dès qu'une des variables Si produite par le générateur physique est inférieure au coefficient Ki associé de la borne K, le procédé ne nécessite plus le traitement des variables Si de rang inférieur à i: on calcule ainsi le plus souvent un nombre restreint de coefficients du nombre R, les plus significatifs. Enfin, par rapport aux procédés connus, un procédé selon l'invention présente l'avantage de travailler sur des nombres de au plus N bits, N étant la taille des registres et autres circuits de calculs des dispositifs utilisés pour la mise en oeuvre. Par exemple, si W est égal à 2N, les coefficients Ki, résultant de la décomposition de K dans la base (W1D-1, ... W1, Wo), sont nécessairement inférieurs à w et donc de taille au plus N bits. De même, les variables aléatoires Si produites par le générateur physique de nombres aléatoires sont également de N bits. En ajoutant aux étapes essentielles une étape d'initialisation et une étape de recombinaison du nombre aléatoire R, on obtient: El: on décompose la borne K dans une base (WP-1, p 1 Wp-2, Wo) (K = Ki *W. ou K = Kp 1...K1Ko) , i étant un i=o indice de boucle, Ki étant un coefficient de la borne K de rang i compris entre 0 et W-1 et p étant le degré de la borne K, E2: on initialise à VRAI une variable booléenne f, E3: on réalise les opération suivantes, dans une boucle indicée par i, i étant un nombre entier variant entre p-1 et 0: E31 on produit une variable aléatoire Si comprise entre 0 et W-1, E32: si la variable aléatoire Si est strictement inférieure au coefficient Ki de rang i, alors on met à FAUX la variable booléenne f, E33_1 si la variable aléatoire Si est strictement supérieure au coefficient Ki de rang i et si la variable booléenne f est VRAI, alors on détermine le coefficient Ri de rang i à partir de la variable aléatoire Si de rang i selon une fonction prédéfinie, E33_2: sinon, on pose Ri = Si E34: on décrémente l'indice de boucle i, E4 on détermine le nombre aléatoire R par recombinaison des coefficients aléatoires Ri dans la base p-1 W (R = Ri * Wl ou Rp-1...R'R0) . i=0 Concrètement, dès que la variable booléenne f est positionnée à FAUX, elle reste à cette valeur, puisqu'il n'est pas prévu de la repositionner à la valeur VRAI, sauf lors de l'initialisation E2 du procédé. L'étape E33 est exécutée uniquement si la variable f est VRAI; ainsi, dès que la variable f est positionnée à la valeur FAUX, l'étape E33_1 n'est plus exécutée et le procédé selon l'invention se termine rapidement. Un deuxième objectif de l'invention est de proposer un procédé de construction de nombres aléatoires dont la distribution soit uniforme ou puisse être rendue aussi proche que souhaitée d'une distribution uniforme. Cet objectif est atteint en choisissant une fonction adéquate pour la détermination du coefficient Ri à partir de la variable aléatoire Si. Selon un premier mode de mise en oeuvre d'un procédé selon l'invention, pour déterminer le coefficient Ri de rang i à partir de la variable aléatoire Si de rang i (étape E33_1), on réalise les sous-étapes suivantes: E33_11: si la variable aléatoire Si est strictement supérieure au coefficient Ki de la borne K, alors on produit une nouvelle variable aléatoire Si, E33_12 on répète l'étape E3311 jusqu'à ce que la variable aléatoire Si soit inférieure au coefficient Ki de la borne K, puis on égalise le coefficient Ri à la variable aléatoire Si. Dans un tel mode de réalisation, tous les coefficients Ri obtenus sont des nombres directement produits par le générateur hardware de nombres aléatoires, ces coefficients sont donc parfaits et le nombre R qui en résulte est également parfait. en d'autres termes, la distribution obtenue des nombres R est uniforme dans l'intervalle [0, K]. Selon un deuxième mode de mise en oeuvre, au cours de l'étape E33, on choisit le coefficient Ri de rang i égal à une partie de la variable aléatoire Si, partie inférieure au coefficient Ki. La dite partie correspondant dans un exemple à un nombre limité de bits de la variable Si. Selon un troisième mode de réalisation, au cours de l'étape E33, on réduit la variable aléatoire Si modulo Ki+l, le résultat de la réduction étant le coefficient Ri cherché. Ces deux derniers modes de réalisation sont rapides par rapport aux procédés connus, essentiellement parce qu'on travaille sur des petits nombres. Les distributions de nombres aléatoires obtenus ne sont cependant pas uniformes: le simple fait de tronquer la variable Si ou d'effectuer une réduction modulo Ki+l introduit nécessairement un biais. Toutefois, ce biais est moindre par rapport aux procédés de l'art antérieur. Par ailleurs, il est possible de réduire le biais des procédés selon les deuxième et troisième modes de réalisation proposés, comme on va le voir ci-dessous. Dans un procédé selon l'invention tel que décrit ci-dessus, on construit un nombre aléatoire R inférieur à K à partir de variables Si de taille N produits par un générateur physique parfaitement aléatoire. Le nombre R obtenu est biaisé, mais le biais est réduit par rapport à un procédé connu. Pour cela, dans le deuxième mode ou le troisième mode de réalisation, on construit notamment au cours de l'étape E33_1 un coefficient Ri Concrètement, pour déterminer le coefficient Ri de rang i à partir de la variable aléatoire Si de rang i (étape E331), on exécute les étapes El à E4 en utilisant une base ((3q-1, ..., (3o) comme base de calcul, (3 étant un nombre entier strictement inférieur à w et q étant le degré de Ki dans la base P. L'étape E33 est ainsi décomposée en les sous-étapes suivantes: E33_41: on décompose le coefficient Ki de rang i de la borne K dans la base ( q-1 q-1 * j R po) ( Ki = (Ki)j (3 ou j=0 Ki = (Ki) q-i... (Ki) 1 (Ki) o) , j étant un indice de boucle, (Ki)j étant un nombre compris entre 0 et (3-1 et q étant un degré du coefficient Ki, E33 42 on initialise à VRAI une deuxième variable booléenne g, E33 43 on réalise les opération suivantes, dans une boucle indicée par j variant entre q-1 et 0: E33431 on produit une variable aléatoire (Si)j comprise entre 0 et (3-1, E33_432 si la variable aléatoire (Si)j est strictement inférieure au coefficient (Ki)j, alors on met à FAUX la deuxième variable booléenne g, E334331 si la variable aléatoire (Si)j est strictement supérieure au coefficient (Ki)j et si la deuxième variable booléenne g est VRAI, alors on détermine un coefficient (Ri)j à partir de la variable aléatoire (Si)j selon une fonction prédéfinie, E33 4332: sinon, poser (Ri) j = (Si) j E33434: on décrémente l'indice de boucle 3, E33 44 on détermine le nombre aléatoire Ri par recombinaison des coefficients aléatoires (Ri)j dans la q-1 base (3 (R1 = E(R1); *ou Ri = (Ri) q-1... (Ri) 1 (Ri) o) i=0 Comme on vient de le voir ci-dessus, en "imbriquant" deux procédés, on réduit le biais des nombres aléatoires R produits par le procédé global, tout en conservant un procédé global rapide. On peut bien sûr imaginer d"imbriquer" plus de deux procédés, par exemple trois ou quatre, en décomposant, dans l'étape E33_43 les nombres dans une base y De manière générale, plus on "imbrique" de procédés, plus les nombres sur lesquels on travaille sont petits. la durée de chaque étape diminue et le biais des nombres produits par le procédé global diminue également. L'invention a également pour objet un composant électronique adapté pour la mise en oeuvre d'un procédé tel que décrit ci- dessus. Un tel composant comprend notamment un générateur produisant des nombres aléatoires de taille N, et des circuits de calcul pour réaliser des opérations sur des nombres de au plus N bits. Selon le mode de réalisation du procédé à mettre en uvre, les circuits de calcul sont adaptés pour réaliser des opérations de comparaison de deux nombres, de troncature de nombre, de réduction modulaire. Le générateur de nombres aléatoires et les circuits de calcul sont pilotés de préférence par un moyen logiciel mémorisé dans une mémoire du composant prévue à cet effet. L'invention concerne également une carte à puce comprenant un composant électronique tel que décrit ci- dessus. 12 REVENDICATIONS, 1. Procédé cryptographique, au cours duquel on utilise un générateur de nombres aléatoires produisant des nombres aléatoires Si de taille N fixée compris entre O et W-1, pour produire un nombre aléatoire R compris entre 0 et une borne K prédéfinie, caractérisé en ce que: E31: on produit une variable aléatoire Si comprise entre 0 et W-1, E32 si la variable aléatoire Si est strictement inférieure à un coefficient Ki de la borne K dans la base W, alors le coefficient Ri de rang i du nombre aléatoire R est égal à la variable aléatoire Si puis, pour tout rang j inférieur à i, on produit une variable aléatoire Si entre 0 et W-1 et on pose Ri = Si. E33: sinon, si la dite variable aléatoire est supérieure au coefficient Ki de rang i de la borne K dans la base W, alors on détermine le dit coefficient Ri à partir de la variable aléatoire Si de rang i selon une fonction prédéfinie, puis on détermine le coefficient Ri_1 du nombre aléatoire R de rang i-1 immédiatement inférieur en répétant les étapes E31 à E33. 2. Procédé selon la revendication 1, au cours duquel on réalise les étapes suivantes: El: on décompose la borne K dans une base (Wp-1, Wp-2, . , p-1 W0) sous la forme K = Ki * W1, i étant un indice de i=0 2861518 13 boucle, Ki étant un coefficient de la borne K de rang i compris entre 0 et W-1 et p étant le degré de la borne K, E2: on initialise à VRAI une variable booléenne f, E3: on réalise les opération suivantes, dans une boucle indicée par i, i étant un nombre entier variant entre p-1 et 0: E31: on produit une variable aléatoire Si comprise entre 0 et W-1, E32: si la variable aléatoire Si est strictement inférieure au coefficient Ki de rang i, alors on met à FAUX la variable booléenne f, E33_1: si la variable aléatoire Si est strictement supérieure au coefficient Ki de rang i et si la variable booléenne f est VRAI, alors on détermine le coefficient Ri de rang i à partir de la variable aléatoire Si de rang i selon une fonction prédéfinie, E33_2: sinon, on pose Ri = Si E34: on décrémente la variable de boucle i, E4: on détermine le nombre aléatoire R par recombinaison des coefficients aléatoires Ri dans la base W selon la p-1 relation: R = Ri * Wl. i=0 3. Procédé selon la revendication 2, au cours duquel, pour déterminer le coefficient Ri de rang i à partir de la variable aléatoire Si de rang i (étapes E33_1 et E33_2), on réalise les sous-étapes suivantes: E33_11: si la variable aléatoire Si est strictement supérieure au coefficient Ki de la borne K, alors on produit une nouvelle variable aléatoire Si, 2861518 14 E33_12 on répète l'étape E33_11 jusqu'à ce que la variable aléatoire Si soit inférieure au coefficient Ki de la borne K, puis on égalise le coefficient Ri à la variable aléatoire Si...CLMF: 4. Procédé selon la revendication 2, au cours duquel, on choisit (étapes E33-1 et 33_2) le coefficient Ri de rang i égal à une partie de la variable aléatoire Si, partie inférieure au coefficient Ki, la dite partie correspondant par exemple à un nombre limité de bits de la variable Si. 5. Procédé selon la revendication 2, au cours duquel, au pour déterminer le coefficient Ri de rang i à partir de la variable aléatoire Si de rang i (étape E33), on réduit la variable aléatoire Si modulo Ki+1, le résultat de la réduction étant le coefficient Ri cherché. 6. Procédé selon l'une des revendications 1 à 5, au cours duquel, pour déterminer le coefficient Ri de rang i à partir de la variable aléatoire Si de rang i (étape E33), on exécute les étapes El à E4 en utilisant une base (pq-1, po) comme base de calcul, (3 étant un nombre entier strictement inférieur à w et q étant le degré de K dans la base P. 7. Procédé selon la revendication 6, dans lequel l'étape E33 est décomposée en les sous-étapes suivantes: E33_41: on décompose le coefficient Ki de rang i de la borne K dans la base (f3q-1, po) sous la forme q-1 Ki = E (Ki)j * R3, j étant un indice de boucle, (Ki) j étant j=0 un nombre compris entre 0 et (3-1 et q étant le degré du coefficient Ki, E33_42 on initialise à VRAI une deuxième variable booléenne g, E33_43. on réalise les opération suivantes, dans une boucle indicée par j variant entre q-1 et 0: E33_431 on produit une variable aléatoire (Si)j comprise entre 0 et (3 - 1, E33_432 si la variable aléatoire (Si)j est strictement inférieure au coefficient (Ki)j, alors on met à FAUX la deuxième variable booléenne g, E33_4331 si la variable aléatoire (Si)j est strictement supérieure au coefficient (Ki)j et si la deuxième variable booléenne g est VRAI, alors on détermine un coefficient (Ri)j à partir de la variable aléatoire (Si)j selon une fonction prédéfinie, E33_4332: sinon, poser (Ri)j = (Si)j E33_434: on décrémente l'indice de boucle j, E33_44 on détermine le nombre aléatoire Ri par recombinaison des coefficients aléatoires (Ri)j dans la q-1 base (3 selon la relation: R _ 1(R;) *(3' . =a 8. Composant électronique comprenant un générateur de nombres aléatoires de taille N, des circuits de calcul réalisant notamment une comparaison, une troncature et / ou une réduction modulaire sur des nombres de au plus N bits, et un moyen de pilotage du générateur de nombres aléatoires et des circuits de calcul, le dit moyen de 2861518 16 pilotage étant adapté pour la mise en oeuvre d'un procédé selon l'une des revendications 1 à 7. 9. Carte à puce comprenant un composant électronique selon la revendication précédente.