La cryptographie du futur
Abderrahmane Nitaj
Laboratoire de Mathématiques Nicolas Oresme
Université de Caen, France
nitaj@math.unicaen.fr
http://www.math.unicaen.fr/~nitajRésuméSans nous rendre compte, la cryptographie fait déjà partie de notre vie
quotidienne. Notre carte bancaire, nos emails quotidiens, certains dvd, lestélévisions par satellite,.... fonctionnent de façon plus ou moins sûre grâce à lacryptographie. Dans le futur, la cryptographie est appelée à jouer un rôle encore plus important, non seulement dans les nouvelles technologies, mais aussi
dans la vie privée et publique : le vote électronique, les télécommunications,le payement électronique ... sont appelés à se développer de façon importante,
et les moyens cryptographiques doivent suivre cette évolution.
On présente ici les principes fondamentaux de la cryptographie, un peu
de son histoire, son présent et son développement dans le futur. On donneen particulier un aperçu des principaux procédés cryptographiques utilisésmassivement actuellement, tels que RSA, El Gamal, ECC ainsi qu’un aperçu
des procédés appelés à jouer un rôle important dans le futur, notamment
NTRU et LWE.

úæ. JJÜÏ @ ÈA¯ ® J»
AJ. J«  AJË@ H. ñJ« ú¯ P @ ÕËðÐ AÒJË@ úÎ« áK PXA®Ë@
A @ ÈA¯ð Ë@ IÊ£A¯
X ñÊmÌ '@ à AJk. ú¯ àA¿ ñËð È
YË@ ¨ Xð ù¢Ë ú¯ Qª
.

1

1

Introduction

La cryptographie est l’art de chiffrer et de déchiffrer les textes par des moyens
définis par les entités qui communiquent entre elles. La cryptanalyse est l’art dedéchiffrer les textes chiffrés par des entités qui interceptent les communications,autre que les destinataires. Il est facile de se rendre compte de l’importance de la
cryptographie dans le monde moderne, mais son invention remonte à plus de 4000
ans. En effet, les premiers symboles hiéroglyphiques représentaient des textes chiffrés
et seuls quelques scribes pouvaient les déchiffrer. Une fois l’écriture hiéroglyphiques’est répondue, l’aspect cryptographique a disparu. Ce principe s’est répété dansplusieurs autres civilisations. En Chine par exemple, l’écriture, qui était très peu
répandu, pouvait être considérée comme une technique cryptographique. Les chinois
avaient aussi développé la technique de la stéganographie qui consiste à dissimuler
les messages. On retrouve d’autres aspects de la cryptographie dans d’autres civilisations antiques : indienne, perse, mésopotamienne, greque et romaine. Les techniques
cryptographiques romaines par exemple étaient basées sur le décalage de l’alphabet.
Cette technique cryptographique est appelée chiffre de César.
La cryptanalyse, science du déchiffrement, naquit avec l’essor de la civilisation
arabo-musulmane. Le nom dominant de cette époque est certainement Al Kindi
(801-873) ø YJºË@ Am @ áK. @ H. ñ®ªK ­ñK ñK. @ qui travailla pour Al Mamoun àñÓAÜÏ @

 K.. La technique de cryptanalyseà la Maison de la Sagesse, Baitu alhikmata éÒºmÌ '@ Iinventée par Al Kindi est basée sur l’analyse des fréquences et fut utilisée jusqu’à lafin de la première guerre mondiale en 1918.
En 1918, les allemands Arthur Scherbius et Richard Ritter inventèrent une
machine à chiffrer électrique et automatique : Enigma. Pendant une longue période,les cryptographes polonais, français, anglais et allemands bataillèrent pour casser ou
renforcer Enigma. Ce ne fut qu’en 1940 qu’Alan Turing a pu inventer une machinepour déchiffrer les textes chiffrés par Enigma.
Aujourd’hui, la cryptographie est utilisée dans un grand nombre de produits.
On la trouve ainsi dans les votes électroniques, les signatures électroniques, le paiement par cartes bancaires, le courrier électronique, les bases de données, les cartesà puces, les portes monnaies électroniques, les décodeurs numériques, les achatsélectroniques, le téléphones cellulaires...

