分组密码之AES算法

AES算法本质上是一种对称分组密码体制,采用代替/置换网络,每轮由三层组成:线性混合层确保多轮之上的高度扩散,非线性层由16个S盒并置起到混淆的作用,密钥加密层将子密钥异或到中间状态。AES是一个迭代分组密码,其分组长度和密钥长度都是可变的,只是为了满足AES的要求才限定处理的分组大小为128位,而密钥长度为128位、192位或256位,相应的迭代轮数N,为10轮、12轮、14轮。AES汇聚了安全性能、效率、可实现性、灵活性等优点。最大的优点是可以给出算法的最佳查分特征的概率,并分析算法抵抗查分密码分析及线性密码分析的能力。

AES算法在整体结构上采用的是Square结构而不是Feistel结构,该结构由4个不同的阶段组成,包括1个混乱和3个代换。

①:字节代换(SubBytes),用一个S盒完成分组中的按字节的代换。

②:行移位代换(ShiftRows),一个简单的置换。

③:列混淆(MixColumns),一个利用在域GF(2^8)上的算术特征的代换。

④:轮密钥加(AddRoundKey),利用当前分组和扩展密钥的一部分进行按位异或(XOR)。

image

AES算法中的加密、解密过程要经过多次数据变换操作,每一次变换操作会产生一个中间结果,称为状态(State),算法的执行过程如下:

①:给定一个明文M,将State初始化为M,并进行AddRoundKey操作,将轮密钥与State异或。

②:对前Nr-1轮中的每一轮,用S盒进行一次SubBytes代替变换,对State做一次ShiftRows行移位操作,再对State做一次MixColumns列混淆操作,然后进行AddRoundKey操作。

③:按照顺序分别进行SubBytes、ShiftRows、AddRoundKey操作。

④:将最后的State中的内容定义为密文C。

AES的解密算法于加密不同,基本运算中除轮密钥加(AddRoundKey)不变之外,其余操作如SubBytes、ShiftRows、MixColumns都要求进行求逆变换。

image

注意最后一轮的轮变换没有列混淆。

明文分组和密钥的组织排列方式: 

image以明文分组(或密钥)为128bits、192bits 、256bits为例组成的阵列:

image 一些相关的的术语定义和表示:

状态(State):密码运算的中间结果称为状态。
State的表示:状态用以字节为基本构成元素的矩阵阵列来表示,该阵列有4行,列数记为Nb。  Nb=分组长度(bits)÷ 32      Nb可以取的值为4,6,8,对应的分组长度为128, 192, 256 bits。
密码密钥(Cipher Key)的表示: Cipher Key类似地用一个4行的矩阵阵列来表示,列数记为Nk。     Nk=密钥长度(bits)÷32      Nk可以取的值为4,6,8,对应的密钥长度为128, 192, 256 bits。

轮数(Round)的不同取值:

image

SubBytes(字节替代)

非线性的字节替代,单独处理每个字节:

求该字节在有限域GF(28)上的乘法逆,”0″被映射为自身,即对于α∈GF(28),求β∈GF(28),

使得α·β=β·α=1mod(x8+x4+x2+x+1)。

对上一步求得的乘法逆作仿射变换

yi=xi + x(i+4)mod8 + x(i+6)mod8 + x(i+7)mod8 + ci

(其中ci是6310即011000112的第i位),用矩阵表示为:

2010103101591769

在下面的程序中就直接用置换表来代替了。

ShiftRows(行移位变换)

在ByteRotation变换中,状态阵列的后3行循环移位不同的偏移量。第1行循环移位C1字节,第2行循环移位C2字节,第3行循环移位C3字节。

2010103102010146

偏移量C1、C2、C3与分组长度Nb有关,如下表所示:

imageMixColumns(列混淆变换)

将状态的列看作是有限域GF(28)上的多项式a(x),与多项式c(x)=’03’x3+’01’x2+’01’x+’02’相乘(模x4+1)。
b(x) = (03·x3 + 01·x2 + 01·x + 02) · a(x) mod(x4 + 1)

令b(x) = c(x) × a(x),写成矩阵形式为:

image

这一运算作用在每一列上:

image数学基础:

1、AES的基础域是有限域 GF(2^8)

一个GF(2)上的8次既约多项式可生成一个 GF(28)
GF(28)的全体元素构成加法交换群,线性空间。
GF(28)的非零元素构成乘法循环群。
GF(28)中的元素有多种表示:
字节: GF(28)={a7,a6,…a1,a0}
多项式形式: GF(28)={a7x7+a6x6+…+a1x+a0}
指数形式:GF(28)*={0, 1… 254}
对数形式:GF(28)*={0, 1… 254}

