LE CRYPTOSYSTEME NTRUREALITES ET PERSPECTIVES
Abderrahmane NITAJ
Université de Caen
Département de Mathématiques
FranceOujda, 27 Avril 2007

Le cryptosystème NTRU

Les réseaux

Les attaques

CONTENU
1

Le cryptosystème NTRU
Introduction
Le principe de NTRU
Comparaison avec RSA

2

Les réseauxDéfinitions
Les problèmes SVP et CVP
Les solutions

3

Les attaques
Premières attaques
Attaques basées sur la réduction des réseaux4

ConclusionRéalitées et perspectives

Conclusion

Le cryptosystème NTRU

Les réseaux

Les attaques

CONTENU
1

Le cryptosystème NTRU
Introduction
Le principe de NTRU
Comparaison avec RSA

2

Les réseauxDéfinitions
Les problèmes SVP et CVP
Les solutions

3

Les attaques
Premières attaques
Attaques basées sur la réduction des réseaux4

ConclusionRéalitées et perspectives

Conclusion

Le cryptosystème NTRU

Les réseaux

Les attaques

Introduction

les algorithmes NTRUNTRUEncrypt
Proposé en 1996.
Le déchiffrement n’est pas garanti .
NSS
Proposée en 2001.
Cassée en 2001 (Gentry, Jonsonn, Stern, Szydlo).
NTRUSign
Proposée en 2002.
Partiellement cassée en 2006 (Nguyen, Regev).

Conclusion

Le cryptosystème NTRU

Les réseaux

Les attaques

Introduction

les algorithmes NTRUNTRUEncrypt
Proposé en 1996.
Le déchiffrement n’est pas garanti .
NSS
Proposée en 2001.
Cassée en 2001 (Gentry, Jonsonn, Stern, Szydlo).
NTRUSign
Proposée en 2002.
Partiellement cassée en 2006 (Nguyen, Regev).

Conclusion

Le cryptosystème NTRU

Les réseaux

Les attaques

Introduction

les algorithmes NTRUNTRUEncrypt
Proposé en 1996.
Le déchiffrement n’est pas garanti .
NSS
Proposée en 2001.
Cassée en 2001 (Gentry, Jonsonn, Stern, Szydlo).
NTRUSign
Proposée en 2002.
Partiellement cassée en 2006 (Nguyen, Regev).

Conclusion

Le cryptosystème NTRU

Les réseaux

Les attaques

Conclusion

Introduction

Introduction

NTRU
NTRU=Number Theorists aRe Us.
NTRU=N-th degree TRUncated polynomial ring.
Inventé et breveté en 1996 par J. Hoffstein, J. Pipher, J.H.
Silverman.
Investisseurs: Texas Instruments, Sonny Corpration,
Macrovision,...
Utilisation: Téléphone céllulaire, la radio identification(RFID).

Le cryptosystème NTRU

Les réseaux

Les attaques

Introduction

Principe des couleurs

La coleur rouge
Toutes les notations rouges sont secrètes.
La couleur bleue ou noire
Toutes les notations bleues ou noires sont publiques.

Conclusion

Le cryptosystème NTRU

Les réseaux

Les attaques

Conclusion

Le principe de NTRU

NotationsParamètres
N ∈ N, typiquement N = 251, 347, 503.
R = Z[X ]/(X N − 1), muni du produit de convolution :f (X ) = f0 + f1 X + · · P· + fN−1 X N−1 ∈ R.
f ∗ g = h avec hk = i+j≡k (mod N) fi gj .

p, q ∈ N (ou p ∈ Z[X ]) pour fixer les anneaux Z/pZ et
Z/qZ avec p < q et gcd(p, q) = 1.
Rp = (Z/pZ[X ])/(X N − 1).
Rq = (Z/qZ[X ])/(X N − 1).
Lf , Lg , Lr sous-ensembles de R. Leurs éléments
possèdent respectivement df dg , ou dr coefficients égaux à
1 et le reste des coefficients est nul.
Lm sous-ensemble de R à coefficients dans Z/pZ.