2

2

Le présent

Dans les processus cryptographiques modernes, on distingues deux types decryptographie, la cryptographie à clé secrète et la cryptographie à clé publique.
Dans la cryptographie à clé secrète, le chiffrement est symétrique et utilise la mêmeclé pour chiffrer et déchiffrer. Dans la cryptographie à clé publique, inventée par
Diffie et Hellman [3], le chiffrement est asymétrique et utilise une clé pour chiffrer etune clé différente pour déchiffrer. Ces deux clés sont généralement liées entre elles
par des formules plus ou moins complexes. L’inconvénient de la cryptographie àclé secrète est que les entités doivent échanger les clés. De plus, chaque entité doit
avoir échangé autant de clés que de partenaires. Pour cette raison, la cryptographieà clé publique joue un rôle important dans les communications modernes car une
seule clé, rendu publique par une entité, peut servir pour tous ses partenaires. Le
principal inconvénient de la cryptographie à clé publique vient du fait que les temps
de calculs deviennent importants. Pour pallier à cet inconvénient, il est possible
d’utiliser une cryptographie hybride, qui consiste à utliser la cryptographie à clésecrète en échangeant les clés par la cryptographie à clé publique.
Comme exemples de systèmes symétriques, on peut citer DES (Data Encryption Standard), remplacé en 2000 par Rijndael, le standard AES (Advanced Encryption Standard) de NIST (National Institute of Standards and Technology).
Parmi les exemples de systèmes asymétriques, on peut citer RSA, El Gamal,
ECC et NTRU.
• Le cryptosystème RSA a été inventé en 1977 par R. Rivest, A. Shamir et L.
Adleman [17]. La sécurité de RSA est basée sur la difficulté de factoriser lesgrands nombres entiers du type N = pq où p et q sont des nombres premiers,
et sur la difficulté d’extraire la racine n-ième d’un entier modulo un grandnombre entier dont la factorisation est inconnue :Etant donné des nombres entiers n, N et a, déterminer un entier x tel que
xn ≡ a (mod N ).
• Le cryptosystème El Gamal a été inventé par T. El Gamal [4] en 1985. La
sécurité de ce cryptosystème est basée sur le problème du logarithme discret :Etant donné deux nombres entiers g et a et un nombre premier p,déterminer un entier x tel que g x ≡ a (mod p).
• L’idée des cryptosystèmes de type ECC (Elliptic Curve Cryptography) àété introduite de façon indépendante en 1985 par N. Koblitz [7] et V.S.
Miller [12]. La sécurité de ces cryptosystèmes est basée sur le problème dulogarithme discret elliptique :Etant donné deux points P et Q d’une courbe elliptique E, déterminer unentier n tel que nP = Q.
• Le cryptosystème NTRU a été inventé entre 1996 et 1998 par J.H. Silverman,
3

J. Hoffstein et J. Pipher [5]. La sécurité de NTRU est basée sur le problème
du plus court vecteur non nul d’un réseau (SVP) :Etant donnée une base B d’un réseau L, déterminer un vecteur non nul deL, le plus court possible pour la norme euclidienne.

2.1

RSA

Depuis son invention en 1977, RSA est devenu un cryptosystème central en
cryptographie.
2.1.1Générations de clés

Le module RSA est un nombre entier N = pq qui est le produit de deux
nombres premiers p et q. La fonction indicatrice d’Euler est définie par ϕ(N ) =(p − 1)(q − 1). Soit e un entier vérifiant 3 ≤ e < ϕ(N ) et gcd(e, ϕ(N )) = 1. On peut
donc déterminer un entier d qui vérifie
ed ≡ 1(mod ϕ(N )).

L’entier e est appelé exposant publique et d est l’exposant privé correspondant. Laclé publique est (N, e), alors que la clé privée est (N, d).
2.1.2