GF(28)的特征为 2 。

2、 AES的GF(2^8)表示
AES采用的既约模多项式:
         m(x)=x8+x4+x3+x+1     
AES采用GF(28)的多项式元素表示。
  字节B=b7b6b5b4b3b2b1b0可表示成GF(2)上的多项式:
       b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x1+b0 
例:字节57=01010111的多项式表示:
          01010111       x6+x4+x2+x+1

加法:两元素多项式的系数按位模 2加
例2:57+83=D4
(x6+x4+x2+x+1)⊕(x7+x+1)= x7+x6+x4+x2
乘法:两元素多项式相乘,模 m(x)
   例3:57×83=C1
   (x6+x4+x2+x+1)×(x7+x+1)=x7+x6+1 mod m(x)
    乘法单位元:字节01     多项式 1
乘法逆元:
设a(x)的逆元为b(x),则 a(x)b(x)=1 mod m(x) 。
根据Euclid算法求出。

imageAddRoundKey(轮密钥加变换) 

将轮密钥与状态按比特异或。轮密钥是通过Key  Schedule过程从密码密钥中得到的,轮密钥长度等于分组长度。

AES 的密钥调度      

密钥调度包括两个部分:密钥扩展和轮密钥选取.

KeyExpansion(密钥扩展)

密钥bit的总数=分组长度×(轮数Round+1)例如当分组长度为128bits和轮数Round为10时,轮密钥长度为128×(10+1)=1408bits。
将密码密钥扩展成一个扩展密钥。
从扩展密钥中取出轮密钥:第一个轮密钥由扩展密钥的第一个Nb个4字节字,第二个圈密钥由接下来的Nb个4字节字组成,以此类推。

image

 

对于每一组 第一列即i=0,有特殊的处理:

image

将前一列即第n-1组第3列的4个字节循环左移1个字节,

并对每个字节进行字节替代变换SubBytes

将第一行(即第一个字节)与轮常量rc[n]相加 

最后再与前一组该列相加.

轮密钥选取

image

解密的基本运算

AES解密算法与加密不同,基本运算中除了AddRoundKey(轮密钥加)不变外,其余的都需要进行逆变换,即

InvSubBytes(逆字节替代)、InvShiftRows(逆行移位)、InvMixColumns(逆列混淆)

加密过程

先将输入的明文按列序组合成4*4的矩阵,直接与第0组密钥(即输入的密钥)相加(异或),作为轮加密的输入

然后循环10次进行SubBytes、ShiftRows、MixColumns、AddRoundKey运算,最后恢复原序列

需要注意的是最后一轮并不进行MixColumns(列混淆变换)

 

这是一个swf演示地址,看一次就更加清晰了:http://coolshell.cn/wp-content/uploads/2010/10/rijndael_ingles2004.swf

 

贴出代码:

main.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include "aes.h"
#include <iostream>
using namespace std;

void main(){
    unsigned char mw[16] = {0x32, 0x88, 0x31, 0xe0, 0x43, 0x5a, 0x31,              //明文
        0x37,0xf6, 0x30, 0x98, 0x07, 0xa8, 0x8d, 0xa2, 0x34};
    unsigned char key[16] = {0x2b, 0x28, 0xab, 0x09, 0x7e, 0xae, 0xf7,             //密钥
        0xcf,0x15, 0xd2, 0x15, 0x4f, 0x16, 0xa6, 0x88, 0x3c};
    AES aes(key);
    cout<<"明文:";
    for(int i = 0; i < 16; i++){
        printf("%0X ",mw[i]);
    }
    cout<<endl;
    cout<<"密钥:";
    for(i = 0; i < 16; i++){
        printf("%0X ",key[i]);
    }
    cout<<endl;
    aes.Clipher(mw);
    cout<<"加密后:";
    for(i = 0; i < 16; i++){
        printf("%0X ",mw[i]);
    }  
    cout<<endl;
    aes.InvClipher(mw);
    cout<<"解密后:";
    for(i = 0; i < 16; i++){
        printf("%0X ",mw[i]);
    }
    cout<<endl;
}

