Soutenance mémoire
La cryptographie asymétrique
La cryptographie asymétrique repose sur la notion de fonction à sens unique à trappe, c’est à dire une fonction facile à calculer dans un sens, mais dont l’inverse est très difficile à calculer sans avoir la clé correspondant à la trappe [38]. Une inversion de la fonction sans clé est censée être impossible, ou du moins à un coût « raisonnable » par rapport à l’application visée. On peut par exemple estimer que pour certaines applications, une résistance aux meilleures attaques connues nécessitant plusieurs années sur plusieurs centaines de machines est suffisante. D’un autre côté, pour certaines applications relevant du secret défense, des informations doivent rester confidentielles pour des dizaines d’années, ce qui est aujourd’hui difficile à garantir. Grâce aux fonctions à sens unique à trappe, on peut définir des protocoles tels que ceux de Diffie-Hellman [38], qui permettent à deux interlocuteurs d’échanger une clé commune. Une autre utilisation est la signature numérique, par exemple les standards Digital Signature Algorithm (DSA) et Elliptic Curve Digital Signature Algorithm (ECDSA) de l’institut américain National Institute of Standards and Technology (NIST) [91]. Ce type de cryptographie est aussi appelé à clé publique car elle ne nécessite pas de clé secrète partagée au préalable par les deux interlocuteurs. Les travaux de Diffie et Hellman [38], puis de Rivest, Shamir et Adleman [102] font parti des pionniers de la cryptographie asymétrique, et sont toujours très utilisés dans les systèmes de sécurité actuels. On compte aussi parmi ces pionniers Clifford Cocks, qui découvrit RSA [102] avant ses auteurs en 1973 mais dont l’algorithme avait été classifié par le gouvernement britannique puis déclassifié en 1997 [30].
Le cryptosystème RSA
Le cryptosystème RSA, du nom de ses auteurs Rivest, Shamir et Adleman [102], repose sur un problème qui lui est propre, que nous appellerons RSAP, et qui s’énonce ainsi :soient n un entier produit de deux nombres premiers p et q (distincts), et e un nombrepremier avec (p − 1) et (q − 1). Étant donné c, résoudre le RSAP revient à trouver m telque me ≡ c mod n ou, autrement dit, cela revient à trouver la racine e-ème d’un élémentmodulo n.
Ce problème est proche du problème de la factorisation des grands entiers. Notamment, si on est capable de factoriser n en p et q, on peut alors calculer d l’inverse de e modulo (p−1)(q −1), et finalement on calcule (me) d = m mod n ce qui résout le RSAP. On ne saitpas par contre si la résolution du RSAP permet de résoudre le problème de la factorisation.
Le protocole de chiffrement RSA est présenté à l’algorithme 1. On considère que le message à chiffrer est un entier naturel inférieur ou égal à n − 1 (si besoin, découper les messages) . À cause des algorithmes de factorisation des grands entiers tels que NFS [70] (number field sieve), le nombre d’opérations à effectuer pour casser RSA avec n = 1024 bits n’est que de 2⁸⁰. Ainsi, en 2009, un module RSA de 768 bits a été factorisé [65], ce qui a nécessité des centaines de machines en parallèle et plus de deux ans et demi de calcul. Différents chercheurs étudient sérieusement la possibilité de mettre en œuvre un système pour casser RSA 1024 bits.
Le problème du logarithme discret, application dans les corps finis
Un autre problème célèbre est celui du logarithme discret (DLP). Il peut être vu comme une fonction à sens unique et est utilisé dans certains standards de cryptographie asymétrique. Le problème est défini comme suit (voir [78], pages 103–113) : soient (G, ×) un groupe cyclique fini et g ∈ G un élément qui le génère. Calculer le logarithme discret de h revient à trouver d tel que h = gᵈ dans G.
Certains cryptosystèmes sont basés sur le DLP sur des groupes G pour lesquelsle logarithme est difficilement calculable. Une idée naturelle de groupe est de choisir les éléments de F∗p , mais à cause de l’attaque du calcul d’indices sur F∗p (voir [3]), on l’utilise peu. Si on l’utilisait, l’attaque réduirait par exemple la sécurité d’un système à clé de 1024 bits à seulement 80 bits de sécurité (comme pour RSA). Dans les faits, on choisit plutôt un sousgroupe de F∗p , noté G, d’ordre premier q. Par exemple, un sous-groupe avec environ 2¹⁶⁰ éléments (log2 q ≈ 160) pour p de taille 1024 bits (voir par exemple [91]). Comme expliqué à la page 113 de [78], le calcul d’indices ne semble pas pouvoir s’appliquer directement sur ce sous-groupe, on doit alors l’appliquer sur tout F∗p , le passage de F∗p au sous-groupe n’impacte donc pas la sécurité du point de vue de cette attaque. Par contre, il faut faire attention à d’autres attaques sur le sous-groupe, comme celle de Pohlig Hellman [96] et l’attaque rho de Pollard [97] qui sont en O(√q) opérations, donnant un nombre de bits de sécurité correspondant à (log2 q)/2 lorsque q est premier. Il faut choisir q premier car ces attaques dépendent seulement de la taille du plus gros facteur premier de q. La sécurité conférée par ce problème est donc le minimum des attaques sur F∗p et sur le sous-groupe sélectionné. Il est recommandé de choisir des paramètres tels que le système soit aussi résistant aux deux types d’attaque. Par exemple, si ⌊log2 q⌋ = 160 bits, on a donc 80 bits de sécurité pour l’attaque Pohlig-Hellman, on prend alors ⌊log2 p⌋ = 1024 on a aussi 80 bits de sécurité pour le calcul d’indices [91]. Si on compare avec RSA, on se retrouve avec un même niveau de sécurité en traitant avec des éléments de même taille (1024 ou 2048 bits par exemple), mais le DLP dans les corps finis (FFDLP) offre des clés bien plus petites (160 bits contre 1024 par exemple).
Le standard américain DSA [91] du NIST, l’échange de clés de Diffie et Hellman [38] (DH, présenté algorithme 2) et le chiffrement d’Elgamal [44] (algorithme 3) se basent sur le fait que le FFDLP n’est pas résoluble en pratique sur un groupe approprié. Les deux cryptosystèmes sont utilisés dans les conditions décrites dans le paragraphe précédent, c’est à dire q est l’ordre de g modulo p, et q est un grand nombre premier. Le problème utilisé pour ces deux protocoles est en réalité un peu plus faible que le FFDLP car il suffit de savoir forger gᵃᵇ à partir de gᵃ et gᵇ pour casser ces deux protocoles (il est évident que si le FFDLP devient facile, ces cryptosystèmes n’apportent plus aucune sécurité).
|
Table des matières
Introduction
Notations
1 État de l’art
1.1 La cryptographie asymétrique
1.1.1 Le cryptosystème RSA
1.1.2 Le problème du logarithme discret, application dans les corps finis
1.1.3 Le problème du logarithme discret sur les courbes elliptiques
1.1.4 Techniques classiques de multiplication scalaire et d’exponentiation
1.1.5 Réduction du coût de la multiplication scalaire
1.1.6 Sécurité et attaques physiques
1.2 Arithmétique modulaire
1.2.1 Définitions et rappels sur l’arithmétique modulaire
1.2.2 Réduction Modulaire
1.2.3 Inversion Modulaire
1.3 La représentation modulaire des nombres (RNS)
1.3.1 Définition et premières propriétés
1.3.2 Extensions de base RNS
1.3.3 Adaptation RNS de l’algorithme de Montgomery
1.3.4 Autres algorithmes de réduction
1.3.5 Implantations RNS
2 Inversion modulaire rapide en RNS
2.1 Inversion modulaire RNS dans l’état de l’art
2.2 Inversion modulaire plus-minus en RNS
2.3 Algorithme binaire-ternaire plus-minus en RNS
2.4 Comparaison avec l’état de l’art
2.4.1 Complexité du FLT-MI
2.4.2 Complexité de PM-MI et BTPM-MI
2.5 Architecture et implantation FPGA
2.6 Validation
2.7 Conclusion
3 Décomposition et réutilisation d’opérandes pour la multiplication modulaire RNS
3.1 Algorithme de multiplication modulaire RNS proposé
3.1.1 L’étape de décomposition
3.1.2 Algorithme de multiplication modulaire SPRR
3.1.3 Preuve des propositions 1 et 2
3.1.4 Sélection des paramètres
3.2 Applications
3.2.1 Application au logarithme discret
3.2.2 Applications aux courbes elliptiques
3.3 Exponentiation rapide RNS sans hypothèse sur P
3.3.1 Un nouvel algorithme d’exponentiation RNS
3.3.2 Autres algorithmes d’exponentiation
3.4 Conclusion
4 Multiplication modulaire RNS mono-base
4.1 La multiplication modulaire RNS à base unique SBMM
4.2 Analyse de l’algorithme SBMM
4.2.1 Généralisation du paramètre c
4.2.2 Utilisation de l’extension de base de Kawamura et al
4.2.3 Compression des sorties de l’algorithme
4.2.4 Analyse des coûts en EMM et EMW
4.3 Implantation FPGA
4.3.1 Architecture implantée
4.3.2 Résultats d’implantation
4.4 Conclusion
5 Tests de divisibilité multiples
5.1 Introduction
5.2 Notations et hypothèses d’implantation matérielle
5.3 État de l’art
5.4 Utilisation directe des rubans de Pascal en base 2
5.5 Amélioration via les rubans de Pascal en grande base 2v
5.6 Comparaisons
5.7 Conclusion
Conclusion
