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
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
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 ?
Notions autour de la division
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
Notions autour de la division
a = b * q + r et r < b
quotient reste
6
Partie 2/7
Nombres premiers
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
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
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
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
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
21
Arithmétique modulaire
ℤ 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
Arithmétique modulaire
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
Arithmétique modulaire
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
Arithmétique modulaire
ℤ/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
Arithmétique modulaire
ℤ/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
Arithmétique modulaire
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
Arithmétique modulaire
Ecrire de la même façon la table de multiplication dans ℤ/7ℤ :
28
Partie 5/7
Groupes cycliques
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
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
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
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
Théorème des restes chinois
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
Théorème des restes chinois
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
Théorème des restes chinois
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
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
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
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
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
Merci