Brevet FR2952774A1 — publié le 20110520

La présente invention concerne un procédé pour la mise en oeuvre du déchiffrement ou de la signature RSA qui consiste à effectuer Xd mod N, l'exponentiation par un nombre d secret, modulo N, d'un nombre X représentant le cryptogramme, le message ou la clé de session ou bien représentant l'identifiant permettant de générer la signature, procédé destiné aux cartes à puce ou aux téléphones portables ou autres appareils du même type, procédé selon lequel le calcul est réalisé par l'opération suivante : k Y = Xdmod N = E C'X x BdimodN avec un k petit. i=0 Les CXi sont les binomiaux et les Bdi sont les coefficients de la matrice B définie par la relation matricielle Puis=P*B avec Puis la matrice des puissances et P la matrice des binomiaux. 10 La présente invention concerne également un dispositif mettant en oeuvre un tel procédé. Le système de chiffrement RSA est le crypto-système à clé publique le plus utilisé et le plus éprouvé pour protéger des données confidentielles ou pour l'authentification. II peut être utilisé 15 comme procédé de chiffrement ou comme procédé de signature ou pour protéger l'échange de la clé de session pour les crypto-systèmes à clé secrète. Le système RSA est utilisé dans les cartes à puce et autres systèmes informatiques, embarqués ou pas. Les applications de RSA • sur une carte à puce ou sur des systèmes embarqués sont par exemple des applications bancaires, des applications de téléphonie, de paiement à distance pour la télévision numérique, 20 la distribution de carburant, lors de passage aux péages d'autoroutes. Afin de diminuer le temps de calcul de la génération de la signature ou le déchiffrement RSA, Il est commun d'utiliser pour des systèmes portables de type carte à puce la version RSA-CRT proposée par J. J. Quisquater et C. Couvreur. II est en effet considéré qu'un procédé en mode CRT est de l'ordre de quatre fois plus rapide qu'un RSA en mode standard. 25 Un des inconvénients de cette primitive c'est qu'elle oblige lors de son implémentation le stockage et le transfert des éléments de la clé secrète : les exposants dp et dq et les facteurs privés p,q. Elle est aussi exposée à des attaques par canaux cachés, par injection de fautes. Des palliatifs ont été proposés pour combler ces vulnérabilités, alourdissant le calcul sans pour autant y 30 remédier comme nous le montre par exemple les oppositions entre les plus grands spécialistes du sujet. Blomer, Otto, Seifert propose une solution appelée BOS, réfutée par David Wagner dans son article « Cryptanalysis of a provably secure CRT-RSA algorthim » qui prouve qu'elle n'est pas sécurisée contre un certain type d'attaques. II en va de même pour les contre-mesures proposées comme solution par Adi Shamir « How to check modular exponentiation » 35 ou les solutions exposées par Gemplus dans les brevets FR2799851 B1, FR2818473B1. Une variante CRT-RSA a aussi été proposée par M. J. Wiener, pour améliorer la vitesse du calcul de l'ordre de 3 fois plus, appelée Rebalanced RSA. Mais elle aussi présente les mêmes vulnérabilités: exposition des éléments de la clé privée, dp, dq, p, q et exposition aux mêmes attaques par canaux cachés, par mesures ou insertion de fautes, sans compter ses propres failles sur les attaques des exposants CRT, dp et dq. L'objectif de la présente invention est de fournir un procédé et un dispositif de déchiffrement et de génération de signature RSA, pour les cartes bancaires, les smartphones. L'invention est plus généralement destinée aux appareils nécessitants la sécurisation de leurs données ainsi 10 que l'authentification des utilisateurs ou des machines et intégrant des cartes à puce ou des composants électroniques non encombrants avec mémoire et unité de calcul limitées. La présente invention a pour but de proposer un procédé et un dispositif plus performants moins vulnérables moins encombrants que les variantes du RSA en mode CRT. En effet les facteurs premiers p et q ne sont pas exposés, comme nous allons le voir. En ce qui concerne la 15 performance, notre procédé est de l'ordre de trente fois plus rapide que le RSA en mode standard. La performance en terme de nombre de multiplications modulaires du procédé ne dépend pas de la taille de la clé, qu'elle soit de 512, 1024, 2048, 4096. Selon l'invention, on propose un procédé d'obtention du déchiffrement ou de la génération de signature RSA qui correspondent à la même opération qui est l'exponentiation par d, l'exposant 20 privé, modulo N comportant les étapes suivantes : - Déterminer au préalable les éléments de la clé privée: - Choisir p et q premiers assez grands, de longueur supérieure à 512 bits par exemple. Calculer N=p*q. 25 - Calculer la matrice B modulo N, où B est définie par l'égalité matricielle Puis=P*B avec P matrice des binomiaux et Puis matrice des puissances entières rangées par colonnes Pi,j=i'. - Conjecturer par observation sur les colonnes de B des coefficients en nombre limité. 30 - Récupérer l'indice dO d'une des colonnes dont les coefficients sont nuls à partir d'un certain rang petit kO, de l'ordre de la dizaine. Trouver un d, représentant l'exposant privé, supérieur à dO de tel sorte que l'écart Delta entre dO et d soit petit, de l'ordre de la dizaine et tel que d respecte le standard PKCS#1. 35 Mémoriser les coefficients de la matrice B présents dans les colonnes d'indices dO ou d. La clé privée est représentée par les coefficients B;,do avec i Calculer Y=Xd mod N où X représente le cryptogramme dans le cas du déchiffrement ou la clé de session à déchiffrer dans le cas du partage de la clé secrète ou l'identifiant pour générer la signature. Le calcul se fait par l'une des deux opérations suivantes: - (1) Y=(X + CX2 *B2dO + CX3*B3d0 +... + CXkO-1 *Bk0-1dO)*XDelta mod N, - (2) Y=X + CX2 *B2d + CX3*B3d +...+ CXkO+Delta-1*BkO+Delta-1d mod N, où les CX sont les binomiaux. Ainsi, l'obtention de l'exponentiation d modulo N revient à un simple produit scalaire qui peut être mis en oeuvre sur des composants électroniques et/ou des systèmes informatiques très rudimentaires sans faire appel à des processeurs spécialisés ni à des algorithmes de calculs complexes. Comme Delta et kO sont des termes petits, de l'ordre de la dizaine, le nombre de multiplications modulaires est limité. Dans la première version (1) par exemple, Il est égale au nombre des termes de la série plus le nombre de multiplications modulaires nécessaires pour réaliser XDeltamod N plus le nombre de multiplications modulaires nécessaires au calcul des binomiaux d'indice maximum kO-1 qui peuvent être préalablement calculés et stockés ou calculés de proche en proche. Selon l'invention, on propose également un dispositif pour mettre en oeuvre le procédé précédent, qui comporte : - un module d'entrée apte à récupérer les coefficients et les termes préalablement calculés par une machine extérieure ; - un module d'entrée permettant de récupérer X, l'identifiant, le cryptogramme ou la clé de session à déchiffrer; une zone de mémoire permettant de stocker les coefficients et les autres éléments de la 25 clé privée ; une zone mémoire ou tampon permettant de stocker X; une unité de calcul apte à effectuer l'un des deux calculs ci-dessus (1) ou (2) permettant l'exponentiation Xd mod N ; - un module de sortie apte à fournir le résultat Y. 30 Ce dispositif est très simple, et peut être par exemple intégré dans une carte bancaire ou dans un téléphone mobile ou tout appareil portable peu encombrant nécessitant une confidentialité des données ou une authentification de son porteur. Les données dont les coefficients de la matrice B et les nombres premiers p et q sont prédéfinis 35 par un serveur qui fournit au dispositif via son interface d'entrée la clé secrète sans pour autant communiquer p et q. En effet les éléments de la clé privée qui sont récupérés sont le module public N, les coefficients B,d° avec Delta ou les B id. Ils sont suffisants pour le calcul de l'exponentiation modulo dans le cadre du déchiffrement ou de la signature. Ce sont ces données qui transiteront et qui seront stockées dans le dispositif et non pas p,q ni dp, dq comme dans le cas du RSA-CRT. De plus ce dispositif permet de fournir la signature, le message en clair en faisant appel à des moyens informatiques très simples et en requérant un minimum d'opérations, donc de temps de 5 calcul. La rapidité est de l'ordre de 30 plus que le RSA en mode standard. Le procédé de l'invention est détaillé à travers les exemples suivants qui permettent de l'illustrer sans limiter l'invention ni dans son cadre ni son esprit. L'illustration se fait au travers de deux cas, le cas trivial avec des petites valeurs et le cas réel 10 avec des valeurs correspondant plus à la cryptographie. Dans un souci de clarté, les valeurs inutiles ou trop encombrantes du cas réel seront omises ou remplacées par celles du cas trivial. On détermine des nombres premiers p et q : pour le cas trivial p=19, q=31, pour le cas réel les facteurs p et q ont des longueurs de l'ordre de 256 à 512 bits. Ils permettent 15 de calculer le module N ci-dessous. On calcul le module N : N=19*31=589 pour le cas trivial, N=632462970997803699091599671258290275232913854713560594996322791\ 0028237118876645193104862397829262752230517033864675133038787 pour le cas réel. 20 On détermine un d0 à partir de la matrice B modulo N. Il est possible d'illustrer cette étape par la matrice B modulo 589 : 36ième 37ième 38ième 39ième colonne colonne colonne colonne 0 0 0 0 1 1 1 1 341 95 192 386 571 380 247 139 227 247 152 418 343 494 171 437 379 209 95 418 248 266 380 380 341 0 361 38 248 0 0 304 341 0 0 0 248 0 0 0 341 0 0 0 248 0 0 o On trouve dO = 37 et les coefficients sont nuls sur la colonne à partir du rang 8. Pour le cas réel il est difficile de représenter ici la matrice B modulo N mais on trouve dO de la même façon que le cas trivial. On cherche un d à partir de dO. On trouve pour le cas réel d=d0+2. On a donc la clé privée composée de Delta=2, de N calculé au-dessus, et des coefficients récupérés sur la colonne dO de la matrice B modulo N : B2d0=142547263713072284816386350183285964012175610362550042395067\ 10 9928749315947541780341706495542439590571451418248714604750541806, B3d0=14254726371307228481638635018328596401217561036255004239506\ 7992874931594754178034170649554\ 2439590571451418248714604750541806. On calcule donc le message en clair ou la signature Y à partir des éléments de la clé et du 15 cryptogramme ou de l'identifiant X selon la relation suivante : (3)Y= (X + Cx2 *B2d° + Cx3 *B3d0)*X2 mod N. Y=571662621930338564776080010111301745602. Ainsi, nous avons une multiplication pour le calcul de Cx2 une autre pour le calcul de Cx3 égal à Cx2 *(x-2)/3. On a donc au total quatre multiplications modulaires dont un carré. 20 On retrouve M représentant le message à chiffrer qui intervient dans le calcul du chiffrement donnant X. M=571662621930338564776080010111301745602. X=M emod N =19309507340727059648226007360004662344243988425533944\ 25 41180082268371451946381868714719043321936151843513403674230577021097733 avec e=14176197382105994564952474999932499798136717174418825765510\ 26055751208481672004351121015677352639645509758244857378219165567. 30 L'invention sera mieux comprise à la lumière de la description qui suit en référence à l'unique figure illustrant schématiquement un dispositif selon l'invention apte à la mise en oeuvre du procédé selon l'invention. Le procédé de l'invention peut être mis en oeuvre à l'aide du dispositif illustré par la figure 1. - Le dispositif comporte une unité d'entrée 10 apte à recevoir les éléments de la clé privée fournie par un serveur générant les clés selon les étapes du procédé détaillé ci dessus. - Le dispositif comporte une deuxième unité d'entrée 11 apte à recevoir le paramètre X. - Il comporte aussi deux zones mémoires ou tampons 20 21 aptes à mémoriser respectivement la clé privée, le paramètre X. On imagine très bien que la zone de stockage de la clé privé et les canaux de transmission de cette clé sont particulièrement sécurisés. Le paramètre X étant le chiffré ou l'identifiant il peut être considéré comme moins sensible mais peut être aussi sécurisé. - Le dispositif comporte aussi une unité de calcul 3 apte au calcul (3). Le dispositif comporte aussi un module de sortie 4 apte à restituer le résultat Y aux autres composants de l'appareil hôte, une carte à puce par exemple ou un téléphone portable pour l'authentification ou le déchiffrement du message. Qu'il s'agisse de la signature ou du déchiffrement, le fonctionnement du dispositif est le suivant. La clé privée est récupérée au préalable par l'interface du module d'entrée 10 et elle est stockée dans le prestataire représenté par la mémoire protégée 20 pour toute la durée de sa validité. Si le paramètre X représente un cryptogramme à déchiffrer alors il est récupéré par le module d'entrée 11 à la volée et il est stocké dans la zone tampon 21 le temps de le déchiffrer. Dans ce cas X peut représenter soit des blocs du message soit le message lui-même à déchiffrer, par exemple une clé de session. Si le paramètre X représente l'identifiant dont on doit générer la signature alors il est récupéré par la module d'entrée 11 et il est stocké dans le prestataire 21 pour toute la durée de sa 25 validité. D'une part l'unité de calcul 3 récupère la clé privée du prestataire 20 et d'autre part il récupère X du prestataire ou de la zone tampon 21 pour le déchiffrement ou la signature. L'unité de calcul doit être apte à calculer des multiplications modulaires pour des grands nombres de longueur pouvant aller jusqu'à 2048 bits. La multiplication modulaire de Montgomery est 30 intéressante à implémenter ici. L'unité de sortie récupère le message déchiffré ou la signature ou une relation triviale entre la signature et l'identifiant. Dans tous les cas elle restitue le résultat au composant client du dispositif. 35 On obtient ainsi un dispositif extrêmement simple, performant, peu encombrant, à faible coût et fiable pour la réalisation du déchiffrement ou de la signature RSA, destiné à la sécurité, par la confidentialité et l'authentification, des cartes à puces et des composants électroniques du même type en particulier les cartes bancaires et les téléphones portables. Rappelons que l'invention n'est pas limitée aux modes particuliers de réalisation de l'invention qui viennent d'être décrits, mais bien au contraire englobe toute variante entrant dans le cadre de l'invention tel que défini par les revendications. Revendications1. Procédé permettant le calcul de l'exponentiation Xd mod N destiné à des cartes à puces ou des composants de même type, ledit procédé ayant pour objectif l'amélioration de la 5 performance, de la sécurité ou la réduction de l'encombrement, caractérisé en ce qu'il comporte les étapes suivantes : a. Déterminer au préalable l'exposant d et les paramètres pré requis : L Choisir p et q premier assez grand de longueur supérieure à 512 bits par exemple. ii. Calculer N=p*q. iii. Calculer la matrice B modulo N, où B est définie par l'égalité matricielle : Puis=P.B avec P matrice des binomiaux et Puis matrice des puissances entières rangées par colonnes Pi,j=i'. iv. Conjecturer par observation sur les colonnes de B des coefficients en nombre limité. v. Récupérer l'indice dO d'une des colonnes dont les coefficients sont nuls à partir d'un certain rang petit k0, de l'ordre de la dizaine. vi. Trouver un d, représentant l'exposant, supérieur à dO de tel sorte que l'écart Delta entre dO et d soit petit, de l'ordre de la dizaine et tel que d respecte les aspects demandés au procédé. vii. Mémoriser les coefficients de la matrice B présents dans la colonne d'indices dO. L'exposant d est représenté par les coefficients B;,do avec i 2. Procédé permettant le calcul de l'exponentiation Xd mod N destiné à des cartes à puces ou des composants de même type, ledit procédé ayant pour objectif l'amélioration de la performance, de la sécurité ou la réduction de l'encombrement, caractérisé en ce qu'il 30 comporte les étapes suivantes : a. Déterminer au préalable l'exposant d et les paramètres pré requis : i. Choisir p et q premier assez grand de longueur supérieure à 512 bits par exemple. ii. Calculer N=p*q. 35 iii. Calculer la matrice B modulo N, où B est définie par l'égalité matricielle : Puis=P.B avec P matrice des binomiaux et Puis matrice des puissances entières rangées par colonnes 10 15 20 25iv. Conjecturer par observation sur les colonnes de B des coefficients en nombre limité. v. Récupérer l'indice d0 d'une des colonnes dont les coefficients sont nuls à partir d'un certain rang petit k0, de l'ordre de la dizaine. vi. Trouver un d, représentant l'exposant, supérieur à d0 de tel sorte que l'écart Delta entre d0 et d soit petit, de l'ordre de la dizaine et tel que d respecte les aspects demandés au procédé. vii. Mémoriser les coefficients de la matrice B présents dans la colonne d'indices d0. L'exposant d est représenté par les coefficients Bl,d avec i 3. Procédé selon la revendication 1, caractérisé en ce que le calcul d'exponentiation 15 correspond à un déchiffrement RSA. 4. Procédé selon la revendication 2, caractérisé en ce que le calcul d'exponentiation correspond à un déchiffrement RSA. 20 5. Procédé selon la revendication 1, caractérisé en ce que le calcul d'exponentiation correspond à une signature RSA. 6. Procédé selon la revendication 2, caractérisé en ce que le calcul d'exponentiation correspond à une signature RSA. 7. Dispositif selon la revendication 3, caractérisé en ce qu'il comporte: a. un module d'entrée 10 apte à récupérer les coefficients et les termes préalablement calculés par une machine extérieure; b. un module d'entrée 11 permettant de récupérer à la volée X le cryptogramme ou la clé de session à déchiffrer; c. une zone mémoire 20 permettant de stocker les coefficients et les autres éléments de la clé privée ; d. une zone tampon 21 permettant de buffériser X; e. une unité de calcul 3 apte à effectuer le calcul (1) permettant l'exponentiation Xd mod N; f. un module de sortie 4 apte à fournir le résultat Y. 8. Dispositif selon la revendication 4, caractérisé en ce qu'il comporte: 10 25 30 35a. un module d'entrée 10 apte à récupérer les coefficients et les termes préalablement calculés par une machine extérieure; b. un module d'entrée 11 permettant de récupérer à la volée X le cryptogramme ou la clé de session à déchiffrer; c. une zone mémoire 20 permettant de stocker les coefficients et les autres éléments de la clé privée ; d. une zone tampon 21 permettant de buffériser X; e. une unité de calcul 3 apte à effectuer le calcul (2) permettant l'exponentiation XdmodN ; f. un module de sortie 4 apte à fournir le résultat Y. 9. Dispositif selon la revendication 5, caractérisé en ce qu'il comporte: a. un module d'entrée 10 apte à récupérer les coefficients et les termes préalablement calculés par une machine extérieure; b. un module d'entrée 11 permettant de récupérer X l'identifiant pour la signature; c. un prestataire 20 permettant de stocker les coefficients et les autres éléments de la clé privée ; d. un prestataire 21 permettant de stocker X l'identifiant; e. une unité de calcul 3 apte à effectuer le calcul (1) permettant l'exponentiation XdmodN ; f. un module de sortie 4 apte à fournir le résultat Y. 10. Dispositif selon la revendication 6, caractérisé en ce qu'il comporte: a. un module d'entrée 10 apte à récupérer les coefficients et les termes préalablement calculés par une machine extérieure; b. un module d'entrée 11 permettant de récupérer X l'identifiant pour la signature; c. un prestataire 20 permettant de stocker les coefficients et les autres 30 éléments de la clé privée ; d. un prestataire 21 permettant de stocker X l'identifiant; e. une unité de calcul 3 apte à effectuer le calcul (2) permettant l'exponentiation XdmodN; f. un module de sortie 4 apte à fournir le résultat Y. 35