Chiffrement d’un message

Pour chiffrer un message clair M , on le transforme en un nombre entier positif
m avec m < ϕ(N ) et on calcule l’entier chiffré c en utilisant la clé publique (N, e) :c ≡ me(mod N ).

Le message chiffré c peut alors être transmis.
2.1.3

Déchiffrement d’un message

Pour déchiffrer un message chiffré c et retrouver le message clair m, il suffit decalculerm ≡ cd (mod N ).
L’exactitude du déchiffrement est basée sur la propriété suivante :kcd ≡ (me )d ≡ med ≡ m1+kϕ(N ) ≡ m mϕ(N ) ≡ m (mod N ),où k est l’unique entier vérifiant ed = 1 + kϕ(N ). La dernière égalité provient duthéorème suivant.
4

Théorème 2.1 (Euler). Soit N un nombre entier et ϕ(N ) l’indicateur d’Euler. Sia est un entier premier avec N , alorsaφ(N ) ≡ 1

2.2(mod N ).

El GamalInventé en 1985 par T. El Gamal [4], le cryptosystème El Gamal a pour univers
un groupe fini.
2.2.1

Générations de clés

Soient p un grand nombre premier et g un générateur du groupe fini F∗p =Z/pZ∗ . Soit a un nombre entier vérifiant 2 ≤ a ≤ p − 1. On poseb ≡ ga(mod p).

La clé publique est le triplet (p, g, b), tandis que la clé privée est (p, g, a).
2.2.2

Chiffrement d’un message

Pour chiffrer un message clair M , on le transforme en un nombre entier positif
m avec m < p − 1. Soit k un nombre entier aléatoire avec 2 ≤ k ≤ p − 2. On calcule
alors les quantités γ et δ en utilisant la clé publique (p, g, b) par :γ ≡ gkδ ≡ mbk(mod p),(mod p).

Le message chiffré est le couple (γ, δ) et peut alors être transmis.
2.2.3

Déchiffrement d’un message

Pour déchiffrer un message chiffré (γ, δ) et retrouver le message clair m, il suffitd’utiliser la clé privée (p, g, a) et de calculerm ≡ γ −a δ(mod p).

L’exactitude du déchiffrement est basée sur la propriété suivante :
−a k
−a
γ −a δ ≡ g k
mb ≡ g km (g a )k ≡ m (mod p).

5

2.3

ECC

La théorie des courbes elliptiques est très ancienne mais son utilisation en
cryptographie date de 1985 et a été proposée indépendamment par N. Koblitz [7] etV.S. Miller [12]. L’idée était de transformer les cryptosystèmes utilisant des groupes
finis du type F∗p en cryptosystèmes utilisant l’arithmétique des courbes elliptiques.
Pour une introduction aux courbes elliptiques et leur utilisation en cryptographie,on peut consulter par exemple [11].
Soit K un corps. Par exemple, K = Q, K = R, K = C, K = Fp ou K = Fpr ,où p est un nombre premier et r ≥ 1. Une courbe elliptique définie sur K peut être
caractérisée par son equation Weierstrass.
Définition 2.2. Une courbe elliptique E définie sur K est une courbe dont l’équationde Weierstrass est
E:

y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 ,en plus du point à l’infini O = (0 : 1 : 0). L’union de {O} et de l’ensemble despoints P = (x, y) ∈ K 2 de la courbe E est noté E(K).
Une particularité importante de E(K) est sa structure de groupe additif. Toutd’abord, l’opposé d’un point P (x, y) est le point −P défini par−P = (−x, −y − a1 x − a3 ).
La somme de deux point P et Q est un point R obtenu en utilisant la droite qui
passe par P et Q si P 6= Q ou la tangente à la courbe en P si P = Q comme indiquédans les figures ci-dessous.

En utilisant les coordonnées des points, le doublement et l’addition sont définies
de façons explicites.
6• Doublement. Soit P = (x, y) un point de E(K).
1. Si 2y + a1 x + a3 = 0, alors 2P = O.
2. Si 2y + a1 x + a3 = 0, alors 2P = (x3 , y3 ) avec
x3 = −2x − a2 + a1 λ + λ2 ,y3 = −y − (x3 − x)λ − a1 x3 − a3 ,où

