欧几里得算法，扩展的欧几里得算法（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的表格是固定的）
.
.
.
.
.
.