Brevet FR2793366A1 — publié le 20001110

Une signature numérique est un élément d'information qui relie le créateur à un message. Des algorithmes de signature numérique, ou création de signature, sont des procédés de construction de signature. Des algorithmes de vérifications sont des procédés de contrôle et de vérification de l'authenticité d'une signature. Une méthode ou mécanisme de signature numérique consiste en un algorithme de création de signature et un algorithme de vérification de signature. Si l'algorithme de vérification exige le message comme entrée, la signature numérique est appelée une signature numérique à appendice. S'il n'exige pas le message, cette signature est appelée une signature numérique à récupération de message. L'exemple de méthode de signature numérique le mieux connu vient du système de chiffrage à clé publique RSA. Il donne une signature numérique à récupération de message. Nyberg et Rueppel ont récemment montré que la classe des signatures numériques appelée communément une méthode du type E1 Gamal peut être modifiée pour donner la propriété de récupération de message. L'un des inconvénients de toutes les méthodes connues de signatures numériques à récupération de message est que le message doit contenir une redondance suffisante pour éviter une attaque de contre- façon existentielle. Par exemple, la norme ISO/IEC 9796 est une norme internationale dont le but est de prescrire la manière dont des messages devraient être formés avant d'être signés par la technique RSA. Elle permet au maximum à la moitié des bits des messages d'être des bits d'information; le reste est réservé pour la redondance. Par conséquent, il faut une largeur de bande accrue pour traiter les messages. 2 2793366 C'est un but de la présente invention que de fournir une méthode de signature dans laquelle la redondance nécessaire est réduite. En termes généraux, la présente invention fournit une composante de signature pour un message qui utilise un hachage du message. Le message est combiné mathématiquement avec la clé privée du signataire et il peut donc être récupéré en utilisant la clé publique du signataire. Le récepteur reçoit le hachage du message et peut le comparer au hachage correspondant du message récupéré afin d'authentifier la signature. Selon un premier aspect, l'invention fournit un procédé d'authentification d'une signature d'un message m caractérisé en ce qu'il comprend les étapes consistant à: (a) déterminer une représentation h(m) dudit message en appliquant une fonction univoque et en dériver une première composante de signature, (b) calculer une fonction liée mathématiquement à ladite représentation h(m) dudit message, (c) appliquer ladite fonction audit message pour obtenir une deuxième composante de signature, liée audit signataire, (d) envoyer à un récepteur lesdites composantes de signature, (e) récupérer à partir de ladite deuxième composante un message m', (f) calculer une valeur de m' en appliquant ladite fonction univoque, et (g) déterminer si ladite valeur de m' et ladite représentation h(m) incorporée dans ladite première composante de signature sont identiques, une telle identité indiquant une signature authentique dudit message. 3 2793366 Ladite fonction univoque peut être une fonction de hachage cryptographique, et en particulier ladite fonction de hachage peut alors être une fonction de hachage SHA-1. Selon un deuxième aspect, l'invention fournit un procédé d'authentification d'une signature d'un message m caractérisé en ce qu'il comprend les étapes consistant à: (a) déterminer un hachage h(m) dudit message en appliquant une fonction de hachage et en dériver une première composante de signature em, (b) calculer une fonction dm liée mathématiquement audit hachage dudit message, telle que em dm = 1 mod (A(n)), (c) appliquer ladite fonction dm audit message pour obtenir une deuxième composante de signature Sm, liée audit signataire, telle que Sm = m m mod (\(n)), (d) envoyer à un récepteur lesdites composantes de signature (em, Sm), (e) récupérer à partir de ladite deuxième composante Sm un message m' o Sm m = m', (f) calculer une valeur de hachage de m' en appliquant ladite fonction de hachage, et (g) déterminer si ladite valeur de hachage de m' et ledit hachage h(m) incorporé dans ladite première composante de signature sont identiques, une telle identité indiquant une signature authentique dudit message. Selon un troisième aspect, l'invention fournit un procédé d'authentification d'une signature d'un message m caractérisé en ce qu'il comprend les étapes consistant à: (a) déterminer un hachage h(m) dudit message en appliquant une fonction de hachage et en dériver une première composante de signature, 4 2793366 (b) sélectionner un entier aléatoire k e (1, 2, * q - 1}, c) calculer une troisième composante de signature r telle que r = m ak (mod p), o a est un générateur d'un groupe cyclique G d'ordre q dans Zpq, et o q divise p - 1, (d) calculer une deuxième composante sm de signature liée mathématiquement audit hachage dudit message, telle que sm = arh(m) + k mod q, a étant une clé privée dudit signataire, (e) envoyer à un récepteur lesdites composantes de signature, (f) récupérer à partir desdites deuxième et troisième composantes de signature un message m', (g) calculer une valeur de m' en appliquant ladite fonction de hachage, et (h) déterminer si ladite valeur de hachage de m' et ladite représentation h(m) incorporée dans ladite première composante de signature sont identiques, une telle identité indiquant une signature authentique dudit message. Selon un quatrième aspect, l'invention fournit un procédé d'authentification d'une signature d'un message m caractérisé en ce qu'il comprend les étapes consistant à: (a) déterminer un hachage h(m) dudit message en appliquant une fonction de hachage et en dériver une première composante de signature, (b) sélectionner un entier aléatoire k e (1, 2, 30..q - 1), c) calculer une troisième composante de signature fonction r telle que r = m + x (mod n), o x est une coordonnée d'un point kP d'une courbe elliptique définie par y2 + xy = x3 + ax2 + b d'ordre n, 2793366 (d) calculer une deuxième composante sm de signature liée mathématiquement audit hachage dudit message, telle que sm = drh(m) + k mod q, d étant une clé privée de signature, (e) envoyer à un récepteur lesdites composantes de signature, (f) récupérer à partir desdites deuxième et troisième composantes de signature un message m', (g) calculer une valeur de m' en appliquant ladite fonction de hachage, et (h) déterminer si ladite valeur de hachage de m' et ladite représentation h(m) incorporée dans ladite première composante de signature sont identiques, une telle identité indiquant une signature authentique dudit message. Selon un cinquième aspect, l'invention réalise un support lisible par un ordinateur dont le contenu amène un système d'ordinateur à engendrer une signature d'un message m, caractérisé en ce que le système d'ordinateur est pourvu d'un programme de génération de signature, comprenant les étapes consistant à: (a) déterminer une représentation h(m) dudit message en appliquant une fonction univoque et en dériver une première composante de signature, (b) calculer une fonction liée mathématiquement à ladite représentation h(m) dudit message, (c) appliquer ladite fonction audit message pour obtenir une deuxième composante de signature, liée audit signataire, (d) envoyer à un récepteur lesdites composantes de signature, lesdites composantes de signature incluant ledit message et une composante dépendant du message. Ce support peut inclure un programme de vérification de signature. 6 2793366 Dans ce cas, ledit programme de vérification de signature peut comprendre les étapes consistant à: (a) récupérer à partir de ladite deuxième composante un message m', (b) calculer une valeur de m' en appliquant ladite fonction univoque, et (c) déterminer si ladite valeur de m' et ladite représentation h(m) incorporée dans ladite première composante de signature sont identiques, une telle identité indiquant une signature authentique dudit message. De telles nouvelles classes de signatures numériques réalisent une récupération de message et possèdent la particularité nouvelle qu'une redondance minimale est nécessaire dans le message à signer. Les économies de largeur de bande pourraient être très utiles dans certaines situations. Par exemple, pour une tierce partie sécurisée, qui peut être désignée aussi par les initiales TTP du terme anglo-saxon trusted third party, qui crée des certificats pour des entités dans un réseau, des exigences de largeur de bande posent un problème. Une tierce partie sécurisée qui utilise une méthode RSA à dimension de module de 1024 bits pour signer des messages de l'ordre de 1000 bits exige une largeur de bande qui dépasse 2000 bits. Un mode de réalisation décrit ci-dessous fournit une méthode qui n'exigerait qu'un petit nombre de bits en plus de cette dimension de message. On va maintenant décrire à titre d'exemple seulement la présente invention en se référant aux dessins annexés dans lesquels: la Figure 1 est une représentation schématique d'un système de communication de données. En se référant donc à la Figure 1, une paire de correspondants 10, 12, appelés le correspondant A et le correspondant B échangent une information par un 7 2793366 canal 14 de communication. Une unité de cryptographie 16, 18 est interposée entre chacun des correspondants , 12 et le canal 14. Chacune des unités cryptographiques 16, 18 peut prendre un message transporté entre chaque unité 16, 18 et son correspondant respectif 10, 12 et engendrer une signature associée au message et au correspondant à transporter sur le canal 14. La signature peut être engendrée de nombreuses manières qui dépendent des principes sous-jacents de cryptographie utilisés. On étudiera successivement des procédés basés sur une factorisation d'entiers puis des procédés basés sur une méthode de signature Rabin, puis des procédés basés sur un problème de log discret dont le procédé de Nyberg-Rueppel et finalement des procédés applicables à des courbes elliptiques, par exemple ici aussi une méthode de Nyberg- Rueppel. Dans chaque cas, on définit un algorithme de génération de signature et un algorithme de vérification de signature. Les abréviations ppcm et pgcd désignent le plus petit commun multiple et le plus grand commun diviseur respectivement. Dans le cas de procédés basés sur une factorisation d'entiers, soient p et q des nombres premiers et n = pq tel que le problème de factorisation d'entiers pour n ne puisse pas être traité. Le procédé à décrire exige une fonction de hachage cryptographique h univoque qui applique des chaines de bits d'une longueur arbitraire à une chaine de bits d'une longueur t. La valeur de t est typiquement de 64 ou 128 bits. Le message à signer peut être considéré comme des entiers dans Zn. Algorithme 1. Génération de signature. Supposons que l'entité A possède la clé publique n et la clé privée > (n) = ppcm (p - 1, q - 1). Afin de 8 2793366 signer un message m E Zn0 l'entité A met en oeuvre les étapes suivantes: (a) Traiter m comme une chaîne de bits et calculer la valeur de hachage em = h(m). (b) Utiliser l'algorithme euclidien étendu pour calculer un entier dm tel que dmem = 1 (mod X(n)), o la chaine de bits em est maintenant considérée comme la représentation binaire d'un entier. (c) Calculer sm = mi m (mod n). (d) La signature pour le message m est (sm, em). Algorithme 2. Vérification de signature. Une entité B peut vérifier la signature (sm, em) en mettant en oeuvre les étapes suivantes: (a) chercher la clé publique n de l'entité A. (b) Calculer m' = sm m (mod n) (c) vérifier que h (m') = em. (d) En cas de succès du processus de vérification de (c), m' est le message récupéré. Pour que l'algorithme de signature fonctionne, il doit être vrai que le pgcd (em, X(n)) = 1. Ceci peut être garanti par la simple modification qui suit. Soit c une chaine de 1 bits. Au lieu d'utiliser h(m), on utilise em = h(m)II c o Il signifie un chaînage et c est choisi d'une manière telle que l'entier représenté par em est premier par rapport à >(n) (c'est-à-dire que pgcd (em. \(n)) = 1). Pour y parvenir, une manière préférée consisterait à sélectionner les nombres premiers p et q de façon telle que p - 1 et q - 1 ne contiennent aucun petit facteur premier impair et à sélectionner c comme bit 1 (c'est-à-dire 1 = 1). Il s'en suit alors que em = h(m) Il c est impair et que la probabilité que pgcd (em, \(n)) = 1 est très élevée. Pour l'algorithme de vérification, à l'étape (c), au lieu de vérifier que h(m') = em, B vérifie que h(m') est égal aux t premiers bits du em. 9 2793366 La signature du message m contient (t + log2n) bits ou (t + 1 + log2n) bit si l'on utilise la modification décrite ci-dessus. Il n'est pas nécessaire que le mécanisme de signature possède la propriété d'homomorphisme que possède la signature RSA. Puisque, pour deux messages m et m' à même valeur de hachage, la valeur de hachage du produit de m et m' peut être différente, une contre-façon existentielle par multiplication de signatures est en général impossible puisque la probabilité que h(m) = h(m') = h(mm') est faible. La probabilité qu'un adversaire puisse deviner une paire (sm, em) qui est une signature d'un certain m est 1 / 2t. Le travail exigé par la génération de signature selon le nouveau procédé n'est que légèrement supérieur à celui d'une génération de signature RSA sur le même module, en raison de l'application de l'algorithme euclidien et de la fonction de hachage. Lorsque l'exposant public de RSA soit faible, le travail exigé par une vérification de signature est plus important, mais de façon non significative, que pour une vérification de RSA; dans le cas contraire, le nouveau procédé est supérieur. Une autre modification de la méthode de factorisation d'entiers est une modification de la méthode de signature RSA. Supposons que la clé publique de l'entité A est n, e et que sa clé privée est d, o ed = 1 (mod n). Algorithme 3. Génération de signature Pour signer un message m, l'entité A doit mettre en oeuvre les étapes suivantes: (a) Traiter m comme une chaîne de bit et calculer la valeur de hachage h(m) o h(m) peut être une fonction univoque quelconque. (b) Calculer sm = (m h(m))d (mod n). (c) La signature du message m est (sm, h(m)). - Algorithme 4. Vérification de signature Une entité B peut vérifier la signature (sm, h(m)) en mettant en oeuvre les étapes suivantes: (a) Chercher la clé publique e, n de l'entité A (b) calculer m' = sm m (h(m))-1 (mod n) (c) vérifier que h(m') = h(m). (d) En cas de succès du processus de vérification selon (c), m est le message récupéré. On va maintenant décrire des procédés basés sur la méthode de signature de Rabin. Une variante de méthode de signature est la méthode dite de Rabin dont la sécurité provient de la difficulté à trouver des racines carrées, modulo un nombre composite. Soit n = pq un produit de deux entiers o p E 3 (mod 8) et q - ?(mod 8). Soit t c )/2 ppcm (p - 1, q - 1) c (p - 1) (q - 1) / 4. Il est facile de montrer que mt = 1 (mod n) dès pourvu que m soit un résidu quadratique modulo n et que mt = -1 (mod n), pourvu que m soit un non résidu quadratique modulo p et modulo q, respectivement. Soit Jm (m/n) le symbole de Jacobi, Qn l'ensemble de résidus quadratiques modulo n, et m est inversible mod n, et on détermine les faits suivante: Fait 1- si Jm 1, alors mt l(mod n) sim ( Qn - 1 (mod n) si m ' Qn Fait 2. si Jm -1, alors Jm/2 = 1. Fait 3. supposons que e est pair et que d satisfait à ed 5 1 (mod t). Si Jm = 1, alors med m (mod n) si m c Qn -m (mod n) si m e Qn. Le Fait 1 et le Fait 2 sont banaux. Pour le Fait 3, on peut trouver un entier impair x tel que ed = 1 + xt. Par conséquent, med c ml+ xt = (mt)Xm 1-m (mod n) si n ( Qn (-l)Xm (mod n) si m Qn' 11 2793366 Algorithme 5. Génération de signature pour la méthode Rabin modifiée. Supposons que la clé publique de l'entité A est n et sa clé privée t. Afin de signer un message m em = 4 h(m) + 2. (b) Utiliser l'algorithme euclidien étendu pour calculer un entier dm tel que dm em = 1 (mod t), o la chaîne de bits em est maintenant considérée comme la représentation binaire d'un entier. (c) Calculer J8m + 2 = (8m + 2) / 2 et déterminer un entier M par la règle suivante: M = 8m + 2 si J8m + 2 = 1 M = 4m + 1 si J8m + 2 = -1 (d) Calculer sm = M m (mod n). (e) La signature du message m est (sm, em). Algorithme 6. Vérification de signature pour la méthode de Rabin proposée. Une entité B peut vérifier la signature (sm, em) en mettant en oeuvre les étapes suivantes: (a) Chercher la clé publique n de l'entité A. (b) Calculer M' = sm (mod n), o 0 (c) Prendre m' selon la règle suivante: m' = (M' - 2) / 8 si M' - 2 (mod 4). m' = (n - M' - 2) / 8 si M' - 3 (mod 4). m' =(M' - 1) / 4 si M' - 1 (mod 4). m' =(n - M' - 1) / 4 si M' - 0 (mod 4). (d) Calculer h(m') et vérifier que 4h(m') + 2 = em. (e) En cas de succès du processus de vérification selon (d), m' est le message recouvré. On va maintenant décrire des procédés basés sur le problème de Log discret. 12 2793366 Une autre classe de méthodes de signature est basée sur le fait que le problème de log discret ne peut être traité, ce dont le procédé de Nyberg-Rueppel est un exemple. Comme pour le procédé RSA, le procédé Nyberg- Rueppel de signature numérique souffre de l'inconvénient que la redondance du message est nécessaire. Le procédé décrit ci-dessous remédie à ce problème. Dans un but de simplicité seulement, l'une des diverses possibilités sera décrite en détail, et le procédé ne sera décrit que dans Zpq bien qu'il soit applicable à un groupe fini quelconque. Soient p et q des entiers tels que plq - 1 et que le problème de logarithme est discret ne peut être traité dans Zpq. Soi a un générateur du sous-groupe cyclique G d'ordre q dans Zpq et soit h une fonction de hachage cryptographique comme décrit ci-dessus. L'entité A sélectionne une clé privée a, qui est un entier sélectionné de facon aléatoire dans (1, 2,..., q - 1), et calcule la clé publique B = aa Algorithme 7. Génération de signature Pour signer un message m E Zp, l'entité A doit mettre en oeuvre les étapes suivantes: (a) Calculer h(m). (b) Sélectionner un entier aléatoire k e (1, 2, q - 1). (c) Calculer r = m ak (mod p). (d) Calculer sm = arh(m) + k mod q. (e) La signature du message m est (sm, r, h(m)). Algorithme 8. Vérification de signature L'entité B peut vérifier la signature (sm, r, h(m)) sur m en mettant en oeuvre les étapes suivantes: (a) Chercher la clé publique B de A (b) Calculer v1 = asm (mod p) (c) Calculer v2 = B-rh(m) (mod p). 13 2793366 (d) Calculer w = v1v2 (mod p). (e) Calculer m' = rw-1 (mod p). (f) Calculer h(m') et vérifier que h(m') = h(m). (g) Le message récupéré est m'. Une génération de signature qui utilise le procédé de l'algorithme 7 et 8 est presque aussi efficace que la méthode Nyberg- Rueppel d'origine, sauf pour le calcul de la fonction de hachage. De même, une vérification d'une signature est presque aussi efficace qu'une méthode de Nyberg- Rueppel d'origine, sauf pour le calcul du produit rh(m) mod q et le calcul de la valeur de hachage (hm'). La méthode de Nyberg-Rueppel ne peut pas être modifiée simplement pour donner les mêmes résultats. Par exemple, envoyer le hachage du message n'exclut pas une attaque par contre-façon existentielle. D'autres méthodes semblables à celle de Nyberg-Rueppel peuvent être modifiées de façon similaire selon les procédés de l'invention. En variante, les procédés de l'invention peuvent aussi être appliqués à des courbes elliptiques: une méthode de Nyberg-Rueppel qui peut être appliquée à des courbes elliptiques est décrite ci-dessous à titre d'exemple. Soit la courbe y2 + xy = x3 + ax2 + b à ordre n de premier élevé et soit P le point de la courbe de coordonnées x et y. Soit aussi h une fonction de hachage cryptographique comme décrit précédemment. Algorithme 9. Génération de signature L'entité A sélectionne une clé privée d, qui est un entier sélectionné de façon aléatoire dans (1, 2,..., n - 1), et calcule la clé publique Q = dP. Pour signer un message m o 1 (a) Calculer h(m). 14 2793366 (b) Sélectionner un entier aléatoire k c (1, 2, n - 1}. (c) Calculer kP et prendre x comme la coordonnée x du point kP. (d) Calculer r = m + x (mod n). (e) Calculer sm = drh(m) + k mod n. (f) La signature du message m est (sm, r, h(m)). Algorithme 10. Vérification de signature L'entité B peut vérifier la signature (sm, r, h(m)) sur m en mettant en oeuvre les étapes suivantes: (a) Chercher la clé publique Q de A (b) Calculer smP (c) Calculer (-rh(m))Q. (d) Calculer T = smP + (-rh(m))Q et prendre x' comme coordonnée x du point. (e) Calculer m' = r - x' (mod n). (f) Calculer h(m') et vérifier que h(m') = h(m). (g) Le message récupéré est m'. Alors que l'invention a été décrite en liaison avec un de ses modes de réalisation spécifique et dans une utilisation spécifique, plusieurs modifications de celle-ci ressortiront à l'homme de l'art sans s'écarter de l'esprit de l'invention. Les termes et expressions qui ont employés dans la spécification sont utilisés comme termes de description et non de limitations et il n'existe, dans 1' utilisation de ces termes, aucune intention d'exclure aucun équivalent des particularités représentées et décrites ou des parties de celles-ci, mais il est reconnu que diverses modifications sont possibles à l'intérieur du cadre des revendications. REVENDICATIONS 1. Procédé pour calculer une signature d'un message m caractérisé en ce qu'il comprend les étapes consistant à: a) déterminer une représentation h(m) dudit message en appliquant une fonction univoque et en dériver une première composante de signature, b) calculer une fonction liée mathématiquement à ladite représentation h(m) dudit message, et c) appliquer ladite fonction audit message pour obtenir une deuxième composante de signature, liée audit signataire. 2. Procédé selon la revendication 1, caractérisé en ce que ladite fonction univoque est une fonction de hachage cryptographique. 3. Procédé selon la revendication 2, caractérisé en ce que ladite fonction de hachage est une fonction de hachage SHA-I. 4. Procédé pour calculer une signature d'un message m caractérisé en ce qu'il comprend les étapes consistant à: a) déterminer un hachage h(m) dudit message en appliquant une fonction de hachage et en dériver une première composante de signature ern, b) calculer une fonction dn, liée mathématiquement audit hachage dudit message, telle que en, dm = 1 mod (X(n)), c) appliquer ladite fonction dm, audit message pour obtenir une deuxième composante de signature Sn, liée audit signataire, telle que Sm = mdni mod (k(n)), et d) envoyer à un récepteur lesdites composantes de signature (e.,, Sm). 5. Procédé pour calculer une signature d'un message m caractérisé en ce qu'il comprend les étapes consistant à a) déterminer un hachage h(m) dudit message en appliquant une fonction de hachage et en dériver une première composante de signature, b) sélectionner un entier aléatoire k e { 1, 2,.. q-I}, c) calculer une troisième composante de signature r telle que r = m Ok (mrod p), o ax est un générateur d'un groupe cyclique G d'ordre q dans Zpq, et o q divise p-l, d) calculer une deuxième composante sm de signature liée mathématiquement audit hachage, dudit message, telle que sm = arh(m) + k mod q, a étant une clé privée dudit signataire, et e) envoyer à un récepteur lesdites composantes de signature. 6. Procédé pour calculer une signature d'un message m caractérisé en ce qu'il comprend les étapes consistant à: a) déterminer un hachage h(m) dudit message en appliquant une fonction de hachage et en dériver une première composante de signature, b) sélectionner un entier aléatoire k E { 1, 2,. q- 1}, c) calculer une troisième composante de signature fonction r telle que r = m+x (mod n), o x est une coordonnée d'un point kP d'une courbe elliptique définie par y2 + xy=x3 + ax2 + b d'ordren, d) calculer une deuxième composante sm de signature liée mathématiquement audit hachage dudit message, telle que s,, = drh(m) + k mod q, d étant une clé privée de signature, et e) envoyer à un récepteur lesdites composantes de signature.