Le cryptosystème NTRU

Les réseaux

Les attaques

Conclusion

Le principe de NTRU

ParamètresSécurité
MoyenneHauteTrès haute

N
251
347
503

p
3 (2 + X )3 (2 + X )3 (2 + X )

q
128
128
256

df
72
64
420

dg
71
173
251

dr
72
64
170

Le cryptosystème NTRU

Les réseaux

Le principe de NTRU

Principe d’utilisation
B veut envoyer un message m à A
Préparation de A1

A choisit N, p, q.

2

A choisit f ∈ Lf , et g ∈ Lg .

3

A calcule fp ∈ Rp tel que fp ∗ f = 1.

4

A calcule fq ∈ Rq tel que fq ∗ f = 1.

5

A calcule h ∈ Rq avec h = fq ∗ g.

6

A publie sa clé publique (h, q, p, N).

7

La clé secrète de A est f (et fp ).

Les attaques

Conclusion

Le cryptosystème NTRU

Les réseaux

Les attaques

Le principe de NTRU

Principe d’utilisation

B veut envoyer un message m à A
Préparation de A: −→ h
Chiffrement par B
1

B transforme son message en un polynôme m ∈ Rp .

2

B choisit un polynôme aléatoire r ∈ Lr .

3

B calcule e = p ∗ r ∗ h + m (mod q) et envoi e à A.

Conclusion

Le cryptosystème NTRU

Les réseaux

Les attaques

Le principe de NTRU

Principe d’utilisation
B veut envoyer un message m à A
Préparation de A: −→ h
Chiffrement par B: −→ eDéchiffrement par A
1

A calcule a = e ∗ f (mod q).

2

A transforme les coefficients de a dans un intervalle[A, A + q − 1], (A est un paramètre ”pour le bonfonctionnement” de NTRU).

3

A calcule fp ∗ a = m (mod p).

Conclusion

Le cryptosystème NTRU

Les réseaux

Les attaques

Le principe de NTRU

Principe d’utilisation
B a envoyé un message m à A
Preuves1
2

fq ∗ f = 1 (mod q),
fp ∗ f = 1 (mod p),
e = p ∗ r ∗ h + m.
h = fq ∗ g,
a = e ∗ f (mod q)= (p ∗ r ∗ h + m) ∗ f (mod q)= p ∗ r ∗ h ∗ f + m ∗ f (mod q)= p ∗ r ∗ (fq ∗ g) ∗ f + m ∗ f (mod q)3= p ∗ r ∗ g + m ∗ f (mod q).
Avec le ”bon paramètre A”,
p ∗ r ∗ g + m ∗ f ∈ Z[X ]/(X N − 1).

4

fp ∗ a = fp ∗ p ∗ r ∗ g + fp ∗ m ∗ f (mod p) = m (mod p)

Conclusion

Le cryptosystème NTRU

Les réseaux

Les attaquesComparaison avec RSA

Equivalence des versions

RSA
n = 1024n = 2048
n = 4096

NTRU
N = 251
N = 347
N = 503

Conclusion

Le cryptosystème NTRU

Les réseaux

Les attaques

Conclusion

Comparaison avec RSA

Avantages et inconvénients
Avantages
Le chiffrement et le déchiffrement sont en O(N 2 ) contreO(n3 ) pour RSA.
Le chiffrement et le déchiffrement sont plus rapides que
RSA : de 30 à 300 fois plus rapide.
Inconvénients
Taille de la clé publiquede RSA (n).

Nlog2 (N/4) plus grande que celle2

Le déchiffrement n’est pas conforme une fois tous les 225
avec N = 251.

Le cryptosystème NTRU

Les réseaux

Les attaques

Conclusion

Comparaison avec RSA

Avantages et inconvénients
Avantages
Le chiffrement et le déchiffrement sont en O(N 2 ) contreO(n3 ) pour RSA.
Le chiffrement et le déchiffrement sont plus rapides que
RSA : de 30 à 300 fois plus rapide.
Inconvénients
Taille de la clé publiquede RSA (n).

