Brevet FR2818471A1 — publié le 20020621

PROCEDE D'AMELIORATION DE LA SECURITE DE SCHEMAS DE CHIFFREMENT A CLEF PUBLIQUE. La présente invention concerne un procédé d'augmentation de la sécurité d'algorithmes de chiffrement à clef publique. Un schéma de chiffrement comprend un algorithme de chiffrement et un algorithme de déchiffrement présentant chacun un procédé de chiffrement et un de déchiffrement particulier. 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 mis 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. Dans ce qui suit, il est entendu que tous les éléments nécessaires au schéma de chiffrement de l'invention comme par exemple le message M, le chiffré C et toutes les abréviations de lettres ou lettres et chiffres qui suivent dans la description ci-dessous, sont des nombres entiers équivalents à des chaînes de bits. Par exemple, le symbole a Il b dénote la concaténation des représentations binaires des entiers a et b, qui sont de fait les chaînes de bits respectives de a et de b. Un algorithme de chiffrement déterministe prend en entrée le message M à chiffrer et renvoie en sortie le message chiffré C. Par ailleurs, un algorithme de chiffrement probabiliste prend usuellement en entrée le message M à chiffrer et un aléa u, et renvoie en sortie un message chiffré C, en utilisant la clef publique du destinataire. L'algorithme de déchiffrement prend en entrée le chiffré C et renvoie en sortie le message M, à l'aide de la clef privée. Un exemple d'algorithme de chiffrement probabiliste à clef publique est l'algorithme de chiffrement El-Gamal. Toutefois, la plupart des algorithmes de chiffrement probabilistes à clef publique ne présentent pas en euxmêmes un niveau de sécurité suffisant. En effet, il existe de nombreuses situations pratiques dans lesquelles un attaquant peut avoir accès à une machine informatique réalisant l'algorithme de déchiffrement à l'aide de la clef privée. Si l'attaquant possède un message chiffré C, il peut ainsi demander à la machine de déchiffrement de déchiffrer certains messages chiffrés C'bien choisis, différent du message chiffré C, et obtenir ainsi des informations sur le message M correspondant au message chiffré C. Le procédé de l'invention consiste en un procédé permettant d'augmenter le niveau de sécurité de tout algorithme de chiffrement probabiliste ou déterministe à clef publique. A partir d'un algorithme de chiffrement à clef publique pour lequel un attaquant ne peut pas obtenir le message clair à partir du message chiffré C, on construit un algorithme de chiffrement à clef publique pour lequel un attaquant ne peut pas obtenir d'information sur le message clair à partir du message chiffré C, même si l'attaquant a accès à une machine lui permettant de déchiffrer tout message chiffré C'différent de C. La construction utilise de plus un algorithme de chiffrement à clef secrète, tel que l'on ne peut pas obtenir d'information sur le message M à partir du message chiffré correspondant C. On obtient ainsi une construction hybride, mettant en oeuvre simultanément un algorithme de chiffrement à clef publique et un algorithme de chiffrement à clef secrète, pour obtenir un schéma de chiffrement hybride présentant un niveau de sécurité maximal. Le procédé de l'invention utilise donc un schéma de chiffrement probabiliste ou déterministe à clef publique EP prenant en entrée un message mp et un aléa u et renvoyant en sortie un chiffré cp. Le procédé utilise également un algorithme de chiffrement à clef secrète ES prenant en entrée un message ms et renvoyant en sortie un chiffré cs, en utilisant une clef k. L'algorithme de chiffrement probabiliste ou déterministe à clef publique utilise la clef pk pour chiffrer un message. Le déchiffrement se réalise en utilisant la clef privée sk correspondante. Le procédé de l'invention comprend deux procédés distincts comprenant chacun deux parties : - le premier procédé utilise un algorithme de chiffrement probabiliste et comprend deux parties : la première partie prenant en entrée le message M à chiffrer et la clef publique pk et renvoyant en sortie le message chiffré C ; la deuxième partie est l'algorithme de déchiffrement correspondant prenant en entrée un message chiffré C et la clef privée sk et renvoyant en sortie le message clair M ; - le second procédé utilise un algorithme de chiffrement déterministe et comprend deux parties : la première partie prenant en entrée le message M à chiffrer et la clef publique pk et renvoyant en sortie le message chiffré C ; la deuxième partie est l'algorithme de déchiffrement correspondant prenant en entrée un message chiffré C et la clef privée sk et renvoyant en sortie le message clair M. La première partie et la seconde partie de chacun des procédés de l'invention utilisent également une fonction de hachage F prenant en entrée un aléa r et le message M, une fonction de hachage G et une fonction de hachage H. La première partie du premier procédé de l'invention comprend les étapes suivantes : a) Générer aléatoirement un aléa r b) Appliquer la fonction de hachage F au message M et à l'aléa r pour obtenir s ; c) Appliquer la fonction de hachage H à s et effectuer un ou-exclusif du résultat avec r pour obtenir t ; d) Définir le message intermédiaire w=sllt, où Il dénote la concaténation de deux chaînes de bits ; e) Appliquer l'algorithme de chiffrement EP au message intermédiaire w et à un aléa u pour obtenir cl, à l'aide de la clef publique pk i f) Appliquer la fonction de hachage G à w et cl pour obtenir k ; g) Appliquer l'algorithme de chiffrement ES au message M en utilisant la clef k pour obtenir le chiffré c2 h) Le message chiffré C est C=clllc2. La seconde partie du premier procédé de l'invention comprend les étapes suivantes : a) Séparer le message chiffré C en cl et c2 b) Appliquer à cl un algorithme de déchiffrement EP-1 correspondant à l'algorithme de chiffrement EP, en utilisant une clef privée sk pour obtenir le message intermédiaire w=sllt ; c) Appliquer la fonction de hachage G à w et cl pour obtenir k ; d) Appliquer l'algorithme de déchiffrement ES-1 correspondant à l'algorithme de chiffrement ES au message chiffré c2 à l'aide de la clef k pour obtenir le message M ; e) Appliquer la fonction de hachage H à s et effectuer un ou-exclusif avec t pour obtenir r ; f) Appliquer la fonction de hachage F au message M et à l'aléa r pour obtenir s, g) Vérifier que s=s ; - Si s'et s diffèrent, rejeter le message chiffré C - Sinon, aller à l'étape h ; h) Renvoyer le message clair M. La première partie du second procédé de l'invention comprend les étapes suivantes : a) Générer aléatoirement un aléa r ; b) Appliquer la fonction de hachage F au message M et à l'aléa r pour obtenir s ; c) Appliquer la fonction de hachage H à s et effectuer un ou-exclusif du résultat avec r pour obtenir t ; d) Définir le message intermédiaire w=s où Il dénote la concaténation de deux chaînes de bits ; e) Appliquer l'algorithme de chiffrement EP au message intermédiaire w pour obtenir cl, à l'aide de la clef publique pk ; f) Appliquer la fonction de hachage G à w et cl pour obtenir k ; g) Appliquer l'algorithme de chiffrement ES au message M en utilisant la clef k pour obtenir le chiffré c2 ; h) Le message chiffré C est C=clllc2. La seconde partie du second procédé de l'invention comprend les étapes suivantes : a) Séparer le message chiffré C en cl et c2 ; b) Appliquer à cl un algorithme de déchiffrement EP-1 correspondant à l'algorithme de chiffrement EP, en utilisant une clef privée sk pour obtenir le message intermédiaire w=sl t ; c) Appliquer la fonction de hachage G à w et cl pour obtenir k ; d) Appliquer l'algorithme de déchiffrement ES-1 correspondant à l'algorithme de chiffrement ES au message chiffré c2 à l'aide de la clef k pour obtenir le message M ; e) Appliquer la fonction de hachage H à s et effectuer un ou-exclusif avec t pour obtenir r ; f) Appliquer la fonction de hachage F au message M et à l'aléa r pour obtenir s, g) Vérifier que s=s ; - Si s'et s diffèrent, rejeter le message chiffré c ; - Sinon, aller à l'étape h ; h) Renvoyer le message clair M. Préférentiellement, les étapes d de la première partie des deux procédés sont remplacées par le calcul w=. ist ou w=sllillt : ou w=slltlli, où i est une valeur quelconque pouvant contenir des informations utiles comme par exemple la taille binaire du message M ou l'identité de l'entité ayant chiffré M et émis le message chiffré C. Egalement, l'algorithme de chiffrement à clef secrète ES est remplacé dans les étapes g par une opération de ou-exclusif entre le message M à chiffrer et la clef k, pour obtenir le chiffré c2. De manière également préférentielle, les étapes b des secondes parties de deux procédés sont remplacées par les opérations : w=. illst ou w=sE jt ou w=sf : , et permettent d'en déduire la valeur i à toute fin de calcul ou de vérification.. Egalement, l'algorithme de déchiffrement à clef secrète ES-1 est remplacé dans les étapes d par une opération de ou-exclusif entre le message c2 à chiffrer et la clef k, pour obtenir le chiffré M. L'algorithme de chiffrement à clef publique construit est donc un algorithme de chiffrement hybride utilisant à la fois un algorithme de chiffrement à clef publique et un algorithme de chiffrement à clef secrète, ce qui permet d'obtenir de meilleures performances en temps de chiffrement. L'algorithme de chiffrement à clef publique ainsi construit présente un niveau de sécurité optimal : un attaquant ne peut pas obtenir d'information sur le message clair M correspondant au message chiffré C, même s'il a accès à une machine de déchiffrement lui permettant de déchiffrer tout message C'distinct de C. Les procédés décrits ci-dessus de l'invention sont destinés à des objets portables électroniques du type carte à puce. REVENDICATIONS 1-Procédé de chiffrement à clef publique prenant en entrée un message M à chiffrer et la clef publique pk et renvoyant en sortie le message chiffré C, ledit procédé utilisant un algorithme de chiffrement probabiliste à clef publique EP prenant en entrée un message mp et un aléa u et renvoyant en sortie un chiffré cp, ledit procédé utilisant également un algorithme de chiffrement à clef secrète ES prenant en entrée un message ms et renvoyant en sortie un chiffré cs, ledit procédé de chiffrement probabiliste à clef publique utilisant la clef pk pour chiffrer un message, utilisant également une fonction de hachage F prenant en entrée un aléa r et le message M, une fonction de hachage G et une fonction de hachage H, caractérisé en ce qu'il comprend les huit étapes suivantes : a) Générer aléatoirement un aléa r b) Appliquer la fonction de hachage F au message M et à l'aléa r pour obtenir s ; c) Appliquer la fonction de hachage H à s et effectuer un ou-exclusif du résultat avec r pour obtenir t ; d) Définir le message intermédiaire w=sllt, où Il dénote la concaténation de deux chaînes de bits ; e) Appliquer l'algorithme de chiffrement EP au message intermédiaire w et à un aléa u pour obtenir cl, à l'aide de la clef publique pk ; f) Appliquer la fonction de hachage G à w et cl pour obtenir k ; g) Appliquer l'algorithme de chiffrement ES au message M en utilisant la clef k pour obtenir le chiffré c2 h) Le message chiffré C est C=cl c2. 2-Procédé de déchiffrement à clef publique correspondant au procédé de chiffrement à clef publique selon la revendication 1, ledit procédé prenant en entrée un message chiffré C et la clef privée sk, sk correspondant à la clé publique pk de l'algorithme de chiffrement probabiliste EP, et renvoyant en sortie le message clair M, ledit procédé étant caractérisé en ce qu'il comprend les étapes suivantes : i) Séparer le message chiffré C en cl et c2 j) Appliquer à cl un algorithme de déchiffrement EP-1 correspondant à l'algorithme de chiffrement EP, en utilisant une clef privée sk pour obtenir le message intermédiaire w=sllt ; k) Appliquer la fonction de hachage G à w et cl pour obtenir k ; 1) Appliquer l'algorithme de déchiffrement ES-1 correspondant à l'algorithme de chiffrement ES au message chiffré c2 à l'aide de la clef k pour obtenir le message M ; m) Appliquer la fonction de hachage H à s et effectuer un ou-exclusif avec t pour obtenir r ; n) Appliquer la fonction de hachage F au message M et à l'aléa r pour obtenir s'i o) Vérifier que s=s ; - Si s' et s diffèrent, rejeter le message chiffré C - Sinon, aller à l'étape h ; p) Renvoyer le message clair M. 3-Procédé de chiffrement à clef publique prenant en entrée un message M à chiffrer et la clef publique pk et renvoyant en sortie le message chiffré C, ledit procédé utilisant un algorithme de chiffrement déterministe à clef publique EP prenant en entrée un message mp et renvoyant en sortie un chiffré cp, ledit procédé utilisant également un algorithme de chiffrement à clef secrète ES prenant en entrée un message ms et renvoyant en sortie un chiffré es, ledit procédé de chiffrement déterministe à clef publique utilisant la clef pk pour chiffrer un message, utilisant également une fonction de hachage F prenant en entrée un aléa r et le message M, une fonction de hachage G et une fonction de hachage H, caractérisé en ce qu'il comprend les 9 étapes suivantes : i) Générer aléatoirement un aléa r j) Appliquer la fonction de hachage F au message M et à l'aléa r pour obtenir s ; k) Appliquer la fonction de hachage H à s et effectuer un ou-exclusif du résultat avec r pour obtenir t ; 1) Définir le message intermédiaire w=s Il t, où Il dénote la concaténation de deux chaînes de bits ; m) Appliquer l'algorithme de chiffrement EP au message intermédiaire w pour obtenir cl, à l'aide de la clef publique pk ; n) Appliquer la fonction de hachage G à w et cl pour obtenir k i o) Appliquer l'algorithme de chiffrement ES au message M en utilisant la clef k pour obtenir le chiffré c2 ; p) Le message chiffré C est C=clllc2. 4-Procédé de déchiffrement à clef publique correspondant au procédé de chiffrement à clef publique selon la revendication 3, ledit procédé prenant en entrée un message chiffré C et la clef privée sk, sk correspondant à la clé publique pk de l'algorithme de chiffrement déterministe EP, et renvoyant en sortie le message clair M, ledit procédé étant caractérisé en ce qu'il comprend les étapes suivantes : i) Séparer le message chiffré C en cl et c2 ; j) Appliquer à cl un algorithme de déchiffrement EP-1 correspondant à l'algorithme de chiffrement EP, en utilisant une clef privée sk pour obtenir le message intermédiaire w=sllt ; k) Appliquer la fonction de hachage G à w et cl pour obtenir k ; 1) Appliquer l'algorithme de déchiffrement ES-1 correspondant à l'algorithme de chiffrement ES au message chiffré c2 à l'aide de la clef k pour obtenir le message M ; m) Appliquer la fonction de hachage H à s et effectuer un ou-exclusif avec t pour obtenir r ; n) Appliquer la fonction de hachage F au message M et à l'aléa r pour obtenir s' ; o) Vérifier que s=s ; - Si s'et s diffèrent, rejeter le message chiffré c ; - Sinon, aller à l'étape h ; p) Renvoyer le message clair M. 5-Procédé selon les revendications 1 et 3, caractérisé en ce que les étapes d sont remplacées par le calcul w=i Il s Il t ou w=s Il i Il t ou w=s Il t Il i, où i est une valeur quelconque pouvant contenir des informations utiles comme par exemple la taille binaire du message M ou l'identité de l'entité ayant chiffré M et émis le message chiffré C. 6-Procédé selon les revendications 2 et 4, caractérisé en ce que les étapes b permettent d'obtenir w=i .s t ou w=sllillt ou w=slltlli, et d'en déduire la valeur i à toute fin de calcul ou de vérification. 7-Procédé selon les revendications 1 et 3, caractérisé en ce que l'algorithme de chiffrement à clef secrète ES est remplacé dans les étapes g de la revendication 1 et g de la revendication 3 par une opération de ou-exclusif entre le message M à chiffrer et la clef k, pour obtenir le chiffré c2. 8-Procédé selon les revendications 2 et 4, caractérisé en ce que l'algorithme de déchiffrement à clef secrète ES-1 est remplacé dans les étapes d de la revendication 2 et d de la revendication 4 par une opération de ou-exclusif entre le message c2 à chiffrer et la clef k, pour obtenir le chiffré M. 9-Procédé suivant l'une quelconque des revendications précédentes, caractérisé en ce que le procédé est utilisé dans un objet électronique portable de type carte à puce.