Eléments de math pour la cryptographie

Eléments de math pour la cryptographie

Remise en selle et échauffement pour le cours de cryptographie

Marie GRIBOUVAL et Isabel LEJEUNE-TÔLargement inspiré du cours de Jean-Jacques SCHWARTZMAN,enseignant à ENSI Caen & Orange Labs

2

Éléments de math pour la cryptographieSommaire

1. Rappels autour de la division

2. Nombres premiers

3. PGCD

4. Arithmétique modulaire

5. Groupes cycliques

6. Théorème des restes chinois

7. Courbes elliptiques

Aller plus loin

3

Partie 1/7

Notions autour de la division


2. Nombres premiers

3. PGCD





Aller plus loin

4

Soient a, b deux entiers naturels, avec b ≠ 0

Nous disons que b divise a ( noté b | a ) s’il existe q un entier naturel tel que a = b*q

Avons-nous 3 | 11 ? 3 | 12 ?


Non, il n’existe pas d’entier naturel q tel que 11 = 3*q

Oui, 12 = 3*4

Propriétés

• Si a | b et b | a → a = b

• Si a | b et b | c → a | c

• Si a | b et a | c → a | (b*x + c*y) pour tout x, y

Exemples : 3 | 12 et 12 | 24 nous avons bien 3 | 24

3 | 12 et 3 | 6 alors 3 | (12*2+6*3) si x = 2 et y = 3 essayer pour d’autres valeurs de x et y

5

Soient a et b deux entiers naturels où b ≠ 0.

Alors, il existe un unique couple d’entiers naturels ( q , r ) tel que :

Exemple :

a = 7, b = 2, alors, a = 2 * 3 + 1 où q = 3 et r = 1

a = 8, b = 3, alors, a = 3 * 2 + 2 où q = 2 et r = 2


a = b * q + r et r < b

quotient reste

6

Partie 2/7

Nombres premiers


2. Nombres premiers

3. PGCD





Aller plus loin

7

Un nombre premier est un entier naturel (noté ℕ, ce sont tous les entiers positifs) qui admet exactement deux diviseurs distincts qui sont 1 et lui-même.

Un nombre entier qui est le produit de deux nombres entiers différents de 1 est un nombre composé.

0 et 1 ne sont ni premiers, ni composés.

Nombres premiers

Exercice :Les nombres suivants sont ils premiers ou composés ?

25 874876 13 31 1721

Composé25 = 52

Composé874876 = 22 * 218719

Premier Premier Premier

8

Théorème fondamental de l’arithmétique :

Tout nombre entier non nul peut s’écrire comme un produit de nombre premiers de façon unique

Nombres premiers

Exercice :Décomposer les nombres suivants en produit de nombres premiers :

8 187 1721 56 12

2 ∗ 2 ∗ 2 = 23 11 ∗ 17 1721 8 ∗ 7 = 23 ∗ 7 22 ∗ 3

Théorème d’Euclide :

Il existe une infinité de nombres premiers

9

Nombres premiers

Méthodes de factorisation de N en nombres premiers :

Méthode 1 – Essayer tous les nombres de 0 à 𝑁.

Méthode 2 – Trouver tous les p nombres premiers entre 0 et 𝑁. Puis, tester tous les nombres p trouvés.

10

Nombres premiers

Petit théorème de Fermat :

1 – Soit 𝒑 un nombre premier et 𝒂 tel que 𝒑 ne divise pas 𝒂, alors 𝒂𝒑−𝟏 −𝟏 est un multiple de 𝒑

2 – Si 𝒑 est un nombre premier et si 𝒂 est un entier quelconque, alors 𝒂𝒑 − 𝒂 est un multiple de 𝒑

Exemple : 𝑝 = 7, 𝑎 = 8,87−1 − 1 = 86 − 1 = 262144 − 1 = 262143Alors : 262143 = 7 ∗ 37449

Exemple : 𝑝 = 7, 𝑎 = 8,87 − 8 = 2097152 − 8 = 2097144Alors : 2097144 = 7 ∗ 299592

La réciproque est fausse

11

Nombres premiers

Test de primalité de Fermat :

A la page précédente nous avons vu une condition nécessaire pour qu’un nombre soit premier.

Le test de primalité de Fermat consiste à regarder si 𝒑 ne divise pas 𝒂 et si 𝒂𝒑−𝟏 − 𝟏 est un multiple de 𝒑

Dans ce cas 𝒑 est probablement premier

12

Partie 3/7