Nlog2 (N/4) plus grande que celle2

Le déchiffrement n’est pas conforme une fois tous les 225
avec N = 251.

Le cryptosystème NTRU

Les réseaux

Les attaquesComparaison avec RSA

Signatures
Signatures NTRU
1NTRU Signature Scheme (NSS):
Proposée en 2000 .
Cassée en 2001 .

2

Revised NTRU Signature Scheme (R-NSS):
Proposée en 2001.
Cassée en 2002.

3

NTRUSign
Proposée en 2002 .
Cassée (Version non perturbée) en 2006.

4

Conclusion: Méfiance de la communauté scientifique.

Conclusion

Le cryptosystème NTRU

Les réseaux

Les attaques

Conclusion

Comparaison avec RSA

La sécurité de NTRU
La factorisation des polynômes modulaires
Rappel: la clé publique est h = fq ∗ g (mod q).
Hypothèse: Etant donné un polynôme h ∈ Zq [X ]/(X N − 1),
il est difficile de déterminer deux ”petits” polynômes f et gtels que f ∗ h = g (mod q).
Le problème SVP: the Shortest Vector Problem
Soit L un réseau. Déterminer le plus petit vecteur non nul de L.
Le problème CVP: the Closest Vector Problem
Soit L un réseau et v0 6∈ L∗ . Déterminer un vecteur v ∈ Lproche de v0 .

Le cryptosystème NTRU

Les réseaux

Les attaques

Conclusion

Comparaison avec RSA

La sécurité de NTRU
La factorisation des polynômes modulaires
Rappel: la clé publique est h = fq ∗ g (mod q).
Hypothèse: Etant donné un polynôme h ∈ Zq [X ]/(X N − 1),
il est difficile de déterminer deux ”petits” polynômes f et gtels que f ∗ h = g (mod q).
Le problème SVP: the Shortest Vector Problem
Soit L un réseau. Déterminer le plus petit vecteur non nul de L.
Le problème CVP: the Closest Vector Problem
Soit L un réseau et v0 6∈ L∗ . Déterminer un vecteur v ∈ Lproche de v0 .

Le cryptosystème NTRU

Les réseaux

Les attaques

Conclusion

Comparaison avec RSA

La sécurité de NTRU
La factorisation des polynômes modulaires
Rappel: la clé publique est h = fq ∗ g (mod q).
Hypothèse: Etant donné un polynôme h ∈ Zq [X ]/(X N − 1),
il est difficile de déterminer deux ”petits” polynômes f et gtels que f ∗ h = g (mod q).
Le problème SVP: the Shortest Vector Problem
Soit L un réseau. Déterminer le plus petit vecteur non nul de L.
Le problème CVP: the Closest Vector Problem
Soit L un réseau et v0 6∈ L∗ . Déterminer un vecteur v ∈ Lproche de v0 .

Le cryptosystème NTRU

Les réseaux

Les attaques

CONTENU
1

Le cryptosystème NTRU
Introduction
Le principe de NTRU
Comparaison avec RSA

2

Les réseauxDéfinitions
Les problèmes SVP et CVP
Les solutions

3

Les attaques
Premières attaques
Attaques basées sur la réduction des réseaux4

ConclusionRéalitées et perspectives

Conclusion

Le cryptosystème NTRU

Les réseaux

Les attaquesDéfinitions

Les réseaux
Le produit scalaire12

u = (u1 , u2 , · · · , un ) ∈ Rn , v = (v1 , v2 , · · · , vn ) ∈ Rn .
nX(u, v ) =ui vi .
i=1

La norme euclidienne12

u = (u1 , u2 , · · · , un ) ∈ Rn .
v
u n
p
uX
||u|| = (u, u) = t
ui2 .
i=1

Conclusion

Le cryptosystème NTRU

Les réseaux

Les attaquesDéfinitions

Les réseauxDéfinition
1