3x21 + 2a2 x1 + a4 − a1 y1
λ=.
2y1 + a1 x1 + a3

• Somme. Soient P = (x1 , y1 ) et Q = (x2 , y2 ) deux points de E(K) avec
P 6= Q.
1. Si x1 = x2 , alors P + Q = O.
2. Si x1 6= x2 , alors P + Q = (x3 , y3 ) avec
x3 = −x1 − x2 − a2 + a1 λ + λ2 ,y3 = −y1 − (x3 − x1 )λ − a1 x3 − a3 .
où
λ=y2 − y1.
x2 − x1

Certains protocoles cryptographiques peuvent être alors adaptés avec les courbes
elliptiques.
2.3.1

Echange de clés de Diffie et Hellman

Si deux personnes A et B veulent échanger une clé, ils peuvent procéder commesuivant.
• A et B s’accordent pour choisir une courbe elliptique E définie sur Fp et un
point P ∈ E(K) ayant un grand ordre, c’est à dire que le plus petit entier
non nul n vérifiant nP = O est assez grand.
• A choisit un entier kA avec 2 ≤ kA ≤ n − 1 et calcule QA = kA P = (xA , yA ).
A envoie alors QA à B.
• B choisit un entier kB avec 2 ≤ kB ≤ n − 1 et calcule QB = kB P = (xB , yB ).
B envoie alors QB à A.
• En recevant QB = kB P = (xB , yB ), A calcule alors kA QB .
• En recevant QA = kA P = (xA , yA ), B calcule alors kB QA .
• La clé commune est alors kA QB = kA kB P = kB kA P = kB QA .

7

2.3.2El Gamal avec les courbes elliptiques

Il est très facile d’adapter le cryptosystème El Gamal en utilisant les courbes
elliptiques. On suppose qu’une personne A veut envoyer un message à une autre
personne B.
• Les personnes A et B s’accordent sur une une courbe elliptique E définie
sur K = Fp et un point P ∈ E(K) ayant un grand ordre, c’est à dire que leplus petit entier non nul n vérifiant nP = O est assez grand.
• A choisit un entier kA avec 2 ≤ kA ≤ n − 1 et calcule QA = kA P = (xA , yA ).
La clé publique de A est kA P et sa clé secrète est kA .
• B choisit un entier kB avec 2 ≤ kB ≤ n − 1 et calcule QB = kB P = (xB , yB ).
La clé publique de B est kB P et sa clé secrète est kB .
• Pour envoyer le message M à B, A doit le transformer en un point m deE(K). En utilisant la clé publique kB P de B, A calcule ensuite m + kA (kB P )et envoie ce message chiffré à B.
• En recevant m+kA (kB P ), B calcule m+kA (kB P )−kB (kA P ) = m en utlisantla clé publique kA P de A.

3

Le futur

Actuellement, les cryptosystèmes à clés publiques les plus dominants sont RSA,El Gamal, et dans une moindre mesure ECC. Dans le futur, et dans l’hypothèse d’undéveloppement rapide des ordinateurs quantiques, ces cryptosystèmes sont appelésà être abandonnés. En effet, avec un ordinateur quantique, l’algorithme de Shor [18]permet de résoudre le problème du logarithme discret aussi bien elliptique que surles corps finis et permet aussi de factoriser un nombre entier en temps polynomial.
Apparemment, le cryptosystème NTRU résiste aux ordinateurs quantiques. Il enrésulte que NTRU est certainement l’un des plus grands systèmes du futur. D’autres
cryptosystèmes qui peuvent jouer un rôle important dans le futur sont basés eux
aussi sur les réseaux, en particulier en utilisant le problème du Learning With Errors(LWE) [16], ou encore des cryptosystèmes basés sur les codes comme McEliece [10]et Niederreiter [13], ainsi que le classique Rinjdael (AES). Les cryptosystèmes qui
résistent aux ordinateurs quantiques sont appelés “post quantum cryptosystems”.

