-
-
[原创]AES中S盒的生成原理与变化
-
2019-8-17 20:19
-
一. 前言
菜鸟本来是写了很长时间，到处修修补补--! 越写越多，数学知识的补充确实花费了很长时间，还有调试。今天看到其他大佬的分析，各种数学公式信手拈来，排版又漂亮，我真的太羡慕了（哭）。本来很长，但既然已经有更好的分析了，那我也就把S盒的原理单独拿出来吧。我这份有些地方写的可能不太严谨，因为还是想已自己的话语来将它表述出来，这样可能使更多像我这样基础薄弱的也能看懂。
如果有粗心的地方，欢迎指出。(纯文本，方便大家保存，除了那个MATLAB的验证截了一张图，不影响~）
符号：
_ 表示下标
^ 表示次方
注：如果有其他含义会特别标出
二. 域、多项式
首先我们要先了解群、环和域的知识，它们都是满足一定公理的集合。
定理就不多做介绍了（主要是目前我也理解的不太深...），我整理一个包含关系，如下：
域
|--如果a属于S，且a!=0，则S中存在一个元素a^-1，满足a * a^(-1) = a^(-1) * a = 1
|--整环
|--如果S中任意两个元素a和b满足ab=0，则a=0或b=0
|--对于S中任意元素a，在S中存在一个元素e，使得ae = ea = a
|--可交换环
|--对于S中任意元素a和b，ab = ba成立
|--环
|--对于S中任意元素a，b，c，
满足a(b + c) = ab + ac，(a + b)c = ac + bc
|--对于S中任意元素a，b，c，满足a(bc) = (ab)c
|--如何a和b属于S，则ab也属于S
|--可交换群
|--对于S中任意元素a和b，满足a + b = b + a
|--群
|--元素a属于S，S中必定存在一个-a，是a + (-a) = (-a) + a = 0
|--S中有一个元素e，使得任意元素a满足a + e = e + a = a
|--对于S中任意元素a, b, c有a + (b + c) = (a + b) + c
|--如果a，b同属于S，则a+b也属于S
要注意的是，因为，所以这里是群的定理是加法，其实群的运算符号可以是任意一个二元符号。
其中的的逆元概念特别说明一下：
加法逆元：已知整数x，它的加法逆元y使得(x+y) mod z = 0成立
乘法逆元：已知非0整数x，它的乘法逆元y使得(x*y) mod z = 1 mod z成立
还有模运算的性质：
[(a mod n) + (b mod n)] mod n = (a + b) mod n
[(a mod n) - (b mod n)] mod n = (a - b) mod n
[(a mod n) * (b mod n)] mod n = (a * b) mod n
2.1. 有限域
这里主要介绍有限域，即元素个数有限的域。
a. 有限域中的元素个数我们称为阶。
b. 有限域的阶必须是一个素数的幂p^n（p为素数，n为正整数），记为GF(p^n)。
c. 当n=1时，元素为0到p-1的集合，且该集合上的运算为模p运算时，这个集合才符合域的条件。
GF(5)来举例，元素为{0, 1, 2, 3, 4}，其中算术运算为模5加法和模5乘法。下面列出模5加法和乘法的结果
【说明：模5加法，就是a，b是GF(5)中的元素，a+b的结果就是(a+b) mod 5】
+ 0 1 2 3 4 * 0 1 2 3 4
0 0 1 2 3 4 0 0 0 0 0 0
1 1 2 3 4 0 1 0 1 2 3 4
2 2 3 4 0 1 2 0 2 4 1 3
3 3 4 0 1 2 3 0 3 1 4 2
4 4 0 1 2 3 4 0 4 3 2 1
大家可以对照下，上面域的那些定理。全部是满足的。
2.2. 多项式
下面我们再说下多项，多项式大家都认识，一个简单的的n次多项式就像这样：
f(x) = (a_n)*x^n + [a_(n-1)]*x^(n-1) + ... + (a_1)*x + a_0
在进制转换时我们经常可以见到，比如这样：
b0111 = 1 * 2^2 + 1 * 2^1 + 1 * 2^0 = 7
只是我们这里不计算x为具体值的情况，即x只作为x。
如下定义：
a. 当多项式的系数在一个域中时，我们称为该多项式是这个域上的多项式。
b. 如果域F上的一个多项式f(x)不能表示成另外两个多项式的乘积时，我们称它为不可约多项式。（另外两个多项式都在上F，且次数都低于f(x)的次数）
多项式的加减乘就不用说，主要来看下除法。
多项式除法定义如下：
一个n次多项式f(x)和m次多项式g(x)，m <= n，满足f(x) = q(x)g(x) + r(x)
q(x)的次数为n-m，r(x)的次数小于等于m-1
需要注意的一点就是除法是直到余式为0或余式的次数低于除数的次数时，运算停止。
2.3. GF(p^n)
现在n>1，如果再按n=1的那种条件构成集合，该集合是不符合域的条件的，比如当p=2, n=3时
看下乘法的结果，一目了然，
* 0 1 2 3 4 5 6 7
0 0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6 7
2 0 2 4 6 0 2 4 6
3 0 3 6 1 4 7 0 5
4 0 4 0 4 0 4 0 4
5 0 5 2 7 4 1 6 3
6 0 6 4 0 0 6 0 2
7 0 7 6 5 4 3 2 1
现在我们就要来找满足域条件的GF(p^n)
我们先定义一个集合S，且这些元素都是整数域GF(p)上的次方小于n的所有多项式。
S中的元素通用形式如下：
f(x) = a_(n-1)*x^(n-1) + ... + a_1*x + a_0 = (n-1)∑(i=0) a_i*x^i (a_i∈{0, 1, ..., p-1})
那么S中共有p^n个不同的多项式。
在普通多项式运算的基础上，增加下面两条规则
a. 系数的运算符合GF(p)上的运算规则，以p为模
b. 如果乘法运算后的结果多项式的次方大于等于n，就必须模上一个GF(p^n)上最大次方为n的不可约多项式g(x)
不要急，下面我们拐一个弯~
2.3.1 剩余类
这里要引入一个模运算里的概念，剩余类。
这里有一个集合{[0], [1], ..., [n-1]}，它是一个剩余类集，每个元素都是一个剩余类，谁的剩余类？模n的剩余类。
比如我们说有一个模4的剩余类集{[0], [1], [2], [3]}，
那么其中[0] = {..., -16, -12, -8, -4, 0, 4, 8, 12, 16, ...}，里面的每个元素模4后等于0，同理[1]里每个元素模4后等于1，依次类推。
一般我们会用最小的非负整数来表示一个剩余类。
理解了剩余类的概念后，来看下多项式也有剩余类集。
有一个系数在{0,... p-1}中的n次多项式m(x)，那么模m(x)的剩余类集就有p^n个元素。
我们拿表示这些剩余类的所有多项式组成集合，它们任意两个的乘积模m(x)后，
结果仍在这个集合里。元素个数有个p^n，且满足了域的所有公理，这不正是我们要找的嘛~
虽然可能会让你感觉模糊，但先认识这些概念。
例子先保留，认识完GF(2^n)后再统一来看例子~然后再回来翻看剩余类的概念
2.3.2 GF(2^n)
现在我们来讨论p=2的情况，即GF(2^n)。
这样a_i是由1和0组成，那么GF(2^n)的每个多项式就可以表示成一个二进制数。
加法：
主要是系数相加，由于是GF(2)上的运算规则，
GF(2)上的加法和乘法如下：
+ 0 1 * 0 1
0 0 1 0 0 0
1 1 0 1 0 1
可以看到模2加法等价于XOR运算，乘法等价于逻辑与运算。
而且从上面我们可以看到模2加法和减法是同等的：由于1+0 = 1-0 = 1, 1+1 = 1-1 = 0, 则0+1 = 0-1 = 1 【锚点A】
乘法：
乘法也就是基本的多项式相乘，但要注意这个乘法还要模最大次方为n的g(x)。
我们先来看一个简单的，以GF(2^3)上的不可约多项式g(x) = x^3 + x + 1为例。
用x^3来除以g(x)，运算如下：
1
——————————————
x^3 + x + 1 ）x^3 + 0x + 0
x^3 + 1x + 1
————————————
x + 1 【参见锚点A的信息】
x^3 mod g(x) = x + 1 = g(x) - x^3。（大家也可以用其他的多项式来试试）
我们可以得出这样一个的结论：在GF(2^n)上的n次多项式g(x)，满足x^n mod g(x) = [g(x) - x^n]
回到GF(2^3)的例子，在它上面的多项式通用形式，以b_n为系数，值为1或0
f(x) = (b_2)*(x^2) + (b_1)*x + b_0
那么我们讨论下x乘以f(x)，且b_2 = 1的情况
x * f(x) = [(b_2)*(x^3) + (b_1)*(x^2) + (b_0)*x] mod g(x)
= {[(b_2)*(x^3) mod g(x)] + [(b_1)*(x^2) + (b_0)*x] mod g(x)} mod g(x)
= {[(x^3) mod (x^3 + x + 1)] + [(b_1)*(x^2) + (b_0)*x] mod (x^3 + x + 1)} mod (x^3 + x + 1)
= (x + 1) + [(b_1)*(x^2) + (b_0)*x]
b_2 = 0的情况就简单了，x*f(x) = (b_1)*(x^2) + (b_0)*x。
我们将其转化为二进制数来看，可以得出：
[(b_1)(b_0)0] (b_2 = 0)
x*f(x) = {
[(b_1)(b_0)0] ⊕ (011) (b_2 = 1) 【⊕表示异或加】
这也就是起手信息了，有了这个，对于x的更高次幂只要重复这个计算就可以了。
2.3.3 例子
举个最简单的例子：GF(2^3)，系数在GF(2)上
他只有有两个满足条件的既约多项式x^3 + x^2 + 1，和x^3 + x + 1
我们选择x^3 + x^2 + 1做既约多项式。模x^3 + x^2 + 1的剩余类集F为
{ [0], [1], [x], [x+1], [x^2], [x^2 + 1], [x^2 + x], [x^2 + x + 1] }
可以看到F中元素个数为2^3。
接着提取表示剩余类的多项式组成集合F'
{ 0, 1, x, x+1, x^2, x^2 + 1, x^2 + x, x^2 + x + 1 }
下面是以x^3 + x^2 + 1为既约多项式的加法和乘法。
加法：
+ 0 1 x x+1 x^2 x^2+1 x^2+x x^2+x+1 0 0 1 x x+1 x^2 x^2+1 x^2+x x^2+x+1 1 1 0 x+1 x x^2+1 x^2 x^2+x+1 x^2+x x x x+1 0 1 x^2+x x^2+x+1 x^2 x^2+1 x+1 x+1 x 1 0 x^2+x+1 x^2+x x^2+1 x^2 x^2 x^2 x^2+1 x^2+x x^2+x+1 0 1 x x+1 x^2+1 x^2+1 x^2 x^2+x+1 x^2+x 1 0 x+1 x x^2+x x^2+x x^2+x+1 x^2 x^2+1 x x^2 0 1 x^2+x+1 x^2+x+1 x^2+x x^2+1 x^2 x+1 x 1 0
乘法：
* 0 1 x x+1 x^2 x^2+1 x^2+x x^2+x+1 0 0 0 0 0 0 0 0 0 1 0 1 x x+1 x^2 x^2+1 x^2+x x^2+x+1 x 0 x x^2 x^2+x x^2+1 x^2+x+1 1 x+1 x+1 0 x+1 x^2+x x^2+1 1 x x^2+x+1 x^2 x^2 0 x^2 x^2+1 1 x^2+x+1 x+1 x x^2+x x^2+1 0 x^2+1 x^2+x+1 x x+1 x^2+x x^2 1 x^2+x 0 x^2+x 1 x^2+x+1 x x^2 x+1 x^2+1 x^2+x+1 0 x^2+x+1 x+1 x^2 x^2+x 1 x^2+1 x
如果你懒得往上翻域的公理，那我们在这里一边看下F'的满足情况，一边复习吧
1. 如果a, b同属S，则a+b也属于S。（通过F'加法表可知满足）
2. 对于S中任意元素a, b, c有a + (b + c) = (a + b) + c，（通过F'加法表，做下计算即可验证）
3. S中有一个元素e，使得任意元素a满足a + e = e + a = a （通过F'加法表可知满足）
4. 元素a属于S，S中必定存在一个-a，是a + (-a) = (-a) + a = 0 （通过F'加法表可知满足）
5. 对于S中任意元素a和b，满足a + b = b + a （满足）
6. 如何a和b属于S，则ab也属于S （通过F'的乘法表可知满足）
7. 对于S中任意元素a，b，c，满足a(bc) = (ab)c（通过F'乘法表，做下计算即可验证）
8. 对于S中任意元素a，b，c，满足a(b + c) = ab + ac，(a + b)c = ac + bc （通过F'加法和乘法表，做下计算即可验证）
9. 对于S中任意元素a和b，ab = ba成立 （满足）
10. 存在一个元素e，使ae = ea =a （在F'里这个e就是1）
11. 如果ab=0, 那么a=0或b=0。（通过F'的乘法结果表可知满足）
通过这个例子，想必你已经明白如何构建满足域条件的GF(p^n)了。
2.4. 欧几里得算法
大家都知道，有一个欧几里得算法可以用来找最大公因子，也叫辗转相除法。简单的描述一下：
整数a和b，用a除以b，得到余数r_1，然后用b除以r_1，得到余数r_2，用r_1除以r_2，
得到余数r_3....，直到余数为0时，除数就是a和b的最大公因子。
也可以换另外一个角度来描述：
a / b = q_1，余数为r_1，可得a = b*q_1 + r_1。依次类推,
b = r_1*q_2 + r_2
r_1 = r_2*q_3 + r_3
r_2 = r_3*q_4 + r_4
...
r_(n-2) = r(n-1)*q_n + r_n
r_(n-1) = r_n*q_(n+1) + r_(n+1)
如果r_(n+1) = 0，那么gcd(a, b) = r_n = d
这里我们来考虑下为什么通过这样的计算就能找到最大公因子,
首先我们要了解下整除的两个重要性质：
1. 如果a|b且b|c，则a|c
2. 如果b|g且b|h，则对任意的整数m和n，有b|(mg + nh)
下面正式开始验证
设d = gcd(a, b)，a >= b > 0。
用a除以b，得到a = q_1 * b + r_1，0 <= r_1 < b
如果是r_1 = 0的情况，说明b整除a，那么b = gcd(a, b) = d。
如果是r_1 != 0的情况，首先我们知道d是肯定可以整除a和b的，
那么根据上面列出的整除的第2条重要性质，可以得出：
d|a, d|b ——> d|(a - q_1b) = d|r_1
假如进入到第2步，求gcd(b, r_1)，已知d|b，d|r_1，那么d = gcd(b, r_1)。
再往下就可以看作一个迭代过程，直到余数为0这个出口，那么这时的被除数就是那个d。
到这里，我们应该说对欧几里得算法了解的基本可以了~
现在让我们去获取最后一个块拼图吧
2.5 扩展的欧几里得算法
对于gcd(a, b) = d，有整数x，y满足ax + by = d，且d为ax + by结果中的最小正整数。
在欧几里得算法上进行扩展，不仅可以求出d，而且还可以连带求出x，y。
对于在欧几里得算法部分描述中，我们知道了r_(n-2) = r(n-1)*q_n + r_n，那么通过移项可以得到r_n = r_(n-2) - r(n-1)*q_n。
我们知道欧几里得算法中每一步除法都会得到一个余数r_n，那么同样有整数x_n和x_y使得a*x_n + b*y_n = r_n满足。
将r_n = r_(n-2) - r(n-1)*q_n与a*x_n + b*y_n = r_n合并，可得
[a*x_(n-2) + b*y_(n-2)] - [a*x_(n-1) + b*y_(n-1)]q_n = r_n
= a*[x_(n-2) - x_(n-1)*q_n] + b*[y_(n-2) - y_(n-1)*q_n]
那么x_n = [x_(n-2) - x_(n-1)*q_n], y_n = [y_(n-2) - y_(n-1)*q_n]。
由于r_1 = a - b*q_1，那么将a看作r_(-1)，将b看作r_0。那么就有：
r_(-1) = a = a*x_(-1) + b*y_(-1)，则x_(-1) = 1，y_(-1) = 0;
r_0 = b = a*x_0 + b*y_0，则x_0 = 0, y_0 = 1;
现在知道了起手信息，最后计算到d = 1时，x的值和y的值也就出来了。
到现在你可能会有"这扩展的欧几里得有啥用？我凭啥要去算那什么x和y这俩鬼东西的值？"这种疑问了。那这里我们就梳理一下吧~
假设gcd(a, b) = 1，那么就有ax + by = 1。
两边同时模上a，根据模运算的基本性质就有：
(ax + by) mod a = 1 mod a
= [(ax mod a) + (by mod a)] mod a = 1 mod a
= 0 + by mod a = 1
= by mod a = 1
则y = b^(-1)，即y为b模a的乘法逆元。扩展的欧几里得算法就是来求乘法逆元的。
简单写个代码验证下：
INT64 EuclidEx(INT64 i64A, INT64 i64B, INT64 &ref_i64X, INT64 &ref_i64Y)
{
if (0 == i64B)
{
return 0;
}
INT64 i64Quotient = 0;
INT64 i64LastLastX = 1;
INT64 i64LastLastY = 0;
INT64 i64LastX = 0;
INT64 i64LastY = 1;
INT64 i64LastLastRemainder = i64A;
INT64 i64LastRemainder = i64B;
INT64 i64Remainder = 0;
ref_i64X = 0;
ref_i64Y = 1;
do
{
i64Quotient = i64LastLastRemainder / i64LastRemainder;
i64Remainder = i64LastLastRemainder % i64LastRemainder;
if (0 == i64Remainder)
{
break;
}
ref_i64X = i64LastLastX - i64LastX * i64Quotient;
ref_i64Y = i64LastLastY - i64LastY * i64Quotient;
i64LastLastRemainder = i64LastRemainder;
i64LastRemainder = i64Remainder;
i64LastLastX = i64LastX;
i64LastX = ref_i64X;
i64LastLastY = i64LastY;
i64LastY = ref_i64Y;
} while (TRUE);
return i64LastRemainder;
} //! EuclidEx() END
int main()
{
INT64 i64X = 0;
INT64 i64Y = 0;
INT64 i64Result = EuclidEx(1759, 550, i64X, i64Y);
printf("Result: %I64d\n", i64Result);
printf("X: %I64d\n", i64X);
printf("Y: %I64d\n", i64Y);
system("pause");
return 0;
}结果
Result: 1
X: -111
Y: 355
(550 * 355) % 1759 = 1，355就是550的乘法逆元
将其转为多项式也是同样的：
如果d(x) = gcd[a(x), b(x)]，b(x)的次数小于a(x)的次数，那么有v(x)和w(x)满足a(x)v(x) + b(x)w(x) = d(x)。
如果d(x) = 1，那么[b(x) mod a(x)]^(-1) = w(x)。
这个有个重点要记住，如果a(x)为既约多项式，那么绝对有gcd[a(x), b(x)] = 1（思考下既约多项式的概念~）
而且还要注意的是，系数运算全是在GF(2)上的，这点千万不可忘记。
三. 矩阵
我们先了解下矩阵的加减乘运算，
a. 矩阵加法/减法，两个矩阵大小要相同，然后对应元素进行相加/相减
b. 矩阵乘法，简单点描述，最后结果矩阵中的每一个元素都是由一行和一列的对应元素分别相乘，最后再将乘积相加。（要求A的列数等于B的行数时才可相乘）
关于除法比较特殊，矩阵A除以矩阵B等于矩阵A乘以矩阵B的逆矩阵，也就是AB = AB^(-1)。
逆矩阵有一个性质就是： AA^(-1) = E, 这里的E表示为单位矩阵。
单位矩阵就是从左上角到右下角的元素为1，其余元素为0。
单位矩阵的性质：任何矩阵与单位矩阵相乘都为本身【重点】
*注意* 这部分是补充矩阵相关的求逆知识，和AES关系不大（时间一长，我自己都忘了当时是为了哪个问题去补充了下这个....⊙﹏⊙b汗），当时也花了很多心思在上面，就放上来了。没有这个需求的可以跳过了...
那么现在重点就是要学习如何求一个矩阵的逆矩阵，最常用的方法就是初等行变换。
3.1 矩阵初等行变换
矩阵初等行变换有3种方式：
a. 用数域P（由复数组成）中的非0数乘以矩阵的第n行元素，第n行元素发生变化
b. 用数域P（由复数组成）中的一个数乘以第n行的元素，然后将结果再加到m行，第m行元素发生变化
c. 直接互换矩阵中两行的位置
使用矩阵初等行变换求逆矩阵就是通过上面的三总方式实现(A E)->(E A^(-1))
先把单位矩阵加到左边，然后根据变换将其移到右边就可以求出A的逆矩阵了。
不太理解也没关系，这里我们直接上栗子
（其实我刚看到时也是懵的, 使用工具是非常方便的，这里手动计算主要目的是使大家更好的理解初等变换）
1 1 0 3 2 2
设A = [ 1 0 1 ]，B矩阵未知，AB = C = [ 2 3 2 ]，求B矩阵。
0 1 1 2 2 3
那么， B = C/A = CA^(-1)，需要求A矩阵的逆矩阵。
因为后面我们会碰到这种情况，所以就直接用一个简单版本来做栗子。
我们来试一下，其中用R_n来表示第n行
1 1 0 1 0 0
(A E) = [ 1 0 1 0 1 0 ]
0 1 1 0 0 1
这里有一个变换的技巧，就是从左向右进行如下处理：
a. 将第n列的第n行的元素变记为a_nn
b. 使用R_(n)将第n行上面的所有行的第n列元素转换为0
c. 使用R_(n)将第n行下面的所有行的第n列元素转换为0
d. 重复b和c，直到遍历为所有的列
b. 将a_nn的值转为转变为1
为了方便大家理解，不进行多步处理，我们一步一步的来看。
(A E)中a_11 = 1，那么用R_(1)的-1倍加到R_(2)上
R_2 - R_1 1 1 0 1 0 0
—————————————> [ 0 -1 1 -1 1 0 ]
0 1 1 0 0 1
现在处理第2列，a_22 = -1，通过变换让a_21 = 0
R_1 + R_2 1 0 1 0 1 0
—————————————> [ 0 -1 1 -1 1 0 ]
0 1 1 0 0 1
通过变换让a_23 = 0
R_3 + R_2 1 0 1 0 1 0
—————————————> [ 0 -1 1 -1 1 0 ]
0 0 2 -1 1 1
现在处理第3列 a_33 = 2，直接不废话了
R_1 - (1/2)R_3 1 0 0 1/2 1/2 -1/2
—————————————> [ 0 -1 1 -1 1 0 ]
0 0 2 -1 1 1
R_2 - (1/2)R_3 1 0 0 1/2 1/2 -1/2
—————————————> [ 0 -1 0 -1/2 1/2 -1/2 ]
0 0 2 -1 1 1
最后变换a_nn，让a_nn都等于1，就大功告成了
(-1)R_2 1 0 0 1/2 1/2 -1/2
————————> [ 0 1 0 1/2 -1/2 1/2 ]
0 0 2 -1 1 1
(1/2)R_3 1 0 0 1/2 1/2 -1/2
————————> [ 0 1 0 1/2 -1/2 1/2 ] = [E A^(-1)]
0 0 1 -1/2 1/2 1/2
3 2 2 1/2 1/2 -1/2 3/2 3/2 1/2
CA^(-1) = [ 2 3 2 ] * [ 1/2 -1/2 1/2 ] = [ 3/2 1/2 3/2 ] = B
2 2 3 -1/2 1/2 1/2 1/2 3/2 3/2
用MATLAB来验证下（确实很方便~）
四. 构建s盒（字节替换表）
字节替换，我们一般在实现时都直接放一张表来操作，正表和逆表（更加正确的称呼应该是S盒和逆S盒），即加密和解密时要查询的表。
而且它需要满足逆s-box[(s-box(a)] = a
主要是方便做替换，其实S盒的构建流程就是字节替换的流程，我们需要重点理解它.
现在我们先来尝试下手动生成它吧。
AES的所有运算都是以字节为单位进行的，一个字节由8位二进制数组成，与之相应的就是由GF(2)上的多项式构成的有限域GF(2^8)，
这样每个多项式都可以看作是一个8位的数了。
按照之前的定义，我们还需要最高次幂为8的一个不可约多项式，AES用的是x^8 + x^4 + x^3 + x + 1。【a. 不可约多项式】
套用x*f(x)，根据前面的例子，可得
[(b_6)(b_5)(b_4)(b_3)(b_2)(b_1)(b_0)0] (b_7 = 0)
x*f(x) = {
[(b_6)(b_5)(b_4)(b_3)(b_2)(b_1)(b_0)0] ⊕ (00011011) (b_7 = 1)
S盒构建的流程如下
1. 行x取0-F，列y取0-F，表中每一项的值由x和y构成，格式为{yx}
2. 每项值看作一个字节，转成二进制，然后求它在GF(2^8)中的乘法逆元
3. 每一项值做位变换，满足
R(b_i) = b_i ⊕ b_[(i+4) mod 8] ⊕ b_[(i+5) mod 8] ⊕ b_[(i+6) mod 8] ⊕ b_[(i+7) mod 8] ⊕ c_i
其中c_i为固定字节{63}的第i位
4. 将最后结果转回字节
逆S盒构建流程如下：
1. 行x取0-F，列y取0-F，表中每一项的值由x和y构成，格式为{yx}
2. 每项值看作一个字节，转为二进制做位变换，满足
逆R(b_i) = b_i ⊕ b_[(i+2) mod 8] ⊕ b_[(i+5) mod 8] ⊕ b_[(i+7) mod 8] ⊕ d_i
其中d_i为固定字节{05}的第i位
3. 然后用变换后的结果，求它在GF(2^8)中的乘法逆元
4. 将最后结果转回字节
这里我们重点来看位变换，回头看R(b_i)，将其进行转化：
R(b_i) = 1*b_i ⊕ 0*b_[(i+1) mod 8] ⊕ 0*b_[(i+2) mod 8] ⊕ 0*b_[(i+3) mod 8] ⊕ 1*b_[(i+4) mod 8] ⊕
1*b_[(i+5) mod 8] ⊕ 1*b_[(i+6) mod 8] ⊕ 1*b_[(i+7) mod 8] ⊕ c_i
以b_0为例
R(b_0) = 1*b_0 ⊕ 0*b_1 ⊕ 0*b_2 ⊕ 0*b_3 ⊕ 1*b_4 ⊕ 1*b_5 ⊕ 1*b_6 ⊕ 1*b_7 ⊕ c_0
根据矩阵乘法，我们可以将转化位变换转化为矩阵运算，得到如下公式:
（注意: 这里矩阵乘法中每项乘积相加时使用的是异或加)
R(b_0) 1 0 0 0 1 1 1 1 b_0 c_0
R(b_1) 1 1 0 0 0 1 1 1 b_1 c_1
R(b_2) 1 1 1 0 0 0 1 1 b_2 c_2
[ R(b_3) ] = [ 1 1 1 1 0 0 0 1 ] * [ b_3 ] ⊕ [ c_3 ]
R(b_4) 1 1 1 1 1 0 0 0 b_4 c_4
R(b_5) 0 1 1 1 1 1 0 0 b_5 c_5
R(b_6) 0 0 1 1 1 1 1 0 b_6 c_6
R(b_7) 0 0 0 1 1 1 1 1 b_7 c_7
同理逆S盒的位变换如下
逆R(b_0) 0 0 1 0 0 1 0 1 b_0 d_0
逆R(b_1) 1 0 0 1 0 0 1 0 b_1 d_1
逆R(b_2) 0 1 0 0 1 0 0 1 b_2 d_2
[ 逆R(b_3) ] = [ 1 0 1 0 0 1 0 0 ] * [ b_3 ] ⊕ [ d_3 ]
逆R(b_4) 0 1 0 1 0 0 1 0 b_4 d_4
逆R(b_5) 0 0 1 0 1 0 0 1 b_5 d_5
逆R(b_6) 1 0 0 1 0 1 0 0 b_6 d_6
逆R(b_7) 0 1 0 0 1 0 1 0 b_7 d_7
这里又有一个疑问了，为什么通过正字节替换，然后再逆字节替换就能还原回原来的值呢？我们来动手验证一下
设字节A为原字节在GF(2^8)上求乘法逆结果，通过位变换得到字节B，设正向位变换使用的矩阵为X，使用的固定字节为C，流程就是：
R(A) = XA ⊕ C = B
设逆向位变换使用的矩阵为Y，使用的固定字节为D，流程就是：
逆R(B) = BY ⊕ D
我们将流程合并一下，可得：
逆R(R(A)) = (XA ⊕ C)Y ⊕ D = YXA ⊕ YC ⊕ D
只要证明结果为A，那么也就证明了我们通过正字节替换，然后再逆字节替换就能还原回原来的值。
现在将A转为矩阵，开始将位变换矩阵和固定值带入YXA ⊕ YC ⊕ D并展开，看着很长，但都是基本运算，来简单化简一下
1 0 0 0 1 1 1 1 0 0 1 0 0 1 0 1 a_0 0 0 1 0 0 1 0 1 1 1
1 1 0 0 0 1 1 1 1 0 0 1 0 0 1 0 a_1 1 0 0 1 0 0 1 0 1 0
1 1 1 0 0 0 1 1 0 1 0 0 1 0 0 1 a_2 0 1 0 0 1 0 0 1 0 1
= [ 1 1 1 1 0 0 0 1 ] * [ 1 0 1 0 0 1 0 0 ] * [ a_3 ] ⊕ [ 1 0 1 0 0 1 0 0 ] * [ 0 ] ⊕ [ 0 ]
1 1 1 1 1 0 0 0 0 1 0 1 0 0 1 0 a_4 0 1 0 1 0 0 1 0 0 0
0 1 1 1 1 1 0 0 0 0 1 0 1 0 0 1 a_5 0 0 1 0 1 0 0 1 1 0
0 0 1 1 1 1 1 0 1 0 0 1 0 1 0 0 a_6 1 0 0 1 0 1 0 0 1 0
0 0 0 1 1 1 1 1 0 1 0 0 1 0 1 0 a_7 0 1 0 0 1 0 1 0 0 0
1 0 0 0 0 0 0 0 a_0 1 1 a_0
0 1 0 0 0 0 0 0 a_1 0 0 a_1
0 0 1 0 0 0 0 0 a_2 1 1 a_2
= [ 0 0 0 1 0 0 0 0 ] * [ a_3 ] ⊕ [ 0 ] ⊕ [ 0 ] = [ a_3 ]
0 0 0 0 1 0 0 0 a_4 0 0 a_4
0 0 0 0 0 1 0 0 a_5 0 0 a_5
0 0 0 0 0 0 1 0 a_6 0 0 a_6
0 0 0 0 0 0 0 1 a_7 0 0 a_7
可以看到，正向位变换矩阵X和逆向位变换Y相乘得到了一个单元矩阵，Y乘以C也得到了D，两次异或抵消，最后结果又得到了A。
这里写了一份标准版S盒简单的生成样例代码试试:
#include <Windows.h>
#include <iostream>
#include "MatrixGF2.h"
#include "PolynomialGF2.h"
MatrixGF2<BYTE> g_mtxPositiveBox(16, 16, 0);
MatrixGF2<BYTE> g_mtxReverseBox(16, 16, 0);
MatrixGF2<BYTE> g_mtxBytePositiveTransformMatrix(8, 8, 0);
MatrixGF2<BYTE> g_mtxByteReverseTransformMatrix(8, 8, 0);
BYTE g_bytPositiveFixed = 0;
BYTE g_bytReverseFixed = 0;
PolynomialGF2 g_polyModle;
#define MAKEBYTE(_high, _low) (((_high) << 4) | (_low))
PolynomialGF2 PolynomialEuclidEx(const PolynomialGF2 &kref_polyA,
const PolynomialGF2 &kref_polyB,
PolynomialGF2 &ref_polyX,
PolynomialGF2 &ref_polyY)
{
if (kref_polyB.EqualZero())
{
throw std::runtime_error("The polyB is zero!");
}
int iHighestBitIndex = kref_polyA.GetHightestBitIndex();
PolynomialGF2 polyQuotient(iHighestBitIndex + 1, 0);
PolynomialGF2 polyRemainder(iHighestBitIndex + 1, 0);
PolynomialGF2 polyLastLastX(iHighestBitIndex + 1, 0);
polyLastLastX = 1;
PolynomialGF2 polyLastLastY(iHighestBitIndex + 1, 0);
PolynomialGF2 polyLastLastRemainder = kref_polyA;
PolynomialGF2 polyLastX(iHighestBitIndex + 1, 0);
PolynomialGF2 polyLastY(iHighestBitIndex + 1, 0);
polyLastY = 1;
PolynomialGF2 polyLastRemainder = kref_polyB;
ref_polyX.Clear();
ref_polyY.Clear();
ref_polyX.Insert(0, iHighestBitIndex + 1, 0);
ref_polyY.Insert(0, iHighestBitIndex + 1, 0);
ref_polyY = 1;
do
{
polyLastLastRemainder.Division(polyLastRemainder,
polyQuotient,
polyRemainder);
if (polyRemainder.EqualZero())
{
break;
}
ref_polyX = polyLastLastX - polyLastX * polyQuotient;
ref_polyY = polyLastLastY - polyLastY * polyQuotient;
polyLastLastRemainder = polyLastRemainder;
polyLastRemainder = polyRemainder;
polyLastLastX = polyLastX;
polyLastLastY = polyLastY;
polyLastX = ref_polyX;
polyLastY = ref_polyY;
} while (TRUE);
return polyLastRemainder;
} //! PolynomialGF2EuclidEx() END
void InitByteTransformMatrix(PolynomialGF2 &ref_polyInit,
MatrixGF2<BYTE> &ref_mtxTarget)
{
size_t uiColumnNumber = ref_mtxTarget.GetColumnNumber();
if (ref_polyInit.GetSize() != ref_mtxTarget.GetColumnNumber())
{
ref_polyInit.PaddingZero(uiColumnNumber);
}
size_t uiRowNumber = uiColumnNumber;
for (size_t cntY = 0; cntY < uiRowNumber; cntY++)
{
size_t iOffset = cntY;
for (size_t cntX = 0; cntX < uiColumnNumber; cntX++)
{
size_t iActualPos = cntX + iOffset;
if (iActualPos >= uiColumnNumber)
{
iActualPos -= uiColumnNumber;
}
ref_mtxTarget[cntY][iActualPos] = ref_polyInit[cntX];
}
}
} //! InitByteTransformMatrix() END
void InitPositiveBox()
{
MatrixGF2<BYTE> mtxFixed = PolynomialGF2(g_bytPositiveFixed).GetDequeFormat();
for (size_t cntY = 0; cntY < 16; cntY++)
{
for (size_t cntX = 0; cntX < 16; cntX++)
{
BYTE bytSource = (BYTE)MAKEBYTE(cntY, cntX);
if (0 == bytSource)
{
g_mtxPositiveBox[cntY][cntX] = g_bytPositiveFixed;
continue;
}
PolynomialGF2 polyInverseElement;
PolynomialGF2 polyX;
PolynomialGF2 polySource = bytSource;
// 求乘法逆元
if (!polySource.EqualZero())
{
PolynomialGF2 polyResult =
PolynomialEuclidEx(g_polyModle,
polySource,
polyX,
polyInverseElement);
}
else
{
polyInverseElement = { 0 };
}
polyInverseElement.ClearInvalidZero();
MatrixGF2<BYTE> mtxValue = polyInverseElement.GetDequeFormat();
mtxValue.PaddingRow(
g_mtxBytePositiveTransformMatrix.GetColumnNumber()
);
mtxFixed.PaddingRow(mtxValue.GetRowNumber());
mtxValue = g_mtxBytePositiveTransformMatrix * mtxValue + mtxFixed;
g_mtxPositiveBox[cntY][cntX] =
(BYTE)PolynomialGF2(mtxValue.Transform2Vector()).ToNumber();
}
}
} //! InitPositiveBox() END
void InitReverseBox()
{
MatrixGF2<BYTE> mtxFixed = PolynomialGF2(g_bytReverseFixed).GetDequeFormat();
for (size_t cntY = 0; cntY < 16; cntY++)
{
for (size_t cntX = 0; cntX < 16; cntX++)
{
BYTE bytSource = (BYTE)MAKEBYTE(cntY, cntX);
MatrixGF2<BYTE> mtxValue = bytSource;
int iValueColumnNumber =
g_mtxByteReverseTransformMatrix.GetColumnNumber();
if (0 == bytSource)
{
mtxValue.InsertRow(0, iValueColumnNumber, 1, 0);
}
mtxValue.PaddingRow(iValueColumnNumber);
mtxFixed.PaddingRow(mtxValue.GetRowNumber());
mtxValue = g_mtxByteReverseTransformMatrix * mtxValue + mtxFixed;
PolynomialGF2 polyInverseElement;
PolynomialGF2 polyX;
PolynomialGF2 polyValue = mtxValue.Transform2Vector();
if (!polyValue.EqualZero())
{
// 求乘法逆元
PolynomialGF2 polyResult =
PolynomialEuclidEx(g_polyModle,
polyValue,
polyX,
polyInverseElement);
}
else
{
polyInverseElement = { 0 };
}
g_mtxReverseBox[cntY][cntX] = (BYTE)polyInverseElement.ToNumber();
}
}
} //! InitReverseBox() END
void InitStandardBox()
{
g_polyModle = { 1, 1, 0, 1, 1, 0, 0, 0, 1 };
PolynomialGF2 polyPositiveSeed = { 1, 0, 0, 0, 1, 1, 1, 1 };
InitByteTransformMatrix(polyPositiveSeed, g_mtxBytePositiveTransformMatrix);
PolynomialGF2 polyReverseSeed = { 0, 0, 1, 0, 0, 1, 0, 1 };
InitByteTransformMatrix(polyReverseSeed, g_mtxByteReverseTransformMatrix);
g_bytPositiveFixed = 0x63;
g_bytReverseFixed = 0x05;
InitPositiveBox();
InitReverseBox();
printf("Positive box: \n%s\n",
g_mtxPositiveBox.GetWrittenFormat().c_str());
printf("Reverse box: \n%s\n",
g_mtxReverseBox.GetWrittenFormat().c_str());
} //! InitStandardBox() END
int main()
{
InitStandardBox();
system("pause");
return 0;
}结果：
结果： Positive box: 0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76 0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0 0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15 0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75 0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84 0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF 0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8 0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2 0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73 0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB 0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79 0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08 0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A 0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E 0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF 0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16 Reverse box: 0x52, 0x09, 0x6A, 0xD5, 0x30, 0x36, 0xA5, 0x38, 0xBF, 0x40, 0xA3, 0x9E, 0x81, 0xF3, 0xD7, 0xFB 0x7C, 0xE3, 0x39, 0x82, 0x9B, 0x2F, 0xFF, 0x87, 0x34, 0x8E, 0x43, 0x44, 0xC4, 0xDE, 0xE9, 0xCB 0x54, 0x7B, 0x94, 0x32, 0xA6, 0xC2, 0x23, 0x3D, 0xEE, 0x4C, 0x95, 0x0B, 0x42, 0xFA, 0xC3, 0x4E 0x08, 0x2E, 0xA1, 0x66, 0x28, 0xD9, 0x24, 0xB2, 0x76, 0x5B, 0xA2, 0x49, 0x6D, 0x8B, 0xD1, 0x25 0x72, 0xF8, 0xF6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xD4, 0xA4, 0x5C, 0xCC, 0x5D, 0x65, 0xB6, 0x92 0x6C, 0x70, 0x48, 0x50, 0xFD, 0xED, 0xB9, 0xDA, 0x5E, 0x15, 0x46, 0x57, 0xA7, 0x8D, 0x9D, 0x84 0x90, 0xD8, 0xAB, 0x00, 0x8C, 0xBC, 0xD3, 0x0A, 0xF7, 0xE4, 0x58, 0x05, 0xB8, 0xB3, 0x45, 0x06 0xD0, 0x2C, 0x1E, 0x8F, 0xCA, 0x3F, 0x0F, 0x02, 0xC1, 0xAF, 0xBD, 0x03, 0x01, 0x13, 0x8A, 0x6B 0x3A, 0x91, 0x11, 0x41, 0x4F, 0x67, 0xDC, 0xEA, 0x97, 0xF2, 0xCF, 0xCE, 0xF0, 0xB4, 0xE6, 0x73 0x96, 0xAC, 0x74, 0x22, 0xE7, 0xAD, 0x35, 0x85, 0xE2, 0xF9, 0x37, 0xE8, 0x1C, 0x75, 0xDF, 0x6E 0x47, 0xF1, 0x1A, 0x71, 0x1D, 0x29, 0xC5, 0x89, 0x6F, 0xB7, 0x62, 0x0E, 0xAA, 0x18, 0xBE, 0x1B 0xFC, 0x56, 0x3E, 0x4B, 0xC6, 0xD2, 0x79, 0x20, 0x9A, 0xDB, 0xC0, 0xFE, 0x78, 0xCD, 0x5A, 0xF4 0x1F, 0xDD, 0xA8, 0x33, 0x88, 0x07, 0xC7, 0x31, 0xB1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xEC, 0x5F 0x60, 0x51, 0x7F, 0xA9, 0x19, 0xB5, 0x4A, 0x0D, 0x2D, 0xE5, 0x7A, 0x9F, 0x93, 0xC9, 0x9C, 0xEF 0xA0, 0xE0, 0x3B, 0x4D, 0xAE, 0x2A, 0xF5, 0xB0, 0xC8, 0xEB, 0xBB, 0x3C, 0x83, 0x53, 0x99, 0x61 0x17, 0x2B, 0x04, 0x7E, 0xBA, 0x77, 0xD6, 0x26, 0xE1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0C, 0x7D
其实这里的重点也就是求字节在GF(2^8)上的乘法逆元
五. 变化点
5.1. 既约多项式
在GF(2)上的8阶既约多项式不仅仅只有一个，这里我列出所有GF(2)上的8阶既约多项式。
x^8 + x^4 + x^3 + x + 1
x^8 + x^4 + x^3 + x^2 + 1
x^8 + x^5 + x^3 + x + 1
x^8 + x^5 + x^3 + x^2 + 1
x^8 + x^5 + x^4 + x^3 + 1
x^8 + x^5 + x^4 + x^3 + x^2 + x + 1
x^8 + x^6 + x^3 + x^2 + 1
x^8 + x^6 + x^4 + x^3 + x^2 + x + 1
x^8 + x^6 + x^5 + x + 1
x^8 + x^6 + x^5 + x^2 + 1
x^8 + x^6 + x^5 + x^3 + 1
x^8 + x^6 + x^5 + x^4 + 1
x^8 + x^6 + x^5 + x^4 + x^2 + x + 1
x^8 + x^6 + x^5 + x^4 + x^3 + x + 1
x^8 + x^7 + x^2 + x + 1
x^8 + x^7 + x^3 + x + 1
x^8 + x^7 + x^3 + x^2 + 1
x^8 + x^7 + x^4 + x^3 + x^2 + x + 1
x^8 + x^7 + x^5 + x + 1
x^8 + x^7 + x^5 + x^3 + 1
x^8 + x^7 + x^5 + x^4 + 1
x^8 + x^7 + x^5 + x^4 + x^3 + x^2 + 1
x^8 + x^7 + x^6 + x + 1
x^8 + x^7 + x^6 + x^3 + x^2 + x + 1
x^8 + x^7 + x^6 + x^4 + x^2 + x + 1
x^8 + x^7 + x^6 + x^4 + x^3 + x^2 + 1
x^8 + x^7 + x^6 + x^5 + x^2 + x + 1
x^8 + x^7 + x^6 + x^5 + x^4 + x + 1
x^8 + x^7 + x^6 + x^5 + x^4 + x^2 + 1
x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + 1
2. 字节变换
我们知道了字节变换最后作为矩阵计算，正反相乘得到的是一个单元矩阵
那么我们也可以换一种变化方式
比如:
正向变化采用
R(b_i) = b_[(i+1) mod 8] ⊕ b_[(i+2) mod 8] ⊕ b_[(i+3) mod 8] ⊕ b_[(i+5) mod 8] ⊕ b_[(i+7) mod 8] ⊕ c_i
c_i = 0x28
根据R(b_i)那么可以得到正向变化矩阵A
0, 1, 1, 1, 0, 1, 0, 1
1, 0, 1, 1, 1, 0, 1, 0
0, 1, 0, 1, 1, 1, 0, 1
1, 0, 1, 0, 1, 1, 1, 0
A = [ 0, 1, 0, 1, 0, 1, 1, 1 ]
1, 0, 1, 0, 1, 0, 1, 1
1, 1, 0, 1, 0, 1, 0, 1
1, 1, 1, 0, 1, 0, 1, 0
设逆向变化为：
逆R(b_i) = ?
d_i = ?
根据逆R(b_i)得到逆向变化矩阵B
由于没有想出好的方法，就遍历了一下..
void GetReverseTransfarmMatrix()
{
PolynomialGF2 polyPositiveSeed = { 0, 1, 1, 1, 0, 1, 0, 1 };
InitByteTransformMatrix(polyPositiveSeed, g_mtxBytePositiveTransformMatrix);
MatrixGF2<BYTE> mtxResult(8, 8, 0);
PolynomialGF2 polyReverseSeed = { 1, 0, 0, 0, 0, 0, 0, 0 };
InitByteTransformMatrix(polyReverseSeed, mtxResult);
MatrixGF2<BYTE> mtxReverseTransformMatrix;
size_t uiPositiveColumnNumber = g_mtxBytePositiveTransformMatrix.GetColumnNumber();
for (size_t cntI = 1; cntI <= 0xFF; cntI++)
{
MatrixGF2<BYTE> mtxTmp(8, 8, 0);
PolynomialGF2 polyTmp = cntI;
polyTmp.PaddingZero(8);
InitByteTransformMatrix(polyTmp, mtxTmp);
if (g_mtxBytePositiveTransformMatrix * mtxTmp == mtxResult)
{
printf("B: \n%s\n", mtxTmp.GetWrittenFormat().c_str());
MatrixGF2<BYTE> mtxPositiveFixed = PolynomialGF2(0x28).GetDequeFormat();
mtxPositiveFixed.PaddingRow(8);
MatrixGF2<BYTE> mtxReverseFixed = mtxTmp * mtxPositiveFixed;
printf("d_i: 0x%2llX",
PolynomialGF2(mtxReverseFixed.Transform2Vector()).ToNumber());
}
}
} //! GetReverseTransfarmMatrix() END求出B
0, 1, 0, 1, 0, 1, 1, 1
1, 0, 1, 0, 1, 0, 1, 1
1, 1, 0, 1, 0, 1, 0, 1
1, 1, 1, 0, 1, 0, 1, 0
B = [ 0, 1, 1, 1, 0, 1, 0, 1 ]
1, 0, 1, 1, 1, 0, 1, 0
0, 1, 0, 1, 1, 1, 0, 1
1, 0, 1, 0, 1, 1, 1, 0
那么，逆R(b_i) = b_[(i+1) mod 8] ⊕ b_[(i+3) mod 8] ⊕ b_[(i+5) mod 8] ⊕ b_[(i+6) mod 8] ⊕ b_[(i+7) mod 8] ⊕ d_i
其中d_i = B * c_i = 0xA0
变化版S盒完整示例：
采用既约多项式使用x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + 1
字节变化采用上面刚刚验证的方式
void InitOtherBox()
{
g_polyModle = { 1, 0, 0, 1, 1, 1, 1, 1, 1 };
PolynomialGF2 polyPositiveSeed = { 0, 1, 1, 1, 0, 1, 0, 1 };
InitByteTransformMatrix(polyPositiveSeed, g_mtxBytePositiveTransformMatrix);
PolynomialGF2 polyReverseSeed = { 0, 1, 0, 1, 0, 1, 1, 1 };
InitByteTransformMatrix(polyReverseSeed, g_mtxByteReverseTransformMatrix);
g_bytPositiveFixed = 0x28;
g_bytReverseFixed = 0xA0;
InitPositiveBox();
InitReverseBox();
printf("Positive box: \n%s\n",
g_mtxPositiveBox.GetWrittenFormat().c_str());
printf("Reverse box: \n%s\n",
g_mtxReverseBox.GetWrittenFormat().c_str());
}结果：
Positive box: 0x28, 0xC2, 0xE8, 0x57, 0x48, 0x24, 0x97, 0xC5, 0x18, 0x8C, 0x9B, 0x72, 0xF7, 0x99, 0xDE, 0xD3 0x85, 0x58, 0x7A, 0x0B, 0x44, 0xD1, 0xB0, 0x47, 0xC7, 0xAE, 0xF0, 0x6D, 0x53, 0xE1, 0x60, 0xB4 0x4B, 0x5C, 0x10, 0x52, 0x01, 0x39, 0xB9, 0x90, 0xAB, 0x00, 0xD4, 0x73, 0x64, 0x32, 0x9F, 0xA1 0x6A, 0x1C, 0x6B, 0x21, 0xF1, 0xEF, 0x3F, 0x67, 0x95, 0xF2, 0x79, 0xE0, 0x0C, 0xD0, 0x66, 0x7F 0x2C, 0xC3, 0x12, 0x5A, 0x34, 0xEB, 0x15, 0xA6, 0xBC, 0x7D, 0xA0, 0xB8, 0x55, 0x49, 0xC1, 0xFB 0xE9, 0x08, 0x3C, 0xE2, 0x56, 0x2F, 0x30, 0x9E, 0x0E, 0xCB, 0x25, 0xE3, 0x46, 0x5D, 0xEC, 0x4C 0x09, 0xBE, 0x87, 0x04, 0x89, 0xD8, 0x19, 0x3D, 0x71, 0x40, 0x7E, 0x5F, 0x16, 0x7B, 0x3A, 0x27 0x43, 0x76, 0x45, 0x8A, 0x35, 0x96, 0xF9, 0x07, 0x8F, 0x0F, 0x54, 0xCF, 0xBA, 0x38, 0x83, 0xCE 0x2A, 0xAC, 0x68, 0xF4, 0x80, 0x31, 0xA4, 0xFE, 0x93, 0xB3, 0x7C, 0xCA, 0xB6, 0x75, 0xDA, 0xA8 0xD7, 0xB1, 0x37, 0xC4, 0x6C, 0x6F, 0xD5, 0x4F, 0x23, 0x14, 0x98, 0xAA, 0xDC, 0x65, 0x74, 0x42 0xC8, 0x41, 0x8D, 0xA5, 0x22, 0xEA, 0x4D, 0xB5, 0x17, 0x02, 0x1E, 0x88, 0x91, 0x33, 0xC6, 0x78 0x3B, 0x2D, 0xD9, 0xFC, 0x1B, 0x9A, 0xCD, 0xE6, 0x1F, 0xED, 0x92, 0x29, 0x4A, 0xFA, 0x1A, 0xEE 0x0D, 0xE7, 0x63, 0x8E, 0xFF, 0x06, 0x3E, 0x1D, 0xF8, 0xAD, 0xE5, 0x36, 0x05, 0x70, 0xA2, 0x69 0x84, 0xBF, 0xA9, 0x8B, 0x03, 0xD6, 0x26, 0x2E, 0x82, 0x62, 0x81, 0xE4, 0x94, 0xA7, 0xAF, 0x5E 0x9D, 0xD2, 0xB2, 0x86, 0x2B, 0x51, 0xCC, 0xDD, 0x13, 0xF5, 0x77, 0x50, 0xC0, 0xB7, 0x0A, 0x59 0x4E, 0xC9, 0xBB, 0x11, 0xA3, 0x6E, 0xDB, 0xF6, 0x61, 0x9C, 0x20, 0xDF, 0xFD, 0xBD, 0x5B, 0xF3 Reverse box: 0x29, 0x24, 0xA9, 0xD4, 0x63, 0xCC, 0xC5, 0x77, 0x51, 0x60, 0xEE, 0x13, 0x3C, 0xC0, 0x58, 0x79 0x22, 0xF3, 0x42, 0xE8, 0x99, 0x46, 0x6C, 0xA8, 0x08, 0x66, 0xBE, 0xB4, 0x31, 0xC7, 0xAA, 0xB8 0xFA, 0x33, 0xA4, 0x98, 0x05, 0x5A, 0xD6, 0x6F, 0x00, 0xBB, 0x80, 0xE4, 0x40, 0xB1, 0xD7, 0x55 0x56, 0x85, 0x2D, 0xAD, 0x44, 0x74, 0xCB, 0x92, 0x7D, 0x25, 0x6E, 0xB0, 0x52, 0x67, 0xC6, 0x36 0x69, 0xA1, 0x9F, 0x70, 0x14, 0x72, 0x5C, 0x17, 0x04, 0x4D, 0xBC, 0x20, 0x5F, 0xA6, 0xF0, 0x97 0xEB, 0xE5, 0x23, 0x1C, 0x7A, 0x4C, 0x54, 0x03, 0x11, 0xEF, 0x43, 0xFE, 0x21, 0x5D, 0xDF, 0x6B 0x1E, 0xF8, 0xD9, 0xC2, 0x2C, 0x9D, 0x3E, 0x37, 0x82, 0xCF, 0x30, 0x32, 0x94, 0x1B, 0xF5, 0x95 0xCD, 0x68, 0x0B, 0x2B, 0x9E, 0x8D, 0x71, 0xEA, 0xAF, 0x3A, 0x12, 0x6D, 0x8A, 0x49, 0x6A, 0x3F 0x84, 0xDA, 0xD8, 0x7E, 0xD0, 0x10, 0xE3, 0x62, 0xAB, 0x64, 0x73, 0xD3, 0x09, 0xA2, 0xC3, 0x78 0x27, 0xAC, 0xBA, 0x88, 0xDC, 0x38, 0x75, 0x06, 0x9A, 0x0D, 0xB5, 0x0A, 0xF9, 0xE0, 0x57, 0x2E 0x4A, 0x2F, 0xCE, 0xF4, 0x86, 0xA3, 0x47, 0xDD, 0x8F, 0xD2, 0x9B, 0x28, 0x81, 0xC9, 0x19, 0xDE 0x16, 0x91, 0xE2, 0x89, 0x1F, 0xA7, 0x8C, 0xED, 0x4B, 0x26, 0x7C, 0xF2, 0x48, 0xFD, 0x61, 0xD1 0xEC, 0x4E, 0x01, 0x41, 0x93, 0x07, 0xAE, 0x18, 0xA0, 0xF1, 0x8B, 0x59, 0xE6, 0xB6, 0x7F, 0x7B 0x3D, 0x15, 0xE1, 0x0F, 0x2A, 0x96, 0xD5, 0x90, 0x65, 0xB2, 0x8E, 0xF6, 0x9C, 0xE7, 0x0E, 0xFB 0x3B, 0x1D, 0x53, 0x5B, 0xDB, 0xCA, 0xB7, 0xC1, 0x02, 0x50, 0xA5, 0x45, 0x5E, 0xB9, 0xBF, 0x35 0x1A, 0x34, 0x39, 0xFF, 0x83, 0xE9, 0xF7, 0x0C, 0xC8, 0x76, 0xBD, 0x4F, 0xB3, 0xFC, 0x87, 0xC4
六. 小结
到这里也算给自己一个总结吧，但战斗还远远没有结束，这还仅仅是S盒。我也知道还有很多没有写出来，比如S盒为了非线性选择了乘法逆，这个非线性度没有展示出来，还有S盒中不会存在’S-box(a) = a‘的情况以及’S-box(a) = a逐位取反‘这种情况的验证..... 希望哪天我回过头来能继续将它们补充完整..
我爱看雪^_^
【忘了补充：那个MatrixGF2用来生成S盒没有问题，但在其他运算还有问题，自己随便写的，用的话慎重....】
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
最后于 2019-8-18 09:22
被菜就一个字编辑
，原因： 修改笔误
，受教了^_^
楼主讲的很详细
，现在想想当时起的标题确实有歧义，有点欠考虑了。以后会多加注意的
