學校課程/資訊安全

資訊安全 Galois Fields C++ 軟體實作體驗

contents

  1. 1. Problem
    1. 1.1. AES
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

在 AES 中，利用 Galois fields$GF(2^{8})$ 為運算單位，有效地在 8-bits CPU 上高效地實作。

Galois Fields$GF(p^{n})$ 限定在質數 p 的 n 次方，便可存在有限的元素集合，支持加減乘除，同時可以利用 擴充歐幾里算法 得得到乘法反元素。從最簡單的 p = 2 開始看起，將 f(x) 視為一個元素。則

$$f(x) = a_{n-1}x^{n-1} + a_{n-2}x^{n-2} + ... + a_{1}x + a_{0} \\ a_{i} \in [0, p)$$

當 p = 2 時，f(x) 就跟一般的二進制數字儲存相同。當選定在 p 的 n 次方時，必須找一個 degree = n 的多項式，不被集合內的任何元素整除，來約束所有的運算保持在一個大小內。特別的是當 p = 2 時，加法和減法是等價運算 (在 p = 2 下，1 乘法反元素是自己本身)。

AES 取 8-bits 作為運算單位的用意很多，其一反元素可以在極小空間內儲存，可以用查表的方式得到。之所以選定 p = 2 的好處在於計算機的儲存架構，若在某些特殊硬體可以支持三進位的情況下，p = 3 則會比較有效率的使用，不然取用 p = 3 在二進制的電腦架構，需要轉換的儲存單位是很沒效率，並且覆蓋的集合大小也沒辦法全部使用。

GF 有什麼好處呢？其一的道理在於加解密設計要 防止線性關係 (線性代數太邪惡，很多種攻擊可以繞過線性關係的運算，拋開未知數也能求解)，對於 AES 的設計概念來說 GF 恰好符合這個條件。

AES

AES 選用$GF(2^{8})$，並且取$m(x) = x^8 + x^4 + x^3 + x + 1$ 作為模數，然後再設計一個以 GF 作為常數類型的多項式 Polynominal

$f(x) = s_{3}x^{3} + s_{2}x^{2} + s_{1}x + s_{0}$

每一個$s_{i}$ 都是一個 8-bits 的儲存單位，也就是說這個多項式是 32-bits 儲存。並且取用$m(x) = x^4 + 1$ 作為多項式的模數。AES 藉由 多項式相乘 ，將 4 個 8-bits 的資料交互影響產生出新的 4 個 8-bits，這在密碼學裡面造成 雪崩效應 。

跟之前講的一樣，GF 一定存在反操作，也就是乘法反元素，因此取用$03 x^{3} + 01 x^{2} + 01 x^{1} + 02$ 其乘法反元素為$0B x^{3} + 0D x^{2} + 09 x^{1} + 0E$。

接著，寫一個程式驗證反元素的計算吧！

備註：GF 裡面套用 GF 相當有趣，感覺可以無限擴充大小，當然任意質數也可以找反元素，但也只有 梅森質數 比較適合在電腦二進制系統中吧？

Sample Input

1
no input

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
00 01 8D F6 CB 52 7B D1 E8 4F 29 C0 B0 E1 E5 C7
74 B4 AA 4B 99 2B 60 5F 58 3F FD CC FF 40 EE B2
3A 6E 5A F1 55 4D A8 C9 C1 0A 98 15 30 44 A2 C2
2C 45 92 6C F3 39 66 42 F2 35 20 6F 77 BB 59 19
1D FE 37 67 2D 31 F5 69 A7 64 AB 13 54 25 E9 09
ED 5C 05 CA 4C 24 87 BF 18 3E 22 F0 51 EC 61 17
16 5E AF D3 49 A6 36 43 F4 47 91 DF 33 93 21 3B
79 B7 97 85 10 B5 BA 3C B6 70 D0 06 A1 FA 81 82
83 7E 7F 80 96 73 BE 56 9B 9E 95 D9 F7 02 B9 A4
DE 6A 32 6D D8 8A 84 72 2A 14 9F 88 F9 DC 89 9A
FB 7C 2E C3 8F B8 65 48 26 C8 12 4A CE E7 D2 62
0C E0 1F EF 11 75 78 71 A5 8E 76 3D BD BC 86 57
0B 28 2F A3 DA D4 E4 0F A9 27 53 04 1B FC AC E6
7A 07 AE 63 C5 DB E2 EA 94 8B C4 D5 9D F8 90 6B
B1 0D D6 EB C6 0E CF AD 08 4E D7 E3 5D 50 1E B3
5B 23 38 34 68 46 03 8C DD 9C 7D A0 CD 1A 41 1C
03 x^3 + 01 x^2 + 01 x^1 + 02 x^0
0B x^3 + 0D x^2 + 09 x^1 + 0E x^0
00 x^3 + 00 x^2 + 00 x^1 + 01 x^0
0B x^3 + 0D x^2 + 09 x^1 + 0E x^0

Solution

