Brevet FR2834155A1 — publié le 20030627

PROCÉDÉ DE GÉNÉRATION DE CLÉS ÉLECTRONIQUES CRYPTOGRAPHIQUES ET COMPOSANT CORRESPONDANT L'invention concerne un procédé de génération d'une ou plusieurs clés électroniques cryptographiques à partir d'un nombre secret. L'invention s'applique tout particulièrement à des algorithmes de cryptographie à clé publique utilisés dans certaines applications pour le cryptage d'informations et/ou l'authentification entre deux entités et/ou la signature électronique de messages. Ce sont notamment des applications d'accès à certaines banques de données, des applications bancaires, des applications de télé-péage par exemple pour la télévision ou le passage de péages d'autoroutes. Elle s'applique en particulier à des algorithmes à clé publique tels que les algorithmes RSA du nom de ses auteurs (Rivest, Shamir et Adleman), El Gamal, Schnorr, ou Fiat Shamir. Ces algorithmes sont mis en oeuvre dans des composants électroniques comportant un microprocesseur et des mémoires, dont une mémoire programme par exemple de type ROM, une mémoire de travail par exemple de type RAM et une mémoire de données par exemple de type EEPROM qui contient la ou les clés cryptographiques. Ces composants électroniques sont notamment utilisés dans les cartes à puce. De telles clés occupent beaucoup d'emplacement mémoire du fait de leur taille. Dans le cas par exemple de l'algorithme à clé publique RSA, utilisant un module de 1024 bits, il faut plus de 2000 bits pour mémoriser une clé RSA. De plus, le nombre de clés est multiplié par le nombre d'applications mises en oeuvre par le composant, voire par le nombre d'interlocuteurs d'une même application, ce qui augmente d'autant l'emplacement mémoire utilisé pour mémoriser ces clés. Par ailleurs, les organismes de normalisation envisagent de recommander de doubler la taille des clés RSA ce qui entraînerait un doublement de la taille des clés des algorithmes dérivés du RSA ou plus généralement des algorithmes à clé publique. Le but de la présente invention est donc d'éviter que ces clés occupent tant d'emplacement mémoire. L'invention a pour objet un procédé de génération d'une ou plusieurs clés électroniques cryptographiques à partir d'un nombre secret S, au moyen d'un composant électronique, principalement caractérisé en ce qu'il comporte les étapes consistant pour chaque clé à : a) lire ledit nombre secret S de longueur prédéterminée, b) choisir un identifiant ID, c) générer au moyen d'une fonction déterministe F, un nombre pseudo-aléatoire R à partir de S et de ID, d) générer ladite clé à partir de R. Selon une caractéristique de l'invention, il comporte en outre préalablement à l'étape c) une étape consistant à déterminer un compteur et en ce que l'étape c) consiste à générer au moyen d'une fonction déterministe F, un nombre aléatoire R à partir de S, ID et dudit compteur. La fonction F est de préférence sans collision et éventuellement à sens unique. La fonction F est avantageusement une fonction de génération de masque MGF. Selon une caractéristique de l'invention, la clé est une clé d'un algorithme cryptographique à clé publique. La clé peut être générée à la demande ou en différé. L'invention concerne également un procédé de génération de clés cryptographiques RSA, El Gamal, Schnorr ou Fiat Shamir, caractérisé en ce qu'il met en oeuvre le procédé tel qu'il vient d'être défini plus haut. L'invention concerne aussi un composant électronique comprenant au moins une unité centrale, une mémoire de programme, une mémoire de travail et une mémoire de données, caractérisé en ce qu'il met en oeuvre le procédé objet de l'invention. L'invention peut avoir pour objet une carte à puce comprenant un tel composant électronique. D'autres particularités et avantages de l'invention apparaîtront clairement à la lecture de la description faite à titre d'exemple non limitatif et en regard de la figure 1 annexée qui représente le schéma de principe d'un composant électronique mettant en oeuvre l'invention. Le procédé selon l'invention consiste à lire un seul nombre secret S et à générer les clés à partir de ce secret S, en tant que de besoin. En dehors du secret S, toutes les données utilisées pour générer les clés ainsi que les clés elles-mêmes sont mémorisées pendant la durée nécessaire à l'exécution de l'algorithme de cryptographie ; mais elles peuvent être ensuite effacées lorsqu'il est nécessaire de libérer de l'emplacement mémoire puisqu'elles peuvent être regénérées. Le secret S est typiquement un nombre de 128 bits, voire 64 bits : il occupe donc peu d'emplacement mémoire. Avant de rentrer dans le détail du procédé de génération de clés selon l'invention, on rappelle les différentes étapes de l'algorithme RSA. L'étape de génération des clés privée et publique consiste à : - choisir deux grands nombres premiers p et q de tailles sensiblement équivalentes ; - définir n=p. q et (D (n) = (p-1). (q-1), (D (n) étant la fonction totient ; - choisir un nombre aléatoire e tel que l La clé publique est (n, e) et la clé privée est d. L'étape de cryptage RSA d'un message m (0 L'étape de décryptage RSA du message chiffré c consiste à calculer m=cd mod n. Le nombre premier p est obtenu selon la méthode qui consiste par exemple à : - choisir un nombre aléatoire impair R ; - si ce nombre n'est pas premier, on ajoute 2 ; - ainsi de suite jusqu'à ce que le nombre obtenu soit premier. De même pour obtenir le nombre premier q. Selon l'invention, le nombre aléatoire R utilisé pour obtenir les nombres premiers p et q, est généré à partir du secret S et d'un identifiant ID. Cet identifiant ID est unique pour chaque application ou, pour chaque interlocuteur d'une même application. Il peut comporter des informations relatives au nom et/ou à l'adresse et/ou à l'adresse Internet, ou..., ou comporter un nombre associé à ces informations ; ce nombre peut être public ou déterminé par l'algorithme de génération de clé. Lorsque la même entité utilise plusieurs clés, un compteur ou toute autre valeur distinctive peut être utilisé en plus de l'identifiant. Le nombre R est généré à partir du secret S, de l'identifiant ID et éventuellement du compteur au moyen d'une fonction déterministe (c'est-à-dire non aléatoire) de préférence sans collision (c'est-à-dire qu'il est difficile de trouver xl et x2 tels que h (xl) =h (x2) ) et éventuellement à sens unique. On rappelle qu'une fonction est à sens unique si, étant donné x, il est facile de calculer f (x) mais qu'étant donné f (x), il est difficile de retrouver x. On utilise de préférence comme fonction sans collision et à sens unique, une fonction de génération de masque, appelée MGF (comme"Mask Generating Function"en anglais) telle que celle décrite par Mihir Bellare et Phillip Rogaway dans la publication"The exact security of digital signatures-How to sign with RSA and Rabin" (Advances in Cryptology, EUROCRYPT'96, Lecture Notes in Computer Science, volume 1070, pages 399-416, Springer-Verlag, 1996), Annexe A. Une fonction MGF a en entrée un nombre déterminé k de bits, et en sortie une chaîne de bits, de taille quelconque. Dans le cas présent, on obtient : R = MGF (S, ID, compteur) On a par exemple, h (x) étant une fonction de hachage : MGF (x) = h (xlll) IIh (xI12) llh (xI13) 11... avec x = SllIDllcompteur le symbole 1 1 signifiant concaténé. On rappelle qu'une fonction cryptographique de hachage est une fonction déterministe (non aléatoire) à sens unique et sans collision ; elle a en entrée une chaîne de bits, de taille quelconque et produit en sortie un nombre de k bits. On peut prendre comme fonction h de hachage, la fonction SHA-1 ("Standard Hash Algorithmen anglais) avec k=160 ou la fonction MD5 ("Message Digest 5"en anglais) avec k=128. Le procédé selon l'invention permet ainsi de réduire considérablement l'emplacement mémoire nécessaire pour stocker habituellement les clés d'algorithmes à clé publique. Il peut être mis en oeuvre à la demande lorsque nécessaire ou en différé en prévision d'une future demande. On a représenté sur la figure 1 le schéma fonctionnel d'un composant électronique susceptible de mettre en oeuvre le procédé selon l'invention. Le composant C comporte notamment une unité centrale de traitement 1, une mémoire de programme 2, une mémoire de travail 3 et une mémoire de données 4 associées à l'unité 1. Le nombre secret S est mémorisé dans la mémoire de données 4. Un tel composant peut bien sûr être inclus dans une carte à puce. REVENDICATIONS 1. Procédé de génération d'une ou plusieurs clés électroniques cryptographiques à partir d'un nombre secret S, au moyen d'un composant électronique, caractérisé en ce qu'il comporte les étapes consistant pour chaque clé à : a) lire ledit nombre secret S de longueur prédéterminée, b) choisir un identifiant ID, c) générer au moyen d'une fonction déterministe F, un nombre pseudo-aléatoire R à partir de S et de ID, d) générer ladite clé à partir de R. 2. Procédé selon la revendication précédente, caractérisé en ce qu'il comporte en outre préalablement à l'étape c) une étape consistant à déterminer un compteur et en ce que l'étape c) consiste à générer au moyen d'une fonction déterministe F, un nombre aléatoire R à partir de S, ID et dudit compteur. 3. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que la fonction F est une fonction sans collision. 4. Procédé selon la revendication précédente, caractérisé en ce que la fonction F est à sens unique. 5. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que la fonction F est une fonction de génération de masque MGF. 6. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que la clé est une clé d'un algorithme à clé publique. 7. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que la clé est générée à la demande ou en différé. 8. Procédé de génération de clés cryptographiques RSA, El Gamal, Schnorr ou Fiat Shamir, caractérisé en ce qu'il met en oeuvre le procédé selon l'une quelconque des revendications précédentes. 9. Composant électronique (C) comprenant au moins une unité centrale (1), une mémoire de programme (2), une mémoire de travail (3) et une mémoire de données (4), caractérisé en ce qu'il met en oeuvre le procédé selon l'une quelconque des revendications précédentes. 10. Carte à puce comprenant un composant électronique (C) selon la revendication précédente.