1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138 | Corps fini = corps de Galois
"Un corps est un ensemble de numéros où on peut add. sous. mult. et
div."
En crypto souvent on s'intéresse à des ensembles finis.
En AES : 256 éléments
Théorème : FF exist seulement s'il y a p^m elt, p nombre premier >= 2, m entier positif
- Il y a un FF avec 11 éléments : GF(11)
- Il y a un FF avec 81 éléments : GF(81) = GF(3^4)
- Il y a un FF avec 256 éléments : GF(256) = GF(2^8)
- Il n'y a pas de FF avec 12 éléments car 12 = 3 × 2^2
GF(p^m)
/ \
/ \
/ \
m = 1 / \ m > 1
/ \
/ \
/ \
/ \
GF(p) GF(p^m)
Prime Field Ext. Field
En crypto on s'intéresse
aux GF(2^m)
Arithmétique dans les corps premiers finis
==========================================
Les éléments de GF(p) sont les entiers dans l'ensemble {0,1,…,p-1}
Add. sous. mult. :
------------------
Soit a,b \in GF(p) = {0,1,…,p-1}
a + b ≡ c mod p
a - d ≡ d mod p
a × b ≡ e mod p
À noter que toutes les cds sont satisfaites avec ces calculs
Ex : c = a + b \in GF(p)
Division : inversion :
----------------------
a \in GF(p) alors l'inverse doit satisfaire a × a^{-1} ≡ 1 mod p
On utilise l'algorithme d'euclide étendu
Corps étendu : GF(2^m)
======================
Les éléments du GF(2^m) sont des polynomes
a_{m-1} X^{m-1} + … + a_1 X + a_0 = A(X) \in GF(2^m)
a_i \in GF(2) = {0,1}
Ex : GF(2^3) = GF(8)
A(X) = a_2 * X^2 + a_1 * X + a_0 = (a2, a1, a0)
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
Gf(2^3) = {0,1,X,X+1,X^2,X^2+1,X^2+X,X^2+X+1}
Question : comment peut-on calculer en utilisant ces éléments
Add. & sous. dans GF(2^m) :
---------------------------
On va utilise add./sous. régulière des polynomes t.q. les coeff sont
dans GF(2) :
C(X) = A(X) + B(X) = \sum_{i=0}^{m-1} c_i X^i
t.q. c_i ≡ a_i + b_i mod 2
C'(X) = A(X) - B(X) = \sum_{i=0}^{m-1} c'_i X^i
t.q. c_i ≡ a_i - b_i mod 2
≡ a_i + b_i mod 2
C(X) = C'(X)
Exemple dans GF(2^3) :
----------------------
A(X) = X^2 + X + 1
B(X) = X^2 + 1
A + B = (1+1)X^2 + X + (1+1)
= X
Mult. dans GF(2^m) :
--------------------
Intuitions : faire mult. dans polynômes régulière
Exemple dans GF(2^3) :
A × B = (X^2 + X + 1)(X^2 + 1)
= X^4 + X^3 + X^2 + X^2 + X + 1
= X^4 + X^3 + X + 1
= C'(X) \not\in GF(2^3) => problème
Solution :
Réduire C'(X) modulo un polynôme qui "se comporte comme un nombre
premier". On l'appelle polynôme irréductible i.e. on ne peut pas le
factoriser.
Un polynôme irréductible de GF(2^3) :
P(X) = X^3 + X + 1
Dans AES, c'est un polynôme fixe, spécifié dans la norme :
P(X) = X^8 + X^4 + X^3 + X + 1
X^4 + X^3 + X + 1 │ X^3 + X + 1
+ ├─────────────
X^4 + X^2 + X │ X + 1
────────────────── │
X^3 + X^2 + 1 │
+ │
X^3 + X + 1 │
────────────────── │
X^2 + X │
A×B mod P(X) = X^2 + X
Inversion dans GF(2^m)
----------------------
L'inverse A^{-1}(X) de A(X) \in GF(2^m) doit satisfaire :
A(X) × A^{-1}(X) ≡ 1 mod P(X)
|