暴力實作，模擬運算，不考慮電路架構，用最樸素的方式儲存每一個欄位。

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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
#include <stdio.h> 
#include <string.h>
// in AES, GF(2^8), m(x) = x^8 + x^4 + x^3 + x + 1
class GaloisField {
public:
    unsigned char v[32];
    int n;
    GaloisField() {
        n = 8;
        memset(v, 0, sizeof(v));
    }
    GaloisField(int val) {
        n = 8;
        memset(v, 0, sizeof(v));
        for (int i = 0; i < 8; i++)
            v[i] = (val>>i)&1;
    }
    GaloisField(const int a[], int an) {
        memset(v, 0, sizeof(v));
        n = 8;
        for (int i = 0; i <= an; i++)
            v[i] = a[i];
    }
    GaloisField operator+(const GaloisField &a) const {
        GaloisField r;
        for (int i = 0; i <= r.n; i++)
            r.v[i] = v[i] xor a.v[i];
        r.normal();
        return r;
    }
    GaloisField operator-(const GaloisField &a) const {
        return (*this) + a;
    }
    GaloisField operator*(const GaloisField &a) const {
        GaloisField r;
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= a.n; j++) 
                r.v[i+j] = r.v[i+j] xor (v[i] and a.v[j]);
        r.normal();
        return r;
    }
    GaloisField shift(int sn) const {
        GaloisField r;
        for (int i = 0; i < n; i++)
            r.v[i + sn] = v[i];
        return r;
    }
    bool operator<(const GaloisField &a) const {
        for (int i = 16; i >= 0; i--) {
            if (v[i] == 1 && a.v[i] == 1)
                return true;
            if (v[i] == 1 && a.v[i] == 0)
                return false;
            if (v[i] == 0 && a.v[i] == 1)
                return false;
        }
        return false;
    }
    GaloisField operator/(const GaloisField &a) const {
        for (int i = 16; i >= 0; i--) {
            if (a.v[i] == 1 && v[i] == 0)
                return GaloisField();
            if (a.v[i] == 0 && v[i] == 1)
                break;
        }
        GaloisField r, b = (*this), c;
        
        for (int i = n; i >= 0; i--) {
            c = a.shift(i);
            if (c < b) {
                r.v[i] = 1;
                for (int j = 16; j >= 0; j--)
                    b.v[j] = b.v[j] xor c.v[j];
            }
        }
        r.normal();
        return r;
    }
    GaloisField operator%(const GaloisField &a) const {
        GaloisField ret = (*this) - (*this) / a * a;
        return ret;
    }
    bool isZero() const {
        for (int i = 16; i >= 0; i--)
            if (v[i])	return 0;
        return 1;
    }
    GaloisField inverse() {
        const int m[] = {1, 1, 0, 1, 1, 0, 0, 0, 1}, mn = 8; // m(x) = x^8 + x^4 + x^3 + x + 1
        GaloisField y(m, mn);
        GaloisField g, a, b;
        
        exgcd((*this), y, g, a, b); // a x + b y = g
        return a;
    }
    void exgcd(GaloisField x, GaloisField y, GaloisField &g, GaloisField &a, GaloisField &b) {
        if (y.isZero()) {
            g = x, a = GaloisField(1), b = GaloisField(0);
        } else {
            exgcd(y, x%y, g, b, a), b = b - (x / y) * a;
        }
    }
    void normal() {
        const int m[] = {1, 1, 0, 1, 1, 0, 0, 0, 1}, mn = 8; // m(x) = x^8 + x^4 + x^3 + x + 1
        for (int i = 16; i - mn >= 0; i--) {
            if (v[i] == 1) {
                for (int j = mn, k = i; j >= 0; j--, k--)
                    v[k] = v[k] xor (m[j]);
            }
        }
    }
    void print() const {
        for (int i = 7; i >= 0; i--) {
            printf("%d", v[i]);
            if (i%4 == 0)	printf(" ");
        }
        puts("");
    }
    int getHbits() const {
        return v[7]<<3 | v[6]<<2 | v[5]<<1 | v[4];
    }
    int getLbits() const {
        return v[3]<<3 | v[2]<<2 | v[1]<<1 | v[0];
    }
};
void testGF() {
    int va[] = {1, 1, 1, 0, 1, 1, 0, 0};
    int vb[] = {0, 1, 0, 0, 0, 0, 1, 0};
    for (int i = 0; i < 256; i++) {
        GaloisField a(i);
        GaloisField b = a.inverse();
        printf("%X%X ", b.getHbits(), b.getLbits());
        if (i%16 == 15) puts("");
    }
}
class GF_Polynominal {
public:
    GaloisField v[32];
    int n;
    GF_Polynominal() {
        n = 4;
        for (int i = 0; i < 16; i++)
            v[i] = GaloisField();
    }
    GF_Polynominal(const GaloisField a[], int an) {
        n = 4;
        for (int i = 0; i <= an; i++)
            v[i] = a[i];
    }
    GF_Polynominal operator+(const GF_Polynominal &a) const {
        GF_Polynominal r;
        for (int i = 0; i <= r.n; i++)
            r.v[i] = v[i] + a.v[i];
        r.normal();
        return r;
    }
    GF_Polynominal operator-(const GF_Polynominal &a) const {
        return (*this) + a;
    }
    GF_Polynominal operator*(const GF_Polynominal &a) const {
        GF_Polynominal r;
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= a.n; j++) 
                r.v[i+j] = r.v[i+j] + (v[i] * a.v[j]);
        r.normal();
        return r;
    }
    GF_Polynominal shift(int sn) const {
        GF_Polynominal r;
        for (int i = 0; i < n; i++)
            r.v[i + sn] = v[i];
        return r;
    }
    bool operator<(const GF_Polynominal &a) const {
        for (int i = 8; i >= 0; i--) {
            if (!v[i].isZero() && !a.v[i].isZero())
                return true;
            if (v[i].isZero() != a.v[i].isZero())
                return false;
        }
        return false;
    }
    GF_Polynominal operator/(const GF_Polynominal &a) const {
        for (int i = 8; i >= 0; i--) {
            if (!a.v[i].isZero() && v[i].isZero())
                return GF_Polynominal();
            if (a.v[i].isZero() && !v[i].isZero())
                break;
        }
        GF_Polynominal r, b = (*this), c;
        
        for (int i = n; i >= 0; i--) {
            c = a.shift(i);
            if (c < b) {
                GaloisField t, x, y;
                for (int j = 16; j >= 0; j--) {
                    if (!c.v[j].isZero()) {
                        y = c.v[j], x = b.v[j];
                        break;
                    }
                }
                t = y.inverse() * x;
//				b.print();
//				c.print();
//				printf("gg %d\n", i);
//				y.print();
//				x.print();
//				y.inverse().print();
//				t.print();
                r.v[i] = t;
                for (int j = 8; j >= 0; j--)
                    b.v[j] = b.v[j] - c.v[j] * t;
            }
        }
//		printf("---> mod "); b.print();
//		puts("");
//		puts("div begin");
//		print();
//		a.print();
//		r.print();
//		(r * a).print();
//		(r * a + b).print();
//		puts("div end\n");
        r.normal();
        return r;
    }
    GF_Polynominal operator%(const GF_Polynominal &a) const {
        GF_Polynominal ret = (*this) - (*this) / a * a;
        return ret;
    }
    bool isZero() {
        for (int i = 8; i >= 0; i--)
            if (!v[i].isZero())	return 0;
        return 1;
    }
    GF_Polynominal inverse() {
        const GaloisField m[] = {GaloisField(1), GaloisField(0), GaloisField(0), GaloisField(0), GaloisField(1)};
        const int mn = 4; // m(x) = x^4 + 1
        GF_Polynominal y(m, mn);
        GF_Polynominal g, a, b;
        
        exgcd((*this), y, g, a, b); // a x + b y = g
        
        return a / g;
    }
    void exgcd(GF_Polynominal x, GF_Polynominal y, GF_Polynominal &g, GF_Polynominal &a, GF_Polynominal &b) {
//		puts("exgcd -----------------");
//		x.print();
//		y.print();
//		getchar();
        if (y.isZero()) {
            const GaloisField m1[] = {GaloisField(1)};
            const GaloisField m0[] = {GaloisField(0)};
            g = x, a = GF_Polynominal(m1, 1), b = GF_Polynominal(m0, 1);
            // a = g.inverse();
        } else {
            exgcd(y, x%y, g, b, a), b = b - (x / y) * a;
        }
    }
    void normal() {
        const GaloisField m[] = {GaloisField(1), GaloisField(0), GaloisField(0), GaloisField(0), GaloisField(1)};
        const int mn = 4; // m(x) = x^4 + 1
        for (int i = 16; i - mn >= 0; i--) {
            if (!v[i].isZero()) {
                GaloisField t = v[i];
                for (int j = mn, k = i; j >= 0; j--, k--)
                    v[k] = v[k] - (m[j] * t);
            }
        }
    }
    void print() const {
        for (int i = 3; i >= 0; i--) {
            printf("%X%X ", v[i].getHbits(), v[i].getLbits());
            printf("x^%d", i);
            if (i)	printf(" + ");
        }
        puts("");
    }
};
void testPoly() {
    const GaloisField m[] = {GaloisField(2), GaloisField(1), GaloisField(1), GaloisField(3)};
    const GaloisField m2[] = {GaloisField(14), GaloisField(9), GaloisField(13), GaloisField(11)};
    const int mn = 3, mn2 = 3;
    GF_Polynominal a(m, mn), b(m2, mn2);
    
    a.print();
    b.print();
    
    GF_Polynominal c = a * b;
    c.print();
    
    GF_Polynominal d = a.inverse();
    d.print();
}
int main() {
    testGF();
    testPoly();
    return 0;
}