Brevet FR3070814A1 — publié le 20190308

DISPOSITIF DE RÉDUCTION MODULAIRE DESCRIPTION DOMAINE TECHNIQUE La présente invention concerne les dispositifs de réduction modulaire. Elle trouve notamment application dans le domaine de la cryptographie, en particulier dans les infrastructures à clés asymétriques tels que RSA ou El Gamal, et les chiffrements basés sur courbes elliptiques ou encore sur les réseaux euclidiens ÉTAT DE LA TECHNIQUE ANTÉRIEURE La réduction modulaire d'un entier XE Z par un diviseur qe Z*, encore appelé modulo, est définie comme le reste de la division euclidienne de x par ce modulo. La plupart des méthodes de chiffrement et de codage de correction d'erreurs font directement ou indirectement appel à des opérations arithmétiques sur un anneau fini Zq =Z/qZ où q, entier positif non nul, est le cardinal de l'anneau, cet anneau fini étant un corps fini si q est un nombre premier. Les opérations arithmétiques sur les anneaux ou corps finis nécessitent des opérations de réduction modulaire. Or, les méthodes naïves de division euclidienne s'avèrent inappropriées pour traiter les grands nombres utilisés en cryptographie (256 bits par exemple). Aussi, les algorithmes de réduction modulaire ont fait l'objet de nombreuses recherches. Une première approche consiste à déterminer les chiffres successifs du quotient par récurrence (méthode de division à la main): division avec ou sans restauration d'état, voire des versions plus avancées comme la méthode SRT (Sweeney, Robertson, Tocher). Ces algorithmes sont très génériques, mais ont une latence relativement élevée et ne se prêtent pas à des calculs sur les grands nombres. En outre, les méthodes de division rapide de type SRT nécessitent des circuits de taille importante. 2 Une seconde approche consiste à n'utiliser que des moduli de forme particulière (nombres de Mersenne par exemple), pour lesquels des algorithmes très efficaces sont connus. Une troisième approche consiste à développer des algorithmes génériques se 5 basant sur des pré-calculs souvent coûteux mais permettant ensuite d'effectuer un calcul rapide du reste modulaire. Parmi ces algorithmes, on peut notamment citer la méthode de Montgomery, la méthode de Barrett ou celle de Barrett généralisée. On pourra trouver une présentation de la méthode de Montgomery et de la méthode de Barrett généralisée dans l'article de M. Kne2evie et al. intitulé « Speeding up 10 Barrett and Montgomery modular multiplications» publié en 2009. La méthode de Barrett généralisée est rappelée ci-après. Elle fait appel à deux paramètres de réduction ae Z, fleZ remplissant des conditions qui seront précisées plus loin. La réduction de x modulo q, notée x mod q est définie par le reste r de la division euclidienne de x par q, soit : 15 r = x-qLxlq j (1) avec 0 r >n le décalage de n bits vers la droite, l'algorithme de Barrett généralisé peut être représenté par le pseudo-code suivant : , q q then 6. r'r'-q 7. end if 8. return r' 4 On notera que la contrainte sur la taille de l'entrée x, sur au plus 2n bits, permet d'effectuer une multiplication modulaire (sur l'anneau Z, où q est un entiers de n bits), autrement dit de calculer le produit z = xy avec x, y eZq. Les valeurs x, y étant représentées sur n bits, z est représenté sur 2n bits et peut faire l'objet d'une réduction 5 modulaire au moyen de l'algorithme ci-dessus. La Fig. 1 représente de manière schématique un circuit implémentant l'algorithme de Barrett généralisé. La valeur x dont on souhaite effectuer la réduction modulaire est représentée par 10 un mot de 2n bits. Ce mot est fourni à un premier circuit de décalage 110 dans lequel il subit un décalage vers la droite de (n+ fi) bits correspondant à une division par 2. Un tel décalage est réalisé avantageusement en extrayant seulement les n-16 bits de poids forts de l'entrée. Le mot ainsi décalé est ensuite multiplié en 120 par le facteur if pré-calculé. 15 Le résultat de la multiplication est fourni à un second circuit de décalage dans lequel il subit un décalage de (a- fi) bits vers la droite en 130 pour obtenir l'estimation k du quotient. Cette estimation du quotient est multipliée en 140 par le diviseur q et le résultat obtenu est soustrait à la valeur x en 150 pour donner une estimation provisoire r' de r. 20 Le diviseur q est ensuite soustrait à r' en 160. Un multiplexeur 170 sélectionne la valeur r' en sortie du soustracteur 150 ou bien la valeur r'-q en sortie du soustracteur 160 en fonction du signe de r'-q. Ainsi, le multiplexeur 170 fournit le résultat de la réduction modulaire r comme r'-q si r'-q est strictement positif et comme r' si r'-q est négatif ou nul. 25 La méthode généralisée de Barrett permet d'effectuer une réduction modulaire de manière efficace. Toutefois, elle nécessite d'effectuer un pré-calcul de la valeur , ce qui augmente sensiblement la latence du circuit. 2'" 5 Le but de la présente invention est par conséquent de proposer un dispositif de calcul modulaire qui soit efficace et qui présente une latence inférieure à celle observée dans l'état de la technique. EXPOSÉ DE L'INVENTION 5 La présente invention est définie par un dispositif de réduction modulaire pour calculer le reste d'un entier x divisé par un modulo q, ledit entier étant représenté par un mot binaire de 2n bits et le modulo par un mot binaire de n bits, comprend un circuit implémentant un algorithme de réduction modulaire de Barrett généralisé, dit circuit de Barrett, une mémoire cache et un circuit de division binaire, le circuit de Barrett recevant 10 ledit entier ainsi qu'un résultat d'un pré-calcul (du) relatif à une valeur du modulo ( q ) et une puissance de 2 ( 2'''), le résultat du pré-calcul étant fourni directement par la mémoire cache au circuit de Barrett s'il est déjà stocké en relation avec ladite valeur du modulo et, sinon, étant calculé par le circuit de division binaire avant d'être stocké dans la mémoire cache et fourni au circuit de Barrett. 15 Dans un premier mode de réalisation, la mémoire cache comprend une première partie, dite mémoire d'étiquettes, et une seconde partie, dite mémoire de données, les première et seconde parties étant adressées par f (g) où f est une fonction de projection de n bits sur m bits avec m REVENDICATIONS1. Dispositif de réduction modulaire pour calculer le reste d'un entier x divisé par un modulo q, ledit entier étant représenté par un mot binaire de 2n bits et le modulo par un mot binaire de n bits, caractérisé en ce qu'il comprend un circuit implémentant un algorithme de réduction modulaire de Barrett généralisé, dit circuit de Barrett (210), une mémoire cache (220) et un circuit de division binaire (230), le circuit de Barrett recevant ledit entier ainsi qu'un résultat d'un pré-calcul (du) ) relatif à une valeur du modulo (q) et une puissance de 2 ( 2'''), le résultat du pré-calcul étant fourni directement par la mémoire cache au circuit de Barrett (220) s'il est déjà stocké en relation avec ladite valeur du modulo et, sinon, étant calculé par le circuit de division binaire (230) avant d'être stocké dans la mémoire cache et fourni au circuit de Barrett. 2. Dispositif de réduction modulaire selon la revendication 1, caractérisé en ce que la mémoire cache comprend une première partie, dite mémoire d'étiquettes (310), et une seconde partie, dite mémoire de données (320), les première et seconde parties étant adressées par f (q) où f est une fonction de projection de n bits sur m bits avec m 3. Dispositif de réduction modulaire selon la revendication 1 ou 2, caractérisé en ce que le circuit de division binaire effectue le pré-calcul 11= où 2'" est le q 2'" q ^ 2"" , plus grand entier inférieur ou égal à ou 2'' est ladite puissance de 2 et a est un q entier tel que a n+1. 17 4. Dispositif de réduction modulaire selon la revendication 3, caractérisé en ce que le circuit de Barrett décale (110) de a+,8 bits le mot binaire représentant x vers les bits de poids faibles, où 16 est un entier tel que 16 -2, multiplie (120) ensuite le mot ainsi décalé par le résultat du pré-calcul, ,u, puis décale (130) à nouveau de a-16 bits le résultat 5 de cette multiplication vers les bits de poids faibles pour obtenir un second mot, ledit second mot étant multiplié (140) par le modulo avant d'être soustrait (150) au mot binaire représentant x pour fournir une valeur provisoire r' du reste, la valeur du reste r étant choisie (170) égale à r' si r'-q est négatif ou nul et égale à r'-q si r'-q est strictement positif. 'o 5. Dispositif de réduction modulaire selon la revendication 1, caractérisé en ce que la mémoire cache (420) reçoit en outre l'entier x et fournit en sus du résultat de pré-calcul relatif à une valeur du modulo q, une valeur de signe associé au couple (x,q) , cette valeur de signe étant fournie au circuit de Barrett. 15 6. Dispositif de réduction modulaire selon la revendication 5, caractérisé en ce que la mémoire cache comprend une première partie, dite mémoire d'étiquettes (510), et une seconde partie, dite mémoire de données (520), les première et seconde parties étant adressées par g (x,q) où g est une fonction de projection de 3n bits sur m bits avec 20 m 7. Dispositif de réduction modulaire selon la revendication 6, caractérisé en ce que le résultat du pré-calcul ainsi que la valeur de signe sont fournis directement par la mémoire cache (420) au circuit de Barrett (410) si le couple (x,q) est stocké dans la mémoire d'étiquettes, et sinon, le résultat du pré-calcul'u, est obtenu par le circuit de 18 division binaire (430) à partir de la valeur du modulo, q, et de la puissance de 2, la valeur du signe, b, étant obtenue à partir de la valeur du modulo, q, de l'entier, x, et du résultat du pré-calcul, le résultat du pré-calcul et la valeur de signe étant stockés dans la mémoire de données à l'adresse à calculer g (x,q) avant d'être fournis au circuit de Barrett. 5 8. Dispositif de réduction modulaire selon la revendication 2, caractérisé en ce qu'il comprend une seconde mémoire cache (625,725) recevant l'entier x et le modulo q et fournissant une valeur de signe b stockée à une adresse en relation avec le couple (x,q) , cette valeur de signe étant fournie au circuit de Barrett. 10 9. Dispositif de réduction modulaire selon la revendication 8, caractérisé en ce la seconde mémoire cache (625) comprend une seconde mémoire d'étiquettes et une seconde mémoire de données, ces secondes mémoires d'étiquettes et de données étant toutes deux adressées par h(x,q) où h est une fonction de projection de 3n bits sur m 15 bits avec m 10. Dispositif de réduction modulaire selon la revendication 9, caractérisé en ce que la valeur de signe est fournie directement par la seconde mémoire cache (625) au circuit de Barrett (610) si la valeur du modulo q est stockée dans la mémoire d'étiquettes et le couple (x,q) est stocké dans la seconde mémoire d'étiquettes, et sinon, la valeur du signe, b , est obtenue à partir de la valeur du modulo, q et de l'entier, x, la valeur de signe 25 étant ensuite fournie au circuit de Barrett. 11. Dispositif de réduction modulaire selon la revendication 8, caractérisé en ce que la seconde mémoire cache (725) comprend une seconde mémoire de données mais ne 19 comprend pas de mémoire d'étiquettes, un comparateur (750) pour vérifier si la sortie r du circuit de Barrett (710) vérifie la condition 0 r 12. Dispositif de réduction modulaire selon l'une quelconque des revendications 5 à 11, caractérisé en ce que le circuit de division binaire (430,630,730) effectue le pré- calcul ,u = 2'" où 2n" 2' le inférieur égal à 2"±a q est est plus grand entier ou ou est - q q - i 10 ladite puissance de 2 et a est un entier tel que a n+1. 13. Dispositif de réduction modulaire selon la revendication 12, caractérisé en ce que le circuit de Barrett (410,610,710) décale (810) de oe+16 bits le mot binaire représentant x vers les bits de poids faibles, où 16 est un entier tel que 16 -2, multiplie 15 (820) ensuite le mot ainsi décalé par le résultat du pré-calcul, du, puis décale (830) à nouveau de a- 16 bits le résultat de cette multiplication vers les bits de poids faibles pour obtenir un second mot, la valeur de signe étant soustraite (835) au second mot avant qu'il soit multiplié (840) par le modulo, le résultat de cette multiplication étant ensuite soustrait (850) à l'entier x pour donner ledit reste, r. 20