Soient b1 , b2 , · · · , bn ∈ Rn , n vecteurs linéairementindépendants.

2

Soit B = {b1 , b2 , · · · bn }.

3

Le réseau engendré par B est( nXL=
λ i bi ,)λi ∈ Z .

i=1

Caractéristiques1

dim(L) = n.

2

det(L) = |det(B)| = volumePn

i=1 αi vi ,0 ≤ αi < 1

Conclusion

Le cryptosystème NTRU

Les réseaux

Les attaques

Conclusion

Les problèmes SVP et CVP

Vecteurs courts
Le problème SVP: the Shortest Vector Problem
1

Soit L un réseau. Déterminer un court vecteur non nulv ∈ L : ||v || = λ1 (L) = inf{||u||, u ∈ L∗ }.

2

NP-dur, Ajtai, 1996 (pour des réductions polynômiales
probabilistes).

3

Peut être résolu en pratique pour les dimensions n ≤ 30.
A la base de certains cryptosystèmes :4

Ajtai-Dwork (1996), cassé par Ngyuen-Stern (1996) pourles petits paramètres et non pratique pour les grands
paramètres.
Cryptosystèmes ”Sac à dos” (dès 1978), cassés totalement(terminus en 1997).
NTRU

Le cryptosystème NTRU

Les réseaux

Les attaques

Conclusion

Les problèmes SVP et CVP

Vecteurs courts

Le problème CVP: the Closest Vector Problem
1

Soit L un réseau et v0 6∈ L∗ . Déterminer un vecteur v ∈ Lproche de v0 (||v − v0 || ≤ λ1 (L))

2

NP-dur, van Emde Boas, 1981.

3

Peut être résolu en pratique pour les dimensions n ≤ 30.
A la base de certains cryptosystèmes :4Goldreich-Goldwasser-Halevi (GGH) (1996), partiellement
cassé par Nguyen (1999), puis encore plus par Nguyen etRegev (2006).

Le cryptosystème NTRU

Les réseaux

Les attaques

Conclusion

Les solutions

Solution théorique

Le théorème de Minkowski
1

Soit L un réseau de dimension n. Il existe un vecteur non
nul v ∈ L tel que√||v || ≤ n det(L)1/n .

2Transformé en algorithme par Ajtai Kumar et Sivakumar en
2001, mais non pratique car le temps et l’espace sont en
2O(n) .

Le cryptosystème NTRU

Les réseaux

Les attaques

Les solutions

L’algorithme LLL
1

LLL=Lenstra-Lenstra- Lovasz, 1982.

2

Nombreuses améliorations.

Théorème
Soit L un réseau. L’algorithme LLL produit une base
(b1 , b2 , · · · , bn ) avec les propriétés
1
2
3

n−1

||b1 || ≤ 2 4 det(L)1/m .

nRelation avec SVP: ||b1 || ≤ 43 2 λ1 (L).
 n(n−1)
Qn
det(L) ≤ i=1 ||bi | ≤ 43 4 det(L).

Complexité : O n6 (log B)3 , avec B = maxi (||biinit ||).
Pratique pour les dimensions n ≤ 1000.

Conclusion

Le cryptosystème NTRU

Les réseaux

Les attaques

Les solutions

Applications de l’algorithme LLL
Cryptogaphie
1Résolution du problème du sac à dos.

2

Attaque de RSA.

3

Attaque des signatures NTRU.

Autres applications
Factorisation des polynômes.
Factorisation des entiers (LLL intervient dans NFS).
Equations diophantiennes.
Courbes elliptiques.
Théorie algébrique des nombres

Conclusion

Le cryptosystème NTRU

Les réseaux

Les attaques

Les solutions

L’algorithme BKZ

1BKZ=Block Korkine- Zolatarev,

2

Schnor-Euchner, 1994

3

Plus adapté pour résoudre le problème SVP.

4

Sa complexité n’est pas prouvé polnômiale.

Conclusion

Le cryptosystème NTRU

Les réseaux

Les attaques

CONTENU
1