aes.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class AES{
public:
    AES(unsigned char key[16]);
    unsigned char* Clipher(unsigned char* input);                     //加密过程
    unsigned char* InvClipher(unsigned char* input);                  //解密过程
protected:
private:
    unsigned char static SBOX[256];                                   //置换表
    unsigned char static INVSBOX[256];                                //逆置换表
    unsigned char static RoundKey[240];                               //扩展后的子密钥
    void SubBytes(unsigned char state[][4]);                          //字节替代
    void ShiftRows(unsigned char state[][4]);                         //行移位变换
    void MixColumns(unsigned char state[][4]);                        //列混淆变换
    void AddRoundKey(unsigned char state[][4],int round);             //轮密钥加变换
    void KeyExpansion(unsigned char key[16]);                         //密钥扩展
    void InvSubBytes(unsigned char state[][4]);                       //逆字节替代
    void InvShiftRows(unsigned char state[][4]);                      //逆行移位
    void InvMixColumns(unsigned char state[][4]);                     //逆列混淆
    unsigned char AES::FFmul(unsigned char a, unsigned char b);       //有限域GF(28)上的乘法
};

aes.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
#include "aes.h"

unsigned char AES::SBOX[256] = {
    /*  0    1    2    3    4    5    6    7    8    9    a    b    c    d    e    f */
    0x63,0x7c,0x77,0x7b,0xf2,0x6b,0x6f,0xc5,0x30,0x01,0x67,0x2b,0xfe,0xd7,0xab,0x76, /*0*/
    0xca,0x82,0xc9,0x7d,0xfa,0x59,0x47,0xf0,0xad,0xd4,0xa2,0xaf,0x9c,0xa4,0x72,0xc0, /*1*/
    0xb7,0xfd,0x93,0x26,0x36,0x3f,0xf7,0xcc,0x34,0xa5,0xe5,0xf1,0x71,0xd8,0x31,0x15, /*2*/
    0x04,0xc7,0x23,0xc3,0x18,0x96,0x05,0x9a,0x07,0x12,0x80,0xe2,0xeb,0x27,0xb2,0x75, /*3*/
    0x09,0x83,0x2c,0x1a,0x1b,0x6e,0x5a,0xa0,0x52,0x3b,0xd6,0xb3,0x29,0xe3,0x2f,0x84, /*4*/
    0x53,0xd1,0x00,0xed,0x20,0xfc,0xb1,0x5b,0x6a,0xcb,0xbe,0x39,0x4a,0x4c,0x58,0xcf, /*5*/
    0xd0,0xef,0xaa,0xfb,0x43,0x4d,0x33,0x85,0x45,0xf9,0x02,0x7f,0x50,0x3c,0x9f,0xa8, /*6*/
    0x51,0xa3,0x40,0x8f,0x92,0x9d,0x38,0xf5,0xbc,0xb6,0xda,0x21,0x10,0xff,0xf3,0xd2, /*7*/
    0xcd,0x0c,0x13,0xec,0x5f,0x97,0x44,0x17,0xc4,0xa7,0x7e,0x3d,0x64,0x5d,0x19,0x73, /*8*/
    0x60,0x81,0x4f,0xdc,0x22,0x2a,0x90,0x88,0x46,0xee,0xb8,0x14,0xde,0x5e,0x0b,0xdb, /*9*/
    0xe0,0x32,0x3a,0x0a,0x49,0x06,0x24,0x5c,0xc2,0xd3,0xac,0x62,0x91,0x95,0xe4,0x79, /*a*/
    0xe7,0xc8,0x37,0x6d,0x8d,0xd5,0x4e,0xa9,0x6c,0x56,0xf4,0xea,0x65,0x7a,0xae,0x08, /*b*/
    0xba,0x78,0x25,0x2e,0x1c,0xa6,0xb4,0xc6,0xe8,0xdd,0x74,0x1f,0x4b,0xbd,0x8b,0x8a, /*c*/
    0x70,0x3e,0xb5,0x66,0x48,0x03,0xf6,0x0e,0x61,0x35,0x57,0xb9,0x86,0xc1,0x1d,0x9e, /*d*/
    0xe1,0xf8,0x98,0x11,0x69,0xd9,0x8e,0x94,0x9b,0x1e,0x87,0xe9,0xce,0x55,0x28,0xdf, /*e*/
    0x8c,0xa1,0x89,0x0d,0xbf,0xe6,0x42,0x68,0x41,0x99,0x2d,0x0f,0xb0,0x54,0xbb,0x16  /*f*/
};

