ENTIERS DUAUX ET CRYPTOGRAPHIE A CLE PUBLIQUE `

ENTIERS DUAUX ET CRYPTOGRAPHIE A CLE PUBLIQUE 

Chiffrement ElGamal 

L’algorithme El Gamal, a été développé par Taher ElGamal en 1984. Il n’est pas breveté et peut être utilisé librement. Introduisons d’abord le problème du logarithme discret Soit G un groupe noté multiplicativement, g ∈ G un élément d’ordre q (assez grand) et H =< g > le sous-groupe engendré par g Problème de logarithme discret (DLP) : Etant donné y ∈ H existe-t-il a ∈ [1, q − 1] tel que y = g a . Si oui, comment le calculer ? a est appelé le logarithme discret de y à base g, on note a = logg(y). Exemples 0.0.1. Soit G le groupe multiplicatif du corps Z pZ avec p un grand nombre prémier et α une racine primitive modulo p. Etant donné un entier B non divisible par p, le problème se résume à trouver un entier a vérifiant : B = α a mod p. Problème Calculatoire de Diffie-Hellman(CDH) : Etant donnés g a et g b dans le sous-groupe H, peut-on reconstituer g ab avec a, b ∈ [1, q − 1]. Bien entendu, on peut résoudre se problème si on sait résoudre le problème du logarithme discret. Problème Décisionnel de Diffie-Hellman(DDH) : Etant donnés (g a , gb ) ∈ H2 (a, b ∈ [1, q − 1]) et un candidat z = g c ∈ H (c ∈ [1, q − 1]), décider si z = g ab c’est-à-dire si c = ab. Là aussi si on sait résoudre le logarithme discret, on résout le problème décisionnelle. La sécurité de ElGamal est basée sur la difficulté du problème de logarithme discret dans un corps fini. Le chiffrement d’ElGamal est non déterministe, car l’opération de chiffrement dépend du message et d’une valeur aléatoire choisie par l’émetteur. Il y a donc plusieurs textes chiffrés qui peuvent correspondre à un même texte clair. Génération des clés Soit p un nombre premier tel que le problème de logarithme discret dans Zp soit difficile, et soit α ∈ Z ∗ p un élément primitif. On sélectionne un entier s ∈ [1, p − 2[ et on calcul t = α s mod p. La clé publique est (p, α, t) et la clé privée est s. Chiffrement ElGamal Si on veut chiffrer le message m pour Oumar on procède comme suit : 1. Obtenir la clé publique (p, α, αs ) 2. Sélectionner un entier k ∈ [1, p − 1[ 3. Calculer K = α k mod p 4. Calculer C = mαks mod p 17 5. Le message chiffré est (K, C) Déchiffrement ElGamal Si Oumar re¸coit le message (K, C) il utilise sa clé privée pour déchiffrer le message. Pour cela il calcule m 0 = C.K−s En effet, m 0 = C.K−s = mαks.α−ks mod p = m NB : Le chiffrement ElGamal n’a pas un niveau de securité elevé. Signature digitale Parmi les problèmes auxquels s’attaque la cryptographie, on trouve l’authentification de l’origine de données et l’intégrité : lorsque l’on communique avec une personne sur un canal peut sûr, on aimerait bien que le destinateur puisse s’assurer que le message émane bien de l’auteur auquel il est attribué et qu’il n’a pas été altéré pendant le transfert. Pour ce, la signature d’un message a été inventé. Terminologie – Soit M est un ensemble appelé espace de messages clairs – Soit S est un ensemble appelé espace des signatures – Soit SA : M → S est une transformation appelée fonction de signature pour une entité A – Soit VA : M × S → {vraie, f aux} est une transformation appelée fonction de vérification de la signature de A Définition 0.0.11. Les transformations SA et VA constituent un schéma de signature digitale. Procédure Si une entité A veut créer une signature pour le message m ∈ M, elle doit effectuer les opérations suivantes : 1. Calculer s = SA(m) 2. Transmettre la pair (m, s). s est appelé la signature de m. Vérification de la Procedure Pour vérifier que la signatire s a été créée par A, une entité O éxecute ce qui suit : 1. Obtenir la fonction de vérication VA de A 2. Calculer v = VA(m, s) 3. Si v = vraie on accepte la signature sinon on rejette la signature. Remarque 0.0.1. Les transformations VA et SA sont typiquement caractérisées par des clés ; c’est à dire il existe une classe des algorithmes de signature et de verification de signature connus publiquement, et chaque algorithme est identifié par une clé. Ainsi l’algorithme de signature SA de A est déterminé par une clé secrète kA et A est le seul à connaˆıtre cette clé privée. De la même manière l’algorithme VA est déterminé par une clé vA qui est publique correspondante à la clé privée kA. 18 Propriétés nécessaires sur les fonctions de signature et vérification de signature Il existe plusieurs propriétés que les fonctions de signature et de vérification de signature doivent satisfaire. – Une signature s de A d’un message m est valide si et seulement si VA(m, s) = vraie. – Il calculatoirement difficile (complexité exponentielle) pour toute entité autre que A de trouver pour tout m ∈ M, un s ∈ S tel que VA(m, s) = vraie. NB : Cette version de signature ne garantie pas l’intégrité car elle n’utilise pas de fonction de hachage que nous allons voir dans la suite. Parmis les signatures numériques examinons la signature RSA et la signature ElGamal Signature RSA Le principe est le suivant : Le module N de RSA est le produit de deux grands nombres premiers p et q. On pose ϕ(N) = (p − 1)(q − 1). Soit un entier e tel que, 0 < e < ϕ(N) et pgcd(e, ϕ(N)) = 1 et soit d un entier vérifiant : 0 < e < ϕ(N) et ed ≡ 1 mod ϕ(N). La clé (e, N) est la clé publique et la clé (d, N) est la clé privée. Signature Pour signer un message m ∈ Z NZ , l’entité A calcule s = SA(m) = md mod N et on transmet (m, s) o`u s est la signature de m. Vérification de la signature On utilise la clé publique (e, N) pour vérifier la validité de la signature en calculant s e mod N. On doit s’assurer que m = s e mod N Signature ElGamal Génération des clés – choisir un grand nombre premier p – choisir α un générateur de Z ∗ p – choisir s ∈ [1, p − 2] – calculer K = α s mod p La clé s est la clé secrète qu’on utilise pour la génereration des signatures, et la clé (p, α, K) est la clé publique qu’on utilise pour la vérification des signatures. Génération de la signature Pour générer la signature s d’un message m, on procède comme suit : – on choisit aléatoirement s ∈ [1, p − 2] tel que pgcd(s, p − 1) = 1 – on calcule γ = α k mod p – on calcule δ = (m − s.γ).k−1 mod p − 1 19 La signature s du message m est le couple (γ, δ) Vérication de la signature Supposons que nous avons re¸cu le message m et la signature s. Cette signature est valide si : – 0 < γ < p – Kγ .γδ ≡ α m mod p NB : Pour garantir une meilleur securité, on modélise cette signature sur les courbes elliptiques. Fonctions de Hachage Une fonction de hachage est une fonction à sens unique sans trappe. Ce type de fonction est très utilisé en cryptographie, principalement dans le but de réduire la taille des données à traiter par la fonction de chiffrement. En effet, la caractéristique principale d’une fonction de hachage est de produire un condensé des données. Une fonction de hachage doit associer un et un seul condensé à un texte en clair( cela signifie que la moindre modification sur le texte clair entraˆıne une modification sur son condensé). Propriétés des Fonctions de Hachage Soit H : {0, 1} ∗ → {0, 1} n une fonction de hachage. x ∈ {0, 1} ∗ est une préimage de y ∈ {0, 1} n si y = H(x) 1. Compression : la fonction de hachage H prend en entrée une chaˆıne binaire x de taille quelconque et renvoie une chaˆıne binaire H(x) de taille fixe n. 2. Fonction facile à calculer : étant donnée une entrée x ∈ {0, 1} ∗ , H(x) doit être facile à calculer (complexité polynomiale). 3. La fonction H doit resister au calcul du préimage c’est-à-dire qu’il doit être très difficile de retrouver ou générer une préimage x (complexité exponentielle) telle que H(x) = y pour tout y donné dont l’entrée correspondant est inconnue. 4. la résistance de la seconde préimage : étant donné x, il est calculatoirement infaisable de trouver une deuxième préimage x 0 6= x telle que H(x 0 ) = H(x). 5. La resistance à la collision : il est calculatoirement infaisable de trouver deux entrés x et x 0 telle que H(x) = H(x 0 ). MAC(Message Authentification Code) Un code d’authentification de message(MAC) est une fonction de hachage paramétrée par une clé secrète k, Hk(), qui respecte la facilité de calcul, la propriété de compression et qui est telle que : pour tout k fixé et inconnu par un adversaire, il est calculatoirement difficile pour cet adversaire de calculer une paire (x, Hk(x)) à partir de sa connaissance d’un nombre quelconque des paires (xi , Hk(xi)) o`u x est différent de tous les xi Sécurité Soit H : {0, 1} ∗ → {0, 1} n une fonction de hachage. On dit que H atteint une sécurité idéale si : 20 . pour toute empreinte y, trouver un x ∈ {0, 1} ∗ tel que y = H(x) nécessite 2n opérations. . étant donné x, trouver une deuxième préimage x 0 6= x telle que H(x 0 ) = H(x) nécessite 2n opérations. . pour trouver un couple (x, x 0 ) tel que x 6= x 0 et H(x) = H(x 0 ) nécessite 2 n 2 opérations. 

RESEAUX ARITHMETIQUES, NTRU ET SES VARIANTES

Dans ce chapitre nous allons faire un petit rappel sur les réseaux arithmétiques, ensuite nous présenterons la version originale du cryptosystème NTRU, comme décrit dans([11]) et quelques variantes de NTRU. Réseaux Arithmétiques Le cryptosystème NTRU est ”probablement basé” sur la difficulté de trouver un court vecteur dans un grand réseau. Il semble donc important de décrire ce qu’est un réseau et dire quelques mots sur les algorithmes de réduction de réseaux. Notre résumé est basé sur ([5]) et ([20]). Notions de Bases Définition 0.0.12. Définissons le produit scalaire de deux vecteurs u = (u1, u2, …, un), v = (v1, v2, …, vn) ∈ R n comme hu, vi = Xn i=1 uivi . Définition 0.0.13. Définissons la norme euclidienne d’un vecteur v = (v1, v2, …, vn) ∈ R n comme kvk = vuutXn i=1 v 2 i . Soientt n un entier positif avec n ≤ m, (b1, …, bn) des vecteurs linéairement indépendants de R m. Soit B la matrice dont les colonnes sont composées des coordonnées des vecteurs b1, …, bn Définition 0.0.14. Le réseau engendré par la famille (b1, …, bn)(ou par B) est l’ensemble L(b1, …, bn) = L(B) = Xn i=1 Zbi = { Xn i=1 λibi |λi ∈ Z} L’entier n est la dimension de L. Il faut noter que L(B) est stable par les opérations élémentaires suivantes sur B : permutation de deux lignes, multiplication d’une ligne par -1, additionner une ligne multiple d’un entier avec une autre ligne. Pour une base matricielle B, considerons la valeur |det(B)|. Il est facile de montrer que si B et B0 génèrent le même reseau alors |det(B)| = |det(B0 )|. Ainsi nous pouvons définir le déterminant d’un réseau et sa dimension. 22 Définition 0.0.15. Soit (b1, …, bn) un n-uplets de vecteurs linéairement indépendants de R m. Soit B la matrice dont les colonnes sont composées des coordonnées des vecteurs b1, …, bn et soit L(B) le réseau généré par B. Le déterminant ou le volume de L(B) est detL(B) = |det(B)|. Définition 0.0.16. Soit (b1, …, bn) un n-uplets de vecteurs linéairement indépendants de R m et soit B la matrice dont les colonnes sont composées des coordonnées des vecteurs b1, …, bn et soit L(B) le réseau généré par B. La dimension de L(B) est n. Si n = m on dira que L(B) est de dimension pleine. Définition 0.0.17. (Parallélépipède fondamental). Soit (b1, …, bn) des vecteurs linéairement indépendants de R m. Le parallélépipède fondamental des bi est : P(b1, …, bn) = { Xn i=1 aibi | 0 ≤ ai < 1}. L’ensemble des points v + P(B), v ∈ L(B) forme une partition de L(B). Nous pouvons montrer facilement que le volume du parallélépipède fondamental est le même pour toutes les bases B qui engendrent le réseau L = L(B) et est égal au déterminant du réseau (voir[5]). Définition 0.0.18. (Orthogonalisation de Gram-Schmidt) Soit (b1, …, bn) une base d’un réseau L ⊂ R m. On considère la famille de vecteurs (b ∗ 1 , …, b∗ n ) définit par b ∗ 1 = b1 b ∗ j = bi − X i−1 j=1 µi,j b ∗ j avec pour j < i µi,j = hbi,b∗ j i hb ∗ j ,b∗ j i Alors (b ∗ 1 , …, b∗ n ) est une base orthogonale de R m. L’algorithme de réduction du reseau L’algorithme LLL de réduction est un composant crucial dans un grand nombre d’algorithmes de la théorie des nombres. Il est utilisé pour résoudre un certain nombre de problèmes, par exemple, il a été utilisé pour cryptanalyser des schémas de chiffrement à clé publique basés sur des problèmes utilisant des réseaux. Définition 0.0.19. Une base (b1, …, bn) est LLL-réduite si, la base (b ∗ 1 , …, b∗ n ) produite par la méthode d’orthogonalisation de Gram-Schmidt vérifie |µi,j | ≤ 1 2 , pour 1 ≤ j < i ≤ n (o`u |µi,j | est la valeur absolue de µi,j ) et kb ∗ i k 2 ≥ ( 3 4 − µ 2 i,i−1 )kb ∗ i−1 k 2 pour 1 < i ≤ n. 23 L’algorithme LLL transforme une base (u1, …, un) du reseau L en une base LLL-réduite (b1, …, bn), avec les propriétés du théorème suivant : Théorème 0.0.1. Soit (b1, …, bn) une base LLL-réduite et (b ∗ 1 , …, b∗ n ) la base orthogonale associée par la méthode de Gram-Schmidt. Alors 1. kb ∗ j k 2 ≥ 2 i−jkb ∗ i k 2 pour 1 ≤ j ≤ i ≤ n 2. det(L) ≤ Qn i=1 kbik ≤ 2 n(n−1) 4 det(L) 3. kbjk ≥ 2 i−1 2 kb ∗ i k pour 1 ≤ j ≤ i ≤ n 4. kb1k ≥ 2 n−1 4 (det(L)) 1 n 5. pour tout vecteur non nul v ∈ L, kb1k ≤ 2 n−1 2 kvk Il faut signaler que la complexité de l’algorithme LLL est polynômiale, ce qui signifie qu’il est très efficace. Les bases que cet algorithme nous fournit sont composées de vecteurs assez courts, ce qui peut apporter une réponse qui satisfait partiellement aux deux problèmes suivants Problème SVP, Shortest Vector Problem (problème du plus court vecteur) : Etant donné une base B d’un réseau L, trouver un vecteur non nul de L le plus court possible pour la norme euclidienne. Problème CVP, Closest Vector Problem (problème du plus proche vecteur) : Etant donné une base B d’un réseau L et un vecteur v ∈ L, trouver un vecteur de L le plus proche possible de v pour la norme euclidienne. 

