Brevet FR2885711A1 — publié le 20061117

PROCÉDÉ ET MATÉRIEL MODULAIRE ET ALÉATOIRE POUR LA RÉDUCTION POLYNOMIALE L'invention concerne des systèmes de traitement et de calculs arithmétiques et des procédés mis en oeuvre par ordinateur, spécialement pour une utilisation dans des applications de cryptographie. L'invention concerne en particulier une réduction modulaire impliquant l'arithmétique des résidus de polynômes dans un champ fini GF (2n), spécialement des calculs dérivés du procédé de réduction de Barrett. De nombreux algorithmes cryptographiques font usage d'une multiplication par un grand nombre entier (ou une élévation à une puissance) et une réduction du produit à une valeur des résidus qui est congruente pour un module spécifié qui est lié à la clé cryptographique. Certains algorithmes cryptographiques, comprenant le chiffrement par blocs AES/Rijndael et également ceux basés sur des algorithmes discrets et des courbes elliptiques, effectuent des opérations arithmétiques sur des polynômes dans un champ fini, tel que le champ binaire GF (2n), comprenant la multiplication (ou l'élévation à une puissance) et les opérations de réduction modulaires sur de tels polynômes. Les calculs mathématiques effectués par les systèmes cryptographiques peuvent être sujets à une analyse de puissance et des attaques de temporisation. En conséquence, il est important que les calculs soient sécurisés de sorte que les informations concernant la clé ne puissent pas être obtenues. Dans le même temps, il est important que ces calculs soient rapides et précis. La multiplication et la réduction, qu'elles soient mises en oeuvre sur des grands nombres entiers ou sur des polynômes dans un champ fini, 2885711 2 sont habituellement la partie la plus intensive, en termes de calculs, d'un algorithme cryptographique. Plusieurs techniques de calcul distinctes ont été développées pour une réduction modulaire efficace, comprenant celles connues comme le procédé de Quisquater, le procédé de Barrett et le procédé de Montgomery, conjointement avec des modifications impliquant un pré-calcul et une consultation de table. Ces techniques bien connues sont décrites et comparées dans l'art antérieur. Voir, par exemple: (1) A. Bosselaers et al., Comparison of three modular reduction functions , Advances in Cryptology/Crypto '93, LNCS 773, Springer-Verlag, 1994, pages 175 à 186. (2) Jean François Dhem, Design of an efficient public-key cryptographic library for RISC-based smart cards , doctoral dissertation, Université catholique de Louvain, Louvain-la-Neuve, Belgique, Mai 1998. (3) C. H. Lim et al., Fast Modular Reduction With Precomputation , preprint, 1999 (disponible auprès de CiteSeer Scientific Literature Digital Library, citeseer.nj.nec. com/109504.html). (4) Hollmann et al., Method and Device for Executing a Decrypting Mechanism through Calculating a Standardized Modular Exponentiation for Thwarting Timing Attacks", Brevet U.S. No. 6 366 673 B1, 2 avril 2002 (basé sur la demande déposée le 15 septembre 1998). Un objectif de la présente invention consiste à proposer une amélioration du procédé de réduction modulaire de Barrett et de l'appareil de calcul correspondant, spécialement tel qu'ils sont appliqués à des polynômes, qui est plus sûr contre les attaques de cryptanalyse, tout en fournissant encore des résultats rapides et précis. 2885711 3 Un autre objet de la présente invention consiste à proposer les procédé et appareil améliorés précités qui accélèrent l'estimation des quotients pour une utilisation dans la réduction modulaire de polynômes. Ces objectifs sont atteints par un procédé mis en oeuvre par ordinateur pour une réduction modulaire de polynômes dans un champ fini binaire GF (2 ) dans lequel un quotient de polynôme utilisé pour le calcul de réduction est estimé (au moins au degré de polynôme correct) en utilisant un inverse mis à l'échelle pré-calculé du module de polynôme comme multiplicateur. Le reste du polynôme résultant de la réduction est toujours congruent au produit intermédiaire correspondant relatif à un module de degré n de polynôme irréductible, mais est typiquement plus grand (en termes du degré du polynôme) que la valeur des résidus minimale et diffère de manière aléatoire pour chaque exécution. Du fait que l'erreur d'estimation est délibérément aléatoire, le procédé est plus sûr contre une cryptanalyse. Cependant, les résultats intermédiaires sont mathématiquement équivalents (congruents aux résultats vrais), et un résultat final peut être obtenu par traitement d'une réduction stricte finale sans aléation, atteignant ainsi la précision nécessaire pour l'aptitude à l'inversion des opérations cryptographiques. Le matériel utilisé pour exécuter les étapes du procédé de l'invention comprend un générateur de nombre aléatoire destiné à injecter une erreur aléatoire dans l'estimation des quotients. Une unité de calcul avec accès à la mémoire opère sous la commande d'un séquenceur d'opérations exécutant un micrologiciel pour réaliser les étapes à la largeur d'un mot d'accumulation de multiplications de multiplication polynomiale multimots 2885711 4 et de réduction modulaire. L'unité de calcul peut comprendre un matériel d'accumulation de multiplication dédié à des opérations de polynôme de champ fini, ou peut être choisie pour effectuer une arithmétique soit naturelle soit polynomiale. La présente invention concerne, dans un sens large, un procédé de réduction polynomiale modulaire sûr du point de vue cryptographique, mis en oeuvre par matériel informatique, dans le champ fini binaire GF (2 ), comprenant les étapes consistant à : pré-calculer et stocker en mémoire une constante polynomiale u(x), représentant un inverse mis à l'échelle du bit d'un module polynomial m(x) ; estimer un quotient polynomial approché q pour un polynôme p(x) à réduire modulo m(x), dans lequel ladite estimation est exécutée sur p(x) dans une unité de calcul par une multiplication polynomiale sur GF (2 ) par ladite constante u(x) et par des décalages de bits; générer dans un générateur de nombre aléatoire une valeur d'erreur polynomiale aléatoire E(x) et appliquer ladite valeur d'erreur polynomiale audit quotient polynomial approché pour obtenir un quotient polynomial aléatoire q'(x) = q(x) + E(x) ; et calculer un reste polynomial r'(x)=p(x)+q'(x).m(x) dans ladite unité de calcul, ledit reste r'(x) étant d'un degré supérieur audit module m(x), mais congruent à p(x) modulo m(x) et où le degré de p(x) est inférieur ou égal à 2k+1. Dans un mode de réalisation, le pré-calcul de ladite 30 constante polynomiale u(x) est effectué selon l'équation u(x) = x2k+"/m(x) . 2885711 5 Dans un mode de réalisation particulier, l'estimation du quotient q(x) est effectuée par l'unité de calcul selon l'équation q(x) = ((p(x)/xk-1).u(x))/xk+z. En particulier, lesdits décalages de bits sont des décalages de la taille du mot, la constante polynomiale est pré-calculée comme u (x) = x2k+'/m(x) et le quotient est estimé comme q(x) = ( (p(x) /xk-W) .u(x)) /xk+Z", où w est la taille du mot en bits, et où le degré de p(x) est inférieur ou égal à 2k + w. Dans un autre mode de réalisation, le générateur de nombre aléatoire a une limite d'erreur spécifiée d'un demi-mot, moyennant quoi 0 Selon un mode de réalisation, la réduction modulaire de p(x) fait partie d'un programme de cryptographie mis 15 en oeuvre par matériel informatique. L'invention concerne également un matériel de calcul destiné à exécuter un procédé de réduction modulaire polynomial sûr en termes de cryptographie sur un champ fini binaire GF (2n), le matériel comprenant: une unité de calcul adaptée pour effectuer des étapes d'accumulation et de multiplications de champ fini à la largeur d'un mot sur des opérandes polynomiaux récupérés à partir d'une mémoire et des résultats intermédiaires de coefficients polynomiaux à partir d'un ensemble de registres de travail; un générateur de nombre aléatoire destiné à générer une valeur d'erreur polynomiale aléatoire E(x) ; un séquenceur d'opérations comprenant un circuit logique destiné à commander l'unité de calcul et un générateur de nombre aléatoire en accord avec les instructions de programme de façon à réaliser une réduction modulaire polynomiale d'un nombre p(x) par rapport à un module m(x) sur un champ fini binaire GF (2n) 2885711 6 qui implique au moins une estimation d'un quotient polynomial q(x) à partir d'une constante polynomiale pré-stockée u(x) représentant un inverse, mis à l'échelle du bit, du module, une aléation dudit quotient polynomial approché avec ladite valeur d'erreur polynomiale aléatoire E(x) pour obtenir un quotient polynomial aléatoire q'(x) = q(x) + E(x), et un calcul d'une valeur de reste polynomiale r'(x) = p(x) + q'(x).m(x). Dans un mode de réalisation, le matériel de calcul comprend en outre des registres de paramètre d'opération accessibles par ledit séquenceur d'opérations, lesdits registres contenant un ou plusieurs parmi (a) des pointeurs destinés à placer les coefficients de la taille d'un mot d'opérandes polynomiaux au sein de ladite mémoire ou des registres de travail, (b) des informations concernant les longueurs des mots des opérandes polynomiaux, et (c) des informations d'adresses de destination pour des résultats intermédiaires d'étapes d'opération. Dans un autre mode de réalisation, la constante polynomiale u(x) préstockée dans ladite mémoire est obtenue à partir d'un pré-calcul selon l'équation u(x) = xZk+W/m(x) , w étant la taille du mot de l'unité de calcul en bits. En particulier, l'estimation dudit quotient polynomial approché q effectuée par ladite unité de calcul sous la commande dudit séquenceur d'opérations réalisant des instructions de programme est effectuée selon l'équation q' (x) = ( (p(x) Éxk-W) Éu(x))/xk+2'. 2885711 7 Plus précisément, le générateur de nombre aléatoire a une limite d'erreur spécifiée d'un demi-mot, moyennant quoi 0 La figure 1 est une vue en plan schématique d'un 5 matériel de calcul en accord avec la présente invention (comprenant une unité de générateur de nombre aléatoire), qui est utilisé pour exécuter le procédé de réduction modulaire de la présente invention. La figure 2 est un organigramme illustrant les 10 étapes générales dans le présent procédé de réduction modulaire. En référence à la figure 1, un matériel de calcul comprend une unité de calcul 10 qui est capable d'effectuer des étapes à la largeur d'un mot de champ fini de multiplication et d'accumulation de multiplications sur des opérandes polynomiaux récupérés à partir d'une mémoire (RAM) 12 et de registres de travail 14. Les registres 14 peuvent être les mêmes registres matériels qui seraient responsables de la réalisation d'une injection dans des opérations normales de nombre entier. Un séquenceur d'opérations 16 comprend un circuit logique destiné à commander l'unité de calcul 10 en accord avec des instructions de micrologiciel ou de logiciel pour que l'ensemble d'opérations réalise la multiplication polynomiale multi-mots de champ fini (ou élévation à une puissance) et la réduction modulaire en utilisant une base polynomiale irréductible. Les paramètres d'opération, stockés dans les registres 18 accessibles par le séquenceur d'opérations 16, consistent en des pointeurs qui permettent au séquenceur d'opérations de placer un opérande au sein de la RAM 12, de même que des informations concernant les longueurs 2885711 8 (nombre de mots) des opérandes et l'adresse de destination des résultats intermédiaires. Tel que décrit jusqu'ici, l'appareil est sensiblement similaire à d'autres matériels disponibles adaptés pour des opérations arithmétiques polynomiales multi-mots. L'arithmétique polynomiale réalisée dans le champ fini binaire GF (2n) diffère d'une arithmétique naturelle en ce qu'elle ignore les retenues et en équivalence de l'addition et de la soustraction. L'unité de calcul peut comprendre un matériel d'accumulation de multiplications dédié à des opérations polynomiales de champ fini, ou peut être un matériel arithmétique naturel/polynomial à fonction double qui peut être choisi pour effectuer une arithmétique soit naturelle soit polynomiale. Hormis les détails des étapes de réduction, que l'on décrira ci-dessous, les instructions de micrologiciel ou de logiciel sont également similaires à des programmes antérieurs destinés à exécuter une multiplication polynomiale multi-mots ou élévation à une puissance efficaces dans des segments à la largeur d'un mot. À l'opposé des matériels antérieurs de ce type, le matériel de la figure 1 comprend également un générateur de nombre aléatoire 20 qui, par exemple, peut être tout circuit générateur de nombre pseudo-aléatoire connu. Le générateur de nombre aléatoire effectue un calcul et sort un nombre aléatoire dont les bits sont interprétés comme les coefficients binaires d'un polynôme aléatoire à utiliser dans le présent procédé. Ici, on accède au générateur de nombre aléatoire 20 par l'unité de calcul 10, comme dirigé par le séquenceur d'opérations 16 en accord avec les instructions de programme mettant en oeuvre le procédé de la présente invention, afin 2885711 9 d'injecter la quantité d'erreur aléatoire dans l'estimation des quotients, comme décrit ci-dessous. En référence à la figure 2, le procédé de la présente invention est une amélioration de la technique de la réduction modulaire de Barrett, fournissant une estimation des quotients plus rapide et une résistance à une attaque cryptanalytique, et applique la technique de réduction modulaire à des polynômes dans le champ fini binaire GF (2'). Le procédé est exécuté par le matériel de la figure 1. L'arithmétique modulaire avec les polynômes est similaire sous divers aspects à l'arithmétique modulaire avec des nombres entiers, bien que son extension à des polynômes sur un champ fini binaire GF (2n) requière certaines modifications de l'opération basique. Introduisons tout d'abord des polynômes sur un champ. À tout multiple (am_l, ..., al, a ) d'éléments d'un champ F, nous pouvons associer un polynôme en x de degré (m-1) : am-lxm-1 + alxl + a x . Dans le cas de tout champ fini binaire, les éléments du champ sont {0,1} et ainsi les coefficients polynomiaux al sont de même 0 ou 1. Ce concept s'adapte particulièrement bien au matériel informatique, qui est binaire par nature, puisque chaque bit peut être interprété comme un élément de champ fini. À titre d'exemple, nous pouvons associer chaque valeur d'octet binaire [a, a6 a5 a4 a3 a2 al a ] avec un polynôme correspondant sur GF (2n) de degré 7 (ou moins) : a,x7 + a6x6 + a5x5 + a4x4 + a3x3 + a2x2 + alx + a . De ce fait, par exemple, la valeur d'octet [01100011] est interprétée comme le polynôme binaire x6 + x5 + x + 1. Des séquences multi-octets plus longues peuvent de même être interprétées comme des polynômes de degré supérieur à condition que, sur le champ fini binaire GF (2n), le 2885711 10 degré (m-1) du polynôme soit inférieur à n, afin que le polynôme appartienne à ce champ. (Note: lors de la comparaison des tailles relatives du polynôme, la comparaison est effectuée degré par degré, en commençant avec le coefficient du polynôme de degré le plus élevé en x). L'addition et la soustraction de polynômes dans un champ sont réalisées de la manière habituelle consistant à ajouter ou soustraire les coefficients pour chaque degré séparément, a xi E bix1 = E (ai b1) x Toutefois, pour chaque champ binaire, les éléments sont {0, 1}, de sorte que l'addition et la soustraction des éléments de champ sont effectuées modulo 2 (0 0 = 0, 0 1= 1 0 = 1, 1 1 = 0). On notera, dans ce cas, que la soustraction est identique à l'addition. informatique, l'addition/soustraction effectuée via une opération logique OU réseau des bits. À titre d'exemple, (x6+ + (x7 + x + 1) _ (x7 + x6 + x4 + x2) ; Dans le matériel modulo 2 est exclusif sur le 4 + xz x + x + 1) ou en notation binaire [01010111] O+ [10000011] = [11010100]. La multiplication polynomiale est ordinairement définie (pour des champs infinis) par: où le coefficient ck est donné k par la convolution: ck= aibj. (De nouveau, dans un champ binaire, la i+j=k sommation est effectuée modulo 2. Toutefois, dans un champ fini, cette définition doit 30 être modifiée afin de s'assurer que le produit ) 2885711 11 appartienne également au champ. En particulier, une multiplication polynomiale ordinaire est suivie par une réduction modulaire par un module m(x) de degré n (où n est la dimension du champ fini, comme dans GF (2n)) . Le module m(x) est de préférence choisi comme étant un polynôme irréductible (le polynôme analogue d'un nombre premier, à savoir un polynôme qui ne peut pas être factorisé en des polynômes non évidents sur le même champ). À titre d'exemple, dans le chiffrement par blocs AES/Rijndael, les opérations sont effectuées sur des octets (polynômes de degré 7 ou moins) dans le champ fini binaire GF (28), en utilisant le polynôme irréductible particulier m(x) = x8 + x4 + x3 + x + 1 comme la base choisie pour une réduction modulaire lors de la réalisation d'une multiplication polynomiale. Comme exemple de multiplication polynomiale dans un champ fini binaire utilisant le m(x) particulier spécifié pour AES: (x6 + x4 + x2 + x + 1) . (x7 + x + 1) = (x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + 1) , qui après réduction, donne (x7 + x6 + 1). Soit F[x] l'ensemble des polynômes dont tous les coefficients sont des éléments d'un champ F. Si le module m(x) est un polynôme de degré d dans F[x], alors pour les polynômes p(x), r(x) E F[x], on peut dire que p(x) est congruent à r(x) modulo m(x), écrit p(x) r(x) (mod m(x)), si et seulement si m(x) divise le polynôme et p(x)-r(x) ; en d'autres termes, p(x) - r(x) est un polynôme multiple de m(x), à savoir p(x) - r(x) = q(x). m(x) pour un certain polynôme q(x) E F[x]. De manière équivalente, p(x) et r(x) ont le même reste lors de la division par m(x). La réduction modulaire d'un polynôme p(x), qui pourrait être un produit ordinaire des polynômes a(x) et b(x) dans F[x], à 2885711 12 savoir p(x) = a(x).b(x), implique de chercher un quotient polynomial q(x) de sorte que le reste ou résidu r(x) est un polynôme de degré inférieur à m(x), à savoir deg(r(x)) Le procédé de Barrett, envisagé à l'origine pour des opérations de réduction de nombres entiers, implique le pré-calcul et le stockage d'une estimée mis à l'échelle de l'inverse du module, U, et le remplacement de la longue division par des multiplications et des décalages de mots ou de bits (en divisant par x) afin d'estimer le quotient. Avec un choix approprié des paramètres, l'erreur dans l'estimée du quotient est au plus de deux. La présente invention adapte le procédé de Barrett à la réduction modulaire d'un polynôme dans un champ fini binaire et améliore également le procédé de Barrett avec une estimation plus rapide du quotient et par une injection intentionnelle d'une erreur aléatoire dans le 2885711 13 quotient avant le calcul du reste. Le reste aléatoire résultant sera légèrement plus grand que (en termes de degré polynomial), mais congruent avec, la valeur de résidu. Soit k la taille du module polynomial m(x) en degré, où k m(x) = i-o mi. xi, avec mk = 1, mi E {0,1} pour k-1 0 et soit p(x) le polynôme à réduire, jusqu'au degré I, où se p(x) = i-0 pj.x', avec pi E {0,1} pour j 0 deg(p(x) s 2.k + 1 Commençons par le pré-calcul et le stockage (étape 30 sur la figure 2) d'un polynôme constant u(x) 20 représentant l'inverse mis à l'échelle du module m(x) u(x) = x21 '/m(x) Cette valeur stockée est ensuite ultérieurement utilisée dans toutes les opérations de réduction polynomiale pour ce module particulier m(x). u(x) est toujours de degré k pour chaque module m(x) de sorte que ça n'est pas une simple puissance de x. Pour effectuer une réduction modulo de p(x), on 30 estime un quotient polynomial q(x) (étape 32) en utilisant la valeur stockée u(x) : 14 q(x) = ( (p(x)/xk-1) Éu(x))/xk+2 Pour un module m(x) de degré élevé (multi-mot) , l'opération peut être effectuée avec des décalages de mot plutôt que des décalages de bit. Avec une taille de mot w, on peut définir u(x) = x2k+"/m(x) et estimer un quotient q(x) = ( (p(x)/xk-") . u(x))/xk+2". Dans ce cas, le polynôme p(x) peut avoir un degré légèrement plus grand: deg(p(x)) À ce stade (étape 36), une erreur polynomiale aléatoire E(x) est injectée dans le quotient polynomial calculé pour obtenir un quotient aléatoire, q'(x) = q(x) + E(x). L'erreur polynomiale aléatoire E(x) peut être générée (étape 34) par tout générateur de nombre aléatoire ou pseudo- aléatoire connu (matériel ou logiciel), où la valeur binaire générée est interprétée comme polynôme de la manière déjà décrite ci-dessus. La seule contrainte est que le degré polynomial de l'erreur se situe dans une gamme spécifiée, telle que 0 s deg(E(x)) Ensuite, on calcule (étape 38) le reste r'(x), qui sera congruent (module m(x)) avec la valeur de résidu 5 r(x) : r'(x) = p(x) + q'(x).m(x) Du fait qu'une erreur polynomiale aléatoire E est introduite dans le quotient polynomial q(x), le reste calculé r'(x) sera légèrement plus grand en degré que le module m(x). Le reste r'(x) peut être utilisé dans des calculs supplémentaires, dont le résultat, si nécessaire, peut de nouveau être réduit. (L'erreur reste délimitée.) En variante, en fonction des besoins de l'application particulière, le résidu r(x) peut être calculé à partir du reste r'(x) en appliquant une réduction polynomiale ordinaire GF (2n) avec le module m(x) pour obtenir une valeur polynomiale plus petite que m(x). L'aléation de la réduction modulaire confère une sécurité contre diverses attaques cryptanalytiques qui reposent sur la cohérence en utilisation de puissance pour déterminer le module. Ici, la réduction polynomiale de champ binaire de p(x) modulo m(x) varie de manière aléatoire d'une exécution à la suivante, tout en produisant encore un reste intermédiaire r'(x) qui est congruent. La séquence de réduction polynomiale de champ binaire à la fin de la génération d'une valeur de résidu finale r(x) varie également de manière aléatoire d'une exécution à la suivante du fait qu'elle opère sur différents restes r'(x). Le polynôme p(x) à réduire de 2885711 16 cette manière peut être obtenu à partir d'une variété de différentes opérations arithmétiques, comprenant la multiplication, la mise au carré, l'élévation à une puissance, l'addition, etc. De même, le module m(x) à utiliser peut être dérivé d'une variété de manières, le plus habituellement en cryptographie à partir d'une clé. Le procédé de réduction modulaire aléatoire de la présente invention est utile dans de nombreux algorithmes cryptographiques qui reposent sur de telles réductions polynomiales de champ binaire GF (2n), comprenant le chiffrement par blocs symétriques Rijndael/AES, de même que des systèmes de cryptographie discrets à base d'algorithmes à clé publique. 17 REVENDICATIONS 1. Procédé de réduction polynomiale modulaire mis en oeuvre par matériel informatique, sûr du point de vue cryptographique, dans le champ fini binaire GF (2n), caractérisé en ce qu'il comprend les étapes consistant à : pré-calculer et stocker en mémoire une constante polynomiale u(x) représentant un inverse mis à l'échelle du bit d'un module polynomial m(x) ; estimer un quotient polynomial approché q pour un polynôme p(x) à réduire modulo m(x), dans lequel ladite estimation est exécutée sur p(x) dans une unité de calcul par une multiplication polynomiale sur GF (2 ) par ladite constante u(x) et par des décalages de bits; générer dans un générateur de nombre aléatoire une valeur d'erreur polynomiale aléatoire E(x) et appliquer ladite valeur d'erreur polynomiale audit quotient polynomial approché pour obtenir un quotient polynomial aléatoire q'(x) = q(x) + E(x) ; et calculer un reste polynomial r'(x) = p(x) + q'(x). m(x) dans ladite unité de calcul, ledit reste r'(x) ayant un degré supérieur audit module m(x) mais congruent à p(x) modulo m(x) et où le degré de p(x) est inférieur ou égal à 2k+1. 2. Procédé selon la revendication 1, caractérisé en ce 25 que le précalcul de ladite constante polynomiale u(x) est effectué selon l'équation u(x) = x2k+W/m(x). 3. Procédé selon la revendication 2, caractérisé en ce que l'estimation du quotient q(x) est effectué par 30 l'unité de calcul selon l'équation q(x) = ( (p(x)/xk-1) Éu(x))/xk+2. 2885711 18 4. Procédé selon la revendication 1, caractérisé en ce que lesdits décalages de bit sont des décalages de la taille d'un mot, la constante polynomiale est pré- calculée comme u (x) = xzk+W/m(x) et le quotient est estimé comme q(x) = p(x) /xk-").u(x)) /xk+z", où w est la taille de mot en bits, et où le degré de p(x) est inférieur ou égal à 2k + w. 5. Procédé selon la revendication 4, caractérisé en ce que le générateur de nombre aléatoire a une limite d'erreur spécifiée d'un demi-mot, moyennant quoi 0 6. Procédé selon la revendication 1, caractérisé en ce que la réduction modulaire de p(x) est une partie d'un programme de cryptographie mis en oeuvre par matériel informatique. 7. Matériel de calcul destiné à exécuter un procédé de réduction modulaire polynomial sûr du point de vue cryptographique sur un champ fini binaire GF (2n), le matériel étant caractérisé en ce qu'il comprend: une unité de calcul adaptée pour effectuer des étapes de multiplication et d'accumulation de champ fini à la largeur d'un mot sur des opérandes polynomiaux récupérés à partir d'une mémoire et des résultats intermédiaires de coefficients polynomiaux à partir d'un ensemble de registres de travail; un générateur de nombre aléatoire destiné à générer une valeur d'erreur polynomiale aléatoire E(x) ; un séquenceur d'opérations comprenant un circuit logique destiné à commander l'unité de calcul et un 2885711 19 générateur de nombre aléatoire en accord avec des instructions de programme de façon à réaliser une réduction modulaire polynomiale d'un nombre p(x) par rapport à un module m(x) sur un champ fini binaire GF (2n) qui implique au moins une estimation d'un quotient polynomial q(x) à partir d'une constante polynomiale pré-stockée u(x) représentant un inverse mis à l'échelle du bit du module, une aléation dudit quotient polynomial approché avec ladite valeur d'erreur polynomiale aléatoire E(x) pour obtenir un quotient polynomial aléatoire q'(x) = q(x) + E(x), et un calcul d'une valeur de reste polynomial r'(x) = p(x) + q'(x).m(x). 8. Matériel de calcul selon la revendication 7, caractérisé en ce qu'il comprend en outre des registres de paramètre d'opération accessibles par ledit séquenceur d'opérations, lesdits registres contenant un ou plusieurs quelconques parmi (a) des pointeurs destinés à placer des coefficients de la taille d'un mot d'opérandes polynomiaux à l'intérieur de ladite mémoire ou des registres de travail, (b) des informations concernant les longueurs de mot d'opérandes polynomiaux, et (c) des informations d'adresses de destination pour des résultats intermédiaires d'étapes de fonctionnement. 9. Matériel de calcul selon la revendication 7, caractérisé en ce que la constante polynomiale pré-stockée u(x) dans ladite mémoire est obtenue à partir d'un pré-calcul selon l'équation u(x) = x2k+'/m(x), w étant la taille de mot de l'unité de calcul en bits. 10. Matériel de calcul selon la revendication 9, caractérisé en ce que l'estimation dudit quotient 2885711 20 polynomial approché q effectué par ladite unité de calcul sous la commande dudit séquenceur d'opérations réalisant des instructions de programme est effectuée selon l'équation q' (x) = ( (p(x) .xk-W) .u(x)) /xk+2W. 11. Matériel de calcul selon la revendication 10, caractérisé en ce que le générateur de nombre aléatoire a une limite d'erreur spécifiée d'un demi-mot, moyennant quoi 0 5 deg(E(x))