Chiffrement homomorphe

Chapitre I

Un groupe est un ensemble G muni d'une loi de composition interne notée multiplicativement * tel que :

· la loi * soit associative :(x * y) * z = x * (y * z),

· la * possède un élément neutre e E G : Vx E Gx * e = e * x = x,

· tout élément x E G possède un symétrique (ou inverse) pour *, noté x^-1, satisfaisant x*x^-1 = x-1 * x = e.

Définition 1.1.1 (Groupe)

· Si de plus,Vx, y E G , on a alors x * y = y * x est dit commutatif (ou abélien)

GENERALITES

Ce chapitre porte sur les généralités des notions mathématiques liées au chiffrement homomorphe.

1.1 Notions mathématiques

Dans cette sous section nous présentons les notions essentielles sur les structures algébriques utiles pour comprendre le chiffrement homomorphe.

1.1.1 Structures algébriques

Soit (G, *) un groupe et H une partie de G. On dit que (H, *) est un sous-groupe de G si :

· H est stable pour la loi *

· (H,*) lui-même est un groupe.

Définition 1.1.2 (Sous-groupe)

Mémoire de Master 2 Recherche 5 MOUYOUME DIEUDONNE(c) UYI

1.1 Notions mathématiques 6

Définition 1.1.6 (Corps)

Un corps est un anneau commutatif dans lequel tout élément non nul est inversible.

Si H est un sous-groupe de (G, *) si et seulement si :

· H contient l'élément neutre du groupe;

· Vx,y E H, x * y^-1 E H.

Proposition 1.1.1

un homomorphisme est une application f : (G, *) -- (G^', *) , entre deux groupes (G, *) et (G^', *) , qui vérifie :

V(g, h) E G², f(g * h) = f(g) * f(h).

Définition 1.1.3 (Homomorphisme de groupe)

Un anneau est la donnée d'un ensemble A et de deux lois de composition interne notées + et x sur A vérifiant les propriétés suivantes :

· (A, +) est un groupe abélien dont le neutre est noté 0A ;

· La loi x est associative : pour tous x, y et z de A, x x (y x z) = (x x y) x z,

· La multiplication x est distributive par rapport à + : pour tout élément x,yetz,xx(y+z)=(xxy)+(xxz)et(x+y)xz=(xxz)+(yxz).

· la loi x possède un élément neutre noté 1A ;

Lorsque la loi x est commutative, on dit que l'anneau A est commutatif.

Définition 1.1.4 (Anneau)

I c A est un idéal d'un anneau commutatif (A, +, *) si et seulement si :

(I, +) est un sous-groupe additif de (A, +)

Va E A,Vx E I,a * x E I