3.1

NTRU

Le cryptosystème NTRU à été présenté en 1996 et publié en 1998 [5]. Son
domaine de calculs est l’anneau des polynômes Z[X]/(X N − 1) où N est un nombre
entier. Il se compose de deux protocoles. Le protocole de chiffrement-déchiffrement
8

NTRUEncrypt et le protocole de signature NTRUSign. NTRU est aujourd’hui considéré
comme fiable par le standard IEEE P1363.1 [6].
3.1.1Définitions

Le cryptosystème NTRU utilise trois nombres entiers, N , p et q. Les opérationsde NTRU ont pour domaine l’anneau des polynômes P avec :
P = Z[X]/ X N − 1 .
Les polynômes de P peuvent être représentés sous la forme
f = (f0 , f1 , · · · , fN −1 ) =N−1X

fi X i .

i=0

L’addition de deux polynômes f, g ∈ P se fait terme à terme de même degrés, alors
que la multiplication
se fait par
produit de convolution
PN −1 noté i ∗. Si f ∗ g = h
Pun
PN −1
N −1
i
i
g
X
,
alors
h
=
f
X
et
g
=
avec f =iii=0 hi X avec pour touti=0
i=00 ≤ k ≤ N − 1,
hk =

X
i+j≡k

f i gj =

mod N

k
X
i=0

N
−1
X

fi gk−i +fi gN +k−i .

i=k+1

Soient p, q ∈ P deux polynômes premiers entre eux. Généralement, q est de la forme
q = 2l avec l = blog2 N c et p = 2 ou p = 3 ou dans certaines versions p = 2 + X.
Soit Zq l’anneau des entiers
 modulo q, c’est à dire Zq = Z/qZ. Dans NTRU, Zq est
représenté par l’intervalle − 2q , 2q . En réduisant P modulo q, on obtient l’anneau
Pq = Zq [X]/(X N − 1).
Ainsi un polynôme f = (f0 , f1 , · · · , fN −1 ) ∈ P sera représenté par le polynôme
πq (f ) = (f0(mod q), f1(mod q), · · · , fN −1(mod q)) ∈ Pq .

Un polynôme f ∈ Pq est dit inversible modulo q s’il existe un polynôme fq dans Pq
tel que f ∗ fq = fq ∗ f ≡ 1 (mod q). De façon similaire, pour un polynôme p ∈ P,
on définit l’anneau Pp par
Pp = Z[X]/ X N − 1, p ,obtenu en réduisant P modulo p. Si p est un entier, alors Pp = Zp [X]/ X N − 1 .

9

3.1.2

Paramètres de NTRU

Soit d un entier positif. On pose
(
)
d
X

B(d) = f ∈ Z2 [X]/ X N − 1 | f =X ni , 0 ≤ n1 < · · · < nd ≤ N .
i=1

Ainsi, les éléments de B(d) ont exactement d coefficients égaux à 1 et le reste descoefficients est nul. De même, soient d1 et d2 deux entiers positifs. On pose
(
)
d1
d2
X
X

T (d1 , d2 ) = f ∈ Z3 [X]/ X N − 1 | f =X ni −X mj , ni 6= mj .
i=1

j=1

Autrement dit, T (d1 , d2 ) est l’ensemble des polynômes ayant exactement d1 coefficients égaux à 1, d2 coefficients égaux à -1 et le reste des coefficients est nul.
Les paramètres de NTRU sont les suivants.
• Un nombre entier N . Ce nombre doit être premier et assez grand.
• Un nombre entier q, généralement de la forme q = 2l avec l = blog2 (N )c.
• Un paramètre p qui est soit un nombre entier p premier avec q soit unpolynôme p = α +βX ∈ Z[X], inversible modulo q. Généralement p = 2+X
ou p = 3.
• Un ensemble Lf ⊂ P de polynômes f .
• Un ensemble Lg ⊂ P de polynômes g.
• Un ensemble Lm ⊂ P de messages secrets.
• Un ensemble Lr ⊂ P de polynômes auxiliaires secrets.
Suivant les versions de NTRU, on rencontrer les paramètres ci-dessus.
Version
1998
2001
2005

