姓名：江家煜 学号：20011210580
转自：https://blog.csdn.net/u011516178/article/details/81221646
【嵌牛导读 】：AES作为一种广为人知的密码算法，S盒变换是其中唯一非线性的部分。既然如此，它又是如何设计以保证密码系统的安全性的呢？事实上，它的设计与描述涉及了数论和有限域的知识，刚接触的同学可能很容易被绕晕，接下来就让我们一起探究AES中S盒变换的原理和代码实现吧。
【嵌牛鼻子】：信息安全 高级加密标准（AES）
【嵌牛提问】：AES中S盒变换的原理是什么？如何利用编程实现？
【嵌牛正文】：
本文对AES的介绍基于《FIPS 197》以及《密码编码学与网络安全–原理和实践》两本教材，感兴趣的同学可以自行查阅。
首先给出《FIPS 197》中对S盒构造的描述步骤:
就这两条。实际上是三个步骤，《密码编码学与网络安全–原理和实践》教材里会讲得更详细些。
以下都按照《密码编码学与网络安全–原理和实践》教材里边的三个步骤进行推导。步骤1、3都比较浅显，即使没有数论和有限域概念，一样可以编程写出来。
1.2 产生S盒初始数组
根据行标号和列标号组合成16X16的二维数组，行标号作为高4bit，列标号作为低4bit;生成代码如下：
for(i=0;i<0x10;i++)
{for(j=0;j<0x10;j++)
{s_box_ary[i][j] = ((i<<4)&0xF0) + (j&(0xF)); } }
代码产生的数组：
1.3 求解字节的逆
本文重点叙述步骤2的推导。
这里边有三个概念：有限域、GF(2^8)、逆。
有限域：我的理解是，有一些元素构成了一个集合，集合中的一个或多个元素，进行某种运算，所得的结果仍然是集合中的元素。 元素，可以是具体的数字，也可以是字母，或是表达式，等等；某种运算，可以是加减乘除，或者逻辑运算，或者求余，或者是这几种运算的组合，等等。 这个定义当然很不严格，但是我觉得对于理解这个S盒推导够用了。
GF(2^8)：GF()是代表一个有限域，2^8=256，是指这个有限域内的元素的个数，即256个。
举个是有限域的集合的例子吧：
GF(7)={0，1，2，3，4，5，6}，它是关于任意两个元素的相加/乘积模7运算的有限域。特点是任意两个元素相加/乘积，对7取余数，这个余数仍然在GF(7)内。
截取《密码编码学与网络安全–原理和实践》中的例子：
此外，这个GF(7)的7叫做阶，特点是阶与域内的元素都互素（互质）。
在计算机中，一个字节是8位，0~255刚好是一个字节所能代表的所有数字，但是呢，GF(256)，256对于0~255内的元素并不是每个都互素（互质），当以251为模时，251~255又不能用，造成浪费，所以不能直接使用上边的计算形式。但是我们还得必须用0~255这256个整数作为一个集合，通过某种运算构成有限域，所有只能把研究重点放在“某种运算”上。可能是为了区分GF(256)，所以用GF(2^8)。
逆：乘法逆元。定义：GF(p)， (a)、(b)、(a-1)都在GF(p)内，其中(a)、(a-1)互为乘法逆元，则有：[(a) X (a-1)] mod p = 1；
第二个步骤，就是 在步骤一得到的数组基础上，对每个元素 在 GF(2^8)有限域上求解出乘法逆元，在原位置替换该元素。
如何求解有限域上的逆元？《密码编码学与网络安全–原理和实践》中从欧几里得算法开始做知识铺垫，到扩展欧几里得算法。我们可以得出求乘法逆元的一个程序上可实现的方法。
d=gcd(a,b)，d是a和b的最大公约数，或者叫最大公因子。求解步骤：
1、定义变量：r0, r1, r2
2、赋初值r0=a;r1=b;
3、求解r0、r1的余数：r3=r0 Mod r1;
4、更新变量：r0=r1;r1=r2;
5、从3开始重复，一直到求解的余数r1是0结束。
6、r0就是要求解的最大公约数。
long gcd(long a, long b)
{
long tmp;
while(b)
{
tmp=a;
a=b;
b=tmp%b;
}
return a;
}
欧几里得算法的关键是gcd(a,b)=gcd(b,(a mod b))；为什么能成立？
可以证明：
当a>b，就有，a=q1 * b + r1，r1 = a - q1 * b;
假设 d=gcd(a,b)，那么d分别是a和b的最大公因子，记作：d|a，d|b，所以：
d|(a-q1 * b)=d|r1
所以有d=gcd(b,r1)=gcd(b, (a mod b));
《密码编码学与网络安全–原理和实践》里边讲解会更详细：
扩展欧几里得算法的计算步骤同欧几里得算法的步骤相似，由一个公式迭代计算，一直到某个条件成立，结束迭代，返回结果。
扩展欧几里得算法用来求解乘法逆元，为什么？
上边已经有了公式：[(a) * (a-1)] mod p = 1；
可以等效变换成：p * x + 1 = (a) * (a-1)
========> - p * x + (a) * (a-1) = 1
与ax+by=1的形式是不是很像？与ax+by=gcd(a,b)=1的形式是不是很像？gcd(a,b)=1,即a、b互素即可。
可以看出，可以运用欧几里得算法的步骤计算乘法逆元，但是怎么计算呢？这点照搬《密码编码学与网络安全–原理和实践》里边的讲解步骤，我觉得不会比他讲得更好了。
总结一下：
1． 初始条件：(R-1) = a; R0=b; (X-1)=1;X0=0;(Y-1)=0;Y0=1;
2． 迭代步骤：
Rn=(Rn-2) Mod (Rn-1)；Qn = [(Rn-2) /(Rn-1)] {(Rn-2) /(Rn-1)的商}；
Xn = (Xn-2) - (Xn-2) ；Yn = (Yn-2) - (Yn-2) 。
3． 终止条件：Rn=1时，计算出来的Yn即是结果。
如果结果为负数，需要加上模值变为正数。
代码如下：
回归到GF(2^8)有限域，需要找到“某种运算”，使GF(2^8)有限域成立。这种运算是多项式除法运算。
多项式如下形式：
我们可以把GF(2^8)有限域内的每一个元素，按照下列方式写成多项式的形式：设 字节a ∈ GF(2^8)，写成二进制的形式a=b7b6b5b4b3b2b1b0，用bn代表a的每一位，其中n是二进制数中的位置；那么，bn当作系数，n作为变量x的指数；可以把一个字节写成：
这种形式。
举例：
0x9A=(b)10011010，写成多项式形式：x^7+x^4+x^3+x。
多项式除法运算，计算规则：
1、遵循代数基本规则中的普通多项式运算规则；
2、系数运算遵循以2为模的加法和乘法运算；（原话是：系数运算以p为模，即遵循有限域Zp上的运算规则）；
3、如果乘法运算的结果是次数大于7(原文：n-1)的多项式，那么必须将其除以某个次数为8(原文：n)的即约多项式m(x)并取余式，对于多项式f(x)，这个余数可表示为：即
r(x) = f(x) mod m(x)。
高级加密标准AES使用有限域GF(2^8)上的运算，其中即约多项式
m(x)=x^8 + x^4 + x^3 + x + 1；
举例：
m(x)=x^8 + x^4 + x^3 + x + 1；
f(x) =x^6 + x^4 + x^2 + x + 1；g(x) =x^7 + x + 1；
f(x) * g(x) = (x^6 + x^4 + x^2 + x + 1) * (x^7 + x + 1)
= x^13 + x^11 + x^9 + x^8 + x^7
+ x^7 + x^5 + x^3 + x^2 + x
+ x^6 + x^4 + x^2 + x + 1
= x^13 + x^11 + x^9 + x^8 + x^6+ x^5 + x^4 + x^3 + 1
r(x) = [f(x) * g(x)] mod m(x) => m(x) * q(x) + r(x) = f(x) * g(x)：
q(x) = x^5 + x^3；r(x) = x^7 + x^6 + 1。
上文已经讲到：扩展欧几里得算法用来求解乘法逆元。
(b-1)*b mod a = 1； => ax+by=1=gcd(a, b)
把a、b用多项式替代，形式如下：
b-1(x) * b(x) mod m(x) = 1 => m(x)v(x) + b(x)w(x) = 1 = gcd(m(x), b(x))
直接引用上边求乘法逆元的步骤，用多项式直接替代数值计算：
重述如下：
1、把带求解的字节变换成多项式形式b(x);
2、初始条件：
(R-1) = m(x)； R0=b(x)；
(v-1)(x)=1； v0(x)=0；
(w-1)(x)=0； w0(x)=1；
3、迭代步骤：
Rn(x)=(Rn-2)(x) Mod (Rn-1)(x)；
Qn(x) = [(Rn-2)(x) / (Rn-1)(x)] 即：{(Rn-2) /(Rn-1)的商}；
vn(x) = (vn-2)(x) - Qn(x)*(vn-2)(x) ；
wn(x) = (wn-2)(x) - Qn(x)*(wn-2) 。
4、终止条件：
Rn(x)=1时，计算出来的wn(x)即是结果多项式。
5、把wn(x)变换回字节。
上述步骤中，需要专门的多项式乘法、多项式除法、多项式求余运算的实现函数。
多项式乘法函数：
多项式除法函数：
多项式的扩展欧几里得算法：
至此，S盒变换的第二步骤实现完成。
根据 扩展欧几里得算法，得到的中间状态的S盒如下：
1.4 S盒字节变换和逆S盒字节变换：
将上述代码整合，便可以得到S盒变换代码：
这样，便可以得到AES的S盒，输出如下：
网友评论