歐幾里得算法，擴展的歐幾里得算法（Euclid）和AES的S-BOX
本文包括：歐幾里得，擴展的歐幾里得，AES的S-BOX.
.
1.歐幾里得
- 計算gcd（a，b）…[最大公約數]
方法：
a = q * b + r1
b = q * r1 + r2
r1 = q * r2 + r3
…
rn = q * rn-1 + rn-2
rn-1 = q * rn-2 + rn-3
…
直至餘數爲0，此時的商就是最大公約數。
.
舉個栗子：
計算gcd（24140,16762）
.
24140 = 1 * 16762 + 7378
16762 = 2 * 7378 + 2006
7378 = 3 * 2006 + 1360
2006 = 1 * 1360 + 646
1360 = 2 * 646 + 68
646 = 9 * 68 + 34
68 = 2 * 34 + 0
.
gcd（24140,16762）=34
再舉個栗子：
計算gcd（4655,12075）
.
12075 =2*4655 + 2765
4655 = 1 * 2765 + 1890
2765 = 1 * 1890 + 875
1890 = 2 * 875 + 140
875 = 6 * 140 + 35
140 = 4 * 35 + 0
.
gcd（4655,12075）=35
.
.
2.擴展的歐幾里得
- 找到兩個數 x，y 使 ax+by = gcd（a，b）
方法：
rn 除以 rn+1 ： 商爲qn+2 ， 餘爲rn+2
vn - vn+1 * qn + 2 = vn+2
wn - wn+1 * qn + 2 = wn+2
滿足：
rn = rn+1 * qn+2 + rn+2
r-1 * vn + r0 * wn = rn
.
舉1個栗子，求1234 mod 4321的乘法逆元：
| i | ri | qi | vi | wi |
|---|---|---|---|---|
| -1 | 4321 | 1 | 0 | |
| 0 | 1234 | 0 | 1 | |
| 1 | 619 | 3 | 1 | -3 |
| 2 | 615 | 1 | -1 | 4 |
| 3 | 4 | 1 | 2 | -7 |
| 4 | 3 | 153 | -307 | 1075 |
| 5 | 1 | 1 | 309 | -1082 |
| 6 | 0 | 3 |
從表中得到 309 * 4321-1082 * 1234 = gcd(1234,4321) = 1
.
舉2個栗子，求16進制數 { B2 }在有限域GF（28）上的逆元：
| i | ri | qi | vi | wi |
|---|---|---|---|---|
| -1 | (1 0001 1011) | 1 | 0 | |
| 0 | (1011 0010) | 0 | 1 | |
| 1 | (0111 1111) | (0000 0010) | (0000 0001) | (0000 0010) |
| 2 | (0011 0011) | (0000 0011) | (0000 0011) | (0000 0111) |
| 3 | (0001 1001) | (0000 0010) | (0000 0111) | (0000 1100) |
| 4 | (0000 0001) | (0000 0010) | (0000 1101) | (0001 1111) |
| 5 | (0000 0000) | (0000 0001) |
從表中得到 (0000 1101) * (1 0001 1011) + (0001 1111) * (1011 0010) = 1
.
.
3.求乘法逆元
- 若最終找到 gcd（a，b）= 1 ， 又因爲1 mod a = 1
- 則 (ax + by) mod a = 1
- 即 by mod a = 1
- 即 y是b mod a的乘法逆元
第1個栗子中，求1234 mod 4321的乘法逆元：
已經知道 309 * 4321-1082 * 1234 = gcd(1234,4321) = 1
又因爲 1 mod 4321 = 1，將上式代入本式
.
(309 * 4321 - 1082 * 1234) mod 4321 = 1
1082 * 1234 mod 4321 = 1
.
所以1082是1234 mod4321的乘法逆元
第2個栗子中求16進制數 { B2 }在有限域GF（28）上的逆元：
已經知道(0000 1101) * (1 0001 1011) + (0001 1111) * (1011 0010) = 1
又因爲 1 mod (1 0001 1011) = 1，代入上式
.
(0000 1101) * (1 0001 1011) + (0001 1111) * (1011 0010) mod (1 0001 1011) = 1
(0001 1111) * (1011 0010) mod (1 0001 1011) = 1
.
所以(0001 1111) 是 (1011 0010) mod (1 0001 1011)的乘法逆元
.
化回16進制：(0001 1111) = { 1F }
.
.
4.AES：S-BOX
承接栗子2的結果(0001 1111) ，我們可以繼續計算AES的S-BOX置換：
（注意：下圖中 列向量是從下往上、倒着寫的）
將矩陣變換的結果（0011 0111），轉化爲16進制：{ 37 }
驗證一下：
查AES_S-BOX的表可知：{ B2 }的結果是{ 37 }，無誤~ （s-box的表格是固定的）
. . . . . .