Le cryptosystème NTRU
Introduction
Le principe de NTRU
Comparaison avec RSA

2

Les réseauxDéfinitions
Les problèmes SVP et CVP
Les solutions

3

Les attaques
Premières attaques
Attaques basées sur la réduction des réseaux4

ConclusionRéalitées et perspectives

Conclusion

Le cryptosystème NTRU

Les réseaux

Les attaques

Premières attaques

Attaques exhaustives

Attaque sur la clé publique1

Principe: h = fq ∗ g (mod q), donc f ∗ h = g (mod q).

2

Méthode: Tester tous les f ∈ Lf jusqu’à ce que f ∗ h(mod q) ait des petits coefficients.

Deuxième attaque sur la clé publique1

Principe: h = fq ∗ g (mod q), donc g ∗ h = f (mod q).

2

Méthode: Tester tous les g ∈ Lg jusqu’à ce que g ∗ h(mod q) ait des petits coefficients.

Conclusion

Le cryptosystème NTRU

Les réseaux

Les attaques

Premières attaques

Attaques exhaustives

Attaque sur la clé publique1

Principe: h = fq ∗ g (mod q), donc f ∗ h = g (mod q).

2

Méthode: Tester tous les f ∈ Lf jusqu’à ce que f ∗ h(mod q) ait des petits coefficients.

Deuxième attaque sur la clé publique1

Principe: h = fq ∗ g (mod q), donc g ∗ h = f (mod q).

2

Méthode: Tester tous les g ∈ Lg jusqu’à ce que g ∗ h(mod q) ait des petits coefficients.

Conclusion

Le cryptosystème NTRU

Les réseaux

Les attaques

Conclusion

Premières attaques

Attaques exhaustives
Attaque sur le message
1

Principe: e = m + pr ∗ h (mod q), donc e − pr ∗ h = m(mod q).

2

Méthode: Tester tous les r ∈ Lm jusqu’à ce que e − pr ∗ h(mod q) ait des petits coefficients.

Attaque par le milieu
1

Principe: h = fq ∗ g (mod q), donc f ∗ h = g (mod q).

2

On pose f = f1 + f2 .

3

Méthode: Tester tous les (f1 , f2 ) ∈ L2f jusqu’à ce que f 1 ∗ h(mod q) et f 1 ∗ h (mod q) ait des coefficients presqueidentiques.

Le cryptosystème NTRU

Les réseaux

Les attaques

Conclusion

Premières attaques

Attaques exhaustives
Attaque sur le message
1

Principe: e = m + pr ∗ h (mod q), donc e − pr ∗ h = m(mod q).

2

Méthode: Tester tous les r ∈ Lm jusqu’à ce que e − pr ∗ h(mod q) ait des petits coefficients.

Attaque par le milieu
1

Principe: h = fq ∗ g (mod q), donc f ∗ h = g (mod q).

2

On pose f = f1 + f2 .

3

Méthode: Tester tous les (f1 , f2 ) ∈ L2f jusqu’à ce que f 1 ∗ h(mod q) et f 1 ∗ h (mod q) ait des coefficients presqueidentiques.

Le cryptosystème NTRU

Les réseaux

Les attaques

Conclusion

Premières attaques

Attaques exhaustives
Attaque sur des transmissions multiples
Si on envoie k fois le même message m avec la même clé h.
1Principe: Pour 1 ≤ i ≤ k , on a ei = m + pr i ∗ h (mod q),
donc ei − e1 = p(ri − r1 ) ∗ h.

2

Méthode: Pour 2 ≤ i ≤ k , on calculeri − r1 = (ei − e1 ) ∗ p−1 ∗ h−1 (mod q).

3

Ceci donne des des informations sur certains coefficientsde r1 .

4

On fait une recherche exhaustive sur les coefficientsmanquants de r1 .

5

On calcule pour chaque r1 la valeur du message
m = e1 − pr1 ∗ h.

Le cryptosystème NTRU

Les réseaux

Les attaques

Conclusion

Attaques basées sur la réduction des réseaux