PGCDplus grand

commun diviseur


2. Nombres premiers

3. PGCD





Aller plus loin

13

PGCD

Soient a et b deux entiers naturels. Un diviseur commun à a et b est un entier m tel que m | a et m | b

Exemple : 2 et un diviseur commun à 4 et 8

Le PGCD de deux entiers a et b est le plus grand diviseur commun de a et b

Exemple : 4 est le PGCD de 4 et 8

Exercice :Calculer les PGCD :

PGCD(9,6) =PGCD(12,16) =PGCD(33,26) =

341 alors 33 et 26 sont premiers entre eux !

14

PGCD

Propriétés :

a - Si b | a alors PGCD(a,b) = b

b - Soit a, b, k trois entiers naturels. Alors, PGCD(a*k,b*k) = k * PGCD(a,b)

c - Si PGCD(a,b) = d. Alors, PGCD(a/d,b/d) = 1

d - Soit a, b, v trois entiers naturels. Alors, PGCD(a,b) = PGCD(a+bv,b)

Lemme de Gauss - Soient a, b, c trois entiers naturels tel que PGCD(a,b) = 1 tel que a | bc

Alors, a | c

Exemple : a - 4 est le PGCD(4 , 8)

b - a = 56, b = 8, k = 2, PGCD(56*2 , 8*2) = 16 et PGCD(56 , 8) = 8

Nous avons bien 16 = 2 * 8

c - PGCD(56 , 8) = 8 et PGCD(56

8, 8

8)=PGCD(7 , 1) = 1

d - a = 56, b = 8, v = 2. Alors, PGCD(56 , 8) = PGCD(56+16 , 8) = PGCD(72 , 8) = 8

15

PGCD

Calcul du PGCD – Méthode naïve :

a - Déterminer la liste des diviseurs de a

b - Déterminer la liste des diviseurs de b

c – Comparer les deux listes pour déterminer le PGCD

Exemple : a = 60, b = 84

a - diviseurs de a :

b - diviseurs de b :

c - PGCD(60 , 84) =

1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60

1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84

12

16

PGCD

Calcul du PGCD – Utilisation de facteurs communs visibles :

Tester les nombres les plus évidents : 2, 3, 5, 7, 11, … et utiliser les propriétés précédentes

Exemple : a = 60, b = 84

a - 4 | 60 et 4 | 84, alors, PGCD(60,84) = 4 * PGCD(15,21)

prop b diapo 14 - Soit a, b, k trois entiers naturels. Alors, PGCD(a*k,b*k) = k * PGCD(a,b)

b - 3 | 15 et 3 | 21, alors, PGCD(60,84) = 4 * 3 * PGCD(5,7) = 4 * 3 * 1 = 12

Donc, PGCD(60,84) = 12

17

PGCD

Calcul du PGCD – Méthode d’Euclide :

Ecrire a sous la forme a = b * q + r

Nous avons PGCD(a,b) = PGCD(b,r)

Ecrire b sous la forme b = r * q’ + r’

Nous avons PGCD(b,r) = PGCD(r,r’)

Et nous continuons tant que le reste est non nul, le dernier reste non nul est le PGCD recherché

Exemple : a = 84, b = 60

a = b * 1 + 24 Alors, PGCD(a,b) = PGCD(b,r) = PGCD(60,24)

60 = 24 * 2 + 12

24 = 12 * 2 + 0 Nous voyons que le PGCD est 12.

Il existe d’autres méthodes de calcul de PGCD comme les soustractions successives, …

18

PGCD

Identité de Bézout :

Soient a et b deux entiers relatifs non nuls.

Il existe au moins un couple (u,v) d’entiers relatifs tels que :

Si a et b sont premiers entre eux alors au + bv = 1

19

PGCD

Exemple de calcul des coefficients de Bézout : a = 182 et b = 165

Calcul du PGCD avec la méthode d’Euclide :

On recalcule le reste de chaque étape en substituant le membre de droite par une combinaison linéaire de a et b :

17 = 1 * 182 – 1 * 165

12 = 1 * 165 – 9 * 17 = 1 * 165 – 9 * (1 * 182 – 1 * 165) = - 9 * 182 + 10 * 165

5 = 1 * 17 – 1 * 12 = 1 * (1 * 182 – 1 * 165) – 1 * (-9 * 182 + 10 * 165) = 10 * 182 – 11 * 165

2 = 12 – 2 * 5 = - 9 * 182 + 10 * 165 – 2 * (10 * 182 – 11 * 165) = - 29 * 182 + 32 * 165

