密码学基础学习总结-06

 

密码学基础学习总结-06说好不当就不当,继续填坑:S盒AES对比前面的DES的S盒来说,没那么玄学,但是其实设计的很巧妙,我这种憨憨肯定不能说出来为什么要这么设计,但是还是能算的,下面就来介绍这个S盒是怎么计算出来的。数学上的一点东西首先,多项式可以用二进制表示: ...

密码学基础学习总结-06

说好不当就不当,继续填坑:

S盒

AES对比前面的DES的S盒来说,没那么玄学,但是其实设计的很巧妙,我这种憨憨肯定不能说出来为什么要这么设计,但是还是能算的,下面就来介绍这个S盒是怎么计算出来的。

数学上的一点东西

首先,多项式可以用二进制表示:

1 0 0 0 1 1 0 1 1

那么$G(2^8)$域上的多项式相乘,对一个不可约不等式$m(x) = x^8 + x^4 + x^3 + x + 1$取余,这样就得到了一个有限域,求解S Box分为两步:

1.求$GF(2^8)$有限域内各元素的乘法逆元.(运用扩展欧几里得算法)

2.用第1步的结果做仿射变换(Affine Transformation)

首先来看求多项式的乘法逆元,利用扩展欧几里得算法,如要计算$(x^6+x^4+x+1)^{-1}mod(x^8+x^4+x^3+x+1)$,也就是要计算,这里的就是一个逆元。

有下面的表格(感觉这种算法适合手算):

R Q S T
1 0001 1011   0000 0001 0000 0000
0101 0011 0000 0101 0000 0000 0000 0001
0000 0100 0001 0100 0000 0001 0000 0101
0000 0011 0000 0010 0001 0100 0100 0101
0000 0010 0000 0001 0010 1001 1000 1111
0000 0001   0011 1101 1100 1010

最后计算得到的结果就是1100,1010也就是$x^7 + x^6 + x^3 + x$,得到了这个乘法逆元,当然对于这个表格的计算,找一组整数来说明,如需要计算,我们有答案,答案就是67:

R Q S T
75   1 0
28 2 0 1
19 1 1 -2
9 2 -1 3
1   3 -8

先写R,Q列,已经可以看出是一个除法了,例如75/28,上2余19,2放在Q,19放在R,28/19上1余9,9放在R,1放在Q,这样继续下去,算好RQ后,在S,T的前两排都是一样的1,0;0,1。放好之后,其实计算方法都是下一排的值都是向前数两排的数减去上一排的Q值乘本列值,举个例子,如S列的第三个数④ 1是由①-②*③:1-2*0=1计算得到的,T列的⑤ -2 是又⑦-②*⑥:0-2*1=-2计算得到的,这样反复计算下去,直到R列最后的值为1,那么T列最后的那个值这里是-8也就是答案,-8不好,75-8=67,就是答案了,这样就可以得到一种计算的方法(希望能看懂)。

例子

下面是求解过程,这里这里以第1列第0元素{10}为例 

1: 求{10}在有限域$GF(2^8)$上的乘法逆元{10}用多项式表示为: $x^4$

由扩展欧几里得算法:

$d$ $X_1$ $X_2$ $X_3$ $Y1$ $Y_2$ $Y_3$
  $1$ $0$ $ x^8+x^4+x^3+x+1$ $0$ $1$ $x^4$
$x^4 + 1$ $0$ $1$ $x^4$ $1$ $X^4+1$ $x^3 +x+1$
$x$ $1$ $x^4 + 1$ $x^3 + x + 1$ $x$ $x ^ 5 + x + 1$ $x^2 + x$
$x+1$ $x$ $x^5+x+1$ $x^2+x$ $x^2 + x + 1$ $x^6 + x^5+x^4+x^2$ $1$

$Y_2=x^6+ x^5 + x^4+ x^2$  即{74},是{10}在$GF(2^8)$有限域上的逆元

2: {74}做仿射变换

$B={74}=01110100 = b7b6b5b4b3b2b1b0$

$C={63}=01100011=c7c6c5c4c3c2c1c0$

$B’=b’_7b’_6b’_5b’_4b’_3b’_2b’_1b’_0$

由仿射变换定义: 即{74}经仿射变换,结果为{ca}

因此,在SBox中,第1行第0列元素的对应值为{ca}。其他元素也可相继求出。规定 {00}映射到其本身。

注:有限域的仿射变换

以下等式表示了有限域中的仿射变换:

此处[M]为矩阵 且 {v} 为向量 :

此处 [M] 为 矩阵且 {v} 为 向量

这样我们就得到了S盒的计算方法,这矩阵维基百科也不好复制,好累。这个S盒应该是不变的,所以在使用AES的时候,大可不必将这些东西都计算一遍,存成表就可以了。

下一篇文章分析密钥与工作模式的问题。