有限域#
域和有限域#
首先给域下一个定义,由于本文不想写得太过复杂,所以可能不是很严格。简单来说,一个域就是定义了加法和乘法的集合,且满足以下条件:
1、加法是封闭的,非零元素乘法是封闭的。
∀a,b∈F:a+b∈F;∀a,b∈F−{0}:a∗b∈F−{0}
2、加法和乘法有单位元和逆元,加法单位元记为0,乘法单位元记为1。
a+0=a,a∗1=a
∀a∈F,∃b∈F:a+b=0;∀a∈F−{0},∃b∈F−{0}:a∗b=1
有了逆元的概念,其实我们也可以定义减法和除法了,减法即+加法逆元,除法即x乘法逆元。
3、加法有交换律、结合律。
a+b=b+a,a+(b+c)=(a+b)+c
4、乘法有交换律、结合律,加法与乘法之间有分配律。
a∗b=b∗a,a∗(b∗c)=(a∗b)∗c,a∗(b+c)=a∗b+a∗c
我们熟知的数域(例如:有理数域Q、实数域R)显然是满足以上条件的,但数域中元素的个数是无限的,如果我们要在有限的元素中定义一个域呢?
先看一个简单的例子,GF(3)即有三个元素0、1、2的有限域,我们如果把加法和乘法定义为模3的加法和乘法,那么就满足域的条件了。
例如:
(1+2)mod3=0
(2∗2)mod3=1
同时也可看出,1的加法逆元是2,2的乘法逆元是2。
实际上,有限域元素的个数是限定的,记为GF(pn),p为质数,n为正整数。即有限域元素的个数必定是质数的正整数幂pn。对于GF(p)的情况,加法和乘法定义就像上面的GF(3)一样,是模p的加法和乘法,就能满足域的条件。但对于GF(pn)的加法和乘法就不一样了。
例如AES算法中用到的GF(28),如果还定义为模256的加法和乘法,会出现(16∗16)mod256=0,这与第1个条件,非零元素的乘法封闭性相悖。那我们如何定义GF(28)的加法和乘法呢?
多项式#
这就要用到多项式了,我们将GF(28)表达为多项式,多项式的加法和乘法就会满足域的定义。例如42的2进制表达为(101010)2,那么42就代表多项式1x5+0x4+1x3+0x2+1x1+0,也就是小于256的数表达为多项式的系数。
假设我们要计算42+12,就把多项式对应项系数相加,系数的加法遵循GF(2)中的加法,即:
(1x5+0x4+1x3+0x2+1x1+0)+(1x3+1x2+0x1+0)=1x5+0x4+0x3+1x2+1x1+0
也就是42+12=(100110)2=38。可以发现,其实GF(28)中的加法,就是两个二进制数的异或运算结果。
对于乘法,两个最高次<8的多项式可能乘出一个最高次>8的多项式(例如x7∗x7=x14),这不是不满足乘法的封闭性了吗?所以,对于GF(28)中的乘法,我们需要模一个不可约的多项式x8+x4+x3+x1+1,这样就能保证乘法的结果也在256的范围内。那么这就牵涉到另一个问题,多项式如何做带余除法呢?参照整数带余除法的定义,我们有:
如果a(X)=q(X)b(X)+r(X),且r(X)的最高次数<b(X)的最高次数,那么称a(X)除以b(X)商q(X)余r(X)。
例如我们要计算GF(28)中的128*128,即(x7∗x7)mod(x8+x4+x3+x1+1):
x8+x4+x3+x+1)x6+x2+xx14x14+x10+x9+x7+x6+x4x10+x9+x7+x6+x4x10+x6+x5+x3+x2x9+x7+x5+x3+x2x9+x5+x4+x2+xx7+x4+x3+x即x14除以x8+x4+x3+x1+1:商x6+x2+x,余x7+x4+x3+x。
将x7+x4+x3+x转换为二进制是(10011010)2即0x9a,也就是0x80*0x80=0x9a。
因此,对于GF(28),我们有了新的加法和乘法定义:对应多项式的加法和mod(x8+x4+x3+x1+1)乘法,其中多项式系数的加法和乘法遵循GF(2)的加法和乘法,即mod 2的加法和乘法。这样的加法和乘法定义,使得它满足域的条件。
AES算法#
AES算法是以块为单位进行的,例如一个128bit的块可以表示为:
000102030405060708090a0b0c0d0e0f我们以128bit的块和密钥加密为例,加密分为加初始轮密钥、10轮循环。每轮循环中,包含S盒变换、行位移、列混合、加轮密钥4个步骤,并且最后一轮循环不再列混合操作,可以记为如下几个步骤:
0、加初始轮密钥K[0]
重复1234循环,9轮:
1、S盒变换
2、行位移
3、列混合
4、加本轮密钥K[i]
再重复124,1轮,即共10轮循环。
对于这些步骤具体的操作如下:
1 S盒变换#
S盒变换遵循以下公式:
y=Ax−1+b
其中
A=1000111111000111111000111111000111111000011111000011111000011111,b=[01100011]T也就是先对原来的值求逆,再左乘变换矩阵A,可以看出A实际上是0xf8的循环移位。然后再加上b,这里的加法仍然是mod 2的加法,也就是与0x63进行异或运算。另外在GF(28)中,0是没有逆元素的,但在这里为了让每个值都在S盒变换后有值,因此这里定义0−1=0,也就是0x00会变换为0x63。这样就保证了每一个字节经过S盒变换变为另一个字节,变换前后的值是一一对应的,因此S盒变换也是可逆的。
由于S盒变换中有求逆的步骤,比较复杂,因此事先生成好S盒变换表,即可根据原值找到S盒变换后的值。同样的,在生成S盒变换表时,同时也生成一个S盒逆变换的表,便于解密过程。
S盒变换表:
0 1 2 3 4 5 6 7 8 9 a b c d e f
0 63 7c 77 7b f2 6b 6f c5 30 01 67 2b fe d7 ab 76
1 ca 82 c9 7d fa 59 47 f0 ad d4 a2 af 9c a4 72 c0
2 b7 fd 93 26 36 3f f7 cc 34 a5 e5 f1 71 d8 31 15
3 04 c7 23 c3 18 96 05 9a 07 12 80 e2 eb 27 b2 75
4 09 83 2c 1a 1b 6e 5a a0 52 3b d6 b3 29 e3 2f 84
5 53 d1 00 ed 20 fc b1 5b 6a cb be 39 4a 4c 58 cf
6 d0 ef aa fb 43 4d 33 85 45 f9 02 7f 50 3c 9f a8
7 51 a3 40 8f 92 9d 38 f5 bc b6 da 21 10 ff f3 d2
8 cd 0c 13 ec 5f 97 44 17 c4 a7 7e 3d 64 5d 19 73
9 60 81 4f dc 22 2a 90 88 46 ee b8 14 de 5e 0b db
a e0 32 3a 0a 49 06 24 5c c2 d3 ac 62 91 95 e4 79
b e7 c8 37 6d 8d d5 4e a9 6c 56 f4 ea 65 7a ae 08
c ba 78 25 2e 1c a6 b4 c6 e8 dd 74 1f 4b bd 8b 8a
d 70 3e b5 66 48 03 f6 0e 61 35 57 b9 86 c1 1d 9e
e e1 f8 98 11 69 d9 8e 94 9b 1e 87 e9 ce 55 28 df
f 8c a1 89 0d bf e6 42 68 41 99 2d 0f b0 54 bb 16
逆变换表:
0 1 2 3 4 5 6 7 8 9 a b c d e f
0 52 09 6a d5 30 36 a5 38 bf 40 a3 9e 81 f3 d7 fb
1 7c e3 39 82 9b 2f ff 87 34 8e 43 44 c4 de e9 cb
2 54 7b 94 32 a6 c2 23 3d ee 4c 95 0b 42 fa c3 4e
3 08 2e a1 66 28 d9 24 b2 76 5b a2 49 6d 8b d1 25
4 72 f8 f6 64 86 68 98 16 d4 a4 5c cc 5d 65 b6 92
5 6c 70 48 50 fd ed b9 da 5e 15 46 57 a7 8d 9d 84
6 90 d8 ab 00 8c bc d3 0a f7 e4 58 05 b8 b3 45 06
7 d0 2c 1e 8f ca 3f 0f 02 c1 af bd 03 01 13 8a 6b
8 3a 91 11 41 4f 67 dc ea 97 f2 cf ce f0 b4 e6 73
9 96 ac 74 22 e7 ad 35 85 e2 f9 37 e8 1c 75 df 6e
a 47 f1 1a 71 1d 29 c5 89 6f b7 62 0e aa 18 be 1b
b fc 56 3e 4b c6 d2 79 20 9a db c0 fe 78 cd 5a f4
c 1f dd a8 33 88 07 c7 31 b1 12 10 59 27 80 ec 5f
d 60 51 7f a9 19 b5 4a 0d 2d e5 7a 9f 93 c9 9c ef
e a0 e0 3b 4d ae 2a f5 b0 c8 eb bb 3c 83 53 99 61
f 17 2b 04 7e ba 77 d6 26 e1 69 14 63 55 21 0c 7d
查表方式:左边每行开头为高位,上边每列开头为低位,例如4b查第一个表得b3,用b3查第二个表得4b。
2 行位移#
行位移可以用下面的矩阵作为例子,即第一行不动,第二行循环左移1个字节,第三行2个,第四行3个。
000102030405060708090a0b0c0d0e0f→03020701060b00050a0f04090e080d0c<<1<<2<<3→00050a0f04090e03080d02070c01060b3 列混合#
列混合是用整个块左乘一个变换矩阵,由于GF(28)中的乘法是可逆的,所以这一步也是可逆的,逆变换左乘一个逆矩阵即可。
列混合:
Y=2113321113211112X逆列混合:
X=e9dbbe9ddbe99dbeY(注意,这里的矩阵相乘运算用到的是GF(28)中的加法和乘法。)
4 加轮密钥#
初始轮加的密钥为K0,即原始密钥,之后每一轮加的密钥由前一轮的密钥变换而来。这一步可以表示为块和密钥相加:
Y=X+Ki
(注意,这里的加法仍然是遵循GF(28)中的加法,即异或。)
密钥的生成算法如下:
设前一轮的密钥表示为:
Ki−1=k0k1k2k3k4k5k6k7k8k9kakbkckdkekf取最后一列,进行循环移位、S盒变换、加Rconi,再与第一列异或得到后一轮密钥的第一列
kckdkekf⟶循环上移kdkekfkc⟶S盒变换S(kd)S(ke)S(kf)S(kc)⟶+RconiS(kd)+RconiS(ke)S(kf)S(kc)⟶+第1列k0+S(kd)+Rconik1+S(ke)k2+S(kf)k3+S(kc)=记为l0l1l2l3其中Rconi=2i−1,算法遵循GF(28)中的乘法,可以得到(均为16进制):
{Rconi}={01,02,04,08,10,20,40,80,1b,36}
之后3列用原来的列和前一列相加得到:
Ki=l0l1l2l3l4l5l6l7l8l9lalblcldlelf=l0l1l2l3k4+l0k5+l1k6+l2k7+l3k8+l4k9+l5ka+l6kb+l7kc+l8kd+l9ke+lakf+lb可以写为一个总的密钥变换公式:
Ki=f(Ki−1)=f(k0k1k2k3k4k5k6k7k8k9kakbkckdkekf)=k0+S(kd)+Rconik1+S(ke)k2+S(kf)k3+S(kc)k4+k0+S(kd)+Rconik5+k1+S(ke)k6+k2+S(kf)k7+k3+S(kc)k8+k4+k0+S(kd)+Rconik9+k5+k1+S(ke)ka+k6+k2+S(kf)kb+k7+k3+S(kc)kc+k4+k0+S(kd)+Rconikd+k9+k5+k1+S(ke)ke+ka+k6+k2+S(kf)kf+kb+k7+k3+S(kc)举个例子#
前面叙述了完整的加密过程,但比较抽象,这里举个简单的例子,设原文为P,加密密钥为K=K0,加密结果为C。
P=3243f6a8885a308d313198a2e0370734,K0=2b7e151628aed2a6abf7158809cf4f3c0、首先加初始轮密钥,也就是计算C=P+K0,例如第一行第一列就是0x32+0x2b=0x19,即异或运算:
C=P+K0=193de3bea0f4e22b9ac68d2ae9f848081、查S盒变换表,对每个字节进行变换,例如0x19查表得0xd4:
C=S(C)=d42711aee0bf98f1b8b45de51e4152302、行位移,第一行不动,后面三行依次循环左移1/2/3个字节:
d42711aee0bf98f1b8b45de51e415230→d4bf5d30e0b452aeb84111f11e2798e53、列混合,左乘变换矩阵,得变换后的矩阵,例如第一行第一列的计算:2*d4+3*bf+5d+30 = b3+da+5d+30 = 04
C=2113321113211112d4bf5d30e0b452aeb84111f11e2798e5=046681e5e0cb199a48f8d37a2806264c4、加轮密钥,首先根据变换公式,生成本轮的密钥K1:
第1列
k0+S(kd)+Rconik1+S(ke)k2+S(kf)k3+S(kc)=2b+S(cf)+017e+S(4f)15+S(3c)16+S(09)=a0fafe17然后依次得第2~4列:
a0fafe1728+a0=88ae+fa=54d2+fe=2ca6+17=b1ab+88=23f7+54=a315+2c=3988+b1=3909+23=2acf+a3=6c4f+39=763c+39=05再将密文加上本轮的密钥:
C=046681e5e0cb199a48f8d37a2806264c+a0fafe1788542cb123a339392a6c7605=a49c7ff2689f352b6b5bea43026a5049然后再重复以上1234步,总共进行9轮,再进行没有3 列混合步骤的第10轮,即得密文:
3925841d02dc09fbdc118597196a0b32图解过程#
画了一张长图涵盖了上述过程