1 = 5 – 2 * 2 = 10 * 182 – 11 * 165 – 2 * (- 29 * 182 + 32 * 165) = 68 * 182 – 75 * 165

Nous obtenons u = 68 et v = - 75.

182 = 165 * 1 + 17165 = 17 * 9 + 1217 = 12 * 1 + 5 12 = 5 * 2 + 2 5 = 2 * 2 + 12 = 1 * 2 + 0

Donc, PGCD(182,165) = 1

20

Partie 4/7

Arithmétique modulaire


2. Nombres premiers

3. PGCD





Aller plus loin

21


ℤ représente l’ensemble des nombres relatifs, c’est-à-dire tous les entiers positifs ou négatifs

a est congru à b modulo n signifie :

Il existe k appartenant à ℤ tel que a = k * n + b

Autrement dit a – b est un multiple de n

Nous le notons a ≡ b mod n

Exemple :

2 ≡ 8 mod 3 car 2 = k * 3 + 8 où k = - 2 ou 3 | (8 – 2)

12 ≡ 2 mod 5 car 12 = k * 5 + 2 où k = 2 ou 5 | (12 – 2)

22


Propriétés de congruence :

a - a ≡ a mod n (réflexivité)

b - Si a ≡ b mod n alors b ≡ a mod n (symétrie)

c - Si a ≡ b mod n et b ≡ c mod n alors a ≡ c mod n (transitivité)

Donc, la congruence est une relation d’équivalence

La classe modulo n d’un élément x (où x est un entier positif) est l’ensemble des y congrus à x modulo n

Par exemple la classe modulo 2 de 0 est l’ensemble {0 ; 2 ; 4 ; 6 ; 8 ; 10 ;…}

23


Propriétés arithmétiques :

Si a ≡ b mod n et a’ ≡ b’ mod n

Alors :

a + a’ ≡ b + b’ mod n

a * a’ ≡ b * b’ mod n

𝒂𝒒 ≡ 𝒃𝒒 mod n pour tout entier q ≥ 1

a * c ≡ b * c mod n pour tout c appartenant à ℤ

k * a + a’ ≡ k * b + b’ mod n

24


ℤ/nℤ est l’ensemble des classes d’équivalence pour la congruence modulo n

Si å appartient à ℤ /nℤ cela signifie que å est une classe d’équivalence pour la congruencemodulo n. C’est-à-dire que å = {a ; a + n ; a + 2n ; a + 3n ; …}

En mathématique un groupe est un ensemble muni d’une loi (par exemple l’addition) respectantcertaines propriétés (l’associativité, l’existence d’un élément neutre et un élément symétrique)

Il existe des groupes plus spécifiques qui en plus de respecter les propriétés des groupesclassiques obéissent à d’autres conditions

25


ℤ/nℤ muni de l’addition. Il est noté (ℤ/nℤ , + ) :

Commutativité - Pour tout a, b appartenant à ℤ/nℤ : a + b ≡ b + a mod n

Associativité - Pour tout a, b, c appartenant à ℤ/nℤ : (a + b) + c ≡ a + (b + c) mod n

Existence d’un élément neutre - Pour tout a appartenant à ℤ/nℤ : a + 0 ≡ 0 + a ≡ a mod n

Existence d’un élément symétrique - Pour tout a appartenant à ℤ/nℤ, il existe s appartenant à ℤ/nℤ

tel que : a + s ≡ 0 mod n (ie : a + s est un multiple de n)

Nous avons donc montré que (ℤ/nℤ , + ) est un groupe commutatif

26


Multiplication dans ℤ/6ℤ :

Si a x b < 6 il s’agit du résultat de la

multiplication

Si a x b = 6 il faut mettre 0 car

6 ≡ 0 mod 6

Si a x b > 6 il faut mettre le résultat

de la congruence obtenu avec

modulo 6

0

0

0

0

0

0

0 0 0 0 0

1 2 3 4 5

2

3

4

5

4

0

2

4

0

3

0

3 2

2

1

4

0

2 4

3

27


Ecrire de la même façon la table de multiplication dans ℤ/7ℤ :

28

Partie 5/7

Groupes cycliques


2. Nombres premiers

3. PGCD





Aller plus loin

29

Groupes cycliques

Un groupe G est un groupe cyclique s’il existe un élément g appartenant à G tel que tout élément deG s’exprime comme un multiple ou une puissance de g

Exemples :