Définition 1.1.5 (Idéal d'un anneau)

Mémoire de Master 2 Recherche 6 MOUYOUME DIEUDONNE(c) UYI

1.1 Notions mathématiques 7

Définition 1.1.7 (Corps d'un polynôme)

Si (V[X], +, X) est un anneau commutatif unitaire et P E V[X] un polynôme irréductible, alors V[X]/(P) est un corps

1.1.2 Problèmes difficiles sur les entiers

Problème 1.1.1 (Factorisation d'entier)

Étant donné un entier naturel n = pq, avec p et q premiers, retrouver p et q

Résoudre ce problème est simple lorsque le nombre n est petit.

Étant donné (n, e, y) avec y E (7L/n7L)^* et n = pq trouver x tel que y [x^e]_n.

Un nombre n de la forme pq où p et q sont deux grands nombres premiers est appelé un module RSA.

Problème 1.1.2 (RSA)

L'algorithme de chiffrement RSA a été inventé par Ron Rivest, Adi Shamir et Leonard Adleman en 1977. Il fut l'un des premiers algorithmes de chiffrement dit à clé publique, c'est-à-dire que le chiffrement d'un message ne requiert pas que l'expéditeur partage un secret avec le destinataire. Il est devenu, depuis, l'un des algorithmes de chiffrement et d'authentification les plus utilisés au monde.

Problème 1.1.3 (Logarithme discret (DLP) dans ?/p?)

Étant donné un nombre premier p, un élément générateur g qui engendre tout le groupe, et un élément cible h, calculer un entier x, 0 < x < p tel que g^x = h.

Mémoire de Master 2 Recherche 7 MOUYOUME DIEUDONNE(c) UYI

On parle de logarithme, car c'est une fonction inverse de l'exponentiation, discret, car il prend des valeurs entières, entre 0 et p - 1.

En 1976, W. Diffie et M. Hellman publient un schéma d'échange de clé qui n'a pas besoin de secret commun préalable. Il repose sur la difficulté de calculer un logarithme discret. Ici aussi, on manipule des entiers, modulo un nombre premier p.

1.1 Notions mathématiques 8

Soit les éléments non nuls (entre 1 et p - 1, p premier), on peut trouver un générateur g parmi eux, tel que g, g², g³, ... , gp^-1 = [1]_p prennent toutes les valeurs possibles entre 1 et p - 1. Ce sous-ensemble est appelé un groupe cyclique. On dit que (7L/p7L)^*, muni de la multiplication est un groupe cyclique.

Définition 1.1.8 (Groupe cyclique dans (7L/p7L)^*)

Plus simplement, deux entités A et B s'accordent sur un nombre premier p tel que (p-1)/2 est premier, et un générateur g. A choisit au hasard un entier a entre 1 et p - 1, de même B choisit au hasard un entier b dans cet intervalle. A envoie g^a mod p à B et B envoie g^b mod p à A. Puis A connaissant gb et a, calcule (g^b)^a modp , et de même B peut calculer (g^a)^b mod p. Par la suite A et B connaissent le secret g^ab . Un attaquant qui peut lire les communications ne connaît que p, g, ga, g^b et ne peut pas calculer g^ab, mais seulement g^a+b . Cette difficulté de casser ce schéma a été formalisée comme suit.

Problème 1.1.4 (Diffie-Hellman)

Étant donné un nombre premier p définissant 7L/p7L, et un générateur g du groupe, pour (g, g^x, gy) avec x, y inconnus, calculer g^xy .

Soit n > 1, un entier positif et x E (7L/n7L)^* tel que pgcd(x, n) = 1

On dit que x est un résidu quadratique modulo n si 3y E (7L/n7L)^* tel que y² = [x]_n Si un tel y n'existe pas, x est un non-résidu quadratique modulo n.

Définition 1.1.9 (Résidu quadratique)

Soit p un premier. Pour un entier a, on définit le symbole de Legendre par :

Définition 1.1.10 (Symbole de Legendre)

! x = n

? ? ?????

??????

x si x divise n

1 si x est un residu quadratique mod n -1 sinon.

Si l'on sait calculer efficacement un logarithme discret, alors cela permet de résoudre le problème de Diffie-Hellman.

Mémoire de Master 2 Recherche 8 MOUYOUME DIEUDONNE(c) UYI

1.1 Notions mathématiques 9

Problème 1.1.5 (Résidualité quadratique)

Consiste à déterminer si un élément de (Z/nZ)^* est un résidu quadratique.

Ce problème est considéré comme étant calculatoirement difficile dans le cas général et sans information supplémentaire. Par conséquent, il s'agit d'un problème important en cryptographie où il est utilisé comme hypothèse calculatoire.

Étant donné S = {s1,.. . , s_n} un grand ensemble d'entiers, t E Z, trouver un sous-ensemble S^' de

XS tel que

xiES

Problème 1.1.6 (Sparse Subset Sum Problem(SSSP))

xi = t

Le problème de la somme de sous-ensembles est un problème classique en informatique théorique et en cryptographie. Il consiste à déterminer s'il existe un sous-ensemble d'éléments, dans un ensemble donné d'entiers, dont la somme est égale à une valeur cible spécifique.

Étant donné un ensemble {x1 . . . , x_ô} dans lequel xi = p.qi + ri pour 1 < i < ô, retrouver p Pour un entier pair, on utilise la distribution suivante sur des entiers de ã-bits

Dã,ñ(p) = {q.p + r, q E [0, 2ã/p], r E [-2ñ, 2ñ]}

Problème 1.1.7 (Approximate-Greatest Common Divisor Problem(AGCD))

Soit X un ensemble fini. Une distribution sur X est dite uniforme si la probabilité de x E X est

égale à ¹

card(X).

La distribution uniforme sur X est notée U(X)

Définition 1.1.11 (Distribution uniforme discrète)

L'idée est que la somme de deux nombres proches d'un multiple de p est également proche d'un multiple de p, de même pour le produit.