p
3
2+X
3

q
2k
2k
2k

Lf
Lg
T (df , df − 1) T (dg , dg )1+p∗FB(dg )
1+p∗F
B(dg )Lr
Lm
T (dr , dr ) T (dm , dm )B(dr )
B(dm )
B(dr )
B(dm )Les nombres entiers df , dg , dr et dm sont fixés pour chaque version. Actuellement,
ces paramètres sont les suivants (voir [5]) :Sécurité
MoyenneHauteTrès haute

N
251
347
503

p
3
3
3

q
df
dg
dr
128 72 71 72
128 64 173 64
256 420 251 170
10

3.1.3

Utilisation de NTRU

Si une personne B souhaite envoyer un message M à une personne A, alors leprocessus peut se faire en trois étapes :1. A doit générer une clé publique h et des clés privées f et fp .
2. B doit transformer le message clair M en un message chiffré e et envoyer lemessage chiffré e à A.
3. A doit déchiffrer le message reçu e et retrouver le message clair M .
3.1.4

Générations de clés
Pour commencer, la personne A doit préparer ses paramètres.
Génération des clés :1. A choisit aléatoirement un polynôme f ∈ Lf .
2. A calcule l’inverse fq de f dans Pq , c’est à dire f ∗ fq ≡ 1 (mod q).
3. A calcule l’inverse fp de f dans Pp , c’est à dire f ∗ fp ≡ 1 (mod p).
4. A choisit aléatoirement un polynôme g ∈ Lg .
5. A calcule h ≡ p ∗ g ∗ fq (mod q) dans Pq .
La clé publique est h et la clé secrète est (f, fp ).

3.1.5

Chiffrement

Pour chiffrer un message M, la personne B doit le transformer en un polynômem ∈ Lm et ensuite le transformer en un polynôme chiffré e avec la procédure suivante.
Chiffrement :1. B choisit aléatoirement un polynôme r ∈ Lr .

Le

2. B calcule e ≡ r ∗ h + m (mod q) dans Pq .
message chiffré est alors e et peut être envoyé à A.
3.1.6

Déchiffrement

Pour déchiffrer un message e ∈ Pq , la personne A doit utiliser ses clés secrètes
f et fp .

11

Déchiffrement :1. A calculea ≡ f ∗ e (mod q) dans Pq avec des coefficients dans l’inter
valle − 2q , 2q .
2. A calcule m ≡ fp ∗ a (mod p) dans Pp .
L’exactitude du processus est dans la propriété suivante.
a ≡
≡
≡
≡
≡

f ∗ e (mod q)f ∗ (r ∗ h + m) (mod q)
f ∗ r ∗ (p ∗ g ∗ fq ) + f ∗ m (mod q)
p ∗ r ∗ g ∗ f ∗ fq + f ∗ m (mod q)
p ∗ r ∗ g + f ∗ m (mod q).

Alors
fp ∗ a ≡ fp ∗ (p ∗ r ∗ g + f ∗ m) ≡ fp ∗ p ∗ r ∗ g + fp ∗ f ∗ m ≡ m(mod p).

En faite, avec une faible probabilité, on peut obtenir un message différent de l’original, mais ce défaut fut finalement corrigé en adaptant les paramètres de départ.
3.1.7

La sécurité de NTRU
La sécurité de NTRU est basée sur deux problèmes difficiles, SVP et CVP.

Soit m un entier positif. On considère l’ensemble Rm des vecteurs u = (u1 , · · · , um ),muni du produit scalaire et de la norme euclidienne.
Définition 3.1. Soient u = (u1 , · · · , um ) et v = (v1 , · · · , vm ) deux vecteurs de Rm .
Le produit scalaire de u et v est
hu, vi =mXui vi .