G = { 0 ; 𝑔 ; 2𝑔 ; 3𝑔 ;… ; 𝑛 − 1 𝑔 } Ici, G est un groupe additif

G = { 1 ; 𝑔 ; 𝑔2 ; 𝑔3 ; … ; 𝑔𝑛−1 } Ici, G est un groupe multiplicatif

30

Groupes cycliques

Propriétés des groupes cycliques :

a – Tout groupe cyclique est commutatif

b – Un groupe cyclique est toujours dénombrable, qu’il soit fini ou infini

Un ensemble est dénombrable s’il est possible d’attribuer une étiquette propre à chaque élément decet ensemble. Les étiquettes sont les nombres entiers positifs

31

Groupes cycliques

Propriétés des groupes cycliques :

c – Tout groupe cyclique infini est isomorphe à (ℤ, + ).

Soit G et G’ deux groupes. Un morphisme de G dans G’ est une application f : G → G’ telle que pourtous g1, g2 dans G nous avons f(g1g2) = f(g1)f(g2). Si de plus f est bijective, c’est un isomorphisme

d – Tout groupe cyclique fini d’ordre n est isomorphe à (ℤ/nℤ, + )

e – Tout sous-groupe d’un groupe cyclique d’ordre n est lui-même un groupe cyclique

H est un sous-groupe de G si H est une partie non vide de G et si H est un groupe muni de la mêmeloi de composition interne que G

32

Partie 6/7

Théorème des restes

chinois


2. Nombres premiers

3. PGCD





Aller plus loin

33

Théorème des restes chinois

Enoncé :

Combien l’armée de Han Xing comporte-t-elle de soldats si, rangés par 3 colonnes, il reste 2soldats, rangés par 5 colonnes, il reste 3 soldats et, rangés par 7 colonnes, il reste 2 soldats ?

Soit x le nombre de soldats. Comment résumer le problème sous forme de congruence ?

Donnez une solution du problème

x ≡ 2 mod 3 → x = { 2 ; 5 ; 8 ; 11 ; 14 ; 17 ; 20 ; 23 ; … } x ≡ 3 mod 5 → x = { 3 ; 8 ; 13 ; 18 ; 23 ; … } x ≡ 2 mod 7 → x = { 2 ; 9 ; 16 ; 23 ; … }

Une solution possible est 23 soldats

34


Solution au problème des restes :

a – Calcul du produit des modules

b – Pour chaque module on calcule le produit des 2 autres modules

c – On cherche ensuite pour chaque ñk un nombre yk tel que yk * ñk ≡ 1 mod k

d – Une solution pour x est alors la somme des t * ñk * yk modulo n où t est le reste

n = 3 * 5 * 7 = 105

ñ3 = 5 * 7 = 35 ñ5 = 3 * 7 = 21 ñ7 = 3 * 5 = 15

y3 * ñ3 ≡ 1 mod 3 → y3 * 35 ≡ 1 mod 3 → y3 = 2 y5 * ñ5 ≡ 1 mod 5 → y5 * 21 ≡ 1 mod 5 → y5 = 1 y7 * ñ7 ≡ 1 mod 7 → y7 * 15 ≡ 1 mod 7 → y7 = 1

2 * ñ3 * y3 + 3 * ñ5 * y5 + 2 * ñ7 * y7 = 2 * 35 * 2 + 3 * 21 * 1 + 2 * 15 * 1 = 140 + 63 + 30 = 233233 ≡ 23 mod 105

35


Les pirates et le cuisinier :

Une bande de 17 pirates s’est emparée d’un butin composé de pièces d’or d’égale valeur. Ilsdécident de se les partager également, et de donner le reste au cuisinier. Celui-ci recevrait alors 3pièces.

Mais, les pirates se querellent, et, six d’entre eux sont tués. Le cuisinier recevrait alors 4 pièces.

Dans un naufrage ultérieur, seuls le butin, six pirates et le cuisinier sont sauvés, et le partagedonnerait alors 5 pièces d’or à ce dernier. Quelle est la fortune minimale que peut espérer lecuisinier quand il décide d’empoisonner le reste des pirates ?

x ≡ 3 mod 17

x ≡ 4 mod 11

x ≡ 5 mod 6

36


17, 11 et 6 sont premiers entre eux donc nous pouvons

utiliser le théorème des restes chinois

a – Calcul du produit des modules

b – Pour chaque module on calcule le produit des 2 autres modules

