Brevet FR2842968A1 — publié le 20040130

à; PROCEDE D'OBTENTION D'UNE SIGNATURE ELECTRONIQUE POSSEDANT UNE GARANTIE SUR SA SECURITE La présente invention se rapporte à un procédé de signature électronique d'un message présentant une forte garantie quant à la sécurité de la signature, et est plus particulièrement destinée à s'appliquer aux schémas de signature basés sur un procédé d'encodage de message de type hachage (" hash-and-sign " dans la littérature anglo-saxonne) et incluant notamment les standards PKCS#1 vl.5 et ISO 9796-2 des schémas de signature RSA ou Rabin. 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. Autrement dit, les clefs de chiffrement et de déchiffrement sont non reconstructibles l'une à partir de l'autre. 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é, d'o un premier avantage, celui de la confidentialité. Un autre avantage de la cryptographie à clé publique est qu'elle 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. Ce système de chiffrement 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 principe du système de chiffrement RSA est le suivant. Il peut être divisé en trois parties distinctes qui sont: 1) 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 f=(p-l)(q-l); 3) Sélectionner aléatoirement un entier e, l exposant de chiffrement et exposant de déchiffrement. L'entier n est appelé le module RSA. La seconde partie consiste en le chiffrement d'un message clair noté m au moyen d'un algorithme, avec l 3 2842968 C=me mod n. La troisième partie consiste en le 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 1 m=cd mod n. Le système Rabin est semblable au système RSA, la différence étant que l'exposant public de chiffrement est fixé à 2, ou plus généralement un entier pair. Les systèmes RSA ou Rabin peuvent également être utilisés 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 ou Rabin, en utilisant la méthode décrite dans la première partie du système RSA ou Rabin décrite précédemment; - 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 f pour obtenir la chaîne de caractère f(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 f pour obtenir la chaîne de caractère f(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 à f(M). Dans ce cas, la signature s du message M est valide, et dans le cas contraire elle est fausse. Une orientation importante dans le domaine des signatures électroniques consiste à prouver que le schéma de signature est sr. Un schéma de signature est dit sr si le temps de calcul nécessaire pour forger une signature est hors de portée avec les moyens de calcul disponibles. La sécurité du schéma de signature basé sur le système RSA résulte du fait d'une part, de la non divulgation des nombres p et q intervenant dans la décomposition du module n et, d'autre part, de la difficulté pratique de la factorisation de n, les algorithmes actuels ayant un temps de calcul prohibitif en pratique quand la taille du module n est suffisamment grande (512 à 1024 bits). Sans l'encodage effectué préalablement à la signature du message, on peut toutefois montrer qu'il est possible à une personne disposant de messages signés, de forger des signatures en appliquant des propriétés mathématiques particulières, notamment des propriétés multiplicatives sur les messages signés. Par exemple, selon le principe exposé plus haut du système de chiffrement RSA, soient un premier message m1 et un second message m2 et les deux signatures correspondantes, respectivement mld et m2d modulo n. La multiplication de ces deux signatures donne le résultat suivant d d Mld * M2= (ml.m2)d modulo n Ainsi, à partir de la signature d'un message m1 et m2, on peut trouver la signature du message m1.m2 et donc forger une signature pour un tel message. L'encodage appliqué au message préalablement à sa signature proprement dite joue donc le rôle de - mécanisme de protection contre cette faille en rendant difficile l'application de propriétés multiplicatives de telles sortes et permet par conséquent de renforcer la sécurité du schéma de signature. Il existe de nombreux procédés d'encodage utilisant différentes fonctions d'encodage. Certain de ces procédés ont toutefois été cassés. En conséquence, malgré l'encodage préalable du message, on a pu démontrer, dès lors qu'un certain nombre de correspondances messages clairs/messages signés était disponible, qu'il était possible de trouver des propriétés multiplicatives et donc de forger des signatures. Une pratique courante pour les schémas de signature avec le système RSA ou Rabin consiste tout d'abord à hacher le message par l'application d'une fonction de hachage H de façon à obtenir un condensé du message, à remplir le condensé du message en concaténant des blocs de données fixes ou dépendants du message jusqu'à ce que la taille de l'encodé du message soit égale à la taille du module RSA n, puis à déchiffrer le résultat de l'encodage avec la clef de déchiffrement privé. Ce principe dit " hash-and-sign " dans la littérature anglo-saxonne est à la base de nombreux schémas de signature. Parmi ceux-ci, on trouve le schéma FDH, acronyme pour l'expression anglo-saxonne " Full Domain Hash ". Dans ce schéma de signature, le condensé du message, obtenu préalablement à la signature par l'application de la fonction de hachage, fait directement la pleine taille, soit la taille du module n. Ce schéma possède une preuve mathématiquement prouvée quant à la sécurité de la signature contre des attaques et garantit donc qu'il est pratiquement impossible de forger une signature à partir de ce schéma. Cependant, d'autres standards, basés sur le principe " Hash-and-Sign ", apparus antérieurement au schéma FDH, ne possèdent pas de preuve de sécurité. Aussi, on ne peut pas avoir totalement confiance dans l'utilisation de ces standards puisque l'impossibilité à forger une signature à partir de tels standards n'est pas garantie. Un exemple est le standard de signature "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 concerne le standard de signature "RSA Laboboratories, PKCS#1 version 1.5". On peut encore citer le standard SSL 3.02, et le standard ANSI x9.31. Ces standards concernent en fait des schémas de signature dits à hachage partiel dans le sens o la taille du condensé obtenu par l'application de la fonction de hachage H est inférieure à la taille du module RSA n et o il est nécessaire de concaténer au condensé des blocs de données indépendants ou qui dépendent du message lui-même. Dans les schémas de signature à hachage partiel, la taille de la fonction de hachage H est donc simplement une fraction de la taille du module n. Ces standards de signature permettent plus particulièrement de signer des messages de taille arbitrairement longue et sont très largement utilisés dans de nombreuses applications commerciales. Aussi, il existe un besoin de renforcer le niveau de sécurité de ces standards. De plus, en ce qui concerne le standard ISO 97962, il a été montré qu'il existe une attaque possible 7 2842968 contre ce standard si la taille de la fonction de hachage est suffisamment petite. Aussi, la présente invention a pour but de déterminer un schéma de signature de type à hachage partiel basé sur le système RSA ou Rabin, qui pallie les inconvénients évoqués ci-dessus, à savoir qui possède un niveau de sécurité prouvé maximal, garantissant ainsi l'impossibilité de forger une signature à partir d'un tel schéma de signature. A cette fin, l'invention concerne un procédé d'obtention d'une signature électronique d'un message possédant une garantie sur sa sécurité, le schéma de signature électronique étant basé sur un encodage dudit message associé à un algorithme de chiffrement à clef publique, ledit procédé comprenant les étapes suivantes consistant à - générer une clef publique et une clef privée correspondante, ladite clef publique étant constituée d'un nombre n très grand, produit de deux nombres premiers p et q de même taille, et d'un exposant de chiffrement e choisi aléatoirement dans l'intervalle [2, (p-l).(q-l)-l], ladite clef privée étant constituée d'un exposant de déchiffrement d tel que e.d = 1 modulo (p-l).(q-1); - encoder le message à signer en calculant tout d'abord un condensé dudit message par l'application d'une fonction de hachage, puis en remplissant ledit condensé en concaténant un ensemble de blocs de données de telle sorte que la longueur du message encodé soit égale à la taille du nombre n; déchiffrer le message encodé en utilisant la clef privée; ledit procédé étant caractérisé en ce que l'exposant de chiffrement e est égal à 2 et en ce que la taille du y condensé obtenu par l'application audit message de la fonction de hachage est égale à au moins deux tiers de la taille du nombre n. On a vu que les schémas de signature de type à hachage partiel basé sur RSA, notamment les standards ISO 9796-2, PKCS#l v.1,5, SSL-3.02 ou encore ANSI x9.31 ne présentent pas un niveau de sécurité maximale face à un attaquant ayant la possibilité d'obtenir la signature de certains messages. En effet, il existe de nombreuses situations pratiques dans lesquelles un attaquant peut obtenir la signature de messages de son choix. Si l'attaquant demande à un signataire un ensemble de signatures correspondants à un ensemble de messages choisis m1.. 15. mk, disposant alors de l'ensemble des messages choisis MI... mk et de leur signature associée, il peut essayer de forger une signature pour un message mk+1, bien choisi, différent des messages m1 à Mk, et fournir de cette façon, sans connaître la clef privée, une signature valide pour un message bien choisi. Ainsi, à partir de l'obtention de signatures associées aux messages de son choix, l'attaquant peut essayer de fournir une forge valide, soit un couple message/signature tel que leur vérification par la clef publique du schéma de signature est valide alors que la signature du message en question n'a jamais été requise par l'attaquant. La preuve de la sécurité des schémas de signature évoqués plus haut repose sur la mise en oeuvre d'un modèle mathématique qui consiste en la suite d'étapes suivantes: - répondre aux requêtes de hachage et aux requêtes de signature d'un attaquant qui, à l'aide des données de messages condensés et de messages signés, renvoie y alors une forge, soit une signature valide d'un message dont il n'a pas demandé la signature auparavant, et le modèle, à partir de la clef publique (n,e), utilise cette forge renvoyée par l'attaquant pour résoudre le problème de la factorisation du module n qui est à la base de la sécurité du schéma de signature basé sur RSA. Ainsi, la preuve consiste à montrer que si il existe un attaquant qui peut forger des signatures, on peut l'utiliser pour résoudre le problème mathématique de la factorisation de n qui est à la base de la sécurité du système RSA. A contrario, si on suppose qu'il est difficile de factoriser n, il est impossible qu'il existe un attaquant. Par conséquent, la preuve de sécurité signifie que, si on suppose qu'il est difficile de factoriser n, alors le schéma de signature est sr. A partir de là, l'invention consiste en fait à garantir cette preuve de sécurité pour tous schémas de signature de type à hachage partiel basé sur RSA, qui jusqu'alors ne présentaient pas un niveau de sécurité maximal, et notamment pour les standards de signature PKCS#l vl.5, ISO 9796-2, SSL 3.02 ou ANSI x9.31. Pour ce faire, le procédé selon l'invention consiste à utiliser les procédés d'encodage prévus par ces standards, mais avec une taille de hachage supérieure à celle habituellement prévue. La preuve de sécurité maximale pour les schémas de signature précités est donc subordonnée à la définition d'un cas particulier dans la mise en òuvre de ces schémas de signature et, plus précisément, on montre que les schémas de signature à hachage partiel possèdent un niveau de sécurité maximal pour une valeur de l'exposant de chiffrement e restreinte à 2 si la taille de la fonction de hachage est supérieure à au moins deux tiers de la taille du module n, en supposant qu'il est difficile de factoriser n. Cette taille minimum imposée au condensé obtenu par l'application de la fonction de hachage H au message est supérieure à la taille habituellement recommandée dans les standards de signature PKCS#l vl.5, ISO 9796-2, SSL 3.02 ou ANSI x9.31. Ce cas particulier défini par la présente invention, permettant de garantir un niveau de sécurité maximal pour les schémas de signature à hachage partiel, revient en fait à fournir un schéma de signature basé sur le système Rabin, puisque l'on impose la valeur 2 à l'exposant de chiffrement e. Soit l'exemple se rapportant à l'application du standard de signature PKCS#l vl.5, qui définit un schéma de signature à hachage partiel, kt(m) étant l'encodé du message m. Dans ce qui suit, il est entendu que toutes les abréviations de lettres ou lettres et chiffres qui suivent sont des nombres entiers équivalents à des chaînes de bits. jtt(m)=0001,61 IFFFF16...FFFF161 100161 IcsHA I H(m) Le symbole | | représente la concaténation de deux chaînes de bits respectives. L'indice 16 signifie une notation hexadécimale. La fonction de hachage H est réalisée dans cette représentation de remplissage par l'algorithme SHA, soit H(m) = SHA(m). CSHA étant une constante telle que csA = 3021300906052BOE03021AO500041416 Selon le standard PKCS#l vl.5, l'encodé pt(m) peut également être représenté de la façon qui suit KL(m)=0001161 FFFF16...FFFF16 100161 I CMD5I IH(m) La fonction de hachage H est alors réalisée dans cette représentation de remplissage par l'algorithme MD5, soit H(m) = MD5(m). CMD5 étant une constante telle que CMD5 = 3020300C6082A864886F70DO2050500041016 Le standard PKCS#1 vl.5 n'a pas été conçu pour fonctionner avec le système de chiffrement Rabin, o l'exposant de chiffrement e est égal à deux. Cependant, en remplaçant le dernier demi-octet de H(m) par 616, on obtient un procédé d'encodage compatible avec le système de chiffrement Rabin. Le standard PKCS#l vl.5 possède alors un niveau de sécurité prouvé maximal si la taille de la fonction de hachage H(m) est supérieure à au moins deux tiers de la taille du module n (typiquement 512 ou 1024 bits), ce qui est bien supérieur à la taille de 128 ou 160 bits qui est habituellement recommandé pour ce standard. La même analyse s'applique aux standards de signature ISO 9796-2, SSL-3. 02 ou ANSI x9.31 et un niveau de sécurité maximal est atteint pour ces standards si la taille de la fonction de hachage est supérieure à au moins deux tiers de la taille du module n. L'invention est particulièrement avantageuse puisqu'elle permet d'atteindre un niveau maximal de sécurité pour un schéma de signature, tout en permettant de continuer à utiliser les standards les plus communément mis en oeuvre dans de telles applications. L'invention est de plus très facile à implémenter puisqu'il suffit d'augmenter la taille de sortie de la fonction de hachage appliquée au message jusqu'à atteindre la valeur minimum prévue par l'invention, à savoir au moins deux tiers de la taille du module n. L'invention est applicable à de nombreux standards, parmi lesquels ceux déjà cités PKCS#l vl.5, ISO 9796-2, SSL 3.02 ou ANSI x9.31, sans pour autant que cette liste soit limitative et est plus généralement applicable à tout schéma de signature de type à hachage partiel basé sur le système RSA ou Rabin. Enfin, l'invention est facilement utilisable dans un dispositif électronique de type carte à puce ou analogue. 13 2842968 REVENDICATIONS 1. Procédé d'obtention d'une signature électronique d'un message m possédant une garantie sur sa sécurité, le schéma de signature électronique étant basé sur un encodage dudit message m associé à un algorithme de chiffrement à clef publique, ledit procédé comprenant les étapes suivantes consistant à: - générer une clef publique et une clef privée correspondante, ladite clef publique étant constituée d'un nombre n très grand, produit de deux nombres premiers p et q de même taille, et d'un exposant de chiffrement e choisi aléatoirement dans l'intervalle [2, (p-l).(q-l)-l, ladite clef privée étant constituée d'un exposant de déchiffrement d tel que e.d = 1 modulo (p-l).(q-1); - encoder le message à signer en calculant tout d'abord un condensé dudit message par l'application d'une fonction de hachage H(m), puis en remplissant ledit condensé en concaténant un ensemble de blocs de données dépendant ou indépendant dudit message m de telle sorte que la longueur du message encodé soit égale à la taille du nombre n; - déchiffrer le message encodé en utilisant la clef privée; ledit procédé étant caractérisé en ce que l'exposant de chiffrement e est égal à 2 et en ce que la taille du condensé obtenu par l'application audit message m de la fonction de hachage H(m) est égale à au moins deux tiers de la taille du nombre n. 2. Procédé selon la revendication 1, caractérisé en ce que le schéma de signature est mis en òuvre selon le standard PKCS#1 vl.5. i4 2842968 > 14 3. Procédé selon la revendication 1, caractérisé en ce que le schéma de signature est mis en oeuvre selon le standard ISO 9796-2 4. Procédé selon la revendication 1, caractérisé en ce que le schéma de signature est mis en oeuvre selon le standard SSL-3.02. 5. Procédé selon la revendication 1, caractérisé en ce que le schéma de signature est mis en oeuvre selon le standard ANSI x9.31. 6. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que le procédé est utilisé dans un dispositif électronique de type carte à puce.