NTRU 

Le cryptosystème NTRU, qui fait l’objet de ce travail, est basé sur le problème : trouver un vecteur court dans un réseau (SVP) ou le vecteur le plus proche d’un vecteur donné (CVP). Le principal avantage du cryptosystème NTRU par rapport aux autres cryptosystèmes à clé publique est sa rapidité dans les processus de chiffrement et de déchiffrement. Il est comparable aux cryptosystèmes à clé secrète. Par exemple, considérons les chiffres tirés du site officiel du Cryptosystème NTRU([28]). NTRU 251 RSA 1024 ECC 163 clé publique (bits) 2008 1024 164 clé secrète (bits) 251 1024 163 blocks claires (bits) 160 702 163 blocks chiffrés (bits) 2008 1024 163 vitesse chiffrement(blocks/seconde) 22727 1280 458 vitesse déchiffrement(blocks/seconde) 10869 110 702 Ils fournissent une comparaison entre les vitesses de NTRU et deux autres cryptosystèmes à clé publique populaires, avec des niveaux plus ou moins équivalents pour la sécurité. Un autre avantage concernant le futur de la cryptographie à clé publique est que le cryptosystème NTRU résiste encore contre les attaques des ordinateurs quantiques contrairement à RSA et ElGamal. 24 Notations Le cryptosystème NTRU depend de plusieurs sortes de paramètres, en particulier les paramètres N, p et q. Soit N un entier premier. Le domaine des opérations de NTRU est l’anneau des polynômes à coefficients entiers P = Z[X] (XN −1) . On considère les deux anneaux quotients : Pp = Z pZ [X] (Xn − 1), Pq = Z qZ [X] (Xn − 1) Supposons que p et q sont premiers entre eux et q est plus grand que p. Supposons aussi que Lf ,Lg,Lr,Lm sont des sous-ensembles de P. Lm sera l’espace des messages clairs, nous choisissons nos clés dans Lf , et dans Lg et les polynômes dans Lr serviront comme des éléments aléatoires dans notre schéma de chiffrement. Ainsi, les éléments f de P peuvent être représentés sous la forme f = N X−1 i=0 fix i = (f0, f1, …, fN−1) et notons par ∗ la multiplication dans P, Pp et Pq, définie comme suit : h = f ∗ g avec hk = X i+j≡k(modN) figj = X k i=0 figk−i + N X−1 i=k+1 figN+k−i Nous définissons aussi la norme d’un élément F ∈ P comme suit kFk∞ = max 0≤i≤n (Fi) − min 0≤i≤n (Fi) Génération de clés Pour la création des clés nous choisissons deux polynômes aléatoires f ∈ Lf , g ∈ Lg. Le polynôme f doit être inversible dans Pp et dans Pq. Soient fp et fq les inverses respectives de f dans Pp et Pq. Nous calculons alors le polynôme h = fq ∗ g ∈ Pq qui est notre clé publique. Notre clé privée est f et on doit aussi garder secrètement fp pour le déchiffrement. 

