Brevet FR2828353A1 — publié le 20030207

PROCEDE DE DETERMINATION DE LA TAILLE D'UN ALEA POUR UN SCHEMA DE SIGNATURE ELECTRONIQUE La présente invention concerne un procédé de détermination de la taille d'un aléa utilisé pour générer une signature électronique dans les systèmes de la cryptographie à clef publique. Le concept de cryptographie à clef publique fut inventé par Whitfield DIFFIE et Martin HELLMAN en 1976. Le principe de la cryptographie à clef publique consiste à utiliser une paire de clefs, une clef publique de chiffrement et une clef privée de déchiffrement. Il doit être calculatoirement infaisable de trouver la clef privée de déchiffrement à partir de la clef publique de chiffrement. Une signature électronique d'un message est un nombre dépendant à la fois de la clef privée connue seulement de la personne signant le message, ainsi que du contenu du message à signer. Une signature électronique doit être vérifiable : il doit être possible pour une tierce personne de vérifier la validité de la signature, sans que la connaissance de la clé privée de la personne signant le message ne soit requise ; la vérification de la signature s'effectue à l'aide de la clef publique correspondante. Il existe de nombreux schémas de signature électronique. Les plus connus sont : - Schéma de signature RSA : c'est le schéma de signature électronique le plus largement utilisé. Sa sécurité est basée sur la difficulté de la factorisation de grands nombres ; - Schéma de signature Rabin : sa sécurité est aussi basée sur la difficulté de la factorisation de grands nombres ; - Schéma de signature de type El-Gamal : sa sécurité est basée sur la difficulté du problème du logarithme discret ; le problème du logarithme discret consiste à déterminer, s'il existe, un entier x tel que y=g'avec y et g deux éléments d'un ensemble E possédant une structure de groupe ; - Schéma de signature Schnorr : il s'agit d'une variante du schéma de signature de type El-Gamal. Techniquement, deux types de schéma de signature électronique se distinguent : - Schémas de signature électronique nécessitant le message original pour la vérification de la signature : on transmet donc le message et la signature séparément ; - Schémas de signature électronique avec reconstitution du message : le message original est obtenu d'après la signature elle-même ; le message original n'étant pas nécessaire pour vérifier la signature, la taille totale de la signature est plus courte. La première réalisation d'un schéma à clef publique fut mise au point en 1977 par Rivest, Shamir et Adleman, qui ont inventé le système de chiffrement RSA. La sécurité de RSA repose sur la difficulté de factoriser un grand nombre qui est le produit de deux nombres premiers. Le système RSA est le système de chiffrement à clé publique le plus utilisé. Il peut être utilisé comme procédé de chiffrement ou comme procédé de signature. Le système RSA est utilisé dans les cartes à puce, pour certaines applications de celles-ci. Les applications possibles de RSA sur une carte à puce sont l'accès à des banques de données, des applications bancaires, des applications de paiements à distance comme par exemple la télévision à péage, la distribution d'essence ou le paiement de péages d'autoroute. Le principe d'un schéma de signature électronique basé sur le système RSA peut généralement être défini en trois parties : - La première partie est la génération de la clef RSA. Chaque utilisateur crée une clé publique RSA et une clé privée correspondante, suivant le procédé suivant en 5 étapes : 1) Générer deux nombres premiers distincts p et q de même taille k/2 bits, k étant un paramètre entier ; 2) Calculer le nombre n tel que : n=p*q et = (p- 1) * (q-1) ; 3) Sélectionner aléatoirement un entier e, 1 Les entiers e et d sont appelés respectivement exposant de chiffrement et exposant de déchiffrement. L'entier n est appelé le module. La deuxième partie est la génération de la signature. Le procédé consiste à prendre en entrée le message M à signer, à lui appliquer un encodage utilisant une fonction pour obtenir la chaîne de caractère (M). La signature S est alors donnée par : S= (M) ^d mod N ; Ainsi, seule la personne possédant la clef privée correspondant à l'exposant d peut générer la signature ; La troisième partie est la vérification de la signature : le procédé consiste à prendre en entrée le message M à signer et la signature S à vérifier, à appliquer un encodage au message M en utilisant une fonction jj. pour obtenir la chaîne de caractère u (M), à calculer Y=S^e mod N et à vérifier que le résultat obtenu est égal à (M). Dans ce cas, la signature S du message M est valide, et dans le cas contraire elle est fausse. Il existe de nombreux procédés d'encodage utilisant différentes fonctions . Un exemple de procédé d'encodage est le procédé décrit dans le standard ISO/IEC 9796-2, Information Technology - Security techniques-Digital signature scheme giving message recovery, Part 2 : Mechanisms using a hash-function, 1997 . Un autre exemple de procédé d'encodage est le procédé d'encodage décrit dans le standard RSA Laboboratories, PKCS&num;1 : RSA cryptography specifications, version 2.0, September 1998 . Ces deux procédés d'encodage permettent de signer des messages de taille arbitrairement longue. L'inconvénient de ces procédés d'encodage précédemment décrits est qu'ils n'offrent pas forcément un niveau de sécurité comparable au système RSA. Au contraire, il existe des procédés d'encodage qui offrent un niveau de sécurité équivalent au schéma RSA. Le plus connu d'entre eux est le schéma de signature PSS, acronyme anglais désignant Probabilistic Signature Scheme , décrit en 1996 par Bellare et Rogaway dans la publication intitulée The exact security of digital signatures-How to sign with RSA and Rabin et publiée à la conférence Eurocrypt 1996. Le schéma de signature PSS est inclus dans de nombreux standards, incluant - IEEE P1363, Standard Specifications For Public Key Cryptography : Additional Techniques ; - PKCS &num;1 v2.1, RSA Cryptography Standard. Le schéma de signature PSS permet de signer un message M de longueur arbitraire. Il existe aussi une variante du schéma PSS nommée PSS-R dans laquelle on retrouve le message au moment de la vérification de la signature. Il n'est alors plus nécessaire de transmettre le message avec la signature. Le procédé de signature PSS fonctionne de la manière suivante : pour signer un message M, on concatène au message un aléa r de taille ko bits, ko étant un paramètre déterminé préalablement. On applique ensuite à Mllr une fonction de hachage H qui renvoie en sortie une chaîne de taille k1 bits, k1 étant un paramètre, pour obtenir le résultat w. On définit une fonction de hachage G prenant en entrée un message de taille k1 bits et renvoyant en sortie un message de taille k-k1-l bits. On définit la fonction G1 qui renvoie les ko premiers bits de la fonction G, ainsi que la fonction G2 qui renvoie les k-k1-ka-l bits restants. La fonction d'encodage p. (M) est alors donnée par : t (M) =0 11 w 11 G, (w) xor r 11 G2 (W)- Pour vérifier la signature S d'un message M, on calcule dans un premier temps Y=SAe mod N Et on écrit ensuite Y sous la forme Y=0##w##r*##g, où w est une chaîne de taille k1 bits, r* est une chaîne de taille ko bits, et g est une chaîne comprenant les k-ko-ki-1 bits restants. On calcule r=G1 (w) xor r* et on vérifie que w=H (M) jr) et g=G2 (w). Le schéma de signature PSS-R, acronyme anglais désignant Probabilistic Signature SchemeRecovery, est analogue au schéma PSS, la différence étant qu'il permet de retrouver le message au moment de la vérification de la signature. La taille du message qui est retrouvée lors de la vérification de la signature est de k- 1-ko-kl. On en déduit que plus la taille ko de l'aléa est petite, plus on peut retrouver un grand message lors de la vérification de la signature. On diminue donc ainsi la taille totale des données échangées : on n'a pas besoin de transmettre le message car il sera retrouvé au moment de la vérification de la signature. Or la taille des données échangées est cruciale dans beaucoup d'applications disposant de peu de mémoires, comme la carte à puce ou les ordinateurs de poches. L'invention consiste en un procédé permettant de déterminer la taille optimale de l'aléa utilisé lors de la génération de la signature. La taille est optimale au sens où elle est la taille minimale permettant de garantir un niveau de sécurité équivalent à RSA. L'utilisation d'un aléa de taille plus petite ne permet pas d'avoir un niveau de sécurité équivalent à celui de RSA. Le procédé de l'invention est particulièrement destiné à s'appliquer au schéma de signature PSS, mais il peut s'étendre à d'autres schémas de signature aux caractéristiques analogues à PSS, par exemple au schéma de signature PFDH, acronyme anglais de Probabilistic Full Domain Hash . Le schéma PFDH fonctionne de la manière suivante. Pour générer une signature d'un message M, on concatène au message M un aléa r de taille ko bits, ko étant un paramètre déterminé préalablement. On applique ensuite à MI Ir une fonction de hachage H qui renvoie en sortie une chaîne de taille k bits notée p. (M) =H (M 1 1 r). Dans une première variante, le procédé consiste à inclure un compteur qui limite le nombre total de signature qui seront générées pour une clef publique donnée. Initialement, le compteur est fixé à zéro. A chaque nouvelle signature, on incrémente le compteur. Lorsque la valeur du compteur a dépassé une valeur maximale notée qsig, on ne peut plus générer de signature. On détermine alors la valeur optimale de la taille ko de l'aléa en déterminant kü=10g (qsig)/log (2), où log désigne la fonction logarithme. L'avantage de cette première variante est que la taille ko de l'aléa est optimale : une taille ko inférieure à cette valeur engendrerait un niveau de sécurité inférieur au niveau de sécurité du système RSA, tandis qu'une taille ko supérieure à cette valeur diminuerait la taille du message qui peut être retrouvé lors de la vérification de la signature. Dans une deuxième variante, le procédé consiste à utiliser le temps tgen nécessaire à la génération d'une signature, ainsi que la durée de vie maximale tvie du système de génération de signatures selon une clé publique donnée. Par exemple, une carte bancaire utilisant ce dit système de génération de signatures selon une clé publique donnée devant être renouvelée tous les deux ans possède une durée de vie tvie=2 ans. On obtient alors le nombre maximal qsig de signatures pouvant être générées en calculant : qsig=tvie/tgen. On obtient ensuite suivant le même procédé décrit dans la première variante la taille optimale ko de l'aléa en calculant : kO=log (qsig) /log (2) L'avantage de cette deuxième variante est que l'on obtient un niveau de sécurité équivalent au système RSA, avec une taille de message retrouvé maximale, et sans utiliser de compteur. Dans une troisième variante, on utilise un compteur q du nombre de signatures générées, mais on ne connaît pas à priori la valeur limite de ce compteur. Initialement, le compteur q est fixé à zéro, et la valeur du paramètre ko est fixée à zéro. A chaque nouvelle génération d'une signature, on incrémente le compteur q. On détermine alors une nouvelle valeur de ko égale à la taille mesurée en nombre de bits de q. Par exemple, si q=7, kO=3, et si q=8, kO=4. L'avantage du procédé de la troisième variante est que l'on conserve tout au long du procédé une valeur optimale pour la taille ko de l'aléa : on conserve un niveau de sécurité équivalent au système RSA tout en permettant de retrouver une taille maximale de message. Les schémas de signature utilisés pour la présente invention sont préférentiellement du RSA, Rabin, PSS, PSS-R et PFHD comme décrits précédemment dans la description. Les trois variantes du procédé précédemment décrites mais non exhaustives peuvent s'appliquer plus généralement à tout système de signature dans lequel on retrouve la valeur de l'aléa au moment de la vérification de la signature. L'application de l'une quelconque des trois variantes du procédé précédemment décrites permettent d'obtenir une taille d'aléa généré optimale. Les trois variantes sont particulièrement destinées à être utilisées dans un objet portable électronique de type carte à puce. REVENDICATIONS 1) Procédé de détermination de la taille d'un aléa utilisé dans la génération d'une signature électronique, ladite taille étant à la fois minimale et permettant de garantir un niveau de sécurité équivalent avec le système cryptographique de base utilisé à clé publique, caractérisé en ce que ledit procédé nécessite la connaissance du nombre total qsig de signatures qui sont générées pour une clef publique donnée, la taille ko de l'aléa étant déterminée par la formulation : ko=log (qsig) /log (2), log désignant la fonction logarithme. 2) Procédé selon la revendication 1 caractérisé en ce qu'il utilise un compteur du nombre de signatures générées, ledit compteur étant fixé initialement à zéro, ledit compteur étant incrémenté à chaque nouvelle génération de signature, le nombre total de signature pouvant être générées étant limité par un paramètre qsig fixé à l'avance, la taille ko de l'aléa généré étant déterminé par la formulation : ko=log (qsig) /log (2), log désignant la fonction logarithme. 3) Procédé selon la revendication 1 caractérisé en ce qu'une durée de vie tvie maximale d'un système de génération de signatures pour une clé publique donnée et un temps de génération tgen d'une signature sont connus, le nombre maximal de signatures pouvant être générées est déterminé par la formulation : qsig=tvie/tgen, la taille ko de l'aléa généré est déterminée par ko=log (qsig) /log (2), log désignant la fonction logarithme. 4) Procédé de détermination de la taille d'un aléa utilisé dans la génération d'une signature électronique, ladite taille étant à la fois minimale et permettant de garantir un niveau de sécurité équivalent avec le système cryptographique de base utilisé, caractérisé en ce qu'il utilise un compteur q du nombre de signatures, ledit compteur q étant fixé initialement à zéro, ledit compteur q étant incrémenté à chaque génération d'une signature, la taille ko de l'aléa étant initialement fixée à 0, ladite taille kO de l'aléa étant ensuite donnée par la taille mesurée en nombre de bits du compteur q. 5) Procédé selon l'une quelconque des revendications 1 à 4, caractérisé en ce que ledit système cryptographique de base est RSA. 6) Procédé selon l'une quelconque des revendications 1 à 4, caractérisé en ce que ledit système cryptographique de base est Rabin. 7) Procédé selon l'une quelconque des revendications 1 à 4, caractérisé en ce que le schéma de signature utilisé est PSS. 8) Procédé, selon l'une quelconque des revendications 1 à 4, caractérisé en ce que le schéma de signature utilisé est PSS-R. 9) Procédé selon l'une quelconque des revendications là 4, caractérisé en ce que le schéma de signature utilisé est PFDH. 10) Procédé selon l'une quelconque des revendications là 9, caractérisé en ce qu'il est mis en oeuvre dans un objet électronique portable. 11) Procédé selon la revendication précédente 9, caractérisé en ce que ledit dispositif électronique est une carte à puce. 12) Dispositif électronique portable mettant en oeuvre le procédé selon l'une quelconque des revendications 1 gall.