Soutenance mémoire
Un système non positionnel de représentation des nombres
L’existence des systèmes de représentation des nombres par les restes est une conséquence du théorème des restes chinois (TRC). Des prémisses de ce résultat remontant aux premiers siècles de notre ère ont trait à des considérations portant sur une résolution heuristique de systèmes d’équations congruentielles. De nombreuses études sur l’Histoire des Mathématiques montrent comment ces considérations arithmétiques ont été particulièrement persistantes à travers les siècles et les civilisations (Ing 2003, Kangsheng 1988, Lam et Ang 2004). L’un des témoignages emblématiques se retrouve dans l’énoncé d’un problème issu d’un traité mathématique chinois du troisième siècle de notre ère et intitulé « Sun Zi Suanjing ». Une traduction anglaise est disponible dans (Ing 2003). « Now there are an unknown number of things. If we count by threes, there is a remainder 2 ; if we count by fives, there is a remainder 3 ; if we count by sevens, there is a remainder 2. Find the number of things. » En l’état actuel, ce théorème se décline en plusieurs versions à caractère plus ou moins général. Il décrit des relations riches entre certains anneaux quotients, qui vont notamment permettre de construire des systèmes de représentation des nombres particuliers, les Residue Number Systems (RNS). Ceuxci, apparus dans les années 50 (Garner 1959), n’ont eu de cesse de croître en popularité, notamment au sein de la communauté centrée sur le traitement du signal (Jenkins et Leon 1977, Soderstrand et al. 1986, Conway et Nelson 2004). Cet intérêt est fondé sur la possibilité donnée par le RNS de passer du paradigme arithmétique traditionnel de l’anneau des nombres entiers Z à un paradigme différent, au sein duquel les entiers deviennent représentables par de petites quantités indépendantes les unes des autres. Il devient même possible de transposer simplement les opérations arithmétiques standards d’addition et de multiplication directement sur ces petites unités. De ce fait, des opérations comme les « sommes de produits », qui sont un schéma calculatoire récurrent dans le traitement du signal notamment (transformée de Fourier rapide (FFT), etc), peuvent être réalisées très efficacement (Tseng et al. 1979, Huang et Taylor 1980, Taylor 1990). De plus, le RNS est un candidat compétitif concernant les problématiques d’implantation matérielle à basse consommation d’énergie (Freking et Parhi 1997, Stouraitis et Paliouras 2001), point essentiel pour réaliser des implantations sur matériel embarqué par exemple. Nous allons introduire une formulation de ce théorème, qui apporte la première pierre dans la construction des RNS. Comme il est question de relations entre des anneaux quotients, il est important de fixer dès à présent les notations suivantes.
Le RNS comme contre-mesure aux attaques par canaux auxiliaires
Les attaques par canaux auxiliaires (Side Channel Attacks, SCA) sont une sérieuse menace pour les cryptosystèmes implantés sur des matériels embarqués. Afin de recouvrer de l’information concernant des données secrètes, ces attaques reposent sur l’exploitation de caractéristiques mesurables depuis l’« extérieur », comme le temps d’exécution (Timing Attacks, Kocher (1996), Brumley et Boneh (2003)), ou encore la mesure de l’énergie consommée ou des émissions électromagnétiques (Simple Power Analysis). Ceci permet par exemple sur des implantations non protégées de RSA de lire directement les bits de l’exposant secret en exploitant la différence de consommation entre une multiplication et un carré modulaires. Pour contrer ce type d’attaque, il est possible de « lisser » les traces relevées en utilisant un algorithme adéquat d’exponentiation modulaire, comme l’échelle de Montgomery (Joye et Yen 2003). D’autres types d’attaques se basent sur l’exploitation d’un ensemble de traces et consistent en une analyse statistique qui doit permettre d’extraire certaines corrélations entre les grandeurs mesurées et les données traitées en interne. C’est le cas par exemple de la Differential Power Analysis (Kocher et al. 1999; 2011, Coron 1999, Goubin 2002) concernant la mesure de consommation d’énergie, ou encore des attaques par analyse différentielle basées sur la mesure des émissions électromagnétiques (Gandolfi et al. 2001, Agrawal et al. 2003). Les contre-mesures classiques pour les attaques différentielles reposent en général sur un masquage aléatoire des données.
Vers une multiplication modulaire résistante aux fautes uniques
Disposer d’un algorithme de multiplication modulaire résistant aux attaques par canaux cachés et aux attaques par injection de faute est primordial en cryptographie. L’état-de-l’art de la cryptanalyse démontre que la multiplication modulaire est un point très sensible, puisqu’elle est l’opération cœur de cryptosystèmes comme le RSA ou le protocole d’échange de clés de DiffieHellman. Dans l’optique de faire du RNS un candidat de premier plan pour une arithmétique adaptée à la cryptographie et à ses contraintes, la question de fournir un algorithme de multiplication modulaire protégé efficacement contre les attaques par canaux auxiliaires est donc centrale. Dans un premier temps, la création d’une arithmétique résistante aux fuites (Bajard et al. 2004) basée sur le RNS a permis de poser les premiers jalons de ce projet. La possibilité de choisir aléatoirement les bases RNS B et B1 utilisées permet un masquage des données traitées via la représentation de Montgomery. Le point central est qu’il a été montré qu’il est possible de changer les bases RNS à la volée très efficacement puisque le calcul des nouvelles représentations de Montgomery qui découlent de ce nouveau choix de bases se réalise simplement par le biais de deux multiplications modulaires RNS consécutives (2.1) et (2.2). Ceci permet notamment de créer un algorithme d’exponentiation modulaire enrichi d’un masquage aléatoire et évolutif des données. Dans un second temps, nous avons vu que les RNS redondants sont une solution efficace pour la protection contre les injections de fautes sur les résidus. Suivant le niveau de protection adopté et relié directement à la quantité de redondance introduite, la détection a cependant le désavantage d’avoir un coût non négligeable qui est celui de la conversion de base utilisée pour la procédure de détection. Dans un contexte d’optimisation des calculs cryptographiques, il est donc naturel de chercher à insérer au mieux les procédures de détection dans les schémas de calcul afin de limiter leur influence sur le temps total des calculs.
De la représentation des effets de fautes physique dans le modèle théorique
L’architecture Cox-Rower de Kawamura et al. (2000) dispose d’un certain nombre de cellules de traitement, les Rowers, chacune étant dédiée aux calculs dans les canaux RNS « théoriques » Z{mZ. En pratique, dans le cas de la réduction modulaire RNS utilisant deux bases B et B1, chaque Rower est généralement alloué à au moins un modulus de B et un modulus de B1 . Comme les calculs dans B et B1 se font de manière séquentielle lors d’une réduction modulaire (i.e. selon un schéma B Ñ B 1 Ñ B), la pertinence de la restriction du nombre de Rowers à maxpCardpBq, CardpB1 qq s’impose d’elle-même. En revanche, lorsque les contraintes de surface ne permettent pas d’avoir autant de Rowers, chacun d’eux peut alors être affecté à plusieurs canaux de chacune des deux bases. Un état de l’art fournit par Barenghi et al. (2012) détaille les moyens dont peut disposer un attaquant pour injecter des fautes dans l’ensemble des valeurs traitées par système physique embarquant l’implantation d’une primitive cryptographique. La puissance de l’adversaire s’évalue essentiellement par les moyens financiers dont il dispose pour monter son attaque. Par exemple, ceux ci influent directement sur la capacité à viser une zone précise du matériel (cf. tableau 1 de Barenghi et al. (2012)). Plus généralement, les effets à prendre en compte sont multiples (Otto 2004) : localisation spatiale, contrôle du timing, faute permanente ou transitoire, etc. Cependant, ce genre de classification ne peut véritablement s’appliquer tel quel à nos propos. En fait, il s’agit de voir qu’il nous suffit de considérer que toute faute induite par une attaque physique est intégrable à notre modèle de l’instant où l’effet d’une telle faute peut se réduire à une faute sur une sortie d’un Rower. Par exemple, une attaque modifiant tout ou partie de précalculs contenus dans une ROM, de manière permanente ou non, s’intègre à notre modèle de l’instant où les valeurs modifiées ne concernent qu’un canal RNS Z{mZ. Que de telles fautes soient permanentes ou transitoires n’a pas véritablement de conséquence à cause du fait que la détection est réalisée systématiquement à la fin de chaque réduction modulaire. Même dans le cas d’une réduction fainéante, où une réduction modulaire n’intervient qu’après le calcul d’une somme plus ou moins grande, l’effet d’une faute permanente est aisément contenu grâce au fait que l’indépendance des canaux RNS n’est brisée qu’au moment d’une réduction modulaire. Les considérations précédentes mettent également en lumière la nécessité de l’Hypothèse 2.2 (p. 62). Lors d’une conversion de base, chaque Rower distribue sa sortie aux autres. Cette phase peut être réalisée simplement via l’utilisation d’un registre à décalages envoyant séquentiellement les valeurs. Cependant, un problème surgit du fait que tout ou partie des sorties distribuées transitent par de mêmes registres. Dans ce cas précis, une faute modifiant de manière permanente ne serait-ce qu’un bit de registre va possiblement impacter sur la valeur de plusieurs résidus, brisant de fait le modèle de faute unique. L’utilisation d’un multiplexeur, ou la redondance de la totalité des registres sont des solutions de protection possibles. Pour résumer, la pertinence du cadre fixé par notre modèle de faute repose sur l’indépendance des unités RNS lors des calculs arithmétiques de base, ainsi que sur le fait que notre détection intervient systématiquement à chaque fois que cette indépendance est levée, à savoir lors d’une réduction modulaire. Les solutions de protection pouvant permettre de lever l’Hypothèse 2.2 ne feront pas nécessairement partie du cœur des propos qui suivront. En revanche, l’adaptation de notre solution de détection de faute doit absolument intégrer les conséquences de la contrainte inévitable de représentation des résidus en binaire.
Réseaux et cryptosystèmes de type GGH
Outil efficace pour la cryptanalyse (Nguyen et Stern 2001), les réseaux prennent une importance croissante en cryptographie asymétrique. La sécurité des cryptosystèmes à base de réseaux s’est initialement reposée sur la difficulté de la résolution de problèmes comme la recherche de vecteurs courts ou de vecteurs proches. En 1996, Ajtai a montré que la résolution de tels problèmes pour des instances moyennes n’est pas plus simple que celle des instances les plus difficiles, renforçant de fait les notions de sécurité utilisées dans ce domaine. Les réseaux tiennent une place de choix en tant que solution face à des problématiques cryptographiques actuelles et futures. Dans le paradigme de l’informatique quantique, alors que les problèmes de factorisation et de logarithme discret peuvent être résolus en temps polynomial (Shor 1994), la complexité des problèmes liés aux réseaux n’est pour le moment pas remise en cause. Les réseaux offrent ainsi un cadre de choix pour une cryptographie postquantique. Enfin, la découverte des propriétés de chiffrement complètement homomorphe offertes par les réseaux (Gentry 2009) a marqué une avancée majeure. Permettant de transposer l’exécution d’additions et de multiplications sur les chiffrés, cette propriété place ainsi la cryptographie à base de réseaux au plus près des enjeux de sécurité à l’ère du « cloud computing ». Le principe des cryptosystèmes de type GGH est introduit en 1997 par Goldreich et al.. Ils sont construits sur le problème de la recherche d’un proche vecteur. Au fil des années, les cryptanalyses successives ont amené à modifier les paramètres de ces systèmes, notamment la dimension des réseaux utilisés, les rendant alors chaque fois plus couteux à utiliser en pratique. Néanmoins, leur principe même de fonctionnement reste d’actualité. Nous décrivons celuici dans cette section, tout de suite après de premières considérations sur les réseaux.
|
Table des matières
Introduction
1 Les systèmes de représentation par les restes
1.1 Les Systèmes de Représentation par les Restes
1.1.1 Un système non positionnel de représentation des nombres
1.1.2 Notations et termes spécifiques aux RNS
1.2 RNS et opérations arithmétiques élémentaires, éléments de complexité
1.2.1 Opérations élémentaires
1.2.2 Influence du RNS sur les bornes de complexité
1.2.3 Sur le choix des moduli
1.2.4 Un système positionnel associé, le Mixed Radix System (MRS)
1.3 Conversions de bases et réduction modulaire RNS
1.3.1 Extensions/Conversions de base
1.3.2 Réduction modulaire en RNS
1.4 RNS et arithmétique dans Fps
1.4.1 Représentation des éléments de Fps
1.4.2 Réduction modulaire de Montgomery dans Fps
Conclusion
2 Protection contre les attaques par faute
2.1 Une arithmétique robuste pour la cryptographie asymétrique
2.1.1 Le RNS comme contre-mesure aux attaques par canaux auxiliaires
2.1.2 Sensibilité des cryptosystèmes asymétriques aux attaques par injection de fautes
2.2 RNS redondants
2.2.1 Définitions
2.2.2 Modèle de faute unique
2.2.3 Redondance nécessaire et suffisante pour la détection des fautes uniques
2.2.4 Théorème fondamental de détection pratique de faute unique
2.3 Vers une multiplication modulaire résistante aux fautes uniques
2.3.1 Adéquation du modèle de faute unique pour la multiplication modulaire RNS
2.3.2 Catégories de fautes – Localisation
2.3.3 Algorithme de réduction modulaire RNS avec capacité de détection de faute unique
2.3.4 Adéquation de l’Algorithme 13 avec la contre-mesure LRA (Bajard et al. 2004)
2.4 Concernant une adaptation à l’architecture Cox-Rower
2.4.1 Considérations pragmatiques sur la pertinence du modèle de faute théorique
2.4.2 Raffinement du modèle de faute
2.4.3 Comparaison avec la technique de détection de Guillermin (2011)
Conclusion
3 Vers une arithmétique RNS dans Fp et Fps résistante aux fautes multiples
3.1 De la détection des fautes multiples
3.1.1 RNS redondants et fautes multiples
3.1.2 Application à la multiplication modulaire RNS
3.1.3 Adaptation à l’architecture Cox-Rower
3.2 Arithmétique protégée pour les calculs dans Fps
3.2.1 Modèle de faute
3.2.2 Détection des fautes multiples
3.2.3 Multiplication modulaire redondante dans Fps
3.2.4 Algorithme proposé, preuve de correction
3.2.5 Comparaison avec la multiplication modulaire redondante de Medoš et Bozta¸s (2008)
Conclusion
4 Contribution à une optimisation arithmétique de la cryptographie asymétrique basée sur les réseaux
4.1 Réseaux et cryptosystèmes de type GGH
4.1.1 Définitions de base et considérations générales
4.1.2 Les cryptosystèmes de type GGH
4.2 De l’adaptation du round-off au RNS
4.2.1 Reformulation adaptée pour le RNS
4.2.2 Du calcul exact de 2cR1 dmod p2dqmod mσ en RNS
4.2.3 Schéma général d’un algorithme RNS-MRS pour la résolution du CVP
4.3 Technique d’accélération applicable à certaines bases
4.3.1 Stratégie nouvelle pour un round-off RNS
4.3.2 Recherche de paramètre et bases concernées
4.3.3 Un algorithme entièrement RNS pour la résolution du CVP
Conclusion
Conclusion générale
Télécharger le rapport complet