Chiffrement et Déchiffrement 

Supposons que Aissa veut nous envoyer un message m ∈ Lm. Elle choisit un polynôme r ∈ Lr aléatoirement et calcule : e = pr ∗ h + m ∈ Pq, O`u h est notre clé publique. Si nous recevons e, premièrement nous multiplions e par notre clé privée pour obtenir a = f ∗ e = pr ∗ f ∗ fq ∗ g + f ∗ m = pr ∗ g + f ∗ m ∈ Pq Sous certaines conditions(c’est-à-dire si kpr ∗ g + f ∗ mk∞ < q), nous pouvons voir a comme un polynôme de P, le reduire modulo p et le multiplier par fp qui est l’inverse de f modulo p pour retrouver le message initial modulo p : b = fp ∗ a = m ∈ Pp 25 Choix des paramètres Succès du Déchiffrement : Nous devons choisir les paramètres de tels sorte que nous soyons capable de déchiffrer : la condition suivante doit être vérifier : kpr ∗ g + f ∗ mk∞ < q. Les coefficients de f, r et g doivent être très petits. Les auteurs de NTRU définissent les ensembles suivants : L(d1, d2) := {f|f ∈ P a d1 coefficients égals à 1, d2 coefficients égals à − 1, reste 0}. Ainsi, ils choisissent les valeurs entières pour df , dg, et dr et les ensembles Lf = L(df , df − 1), Lg = L(dg, dg1), Lr = L(dr, dr) Il faut noter que Lf ne doit pas être L(df , df ), si non les éléments f ∈ Lf ne serons certainement pas inversibles : nous voulons trouver f 0 tel que f 0 f = 1, mais le choix de f implique que f(1) = 0 et alors f 0 f(1) = 0 = 1, qui est une contradiction. Soit pr ∗ g + f ∗ m ∈ P L’objectif est de déterminer df , dg, dr, de sorte que l’inégalité |ai | < q−1 2 soit vérifiée pour chaque i, 0 ≤ i < N avec une probabilité très grande. Les nombres entiers df , dg, dr et dm sont fixés pour chaque version. Actuellement, ces paramètres sont les suivants (voir[11]) : Sécurité N p q df dg dr Moyenne .

 Analyse de la sécurité

 Attaque par force brute Un attaquant peut récupérer la clé privée, en essayant de trouver f ∈ Lf et de vérifier si les coefficients de f ∗ h mod q sont petits. Dans la pratique, la taille de Lg est plus pétite que |Lf | et, par conséquent, il est logique de tester tous les g ∈ Lg et voir si les coefficients de f ∗ h −1 mod q sont petits. De la même manière, il peut essayer de récupérer un message individuel en essayant toutes les r ∈ Lr et tester la taille des coefficients de e − r ∗ h mod q En résumant ce qui est en haut, la sécurité de la clé est donnée par |Lg| et la sécurité du message par |Lr|. Ce qui donne : |Lg(dg, dg)| = N dg ! N − dg dg ! = N! (dg!)2(N − 2dg)! 26 et |Lr(dr, dr)| = N dr ! N − dr dr ! = N! (dr!)2(N − 2dr)! Il existe une autre attaque appelée attaque du milieu qui concerne la clé publique et le message ([16]) . Attaques basées sur les réseaux Dans NTRU, la clé publique h ≡ fq ∗ g (mod q) vérifie f ∗ h ≡ g (mod q). Alors, il existe un polynôme u ∈ P = Z[x] (xN −1) tel que f ∗ h − q ∗ u = g On considère alors l’ensemble L = {(f, g) ∈ P2 |∃u ∈ P, f ∗ h − q ∗ u = g}. Avec les coordonnées de f, g et h, l’égalité ci-dessus prend la forme   f0 f1 . . . fN−1 −u1 −u2 . . . uN−1   ∗   1 0 . . . 0 h0 h1 . . . hN−1 0 1 . . . 0 hN−1 h0 . . . hN−2 0 0 . . . . . . . . . . . . . 0 0 . . . 1 h1 h2 . . . h0 0 0 . . . 0 q 0 . . . 0 0 0 . . . 0 0 q . . . 0 . . . . . 0 . . . . . 0 . . . . . 0 0 0 . . 0 0 0 . . . q   =   f0 f1 . . . fN−1 g0 g1 . . . gN−1   Dans la clé publique h, les polynômes f et g ont de petits coefficients et (f, g) ∈ L. Alors en appliquant l’algorithme LLL au reseau L, on obtient une base réduite dans laquelle les premiers vecteurs sont assez courts, et on peut ainsi déterminer f et g. Si (f, g) est le plus court vecteur du reseau L, cela revient à résoudre le problème SVP. Ceci illustre que la sécurité de NTRU est basée sur ce problème difficile.

 Quelques variantes de NTRU 

A cause des multiples attaques sur les premières versions de NTRU, le cryptosystème NTRU, possède plusieurs versions. Ce qui fait l’évolution de NTRU vers des versions plus sûres. Ainsi on peut éviter les attaques basées sur la réduction des réseaux en rempla¸cant l’anneau Z par un autre anneau. 27 Généralisation par Banks et Shparlinski En 2002, Banks et Shparlinski[1] ont présenté une nouvelle variante de NTRU. La différence fondamentale entre NTRU et cette nouvelle variante se trouve au niveau de la génération des clés. Génération des clés Pour la génération des clés on procède comme suit : 1. Choisir aléatoirement un polynôme f ∈ Lf 2. Calculer l’inverse fp de f dans Pp. 3. Choisir aléatoirement un polynôme G ∈ P 4. Calculer l’inverse Gq de G dans Pq. 5. Choisir aléatoirement un polynôme g ∈ Lg 6. Calculer h = (Gq ∗ g) mod q dans Pq 7. Calculer H = (Gq ∗ f) mod q dans Pq La clé publique est alors constituée par le couple (h, H) et (f, fp, G) est la clé privée. Maintenant si on veut chiffrer un message m ∈ Lm on procède comme suit : Chiffrement On choisit d’abord aléatoirement un polynôme ϕ ∈ Lϕ et on calcule e = pϕ ∗ h + H ∗ m (mod q). On transmet le message chiffré e. Pour déchiffrer e, on effectue les opérations suivantes : On calcule a = G ∗ e (mod q) avec des coefficients dans l’intervalle ] − q 2 , q 2 [ et on retrouve m en calculant m = fp ∗ a (mod p) Cette version resiste aux attaques classiques sur NTRU, mais son temps d’exécution est pratiquement double à cause de la présence de deux polynômes h et H. MaTRU Une nouvelle variante de NTRU a été proposée en 2005 par Coglianese et Goi[3]. Dans cette variante l’anneau Z a été remplacé par l’anneau des matrices M carrées k × k à coefficients dans P = Z[X] (XN −1) . En plus de N et k, MaTRU utilise aussi les paramètres p, q ∈ N. Les nombres p et q peuvent être premiers ou non, mais ils doivent être premiers entre eux. Les paramètres de MaTRU sont composés de quatres entiers (n, k, p, q) et les 5 ensembles de matrices (Lf , Lϕ, LA, Lw, Lm) ⊂ M 1. LA est l’ensemble de toutes les matrices C ∈ M telles que C 0 , C1 , . . ., Ck−1 sont linéairement indépendants modulo q. 2. Lf et Lϕ sont des ensembles de toutes les matrices D ∈ M vérifiant X k−1 i=0 ciC i , C ∈ LA, c0, c1, . . . ck−1 ∈ P 3. Lm est l’ensemble des messages constitués des toutes les matrices dont les termes sont des polynômes ayant des coefficients modulo p. Lm = {M ∈ M | les coefficients des polynômes dans M sont entre d−p−1 2 e et d p+1 2 e} 28 Génération des clés Pour créer une paire de clés publique et privée, on procède comme suit : – Choisir deux matrices A, B ∈ LA. – Selectionner aléatoirement k polynômes α0, α1, . . ., αk−1 ∈ P – Selectionner aléatoirement k polynômes β0, β1, . . ., βk−1 ∈ P – Calculer f = X k−1 i=0 αiA i ∈ Lf – Calculer g = X k−1 i=0 βiB i ∈ Lf – Calculer Fp tel que Fp ∗ f = I (mod p) et Fq tel que Fq ∗ f = I (mod q) o`u I est la matrice unité. – Calculer Gp tel que Fp ∗ g = I (mod p) et Gq tel que Gq ∗ g = I (mod q) o`u I est la matrice unité. – Choisir aléatoiment une matrice w ∈ Lw – Calculer h = Fq ∗ w ∗ Gq (mod q) dans Pq La clé publique est le triplet (h, A, B) et la clé privée est (f, g, Fp, Gp) Chiffrement Pour chiffrer un message m ∈ Lm, on choisit d’abord aléatoirement k polynômes φ0, φ1, . . ., φk−1 ∈ P et k polynômes ψ0, ψ1, . . ., ψk−1 ∈ P et on calcule successivement φ = X k−1 i=0 φiA i ∈ Lφ, ψ = X k−1 i=0 ψiB i ∈ Lψ et e = pφ ∗ h ∗ ψ + m (mod q) e est le message chiffré que l’on va transmetre. Déchiffrement Si on re¸coit le message chiffré e, on calcule d’abord a = f ∗ e ∗ g (mod q) en mettant les coefficients des polynômes dans l’intervalle [− q 2 , q 2 [. On retrouve le message en calculant m0 = Fp ∗ a ∗ Gp (mod p). Remarquons que les niveaux de sécurité de MaTRU sont comparables à ceux de NTRU et de plus le chiffrement et le déchiffrement de MaTRU sont k 2 fois plus rapides que NTRU. Il faut signaler egalement que le déchiffrement de MaTRU peut rencontrer les mêmes problèmes que NTRU Classique. CTRU En 2002 Gaborit, Ohler et Solé ont proposé une nouvelle version de NTRU qu’ils ont appelé CTRU[7]. Dans cette version l’anneau des entiers est remplacé par l’anneau A = F[T] des polynômes univariés à coefficients dans un corps fini. Ils évitent ainsi les attaques basées sur l’algorithme LLL ou le théorème des restes chinois. Un outil de cryptanalyse de CTRU est la forme normale de Popov des matrices à coefficients polynomiaux. Noter que CTRU a été cassé par Kouzmenko dans sa thèse unique [18] en 2006 et par Vats [32] en 2008. La vitesse de chiffrement et de déchiffrement de CTRU est la même que celle de NTRU pour les mêmes valeurs de N. Le domaine des opérations de CTRU est l’anneau R = A[X] (XN − 1) Soit F un polynôme de R. Le degré de F qu’on note degT (F) est le degré de F en tant que polynôme en T. 29 Soit N un entier et P, Q deux polynômes de A, avec degT (P) = m et degT (P) = s, gcd(m, s) = 1, 2 ≤ m ≤ s. Soit df , dg et dϕ des entiers vérifiants df = s − m − 1 et dg = dϕ = b 1 2 (s − m − 1)c. Considérons les ensembles Lm = {M ∈ R|degT (M) < S} Lf = {f ∈ R|degT (f) < 1 + df } Lg = {g ∈ R|degT (g) < 1 + dg} Lf = {ϕ ∈ R|degT (ϕ) < 1 + dϕ} , o`u degT (f) est le degré de f en tant que polynôme en T. CTRU s’utilise de la même fa¸con que NTRU. Génération des clés – choisir aléatoirement f ∈ Lf – Calculer l’inverse fQ de f modulo (XN − 1, Q) – Calculer l’inverse fP de f modulo (XN − 1, P) – Choisir aléatoirement g ∈ Lg – Calculer h ≡ g ∗ fQ dans l’anneau quotient R (Q) . La clé publique est h et la clé secrète est (f, fP ). Pour chiffrer un message M ∈ Lm, on procède comme suit : Chiffrement – Choisir aléatoirement un polynôme ϕ ∈ Lϕ – Calculer e = P ∗ ϕ ∗ h + M (mod Q) dans l’anneau quotient R (Q) . Le message chiffré est e. Pour retrouver le message originale M on procède de la manière suivante : Déchiffrement – Calculer a = e ∗ f dans l’anneau quotient R (Q) – On calcule M = a ∗ fQ dans l’anneau quotient R (P) Cryptanalyse de NTRU La sécurité du cryptosystème NTRU([11] est liée à la difficulté de trouver le plus court vecteur (SVP) dans un réseau euclidien de grande dimension. Cette caractéristique est intéressante puisqu’elle s’avère résistante aux attaques basées sur des ordinateurs quantiques, ce qui n’est pas le cas de l’algorithme RSA basé sur la factorisation d’entiers de grande taille. Plusieurs recherches ont été effectuées afin d’améliorer la sécurité de NTRU, notamment en augmentant la taille des paramètres utilisés. Cela a pour conséquence de complexifier la reduction de base à l’intérieur des réseaux, au détriment de la rapidité de l’algorithme puisque la taille des clés publiques devient plus grande et la durée du chiffrement/déchiffrement croˆıt. Il faut juste signaler que NTRU reste cependant toujours avantageux en termes de performance lorsqu’on le compare à RSA. Le cryptanalyse de NTRU est basé sur l’algorithme LLL([19] qui permet la réduction de réseau, c’est-à-dire extraire une base presque orthogonale à partir d’une base quelconque. En décomposant la clé publique h sous la forme d’un produit de deux polynômes f et g, on arrive à utiliser l’algorithme LLL pour trouver une base et obtenir le plus petit vecteur d’un réseau euclidien particulier. Cela nous permet 30 de retrouver les polynômes f et g utilisés pour déchiffrer le message. Cette méthode ne fonctionne en pratique que pour des paramètres de NTRU assez faibles. Les versions actuelles de NTRU utilisant les paramètres suivants sont considérées sûres.