c – On cherche ensuite pour chaque ñk un nombre yk tel que yk * ñk ≡ 1 mod k

d – Une solution pour x est alors la somme des t * ñk * yk modulo n où t est le reste

n = 17 * 11 * 6 = 1122

ñ17 = 11 * 6 = 66 ñ11 = 17 * 6 = 102 ñ6 = 17 * 11 = 187

y17 * ñ17 ≡ 1 mod 17 → y17 * 66 ≡ 1 mod 17 → y17 = 8y11 * ñ11 ≡ 1 mod 11 → y11 * 102 ≡ 1 mod 11 → y11 = 4 y6 * ñ6 ≡ 1 mod 6 → y6 * 187 ≡ 1 mod 6 → y6 = 1

3 * ñ17 * y17 + 4 * ñ11 * y11 + 5 * ñ6 * y6 = 3 * 66 * 8 + 4 * 102 * 4 + 5 * 187 * 1 = 1584 + 1632 + 935 = 41514151 ≡ 785 mod 1122 Le cuisinier peut donc espérer avoir 785 pièces !

37

Partie 7/7

Courbes elliptiques


2. Nombres premiers

3. PGCD





Aller plus loin

38

Courbes elliptiques

Une courbe elliptique sur un corps K est l’ensemble E des points définis par :

Condition : le discriminant Δ = -16 (4a3 + 27b2) doit être non nul

Un corps est un ensemble muni de loi de composition interne respectant certaines propriétés

39

Courbes elliptiques

Exemple de courbes elliptiques :

y2 = x3 – x

Δ = -16 (4a3 + 27b2) = -16 * (4*(-1)3 + 27 * 0) = 64

Nous avons 3 racines (-1 ; 0 ; 1)

y2 = x3 – x + 1

Δ = -16 (4a3 + 27b2) = -16 * (4*(-1)3 + 27 * 12) = -368

Nous avons 1 racine : -1.32

40

Courbes elliptiques

Addition de points

Soient P et Q deux points appartenant à la courbe

La droite passant par P et Q coupe la courbe en un 3e point noté R

Soit R’, le symétrique de R par rapport à l’axe des abscissesLa courbe étant symétrique à cet axe, le point R’ appartient à la courbe

La somme P+Q est définie comme étant le point R’

41

Courbes elliptiques

Elément neutre et opposé

Nous cherchons à calculer P + O où O est le point à l’infini

O est le point à l’infini donc (PO) est la droite verticale passant par PLe 3e point d’intersection noté R est le symétrique de P par rapport à l’axe des abscisses

P étant le symétrique de R, nous avons donc P + O = PLe point O est donc l’élément neutre pour l’addition de points sur E

La droite (PR) étant verticale, nous avons P + R = ODonc, R est l’opposé de PNous notons R = -P

42

Courbes elliptiques

Commutativité et associativité

La commutativité est évidente : la sécante joignant P et Q est également la sécante qui joint Q à P

Pour tout P, Q, R appartenant à E :(P + Q) + R = P + (Q + R)

Nous pouvons le voir graphiquement mais attention ce n’est pas une démonstration !

Finalement, (E, +) est un groupe abélien

43

Courbes elliptiques

Multiplication par un entier

Soit un point P appartenant à E, où E est une courbe elliptique sur un corps KOn définit Q = kP = P + P + … + P

Graphiquement si k = 2, il faut tracer la droite tangente à E au point P, le point d’intersection entre la droite et E nous donne -2Ple symétrique de -2P par rapport à l’axe des abscisse est 2P

On appelle ordre d’un point G appartenant à E le nombre n tel que nG = O (point à l’infini)

44

Allerplus loin


2. Nombres premiers

3. PGCD





Aller plus loin

45

Pour aller plus loin

Domaine Objectif Lien

Notion d’ensembles dénombrables, finis et infinis

Comprendre les notions ( de 0 à 1min27 )

https://www.youtube.com/watch?v=0hB95JwlzBY

Groupes Comprendre la notion de groupe

https://homeomath2.imingo.net/groupe.htm

Classes modulo n Comprendre la notion de classes modulo n

https://homeomath2.imingo.net/classem.htm

Corps Comprendre la notion de corps http://homeomath2.imingo.net/corps.htm

https://www.youtube.com/watch?v=0hB95JwlzBY

https://homeomath2.imingo.net/groupe.htm

https://homeomath2.imingo.net/classem.htm

http://homeomath2.imingo.net/corps.htm

Merci

Documents

Eléments de math pour la cryptographie