i=1

Définition 3.2. Soit u = (u1 , · · · , um ) un vecteur de Rm . La norme euclidienne de
u est
v
u m
p
uX
||u|| = hu, ui = tu2i
i=1Soit n un entier positif avec n ≤ m. Soient (b1 , · · · , bn ) des vecteurs linéairementindépendants de Rm . Soit B la matrice dont les colonnes sont composées des coordonnées des vecteurs b1 , · · · , bn .
12

Définition 3.3. Le réseau engendré par la famille (b1 , · · · , bn ) (ou par B) est l’ensemble
( n
)
n
X
X
L=
Zbi =
x i bi | x i ∈ Z .
i=1

i=1

L’entier n est la dimension de L.
Un réseau L admet plusieurs bases. Le passage entre deux bases se fait à l’aide
d’une matrice carrée à coefficients dans Z, de déterminant ±1. Parmi toutes les
bases possibles, certaines ont de meilleures propriétés que d’autres. La recherched’une bonne base est un problème NP-complet. En 1982, Lenstra, Lenstra et Lovasz [9] ont proposé l’algorithme LLL qui détermine une base avec de très bonnes
propriétés. L’algorithme LLL est très efficace puisque sa complexité est polynomiale.
On remarque en particulier que l’algorithme LLL produit des bases avec des vecteursassez courts, ce qui peut apporter une réponse partiellement satisfaisante aux deux
problèmes (NP-durs) sur lesquels repose la sécurité de NTRU.
Problème SVP, Shortest Vector Problem (problème du plus court vecteur) : Etant donné une base B d’un réseau L, trouver un vecteur non nul de L leplus court possible pour la norme euclidienne.
Problème CVP, Closest Vector Problem (problème du plus proche vecteur) : Etant donné une base B d’un réseau L et un vecteur v0 , trouver un vecteurde v ∈ L le plus proche possible de v0 pour la norme euclidienne.

3.2

Learning With Errors (LWE)

En 2005, Regev [16] a introduit un problème appelé “Learning With Errors”(LWE). Il s’agit de résoudre un système de presque-équations.
Soient p un nombre premier. On pose Zp = Z/pZ. Soit n ≥ 1 un nombre entier.
Le produit de deux vecteurs s = (s1 , · · · , sn ) ∈ Znp et ai = ((ai )1 , · · · , (ai )n ) ∈ Znp
est par définition :nXhs, ai i =sj (ai )j .
j=1

Soit χ une distribution de probabilité χ : Zp → R+ sur Zp . Soit m un entieret e1 , · · · , em des valeurs de Zp choisis indépendamment selon χ. On considère le13

système de m équation avec erreurs d’inconnues shs, a1 i + e1
hs, a2 i + e2..
.
hs, am i + em

= b1 ,= b2 ,.
= ..
= bm .

m
Le problème LWE est de déterminer s connaissant les vecteurs (a1 , · · · , am ) ∈ Znp
et (b1 , · · · , bm ) ∈ Zm
p . Regev a montré que ce problème est difficile et peut donc servirà la construction de cryptosystèmes.
Un cryptosystème à base de LWE (Regev 2005)• Paramètres : Choisir un nombre premier p, deux paramètres m et n, et
une distribution de probablité χ.
• La clé privée : Choisir aléatoirement un clé privée s ∈ Znp .
• La clé publique :1. Choisir m vecteurs ai ∈ Znp , i = 1, · · · , m, de façon indépendante.
2. Choisir des entiers e1 , · · · , em ∈ Z de façon indépendante relativementà χ.
3. Pour i = 1, · · · , m, calculer bi = hs, ai i + ei .
4. Former la clé publique ((a1 , b1 ), · · · , (am , bm )).
• Chiffrement : Le chiffrement se fait bit par bit.
1. Choisir aléatoirement un sous-ensemble S parmi les 2m sous-ensembles
de l’intervalle [1, m].
PPbi (mod p) .
2. Si le bit est 0, calculeri∈S ai (mod p),  i∈S

 P