unsigned char AES::INVSBOX[256] = {
    /*  0    1    2    3    4    5    6    7    8    9    a    b    c    d    e    f  */
    0x52,0x09,0x6a,0xd5,0x30,0x36,0xa5,0x38,0xbf,0x40,0xa3,0x9e,0x81,0xf3,0xd7,0xfb, /*0*/
    0x7c,0xe3,0x39,0x82,0x9b,0x2f,0xff,0x87,0x34,0x8e,0x43,0x44,0xc4,0xde,0xe9,0xcb, /*1*/
    0x54,0x7b,0x94,0x32,0xa6,0xc2,0x23,0x3d,0xee,0x4c,0x95,0x0b,0x42,0xfa,0xc3,0x4e, /*2*/
    0x08,0x2e,0xa1,0x66,0x28,0xd9,0x24,0xb2,0x76,0x5b,0xa2,0x49,0x6d,0x8b,0xd1,0x25, /*3*/
    0x72,0xf8,0xf6,0x64,0x86,0x68,0x98,0x16,0xd4,0xa4,0x5c,0xcc,0x5d,0x65,0xb6,0x92, /*4*/
    0x6c,0x70,0x48,0x50,0xfd,0xed,0xb9,0xda,0x5e,0x15,0x46,0x57,0xa7,0x8d,0x9d,0x84, /*5*/
    0x90,0xd8,0xab,0x00,0x8c,0xbc,0xd3,0x0a,0xf7,0xe4,0x58,0x05,0xb8,0xb3,0x45,0x06, /*6*/
    0xd0,0x2c,0x1e,0x8f,0xca,0x3f,0x0f,0x02,0xc1,0xaf,0xbd,0x03,0x01,0x13,0x8a,0x6b, /*7*/
    0x3a,0x91,0x11,0x41,0x4f,0x67,0xdc,0xea,0x97,0xf2,0xcf,0xce,0xf0,0xb4,0xe6,0x73, /*8*/
    0x96,0xac,0x74,0x22,0xe7,0xad,0x35,0x85,0xe2,0xf9,0x37,0xe8,0x1c,0x75,0xdf,0x6e, /*9*/
    0x47,0xf1,0x1a,0x71,0x1d,0x29,0xc5,0x89,0x6f,0xb7,0x62,0x0e,0xaa,0x18,0xbe,0x1b, /*a*/
    0xfc,0x56,0x3e,0x4b,0xc6,0xd2,0x79,0x20,0x9a,0xdb,0xc0,0xfe,0x78,0xcd,0x5a,0xf4, /*b*/
    0x1f,0xdd,0xa8,0x33,0x88,0x07,0xc7,0x31,0xb1,0x12,0x10,0x59,0x27,0x80,0xec,0x5f, /*c*/
    0x60,0x51,0x7f,0xa9,0x19,0xb5,0x4a,0x0d,0x2d,0xe5,0x7a,0x9f,0x93,0xc9,0x9c,0xef, /*d*/
    0xa0,0xe0,0x3b,0x4d,0xae,0x2a,0xf5,0xb0,0xc8,0xeb,0xbb,0x3c,0x83,0x53,0x99,0x61, /*e*/
    0x17,0x2b,0x04,0x7e,0xba,0x77,0xd6,0x26,0xe1,0x69,0x14,0x63,0x55,0x21,0x0c,0x7d  /*f*/
};

unsigned char AES::RoundKey[240] = {0x00};

//-------------构造函数,密钥扩展-------------
AES::AES(unsigned char key[16]){
    KeyExpansion(key);
}

//-------------字节替代-------------
void AES::SubBytes(unsigned char state[][4]){
    for(int r = 0; r < 4; r++){
        for(int c = 0; c < 4; c++){
            state[r][c] = SBOX[state[r][c]];
        }
    }
}

//-------------行移位变换-------------
void AES::ShiftRows(unsigned char state[][4]){
    unsigned char temp[4];
    int r,c;
    for(r = 1; r < 4; r++){
        for(c = 0; c < 4; c++){
            temp[c] = state[r][(r+c)%4];
        }
        for(c = 0; c < 4; c++){
            state[r][c] = temp[c];
        }
    }
}

//-------------列混淆变换-------------
void AES::MixColumns(unsigned char state[][4]){
    unsigned char t[4];
    int r,c;
    for(c=0; c< 4; c++){
        for(r=0; r<4; r++){
            t[r] = state[r][c];
        }
        for(r=0; r<4; r++){
            state[r][c] = FFmul(0x02, t[r])           // 在GF(256)中,加法就是异或运算
                ^ FFmul(0x03, t[(r+1)%4])
                ^ FFmul(0x01, t[(r+2)%4])
                ^ FFmul(0x01, t[(r+3)%4]);
        }
    }
}

//-------------轮密钥加变换-------------
void AES::AddRoundKey(unsigned char state[][4],int round){
    for(int c = 0; c < 4; c++){
        for(int r = 0; r < 4; r++){
            state[r][c] ^= RoundKey[round * 4 * 4 + c * 4 + r];
        }
    }
}

