Brevet FR2814619A1 — publié le 20020329

PROCEDE D'ENCODAGE DE MESSAGES LONGS POUR SCHEMAS DE SIGNATURE ELECTRONIQUE A BASE DE RSA. La présente invention concerne un procédé d'encodage de messages longs pour des schémas de signature électronique à base de RSA. Dans le modèle classique de la cryptographie à clef secrète, deux personnes désirant communiquer par l'intermédiaire d'un canal non sécurisé doivent au préalable se mettre d'accord sur une clé secrète de chiffrement K. La fonction de chiffrement et la fonction de déchiffrement utilisent la même clef K. L'inconvénient du système de chiffrement à clé secrète est que ledit système requiert la communication préalable de la clé K entre les deux personnes par l'intermédiaire d'un canal sécurisé, avant qu'un quelconque message chiffré ne soit envoyé à travers le canal non sécurisé. Dans la pratique, il est généralement difficile de trouver un canal de communication parfaitement sécurisé, surtout si la distance séparant les deux personnes est importante. On entend par canal sécurisé un canal pour lequel il est impossible de connaître ou de modifier les informations qui transitent par ledit canal. Un tel canal sécurisé peut être réalisé par un câble reliant deux terminaux, possédés par les deux dites personnes. Le concept de cryptographie à clef publique fut inventé par Whitfield DIFFIE et Martin HELLMAN en 1976. La cryptographie à clef publique permet de résoudre le problème de la distribution des clefs à travers un canal non sécurisé. 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 personne A désirant communiquer une information à une personne B utilise la clef publique de chiffrement de la personne B. Seule la personne B possède la clef privée associée à sa clef publique. Seule la personne B est donc capable de déchiffrer le message qui lui est adressé. Un autre avantage de la cryptographie à clé publique sur la cryptographie à clé secrète est que la cryptographie à clef publique permet l'authentification par l'utilisation de signature électronique. La première réalisation de schéma de chiffrement à 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. Depuis, de nombreux systèmes de chiffrement à clef publique ont été proposés, dont la sécurité repose sur différents problèmes calculatoires (cette liste n'est pas exhaustive). Sac à dos"de Merckle-Hellman : Ce système de chiffrement est basé sur la difficulté du problème de la somme de sous- ensembles - McEliece : Ce système de chiffrement est basé sur la théorie des codes algébriques. Il est basé sur le problème du décodage de codes linéaires - ElGamal : Ce système de chiffrement est basé sur la difficulté du logarithme discret dans un corps fini ; - Courbes elliptiques : Le système de chiffrement à courbe elliptique constitue une modification de systèmes cryptographiques existant pour les appliquer au domaine des courbes elliptiques. L'avantage des systèmes de chiffrement à courbes elliptiques est qu'ils nécessitent une taille de clef plus petite que pour les autres systèmes de chiffrement. Le système de chiffrement 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 de chiffrement 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 du système de chiffrement RSA est le suivant. Il peut être divisé en trois parties distinctes qui sont : l) La génération de la paire de clés RSA 2) Le chiffrement d'un message clair en un message chiffré, et 3) Le déchiffrement d'un message chiffré en un message clair. 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 ; 2) Calculer n=pq et = (p-l) (q-1) 3) Sélectionner aléatoirement un entier e, l tel que pgcd (e, ) =1 i 4) Calculer l'unique entier d, l exposant de chiffrement et exposant de déchiffrement. L'entier n est appelé le module. La seconde partie consiste au chiffrement d'un message clair noté m au moyen d'un algorithme avec l Calculer c=mAe mod n. La troisième partie consiste au déchiffrement d'un message chiffré utilisant l'exposant privé d de déchiffrement au moyen d'un algorithme. L'algorithme de déchiffrement d'un message chiffré noté c avec l Calculer m=cad mod n. Le système RSA peut également être utilisé pour générer des signatures électroniques. 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 étant la génération de la clef RSA, en utilisant le méthode décrite dans la première partie du système RSA décrite précédemment i La deuxième partie étant 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 jn. pour obtenir la chaîne de caractère g (M), et à appliquer le procédé de déchiffrement de la troisième partie du système RSA décrit précédemment. Ainsi, seule la personne possédant la clef privée peut générer la signature ; La troisième partie étant 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 pour obtenir la chaîne de caractère jn. (M), à appliquer à la signature s le procédé de chiffrement décrit dans la deuxième partie du système RSA, et à vérifier que le résultat obtenu est égal à ) J. (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 p. 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#l : 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 des deux procédés d'encodage cités précédemment est qu'ils nécessitent l'utilisation d'une fonction de hachage. Une fonction de hachage est une fonction prenant en entrée un message de taille arbitrairement longue et renvoyant en sortie une chaîne de caractère de taille fixe. L'inconvénient est qu'il n'est pas possible dans l'état actuel des connaissances de prouver rigoureusement la sécurité de telles fonctions de hachage. Il n'est donc pas possible de prouver rigoureusement la sécurité des deux procédés d'encodage cités précédemment. Le procédé de l'invention consiste en une méthode permettant de réaliser une fonction d'encodage prenant en entrée des messages arbitrairement longs, à partir d'une fonction d'encodage prenant en entrée des messages de taille limitée. Le procédé de l'invention utilise exclusivement des opérations de type arithmétique, pour lesquelles il est possible de prouver rigoureusement la sécurité. L'invention comprend 2 procédés distincts réalisant une fonction d'encodage, ladite fonction d'encodage prenant en entrée des messages arbitrairement longs, à partir d'une fonction d'encodage prenant en entrée des messages de taille limitée. Le premier procédé de l'invention utilise un module RSA unique N tel que défini dans la première partie du système RSA décrit précédemment. Le premier procédé de l'invention utilise une fonction d'encodage jjL prenant en entrée un message de taille limitée à k+1 bits, k étant un paramètre entier, et renvoyant en sortie une chaîne de caractère de taille exactement k bits. Le premier procédé de l'invention prend en entrée un paramètre entier a compris entre 0 et k-1. Le premier procédé de l'invention consiste à définir une nouvelle fonction d'encodage'prenant en entrée un message de taille au plus (2axa) * (k-a) bits et renvoyant en sortie un message de taille k bits. Par une application répétée du premier procédé de l'invention, il est ainsi possible de construire une fonction d'encodage prenant en entrée des messages de taille arbitrairement longue. Le premier procédé de l'invention consiste en les 4 étapes suivantes : 1) Séparer le message en blocks de taille k-a bits. Le message est noté m=m [l] jjm [2] )..) jm [r] où r est le nombre de blocks. 2) Initialiser à 1 une variable entière b. 3) Pour i allant de 1 à r, calculer le résultat de la fonction appliquée à la chaîne de bits constituée par la concaténation du bit 0, du compteur i représenté par une chaîne de a bits et du block m [i], et multiplier ledit résultat par la variable b, le résultat de la multiplication étant stocké dans la variable b, ladite multiplication s'opérant modulo N ; 4) Appliquer la fonction à la chaîne de bits constituée par la concaténation du bit 1 et de la variable b, et renvoyer en sortie le résultat. Le deuxième procédé de l'invention consiste à utiliser deux modules distincts NI et N2, lesdits modules étant tels que définis dans la première partie du système RSA décrit précédemment. Le deuxième procédé de l'invention utilise deux fonctions d'encodage 1 et 2 prenant en entrée un message de taille kl et k2, respectivement, et renvoyant en sortie un message de taille kl'et k2', respectivement. Le deuxième procédé de l'invention prend en entrée un paramètre entier a compris entre 0 et k-1. Le deuxième procédé de l'invention consiste à définir une nouvelle fonction d'encodage' prenant en entrée un message de taille au plus (2^a) * (kl-a) bits et renvoyant en sortie un message de taille k2'bits. Par une application répétée du deuxième procédé de l'invention, il est ainsi possible de construire une fonction d'encodage prenant en entrée des messages de taille arbitrairement longue. Le deuxième procédé de l'invention consiste en les 4 étapes suivantes : 1) Séparer le message en blocks de taille kl- a bits. Le message est noté m=m [l] | | m [2] | | ## | | m [r] où r est le nombre de blocks. 2) Initialiser à 1 une variable entière b. 3) Pour i allant de 1 à r, calculer le résultat de la fonction ju. l appliquée à la chaîne de bits constituée par la concaténation du compteur i représenté par une chaîne de a bits et du block m [i], et multiplier ledit résultat par la variable b, le résultat de la multiplication étant stocké dans la variable b, ladite multiplication s'effectuant modulo NI. 4) Appliquer la fonction zu à la chaîne de bits constituée de la variable b, et renvoyer en sortie le résultat. Par le procédé précédant est défini une fonction d'encodage ' prenant en entrée un message de taille (2axa) * (kl-a) et renvoyant en sortie un message de taille k2'bits. Lors de l'application des procédés de génération de signature et de vérification de signature basés sur RSA précédemment décrits, les calculs s'effectuent en utilisant le module RSA N2. L'avantage du deuxième procédé de l'invention sur le premier procédé de l'invention est qu'il offre plus de souplesse dans le choix de la fonction d'encodage . En effet, dans le premier procédé, la contrainte était que JL est une fonction d'encodage de k+l bits vers k bits. Cette contrainte n'existe pas dans le deuxième procédé de l'invention. REVENDICATIONS 1. Procédé utilisant un module RSA N, ledit procédé utilisant une fonction d'encodage . prenant en entrée un message de taille limitée à k+l bits, k étant un paramètre entier, et renvoyant en sortie une chaîne de caractère de taille exactement k bits, ledit procédé prenant en entrée un paramètre entier a compris entre 0 et k-1, ledit procédé consistant à définir une nouvelle fonction d'encodage'prenant en entrée un message de taille au plus (2axa) * (k-a) bits et renvoyant en sortie un message de taille k bits, ledit procédé caractérisé en ce qu'il comporte les 4 étapes suivantes : 1) Séparation du message en blocks de taille k-a bits, le message étant noté m=m [l] j jm [2].. j m [r] où r est le nombre de blocks. 2) Initialisation à 1 d'une variable entière b. 3) Pour i allant de 1 à r, calcul du résultat de la fonction appliquée à la chaîne de bits constituée par la concaténation du bit 0, du compteur i représenté par une chaîne de a bits et du block m [i], et multiplication dudit résultat par la variable b, le résultat de la multiplication étant stocké dans la variable b, ladite multiplication s'opérant modulo N. 4) Application de la fonction jn à la chaîne de bits constituée par la concaténation du bit 1 et de la variable b, et renvoi en sortie le résultat. 2. Procédé d'encodage selon la revendication 1 prenant en entrée un message de taille arbitrairement longue, caractérisé en ce que le procédé de la revendication 1 est répété plusieurs fois. 3. Procédé utilisant deux modules RSA distincts N1 et N2, ledit procédé utilisant deux fonctions d'encodage jn. 1 et 2 prenant en entrée un message de taille kl et k2, respectivement, et renvoyant en sortie un message de taille kl'et k2', respectivement, ledit procédé prenant en entrée un paramètre entier a compris entre 0 et k-1, ledit procédé consistant à définir une nouvelle fonction d'encodage'prenant en entrée un message de taille au plus 2^a* (kl-a) bits et renvoyant en sortie un message de taille k2'bits, ledit procédé étant caractérisé en ce qu'il comprend les 4 étapes suivantes : 1) Séparation du message en blocks de taille kl-a bits, le message étant noté m=m [l] jm [2] .. m [r] où r est le nombre de blocks. 2) Initialisation à 1 la variable entière b. 3) Pour i allant de 1 à r, calcul du résultat de la fonction p1 appliqué à la chaîne de bits constituée par la concaténation du compteur i représenté par une chaîne de a bits et du block m [i], et multiplication dudit résultat par la variable b, le résultat de la multiplication étant stocké dans la variable b, ladite multiplication s'effectuant modulo NI. 4) Application de la fonction ju. 2 à la chaîne de bits constituée de la variable b, et renvoie en sortie du résultat. 4. Procédé d'encodage selon la revendication 3, caractérisé en ce que la génération et la vérification de la signature s'effectuent en utilisant le module RSA N2 tel que défini dans la revendication 3. 5. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce qu'il est utilisé dans le cadre d'un objet portable de type carte à puce.