Les attaques
Coppersmith-Shamir, 1998
Principe: Puisque h = fq ∗ g (mod q), alors f ∗ h = g(mod q) avec f et g ”petits”.
Réseau: LCS = (a, b) ∈ Z2N , a ∗ h = b (mod q) .
La matrice correspondante est de la forme:


IN
0N


h0
hN−1 · · · h1




h1
h0
· · · h2


qI


..
..
.
N
.
.
.


. .
.
.
hN−1 hN−2 · · ·h0Réduire LCS et déterminer (f , g) parmi les petites solutions(a, b).

Le cryptosystème NTRU

Les réseaux

Les attaques

Conclusion

Attaques basées sur la réduction des réseaux

Les attaques
May, 2000
C’est une variante de l’attaque de Coppersmith-Shamir
Gentry, Jonsonn, Stern, Szydlo, 2001
Attaque contre la signature NSS.
Défaut: Chaque signature sur un message donne desrenseignements sur la clé privée.
Contrefaçon: Toute personne peut signer n’importe quelmessage sans connaı̂tre la clé privée.
Méthode basée sur la réduction de réseaux de dimension
2N (LLL et BKZ).

Le cryptosystème NTRU

Les réseaux

Les attaques

Conclusion

Attaques basées sur la réduction des réseaux

Les attaques
May, 2000
C’est une variante de l’attaque de Coppersmith-Shamir
Gentry, Jonsonn, Stern, Szydlo, 2001
Attaque contre la signature NSS.
Défaut: Chaque signature sur un message donne desrenseignements sur la clé privée.
Contrefaçon: Toute personne peut signer n’importe quelmessage sans connaı̂tre la clé privée.
Méthode basée sur la réduction de réseaux de dimension
2N (LLL et BKZ).

Le cryptosystème NTRU

Les réseaux

Les attaques

Conclusion

Attaques basées sur la réduction des réseaux

Les attaques

Gentry-Szydlo 2001
Attaque contre la version Revisée de NSS
Méthode : Réduction de réseaux sous-jacents à R-NSS etrésolution de SVP en temps polynômial.

Le cryptosystème NTRU

Les réseaux

Les attaques

Conclusion

Attaques basées sur la réduction des réseaux

Les attaques
Nguyen-Regev, 2006
Attaque contre la signature NTRUSign avec N = 251.
Défaut: Chaque signature sur un message donne desrenseignements sur la clé privée.
Problème sous-jacent: Connaissant un grand nombre depoints d’un parallélépipède inconnu, comment déterminerce parallélépipède.
Méthode basée sur la résolution de problèmes
d’optimisation.
Avec 90000 (amélioré à 400) signatures délivrées avec lamême clé privée, on peut retrouver cette clé.

Le cryptosystème NTRU

Les réseaux

Les attaques

CONTENU
1

Le cryptosystème NTRU
Introduction
Le principe de NTRU
Comparaison avec RSA

2

Les réseauxDéfinitions
Les problèmes SVP et CVP
Les solutions

3

Les attaques
Premières attaques
Attaques basées sur la réduction des réseaux4

ConclusionRéalitées et perspectives

Conclusion

Le cryptosystème NTRU

Les réseaux

Les attaques

ConclusionRéalitées et perspectives

Le présent et le futurRéalités
NTRU est encore au stade expérimental.
Nombreuse versions.
Faiblesse des signatures.
Déchiffrement non toujours conforme.
Perspectives
Chiffrement et déchiffrement rapides.
Une alternative à RSA?
Applications dans les puces radio RFID (Radio Frequency
Identification).

Le cryptosystème NTRU

Les réseaux

Les attaques

ConclusionRéalitées et perspectives

Le présent et le futurRéalités
NTRU est encore au stade expérimental.
Nombreuse versions.
Faiblesse des signatures.
Déchiffrement non toujours conforme.
Perspectives
Chiffrement et déchiffrement rapides.
Une alternative à RSA?
Applications dans les puces radio RFID (Radio Frequency
Identification).