//-------------有限域GF(28)上的乘法-------------
unsigned char AES::FFmul(unsigned char a, unsigned char b){
    unsigned char bw[4];
    unsigned char res=0;
    int i;
    bw[0] = b;                  //b[0] b[1] b[2] b[4]
    for(i=1; i<4; i++){         //0x01 0x02 0x04 0x08
        bw[i] = bw[i-1]<<1;
        if(bw[i-1]&0x80){                      
            bw[i]^=0x1b;
        }
    }
    for(i=0; i<4; i++){
        if((a>>i)&0x01){                      
            res ^= bw[i];
        }
    }
    return res;
}

//-------------密钥扩展-------------
void AES::KeyExpansion(unsigned char key[16]){
    unsigned char temp[4],swap;
    unsigned char Rcon[] = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36};  
    //第一轮密钥就是原始密钥
    int i,j;
    for(i = 0; i < 4; i++){
        for(j = 0; j < 4; j++){
            RoundKey[i*4+j] = key[i*4+j];
        }
    }
   
    //其他 密钥均来源于上轮密钥
    while(i < 44){
        for(j = 0; j < 4; j++){
            temp[j] = RoundKey[(i-1)*4+j];              //取轮密钥最后一列
        }
        if(i%4==0){
            //32位字中4字节循环左移一次
            swap = temp[0];
            temp[0] = temp[1];
            temp[1] = temp[2];
            temp[2] = temp[3];
            temp[3] = swap;

            //S盒转换
            for(int k = 0; k < 4; k++){
                temp[k] = SBOX[temp[k]];
            }

            //与Rcon异或
            temp[0] = temp[0] ^ Rcon[i/4-1];
        }
        for (int k = 0; k < 4; k++){
            RoundKey[i*4+k] = RoundKey[(i-4)*4+k] ^ temp[k];
        }  
        i++;
    }  
}

//-------------逆字节替代-------------
void AES::InvSubBytes(unsigned char state[][4]){
    for(int r = 0; r < 4; r++){
        for(int c = 0; c < 4;c++){
            state[r][c] = INVSBOX[state[r][c]];
        }
    }
}

//-------------逆行移位-------------
void AES::InvShiftRows(unsigned char state[][4]){
    unsigned char temp[4];
    int r,c;
    for(r = 1; r < 4; r++){
        for(c = 0;c < 4; c++){
            temp[c] = state[r][(c-r+4)%4];
        }
        for(c = 0; c < 4; c++){
            state[r][c] = temp[c];
        }
    }
}

//-------------逆列混淆-------------
void AES::InvMixColumns(unsigned char state[][4]){
    unsigned char temp[4];
    int r,c;
    for(c = 0; c < 4; c++){
        for(r = 0;r < 4; r++){
            temp[r] = state[r][c];
        }
        for(r = 0; r < 4; r++){
            state[r][c] = FFmul(0x0e, temp[r])
                        ^ FFmul(0x0b, temp[(r+1)%4])
                        ^ FFmul(0x0d, temp[(r+2)%4])
                        ^ FFmul(0x09, temp[(r+3)%4]);
        }
    }
}

//-------------加密过程-------------
unsigned char* AES::Clipher(unsigned char* input){
    unsigned char state[4][4];
    int i,r,c;

    for(r = 0; r < 4; r++){
        for(c = 0; c< 4; c++){
            state[r][c] = input[c*4+r];
        }
    }

    AddRoundKey(state,0);

    for(i = 1; i <= 10; i++){
        SubBytes(state);
        ShiftRows(state);
        if(i!=10)MixColumns(state);
        AddRoundKey(state,i);
    }

    for(r = 0; r < 4; r++){
        for(c = 0; c < 4; c++){
            input[c*4+r] = state[r][c];
        }
    }

    return input;
}

//-------------解密过程-------------
unsigned char* AES::InvClipher(unsigned char* input){
    unsigned char state[4][4];
    int i,r,c;

    for(r = 0; r < 4; r++){
        for(c = 0; c< 4; c++){
            state[r][c] = input[c*4+r];
        }
    }

    AddRoundKey(state,10);

    for(i = 9; i >= 0; i--){
        InvShiftRows(state);
        InvSubBytes(state);
        AddRoundKey(state,i);
        if(i)InvMixColumns(state);
    }

    for(r = 0; r < 4; r++){
        for(c = 0; c< 4; c++){
            input[c*4+r] = state[r][c];
        }
    }

    return input;
}

以上为网上资料、PPT和个人总结。

本文链接:http://www.blogfshare.com/aes-rijndael.html

2条评论

  1. Valder

    你好,请问一下,为什么程序里面是固定的128长度的密钥,有可供选择密钥长度的代码吗?(192,256也能选择输入)

    回复

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>