Brevet FR2985128A1 — publié le 20130628

Procédé de détermination de la valeur de U mod N, avec 2' > R où R est une constante de Montgomery. 1. DOMAINE DE L'INVENTION Le domaine de l'invention est celui de la cryptographie. Plus précisément, l'invention concerne une technique permettant de faciliter la réalisation d'une multiplication modulaire à partir d'une multiplication modulaire de Montgomery. L'invention permet ainsi de faciliter la mise en oeuvre de nombreux cryptosystèmes à clé publique (RSA pour « Rivest Shamir Adelman », ECDSA pour « Elliptic Curve Digital Signature Algorithm »). 2. ARRIÈRE-PLAN TECHNOLOGIQUE On s'attache plus particulièrement dans la suite de ce document à décrire la problématique relative à la détermination de la valeur de R2 mod N, où R est une constante de Montgomery et la variable N un modulus, à laquelle ont été confrontés les inventeurs de la présente demande de brevet. L'invention ne se limite bien sûr pas à ce domaine particulier d'application, mais présente un intérêt pour toute technique de détermination d'une valeur d'une variable U mod N, avec 2r > R, r étant un entier, R étant une constante de Montgomery et la variable N étant un modulus. Les composants électroniques mettant en oeuvre une opération de multiplication modulaire de Montgomery, notée *, sont très répandus car la transposition d'un point de vue matériel d'une telle opération est relativement peu complexe au vu des autres techniques existantes. Ainsi, une multiplication modulaire (par un module N) de Montgomery réalisée à partir de deux opérandes A et B consiste à réaliser l'opération suivante : A*B mod N mod N, où la variable R correspond à une constante de Montgomery. Classiquement, cette constante R est une puissance de 2, dont la taille est plus grande que celle du modulus N (de 1 bit à 128 bits, en fonction de l'architecture utilisée). De plus, on doit avoir R = 2'1 qui doit être inversible i.e gcd(R, N) = 1. Remarquons aussi que les contraintes suivantes portent sur la réalisation d'une multiplication modulaire de Montgomery ; il faut que : A T, avec Tune borne étant par exemple égale à N. Dès lors, le choix des opérandes est limité, et il n'est pas possible de prendre un opérande, A ou B, égal à la constante de Montgomery R utilisée de par l'existence de ces contraintes. Cependant, lorsqu'on souhaite obtenir la valeur de A.B mod N en utilisant l'opération de multiplication modulaire de Montgomery, il est nécessaire d'obtenir la valeur de R2 mod N. En effet, en calculant dans un premier temps s := A*B mod N = mod N puis s *R2 mod N, on obtient A.B mod N. Ainsi, pour obtenir la valeur de R2 mod N, il existe une première technique, bien connue de l'Homme du métier consistant à réaliser les opérations suivantes : a) u := 2 - Rmod N ; b) u*Â mod N = u* ...*u mod N = R2 mod N Cependant, cette première technique nécessite, pour l'obtention de l'élément u, de réaliser une réduction modulaire qui peut être coûteuse, notamment lorsque 2 - R et N ont une différence de taille importante (par exemple 128 bits). Pour pallier ce problème, une deuxième technique a été proposée dans le document EP 2385461 , qui comprend notamment des étapes consistant à obtenir dans un premier temps un nouveau modulus N' puis à calculer (R- N) + (R- N) mod N'. Cependant, un inconvénient de cette deuxième technique est que celle-ci nécessite la mise à disposition d'une opération d'addition et/ou de soustraction modulaire, élément qui n'est pas nécessairement présent sur un composant électronique comprenant une multiplication modulaire de Montgomery. 3. EXPOSÉ DE L'INVENTION Dans un mode de réalisation particulier de l'invention, il est proposé procédé de calculs cryptographiques mis en oeuvre dans un composant électronique, comprenant une étape de détermination d'une valeur d'une variable U = mod N, avec 2r > R, r étant un entier, R étant une constante de Montgomery et la variable N étant un modulus. Ladite étape de détermination est remarquable en ce qu'elle comprend une étape d'exécution d'une multiplication modulaire de Montgomery utilisant ledit modulus N et une autre constante de Montgomery R', de taille supérieure à ladite variable R. Dans un mode de réalisation particulier de l'invention, il est proposé un procédé de calculs cryptographiques pour lequel la valeur de U = R2 mod N. Ainsi, l'objet de ce mode de réalisation consiste à utiliser au moins une multiplication modulaire de Montgomery afin de déterminer la valeur de R2 mod N. Ainsi, cette technique ne nécessite pas l'utilisation d'une réduction modulaire supplémentaire à mettre en oeuvre, ou une opération d'addition modulaire. Dans, dans au moins un mode de réalisation de l'invention, un objectif est de fournir une technique de détermination de la valeur de R2 mod N, qui soit facile à mettre en oeuvre. Selon un aspect particulier de l'invention, il est proposé un procédé de calculs cryptographiques qui comprend une étape de détermination d'opérandes A', B' et de ladite autre constante de Montgomery R', et pour lequel ladite étape d'exécution d'une multiplication modulaire de Montgomery délivre A' * B' mod N = R2 mod N. Ainsi, la présente technique permet via l'usage d'une unique multiplication modulaire de Montgomery d'obtenir la valeur de R2 mod N. Selon un aspect particulier de l'invention, il est proposé un procédé de calculs cryptographiques dans lequel l'étape de détermination comprend une étape de détermination d'une première borne T' dépendante de R', telle que l'on puisse sélectionner les opérandes A' = x.R Selon un aspect particulier de l'invention, il est proposé un procédé de calculs cryptographiques dans lequel l'étape de détermination comprend : - une étape de détermination d'entiers p, c et k tels que R 2P(c+k) ; - une étape de détermination d'entiers p' et c' permettant de définir l'autre constante de Montgomery R' 2p ye '+k) Selon une implémentation préférée, les différentes étapes du procédé selon l'invention sont mises en oeuvre par un logiciel ou programme d'ordinateur, ce logiciel comprenant des instructions logicielles destinées à être exécutées par un processeur de données d'un module relais selon l'invention et étant conçu pour commander l'exécution des différentes étapes de ce procédé. En conséquence, l'invention vise aussi un programme, susceptible d'être exécuté par un ordinateur ou par un processeur de données, ce programme comportant des instructions pour commander l'exécution des étapes d'un procédé tel que mentionné ci-dessus. Ce programme peut utiliser n'importe quel langage de programmation, et être sous la forme de code source, code objet, ou de code intermédiaire entre code source et code objet, tel que dans une forme partiellement compilée, ou dans n'importe quelle autre forme souhaitable. L'invention vise aussi un support d'informations lisible par un processeur de données, et comportant des instructions d'un programme tel que mentionné ci-dessus. Le support d'informations peut être n'importe quelle entité ou dispositif capable de stocker le programme. Par exemple, le support peut comporter un moyen de stockage, tel qu'une ROM, par exemple un CD ROM ou une ROM de circuit microélectronique, ou encore un moyen d'enregistrement magnétique, par exemple une disquette (floppy disc) ou un disque dur. D'autre part, le support d'informations peut être un support transmissible tel qu'un signal électrique ou optique, qui peut être acheminé via un câble électrique ou optique, par radio ou par d'autres moyens. Le programme selon l'invention peut être en particulier téléchargé sur un réseau de type Internet. Alternativement, le support d'informations peut être un circuit intégré dans lequel le programme est incorporé, le circuit étant adapté pour exécuter ou pour être utilisé dans l'exécution du procédé en question. Selon un mode de réalisation, l'invention est mise en oeuvre au moyen de composants logiciels et/ou matériels. Dans cette optique, le terme "module" peut correspondre dans ce document aussi bien à un composant logiciel, qu'à un composant matériel ou à un ensemble de composants matériels et logiciels. Un composant logiciel correspond à un ou plusieurs programmes d'ordinateur, un ou plusieurs sous-programmes d'un programme, ou de manière plus générale à tout élément d'un programme ou d'un logiciel apte à mettre en oeuvre une fonction ou un ensemble de fonctions, selon ce qui est décrit ci-dessous pour le module concerné. Un tel composant logiciel est exécuté par un processeur de données d'une entité physique (terminal, serveur, etc) et est susceptible d'accéder aux ressources matérielles de cette entité physique (mémoires, supports d'enregistrement, bus de communication, cartes électroniques d'entrées/sorties, interfaces utilisateur, etc). De la même manière, un composant matériel correspond à tout élément d'un ensemble matériel (ou hardware) apte à mettre en oeuvre une fonction ou un ensemble de fonctions, selon ce qui est décrit ci-dessous pour le module concerné. Il peut s'agir d'un composant matériel programmable ou avec processeur intégré pour l'exécution de logiciel, par exemple un circuit intégré, une carte à puce, une carte à mémoire, une carte électronique pour l'exécution d'un micrologiciel (firmware), etc. Selon un aspect particulier de l'invention, il est proposé un composant électronique permettant de réaliser des calculs cryptographiques, ledit composant comprenant une unité matérielle capable de réaliser une opération de multiplication modulaire de Montgomery, paramétrée par un choix des deux opérandes A et B, ainsi qu'un modulus N et une constante de Montgomery R, ladite opération de multiplication modulaire de Montgomery comprenant une borne T, dépendant de ladite constante de Montgomery R choisie, ladite borne permettant de définir les contraintes suivantes A T, ledit composant électronique comprenant en outre une autre unité matérielle capable de déterminer la valeur de U mod N, où r est un entier. Ladite autre unité matérielle étant remarquable en ce qu'elle utilise ladite unité matérielle capable de réaliser une opération de multiplication modulaire de Montgomery, en fonction du choix d'une autre constante de Montgomery R' plus grande que ladite constante de Montgomery R, et de deux opérandes A' et B'. Selon un aspect particulier de l'invention, un tel composant électronique détermine la valeur de U = R2 modN. Selon un aspect particulier de l'invention, il est proposé un composant électronique qui est remarquable en ce que le choix de ladite autre constante de Montgomery R' et des deux opérandes A' et B' permettent d'obtenir via ladite unité matérielle capable de réaliser une opération de multiplication modulaire de Montgomery, directement la valeur de R2 mod N. Selon un aspect particulier de l'invention, il est proposé un composant électronique qui est remarquable en ce que le choix de ladite autre constante de Montgomery R' et des deux opérandes A' et B' permettent d'obtenir via ladite unité matérielle capable de réaliser une opération de multiplication modulaire de Montgomery, directement la valeur de 2.R mod N. Selon un aspect particulier de l'invention, il est proposé un module sécurisé comprenant un tel composant électronique. 4. LISTE DES FIGURES D'autres caractéristiques et avantages de l'invention apparaîtront à la lecture de la description suivante, donnée à titre d'exemple indicatif et non-limitatif, et des dessins annexés, dans lesquels : - la figure 1 présente un organigramme d'un mode de réalisation particulier du procédé selon l'invention ; - la figure 2 présente un organigramme d'un autre mode de réalisation du procédé selon l'invention ; - la figure 3 présente la structure d'un composant électronique selon un mode de réalisation particulier de l'invention. 5. DESCRIPTION DÉTAILLÉE Sur toutes les figures du présent document, les éléments et étapes identiques sont désignés par une même référence numérique. La figure 1 présente un organigramme d'un mode de réalisation particulier du procédé selon l'invention. Dans ce mode de réalisation de l'invention, l'objectif est de déterminer R2 mod N, dont l'emploi a été rappelé précédemment, en utilisant une multiplication modulaire de Montgomery. En notant que sur certaines architectures matérielles, la variable T précédemment mentionnée est indépendante de la valeur du modulus N utilisé (plus précisément que la valeur de cette variable T dépend uniquement du choix de la constante de Montgomery sélectionnée), il est possible d'établir une technique de determination de la valeur de R2 mod N, en utilisant une unique multiplication modulaire de Montgomery. Pour ce faire, le présent procédé comprend une étape de determination 101 d'opérandes A' et B', ainsi que d'une constante de Montgomery R', plus grande que la constante de Montgomery R d'intérêt, tel que l'on ait, suite à l'exécution de l'étape 102, A' * B' mod N = A'. mod N = R2 mod N. De par les contraintes inhérentes à l'utilisation d'une multiplication modulaire de Montgomery, il est nécessaire d'avoir A' T'. C'est le choix de la taille de la constante de Montgomery utilisée dans la multiplication modulaire de Montgomery qui induit la valeur de la borne maximale à utiliser. Par exemple, il convient de sélectionner A' = B ' = x. R tel que x vérifie l'équation suivante x2 R'. Cette étape de sélection n'est possible que si le multiplicateur modulaire de Montgomery le permet (de par l'existence des contraintes qui portent sur la taille des opérandes). En effet, pour que l'on puisse sélectionner A' - B' = x.R, il faut que l'inégalité suivante soit vérifiée (R)1/ 2.R Dans un mode de réalisation, en établissant que R 2P(c±ic ) où p, c et k sont des entiers, sont des paramètres internes d'un multiplicateur modulaire de Montgomery possédant p instances d'un multiplieur de c bits. Les k bit supplémentaires permettent la gestion des retenues internes. De plus, dans ce mode de réalisation, on a T On souhaite alors procéder à la détermination 101 de cette autre constante de Montgomery R' = 211' = 2P'(''±k), oùp 'et c' sont des entiers qui sont à déterminer, et donc de T' = 2P'''. Ainsi, à partir des entiers p, c et k, il faut déterminer les entiers c' et p' tels que .' l'on ait 2(P'(c'+k))/2 2p(c+k) T'. C'est le choix de la taille de la constante de Montgomery utilisée dans la multiplication modulaire de Montgomery qui induit la valeur de la borne maximale à utiliser. Par exemple, il convient de sélectionner A'= x.R1/2 tel que x vérifie l'équation suivante x2 = R', et B'=2A'. Cette étape de sélection n'est possible que si le multiplicateur modulaire de Montgomery le permet (de par l'existence des contraintes qui portent sur la taille des opérandes). En effet, pour que l'on puisse sélectionner A'- x.R1/2 et B'=2A', il faut que l'inégalité suivante soit vérifiée 2.R1/2 .Ril/2 Max(A',B), on a T' > B'=2A' 2R,1/2 R1/2 Par conséquent, on a 2.2(11'(c'+k))/2 2p(c+k)/2 REVENDICATIONS1. Procédé de calculs cryptographiques mis en oeuvre dans un composant électronique, comprenant une étape de détermination (100 ; 200) d'une valeur d'une variable U = 2' mod N, avec 2' > R, r étant un entier, R étant une constante de Montgomery et la variable N étant un modulus, ladite étape de détermination (100 ; 200) étant caractérisé en ce qu'elle comprend une étape d'exécution d'une multiplication modulaire de Montgomery (102 ; 202) utilisant ledit modulus N et une autre constante de Montgomery R', de taille supérieure à ladite variable R. 2. Procédé de calculs cryptographiques selon la revendication 1 caractérisé en ce que la valeur de U = R2 mod N. 3. Procédé de calculs cryptographiques selon la revendication 2 caractérisé en ce que qu'il comprend une étape de détermination (101) d'opérandes A', B' et de ladite autre constante de Montgomery R', et en ce que ladite étape d'exécution d'une multiplication modulaire de Montgomery (102) délivre A' * B' mod N = R2 mod N. 4. Procédé de calculs cryptographiques selon la revendication 3 caractérisé en ce que l'étape de détermination (101) comprend une étape de détermination d'une première borne T' dépendante de R', telle que l'on puisse sélectionner les opérandes A' = x.R 5. Procédé de calculs cryptographiques selon la revendication 4 caractérisé en ce que l'étape de détermination (101) comprend : - une étape de détermination d'entiers p, c et k tels que R = 2p(C-Fk) ; - une étape de détermination d'entiers p' et c' permettant de définir l'autre constante de Montgomery R' = 2pyc'+k). 6. Procédé de calculs cryptographiques selon la revendication 2 caractérisé en ce qu'il comprend une étape de détermination (201) d'opérandes A', B' et de ladite autre constante de Montgomery R', et en ce que ladite étape d'exécution d'une multiplication modulaire de Montgomery (202) délivre A' * B' mod N = 2.R mod N. 7. Procédé de calculs cryptographiques selon la revendication 6 caractérisé en ce que l'étape de détermination (201) comprend une étape de détermination d'unedeuxième borne T' dépendante de R', telle que l'on puisse sélectionner les opérandes A' = x.Rn2 8. Procédé de calculs cryptographiques selon la revendication 7 caractérisé en ce que l'étape de détermination (201) comprend : - une étape de détermination d'entiers p, c et k tels que R = 2p(c+k) ; - une étape de détermination d'entiers p' et c' permettant de définir l'autre constante de Montgomery R'2= p'(c' +k) 9. Produit programme d'ordinateur, comprenant des instructions de code de programme pour la mise en oeuvre du procédé selon au moins une des revendications 1 à 8 lorsque ledit programme est exécuté sur un ordinateur. 10. Médium de stockage lisible par ordinateur et non transitoire, stockant un programme d'ordinateur comprenant un jeu d'instructions exécutables par un ordinateur ou un processeur pour mettre en oeuvre le procédé selon au moins une des revendications 1 à 8. 11. Composant électronique permettant de réaliser des calculs cryptographiques, ledit composant comprenant une unité matérielle capable de réaliser une opération de multiplication modulaire de Montgomery, paramétrée par un choix des deux opérandes A et B, ainsi qu'un modulus N et une constante de Montgomery R, ladite opération de multiplication modulaire de Montgomery comprenant une borne T, dépendant de ladite constante de Montgomery R choisie, ladite borne permettant de définir les contraintes suivantes A T, ledit composant électronique comprenant en outre une autre unité matérielle capable de déterminer la valeur de U = mod N, où r est un entier, ladite autre unité matérielle étant caractérisé en ce qu'elle utilise ladite unité matérielle capable de réaliser une opération de multiplication modulaire de Montgomery, en fonction du choix d'une autre constante de Montgomery R' plus grande que ladite constante de Montgomery R, et de deux opérandes A' et B'. 12. Composant électronique selon la revendication 11 caractérisé en ce que la valeur de U = R2 mod N. 13. Composant électronique selon la revendication 12 caractérisé en ce que le choix de ladite autre constante de Montgomery R' et des deux opérandes A' et B' permettentd'obtenir via ladite unité matérielle capable de réaliser une opération de multiplication modulaire de Montgomery, directement la valeur de R2 mod N. 14. Composant électronique selon la revendication 12 caractérisé en ce que le choix de ladite autre constante de Montgomery R' et des deux opérandes A' et B' permettent d'obtenir via ladite unité matérielle capable de réaliser une opération de multiplication modulaire de Montgomery, directement la valeur de 2.R mod N. 15. Module sécurisé comprenant un composant électronique selon l'une quelconque des revendications 11 à 14.