P
p
a
(mod
p),
3. Si le bit est 1, calculer
b
(mod
p)
où
+
i
i
i∈S
i∈S
2
bxc désigne la partie entière de x.
• Déchiffrement : Pour déchiffrer une paire (a, b) ∈ Znp × Z.
1. Calculer c ≡ b − hs, ai (mod p).
 
2. Si c est plus proche de 0 que de p2 , alors le bit est 0, sinon le bit est
1.
Regev a montré que casser ce cryptosystème revient à résoudre le problème
SVP à l’aide d’un algorithme quantique à temps polynomial.

4

Conclusion

Un certain nombre de cryptosystèmes basés sur des problèmes issus de lathéorie des réseaux commencent à émerger. Ces cryptosystèmes sont appelés à jouer14

un rôle de plus en plus déterminant dans le futur et la cryptographie telle qu’elle est
pratiquée aujourd’hui et qui est basée sur RSA et El Gamal sera dans l’obligation decéder la place. En effet, la cryptographie du présent ne résistera pas aux ordinateurs
quantiques contrairement aux nouveaux cryptosystèmes émergents tels que NTRU
et les cryptosystèmes basés sur LWE.

Références[1] H. Cohen, A Course in Computational Number Theory, Graduate Texts in
Mathematics, Springer, 1993.
[2] D. Coppersmith and A. Shamir, Lattice attacks on NTRU. In Advances incryptology—EUROCRYPT ’97, volume 1233 of Lecture Notes in Comput. Sci.,
pages 52–61. Springer, Berlin, 1997.
[3] W. Diffie, E. Hellman, New Directions in Cryptography, IEEE Trans- actions
on Information Theory, 22, 5 (1976), pp. 644–654.
[4] T. El Gamal, A public key cryptosystem and signature scheme based on discrete
logarithms. IEEE Transactions on Information Theory IT-31, 496-473,1976.
[5] J. Hoffstein, J. Pipher, and J. H. Silverman, NTRU : A Ring Based Public
Key Cryptosystem in Algorithmic Number Theory. Lecture Notes in Computer
Science 1423, Springer-Verlag, pages 267–288, 1998.
[6] IEEE P1363.1 Public-Key Cryptographic Techniques Based on Hard Problems
over Lattices, June 2003. IEEE.
[7] N. Koblitz, Elliptic curve cryptosystems, Mathematics of Computation 48,
1987, pp. 203–209[8] N. Koblitz, A Course in Number Theory and Cryptography, Springer-Verlag,
New York, 1994.
[9] A.K. Lenstra, H.W. Lenstra and L. Lovasz, Factoring polynomials with rationalcoefficients, Mathematische Annalen, Vol. 261, 513—534, 1982.
[10] McEliece, R.J. : A public-key cryptosystem based on algebraic coding theory.
The Deep Space Network Progress Report 42–44, Jet Propulsion Laboratory,
Pasadena, CA, (1978), 114–116.
[11] A. Menezes, Elliptic Curve Public Key Cryptosystems, Kluwer Academic Publishers, Boston, 1993.
[12] V.S. Miller, Use of elliptic curves in cryptography, CRYPTO 85, 1985.
[13] H. Niederreiter. Knapsack-Type Cryptosystems and Algebraic Coding Theory.
Problems of Control and Information Theory (Problemy Upravlenija i Teorii
Informacii) 15, 1986, pages 159–166.
15

[14] NTRU Inc. http://www.ntru.com/[15] NTRU Inc. http://www.ntru.com/cryptolab/faqs.htm#six[16] O. Regev, On lattices, learning with errors, random linear codes, and cryptography, STOC 2005, ACM (2005) p. 84–93.
[17] R. Rivest, A. Shamir, L. Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Communications of the ACM, Vol. 21(2), 120—126 (1978)[18] P.W. Shor, Polynomial-time algorithms for prime factorization and discrete
logarithms on a quantum computer, SIAM J. Computing 26, pp. 1484-1509(1997).

16