aes
更新时间:2023-12-30 01:28:01 阅读量: 教育文库 文档下载
高级加密标准(AES)
目 录
1.引言 ....................................................................................................... 4 2.定义 ....................................................................................................... 4
2.1 术语和缩写词表.............................................................................................. 4
2.2 算法参数、符号和函数.................................................................................. 5
3.符号和惯例........................................................................................... 6
3.1 输入和输出...................................................................................................... 6
3.2 字节(Bytes) ...................................................................................................... 6 3.3 字节数组.......................................................................................................... 7 3.4 状态(State) ....................................................................................................... 8 3.5 将状态看作列数组.......................................................................................... 9
4.数学基础............................................................................................... 9
4.1 加法.................................................................................................................. 9
4.2 乘法.................................................................................................................. 9
4.2.1 乘x ........................................................................................................................ 10
4.3 系数在GF(28)中的多项式 ........................................................................... 10
5.算法说明............................................................................................. 12
5.1 加密................................................................................................................ 13
5.1.1 字节替代(SubBytes( ))变换 ................................................................................. 13 5.1.2 行移位(ShiftRows( ))变换 .................................................................................... 15 5.1.3 列混合(MixColumns( ))变换 ............................................................................... 16 5.1.4 轮密钥加(AddRoundKey( ))变换 ........................................................................ 16
5.2 密钥扩展........................................................................................................ 17 5.3 解密................................................................................................................ 18
5.3.1 逆行移位(InvShiftRows( ))变换 .......................................................................... 19 5.3.2 逆字节替代(InvSubBytes( ))变换 ........................................................................ 20 5.3.3 逆列混合(InvMixColumns( ))变换 ...................................................................... 20 5.3.4 轮密钥加(InvMixColumns( ))变换的逆变换 ...................................................... 21 5.3.5 等价的解密变换 ................................................................................................... 21
6.实现方面的问题 ................................................................................ 22
6.1 密钥长度要求................................................................................................ 22
6.2 密钥限制........................................................................................................ 22 6.3 密钥长度,分组大小和轮数的参数化........................................................ 23 6.4 针对不同平台的实现建议............................................................................ 23
图表目录
图表 1 比特类型的16进制表示 ................................................................................................. 7 图表 2 字节和比特编号 ............................................................................................................... 8 图表 3 状态矩阵、输入和输出 ................................................................................................... 8 图表 4 Key-Block-Round 组合 ................................................................................................. 12 图表 5 加密算法伪代码 ............................................................................................................. 13 图表 6 SubBytes():作用在状态的单个字节上 .................................................................... 14 图表 7 S盒:字节xy(16进制格式)的替代值 .................................................................... 15 图表 8 ShiftRows()在状态的后三行上循环移位 ................................................................ 15 图表 9 MixColumns()在状态的列上运算 ............................................................................ 16 图表 10 AddRoundKey() 将密钥编排得到的字异或到状态的每一列上 ......................... 17 图表 11 密钥扩展伪代码 ........................................................................................................... 18 图表 12 解密算法的伪代码 ....................................................................................................... 19 图表 13 InvShiftRows()在状态的后三行上循环移位 ......................................................... 20 图表 14 S盒的逆:字节xy的替代值(16进制格式) ......................................................... 20 图表 15 等价解密算法的伪代码 ............................................................................................... 22
1.引言
该标准详细说明了Rijndael算法([3]和[4]),一个对称分组密码算法。可以处理128 bits数据分组,使用的密钥长为128,192和256 bits。Rijndael的设计还可以允许处理其它的分组长度和密钥长度,然而该标准中没有采用。 在本标准的其余部分,本文说明的算法均被称为“AES算法”。如上所述,该算法可以使用3种不同的密钥长度,分别称为“AES-128”、“AES-192”、“AES-256”。 该说明包括下列部分: 2.术语定义,缩写词,算法参数、符号和函数; 3.算法说明中使用的符号和惯例,包括bits,bytes,words的排序和编号方式; 4.对理解算法有帮助的数学工具; 5.算法说明,包括密钥扩展、加密和解密程序; 6.实现方面,如密钥长度支持、密钥限制和其它的分组/密钥/轮大小。 该标准以几个附录做为结尾,包括密钥扩展和加密的每一步的示例、加密和解密的示例向量以及参考文献列表(本翻译略去,详见Fips-197文档)。
2.定义
2.1 术语和缩写词表
下面是文中经常出现的术语: AES Affine Transformation Array Bit Block
Byte
Cipher
Cipher Key
高级加密标准
仿射变换,由一个线性变换和一个向量加变换复合而成 包含一定个数的相同实体的集合(如字节数组)。 一个二进制数(比特),0或1。
一个比特序列,如输入、输出、状态和轮密钥。该序列的长度即是其包含的比特个数。分组也可以解释为字节数组。 字节,一个8比特序列。
使用密钥将明文变换为密文的一系列变换。
密码所使用的秘密密钥,在密钥扩展程序中用来生成一系列轮密钥;这些轮密钥可以表示成以字节为元素的矩阵形式,包含4行Nk列。
Ciphertext
Inverse Cipher
Key Expansion
Plaintext
Rijndael
Round Key State
S-box
Word
加密算法得到的输出或解密算法的输入。 使用密钥将密文变换为明文的一系列变换。 密钥扩展算法:将秘密密钥扩展为一系列轮子密钥。 输入到加密算法的数据或从解密算法得到的输出。
该高级加密标准(AES)中描述的密码算法的名字。 秘密密钥经过密钥扩展算法得到的一系列子密钥;它们将被应用到加密和解密中的状态上。
加密算法的中间结果,可以表示为字节的矩阵数组,有4行Nb列。
一个非线性替代表: 在字节替代变换和密钥扩展程序中用于执行字节替变换。
一个32比特的比特串,也可以看作包含4个字节的数组。
2.2 算法参数、符号和函数
下列算法参数、符号和函数将贯穿于该标准始终:
AddRoundKey() 加密和解密中使用的变换,将一个轮密钥异或到状态上。轮
密钥的长度等于状态的大小(即对于Nb=4,轮密钥长度等于128bits/16bytes)。
InvMixColumns() 解密中使用的变换,MixColumns()的逆变换。 InvShiftRows() 解密中使用的变换,ShiftRows()的逆变换。 InvSubBytes() 解密中使用的变换,SubBytes()的逆变换。 K 密码所使用的秘密密钥
MixColumns() 加密中使用的变换,以状态的每一列作为输入,混合每一列
的数据(彼此独立的)得到新的列。
Nb 状态包含的列(32-bit字)的个数。对于AES,Nb=4 (参见6.3.)
Nk 密钥包含的32-bit字的个数。对于该标准,Nk=4,6或8。(参
见6.3.)
Nr
Rcon[]
RotWord()
ShiftRows()
SubBytes()
SubWord()
XOR
轮数,是Nk和Nb(固定的)的函数。对于该标准,Nr=10,12或14。(参见6.3.)
密钥扩展算法中用到的轮常数。
密钥扩展算法中使用的函数,对4-byte字进行循环移位。 加密中使用的变换,将状态的最后3行循环移动不同的位移量。
加密中使用的变换,利用一个非线性字节替代表(S盒),独立地对状态的每个字节进行操作。
密钥扩展算法中使用的函数,它以4-byte字作为输入,对于4字节中的每一字节分别应用S盒,得到一个输出字。
异或运算 异或运算
4
?
?
两个多项式(每一个的度(degree)均小于4)相乘再模x?1。 有限域上的乘法
?
3.符号和惯例
3.1 输入和输出
AES算法的输入和输出均为一个长度为128的比特串(值为0或1)。这些序列也可以称为分组(blocks),其中含有的位(bits)数也称为分组长度。AES算法的密钥是128,192或256 比特的序列。本标准中不允许其它的输入、输出长度和密钥长度。 序列中比特的编号从0开始,至序列长度(分组长度或密钥长度)减1。将该比特的编号i称为其索引。根据分组长度和密钥长度决定其值属于下列范围中的哪一个:0?i<128, 0?i<192或0?i<256。
3.2 字节(Bytes)
AES算法中基本的运算单位是字节(byte),即视为一个整体的8比特序列。3.1节中描述的输入、输出和密钥比特序列将以字节为单位进行运算,将这些序列分成8个连续比特的组
形成字节数组(参见3.3)。对于记为a的输入、输出或密钥,数组中的字节可以用如下两种形式表示:an或a[n]。n可以属于如下范围:
Key length=128 bits, 0?n?16 Block length=128 bits, 0?n?16 Key length=192 bits, 0?n?24 Key length=256 bits, 0?n?32
AES算法中的所有字节都可以表示成夹在大括号中间的值为0或1的比特联成的串,
顺序如下{b7,b6,b5,b4,b3,b2,b1,b0}。这些字节可以看作以多项式表示的有限域上的元素:b7x+b6x+b5x+b4x+b3x+b2x+b1x+b0=657654321?bxi=0i7i (3.1)
例如,{01100011}表示有限域上的元素x?x?x?1。
也可以方便的用16进制符号来表示字节值,将每4比特表示成如图1所示的一个符号。
Bit Pattern Character 0000 0001 0010 0011
0 1 2 3 Bit Pattern 0000 0001 0010 0011 0000 0001 0010 0011
图 1 16进制
Character 4 5 6 7 c d e f Bit Pattern Character 0000 0001 0010 0011 8 9 a b Bit Pattern Character 因此,元素{01100011}可以表示为{63},代表较高位4比特的符号仍在左边。 一些有限域运算将包括8-bit字节左侧的一个比特(b8)。 当该比特出现时,它将立即以{01}的形式出现在8-bit字节前;例如,一个9-bit序列将表示为{01}{1b}。
3.3 字节数组
字节数组将表示为如下形式:
a0a1a2...a15
128-bit输入序列划分成字节时,字节和字节内的比特排序按照如下方式:
input0input1input2...input126input127 a0?{input0,input1,...,input7};
a1={input8,input9,...,input15};
?
? ?
a15={input120,input121,...,input127}.
该形式可以扩展到更长的序列(如192-和256-bit密钥),一般的有:
an={input8n,input8n+1,...,input8n+7}.
(3.2)
结合第3.2节和第3.3节,图2表示了字节中的每一比特如何编号。
图 2 字节和比特编号
3.4 状态(State)
AES算法的运算都是在一个称为状态的二维字节数组上进行。一个状态由四行组成,每一行包括Nb个字节,Nb等于分组长度除以32。用s表示一个状态矩阵,每一个字节的位置由行号r (范围是0?r4)和列号c (范围是0?cNb)唯一确定,记为sr,c或s[r,c]。在该标准中Nb=4,即0?c4(参见6.3节)。
如第5节所示,在加密和解密的初始阶段将输入字节数组in0,in1,...,in15复制到如图3
所示的状态矩阵中。加密或解密的运算都在该状态矩阵上进行,最后的结果将被复制到输出字节数组out0,out1,...,out15。
输入字节
状态矩阵
输出字节
图 3 状态矩阵、输入和输出
在加密和解密的初始阶段,输入数组in按照下述规则复制到状态矩阵中:
s[r,c]=in[r+4c] for 0?r4 且 0?cNb (3.3) 在加密和解密的结束阶段,状态矩阵将按照下述规则被复制到输出数组out中:
out[r+4c]= s[r,c] for 0?r4 且 0?cNb (3.4)
3.5 将状态看作列数组
状态矩阵中每一列的四个字节可以看作一个32-bit字,行号r可以作为每一个字中四个
字节的索引。因此状态可以看作32-bit字(列),w0...w3的一维数组,列号c是该数组的索引。因此对于图3中的例子,该状态可以看作4个字组成的数组,如下所示:
w0=s0,0s1,0s2,0s3,0
w2=s0,2s1,2s2,2s3,2 w3?s0,3s1,3s2,3s3,3
(3.5)
w1?s0,1s1,1s2,1s3,1
4.数学基础
AES算法中的所有字节都将按照3.2节的记号表示有限域中的元素。有限域元素可以进行加法和乘法运算,但是这些运算不同于代数中使用的运算。下面将介绍一些第5章节要用到的基本数学概念。
4.1 加法
有限域中两个元素的加法定义为其多项式表示的相应系数的“加法”。此处加法是异或运算(记为?),即模2加,1?1=0,1?0=1,0?0=0。因此,多项式减法与多项式加法的规则相同。 有限域元素的加法也可以表示成字节中相应比特的模2加。对于两个字节{a7a6a5a4a3a2a1a0}和{b7b6b5b4b3b2b1b0},其和为{c7c6c5c4c3c2c1c0},
ci?ai?bi(即c7?a7?b7,c6?a6?b6,…, c0?a0?b0)。
例如,下述表达式彼此相等:
(x6+ x4+ x2+ x+1)+(x7+ x+1)= x7+x6+ x4+ x2 {01010111}?{10000011}={11010100} {57}?{83}={d4}
(多项式记法);
(二进制记法); {十六进制记法}。
4.2 乘法
在多项式表示中,有限域GF(28)上的乘法(记为?)定义为多项式的乘积模一个次数为8的不可约多项式:
m(x)?x8?x4?x3?x?1
用十六进制表示该多项式为{01}{1b}。 例如,{57}?{83}={c1},因为
(4.1)
(x6+ x4+ x2+ x+1)(x7+ x+1)
= x13+ x11+ x9+ x8+ x7+x7+ x5+ x3+ x2+ x+x6+ x4+ x2+ x+1 = x13+ x11+ x9+x8+x6+x5+x4+x3+1 而x13+ x11+ x9+x8+x6+x5+x4+x3+1 modulo (x8+x4+x3+x+1) = x7+ x6+1
模m(x)确保了所得结果是次数小于8的二元多项式,因此可以用一个字节表示。不像加法,乘法在相应的字节级别并没有简单运算。 上述定义的乘法具有结合性,元素{01}是乘法单位元。对任意次数小于8的非零二元多项式b(x),其乘法逆元记为b-1(x),可通过下述方法找到:使用扩展欧几里德算法计算多项式a(x)和c(x)使得
b(x)a(x)+m(x)c(x)=1 (4.2)
因此a(x)?b(x) mod m(x)=1意味着 b-1(x)=a(x) mod m(x). (4.3) 而且,对该域上的任意a(x),b(x)和c(x)均有下式成立 a(x)?(b(x)+c(x))=a(x)?b(x)+a(x)?c(x) 由此可见,由所有256个可能的字节值组成的集合,使用异或作为加法以及上述定义的乘法运算,构成有限域GF(28)。
4.2.1 乘x
用多项式x乘以等式(3.1)中定义的二元多项式将得到
b7x8nb6x7nb5x8nb4x8nb3x4nb2x3nb1x2nb0x
(4.4)
由等式(4.1)的定义知,将上述结果模m(x)即可得到x?b(x)的结果。如果b7 = 0,则该结果已经是模运算后的形式。如果b7 = 1,则模运算需要异或多项式m(x)完成。乘x (即{00000010}或{02})可通过字节级别的左移和与{1b}进行有条件的按位异或来实现。将该操作记为xtime( )。x的高次幂的乘法可以通过重复应用xtime( )实现。通过将中间结果相加,可以实现任意常数的乘法。
例如,{57}?{13}={fe} 因为 {57}?{02}=xtime({57})={ae} {57}?{04}=xtime({ae})={47} {57}?{08}=xtime({47})={8e} {57}?{10}=xtime({8e})={07} 因此 {57}?{13}={57}?({01}?{02}?{10}) ={57}?{ae}?{07} ={fe}
4.3 系数在GF(28)中的多项式
考虑含有4个项、且系数为有限域元素的多项式,即
a(x)=a3x3+a2x2+a1x+a0
(4.5)
它可以表示为如下形式[a0,a1,a2,a3]的字(word)。注意本节中的多项式与有限域元素定义中使用的多项式操作起来是不同的,即使这两类多项式均使用相同的变量x。该节中的系数本身就是有限域元素,即字节(bytes)而不是比特(bits)。同时,该4项多项式的乘法使用了一个不同的模多项式,将在下面定义。 为说明加法和乘法运算,令
b(x)?b3x3?b2x2?b1x?b0
(4.6)
为另一个4项多项式。加法是对x相应次数项的有限域系数进行相加运算。该加法对应于相应字节间的异或运算。换句话说,即整个字值的异或。 因此,使用等式(4.5)和(4.6),
a(x)+b(x)?(a3?b3)x3?(a2?b2)x2?(a1?b1)x?(a0?b0)
(4.7)
乘法要用两步完成。第一步,对多项式相乘的结果c(x)?a(x)?b(x)进行代数扩展:
c(x)?c6x6?c5x5?c4x4?c3x3?c2x2?c1x?c0
(4.8)
其中
c0?a0?b0
c4?a3?b1?a2?b2?a1?b3 c5?a3?b2?a2?b3
c1?a1?b0?a0?b1
c2?a2?b0?a1?b1?a0?b2 c6?a3?b3
(4.9)
c3?a3?b0?a2?b1?a1?b2?a0?b3
所得结果c(x)并没有表示为一个4 – 字节的字。因此,乘法的第二步是模一个4次多项式来化简c(x),使得结果化简为一个次数小于4的多项式。在AES算法中,这一模多项式取为
x4?1,由于
xj
mod (x4+1)=xj mod 4
(4.10)
则a(x)和b(x)取模的乘积记为a(x)?b(x),表示为下述的4项多项式d(x),即
d(x)?d3x3?d2x2?d1x?d0
(4.11)
其中
d0=a0放b0d1=a1放b0d2=a2放b0a3放b1a0放b1a1放b1a2放b2a3放b2a0放b2a1 b3 a2 b3 a3 b3
(4.12)
d3?a3?b0?a2?b1?a1?b2?a0?b3
当a(x)是一个固定多项式时,等式(4.11)中定义的运算可以写成矩阵形式,如:
?d0??a0?d??a?1???1?d2??a2????d3??a3a3a0a1a2a2a3a0a1a1??b0??b?a2???1? a3??b2????a0??b3? (4.13)
由于x?1不是GF(28)上的不可约多项式,因此被一个固定的4次多项式相乘的乘法不一定可逆。然而,在AES算法中选择了一个固定的4项多项式的乘法,它按照乘法运算有逆元(见5.1.3节和5.3.3节):
4a(x)?{03}x3?{01}x2?{01}x?{02} a?1(x)?{0b}x3?{0d}x2?{09}x?{0e}
(4.14) (4.15)
AES算法中用到的另一个多项式(见5.2节中的RotWord( )函数)为
a0?a1?a2?{00},a3?{01},即多项式x3。通过对上述等式(4.13)的观察,可以发现
其效果是将输入字中的字节循环移位来得到输出字。即?b0,b1,b2,b3?将变换为
?b1,b2,b3,b0?。
5.算法说明
对于AES算法,输入分组、输出分组、状态长度均为128比特。Nb=4 ,该值反应了
状态中32-bit字的个数(列数)。 对于AES算法,密钥K的长度是128、192或256 bits。密钥长度表示为Nk=4、6或8,反应了密钥中32-bit字的个数(列数)。 对于AES算法,算法的轮数依赖于密钥长度。将轮数表示为Nr,当Nk=4时Nr=10;当Nk=6时Nr=12;当Nk=8时Nr=14。 符合该标准的一切密钥长度 - 分组长度 - 轮数的组合如图4所示。 与密钥长度、分组大小和轮数有关的实现方面的问题见6.3节。 密钥长度 (Nk words) AES-128 AES-192 AES-256 4 6 8
分组大小 (Nb words) 4 4 4 轮数 (Nr) 10 12 14 图 4 Key-Block-Round 组合
对于加密和解密变换,AES算法使用的轮函数由4个不同的以字节为基本单位的变换复合而成:1)字节替代,利用一个替代表(即S盒),2)将状态矩阵的每一行循环移位不同的位移量,3)将状态矩阵中每一列的数据进行混合,4)将轮密钥加到状态上。这些变换(及其逆变换)将在5.1.1-5.1.4和5.3.1-5.3.4节描述。 加密和解密分别在5.1节和5.3节描述,密钥扩展算法在5.2节描述。
5.1 加密
加密开始时,使用4.3节描述的惯例将输入复制到状态矩阵中。经过初始轮子密钥加后,通过执行10、12或14次轮函数来变换状态矩阵(依赖于密钥长度),最后一轮与前Nr -1轮略有不同。最后状态将如3.4节中所述被复制到输出。 轮函数通过密钥扩展算法进行参数化,密钥编排由5.2节中描述的密钥扩展程序得到的一维4-byte字数组组成。 加密算法由图5中的伪代码表示,下面的每一个个变换—SubBytes(),ShiftRows(),MixColumns(),和AddRoundKey()— 都作用在状态上,将在下面的章节中说明。在图5中,数组w[ ]中包含了密钥编排得到的密钥,这些将在5.2节中说明。 如图5所示,除了最后一轮,所有的轮变换均相同。最后一轮不包括MixColumns()变换。 附录B给出了该加密算法的一个例子,列出了每一轮变换之前的状态矩阵值以及应用了下面几节描述的4个变换后的值。
图 5 加密算法伪代码
1
5.1.1 字节替代(SubBytes( ))变换
字节替代(SubBytes())变换是一个非线性的字节替代,它独立地将状态中的每个字节 1
作用于状态矩阵上的各种变换(如SubBytes(),ShiftRows()等等)由‘state’指针指向其地址。AddRoundKey()使用额外的指针指向轮密钥的地址。
利用替代表(S盒)进行运算。该S盒(图7)是可逆的,由两个变换复合而成:
1. 选取4.2节所描述的有限域GF(28)上的乘法逆运算,其中,元素{00}映射到它自身。 2. 应用下面定义的(GF(2)上的)仿射变换:
bi'?bi?b(i?4)mod8?b(i?5)mod8?b(i?6)mod8?b(i?7)mod8?ci
(5.1)
对于0?i?8,bi是字节的第i比特,ci是值为{63}或{01100011}的字节c的第i
比特。在此处和其它地方,在变量的右上角作标记(如b’)表示该变量将用右侧的值更新。 以矩阵的形式,S盒的仿射变换可以表示为:
图6画图说明了SubBytes()变换在状态上的作用效果。
(5.2)
图 6 SubBytes()作用在状态的单个字节上
以16进制表示的SubBytes()变换对应的S盒如图7所示。
'例如,如果s1,1={53},则替代后的值将由图7中行标为5列标为3的交集决定。即s1,11,1的值为{ed}。
图 7 S盒:字节xy的替代值(16进制格式)
5.1.2 行移位(ShiftRows( ))变换
在行移位(ShiftRows( ))变换中,状态的最后3行循环移位不同的位移r。第一行中r = 0,即保持不变。 具体地,行移位变换按照下述方法进行:
sr',c?sr,(c?shift(r,Nb))modNb 0?r?4且0?c?Nb (5.3)
移位量shift(r,Nb)依赖于行号r,如下所示(记着Nb=4): shift(1,4)=1; Shift(2,4)=2; Shift(3,4)=3; (5.4)
其作用效果是将行中的字节移向较低位(即给定行中c的较低值),最低位的字节将交换至行的最高位(即给定行中c的较高值)。
图8描述了行移位变换。
图 8 ShiftRows()在状态的后三行上循环移位
5.1.3 列混合(MixColumns( ))变换
列混合(MixColumns( ))变换在状态上按照每一列进行运算,并将每一列看作4.3节中描
4述的4次多项式,即将状态的列看作GF(28)上的多项式且被一个固定的多项式a(x)模x?1乘,a(x)为:
a(x)?{03}x3?{01}x2?{01}x?{02}
(5.5)
正如4.3节中所述,这可以写成矩阵乘法。令s'(x)?a(x)?s(x):
'?s0??02,c?'???s1,c???01'??s2?01,c?'????s3,c???03
030201010103020101??s0,c??s?01???1,c? 03??s2,c????02??s3,c?
0?c?Nb
(5.6)
经过该乘法计算后,一列中的4个字节将由下述结果取代:
's002}?s0,c)?({03}?s1,c)?s2,c?s3,c ,c?({'s102}?s1,c)?({03}?s2,c)?s3,c ,c?s0,c?({'s202}?s2,c)?({03}?s3,c) ,c?s0,c?s1,c?({'s303}?s0,c)?s1,c?s2,c?({02}?s3,c) ,c?({图9描述了MixColumns()变换。
图9 MixColumns()在状态的列上运算
5.1.4 轮密钥加(AddRoundKey( ))变换
在轮密钥加变换中,用简单的比特异或将一个轮密钥作用在状态上。每一个轮密钥由
通过密钥编排得到的Nb个字组成(5.2节描述)。将这Nb个字异或到状态的列上,即
''''[s0,s,s,s,c1,c2,c3,c]?[s0,c,s1,c,s2,c,s3,c]?[wround?Nb?c]
0?c?Nb
(5.7)
其中的[wi]是5.2节中描述的密钥编排得到的字,round是如下范围内的值
0?round?Nr。在加密算法中,当round=0,在应用第一个轮函数之前进行初始轮密钥加。当1?round?Nr时,AddRoundKey()变换应用到加密算法的Nr轮上。
该运算如图10所示,其中l=round*Nb。密钥编排得到的字中的字节编号如3.1节所述。
图 10 AddRoundKey() 将密钥编排得到的字异或到状态的每一列上
5.2 密钥扩展算法
AES算法接受密码的秘密密钥K,运行密钥扩展程序来生成密钥编排的结果。密钥扩展总共生成Nb(Nr+1)个字:该算法需要一个Nb个字组成的初始集合,Nr轮中的每一轮需要Nb个字的密钥数据。密钥编排结果由一个4-byte字的线性数组组成,记为[wi],其中
0?i?Nb(Nr?1)。
根据图11中的伪代码将输入密钥扩展成密钥编排结果。
SubWord()函数将接受一个4-byte输入字,对每一个字节应用S盒(5.1.1节图7)得到
输出字。函数RotWord()接受字[a0,a1,a2,a3]作为输入,执行循环移位后返回字[a1,a2,a3,a0]。轮常数字数组Rcon[i],包含了由[x节所述(注意到i从1开始,而不是0),xi?1i?1,{00},{00},{00}]给定的值。如4.2
是有限域GF(28)上x(x记为{02})的指数幂。
由图11可见,第一个Nk字由密码的秘密密钥直接填充。接下来的每个字w[i],等于其前一个字w[i-1]与Nk个位置之前的字w[i-Nk]的异或(XOR)。对于Nk的整数倍位置的字,在异或之前,要对w[i-1]进行一次变换,该变换先进行一次字的字节循环移位(RotWord()),然后再做一次字节替代变换(SubWord()),即对字中的4个字节应用查表。再异或一个轮常数。 需要注意256-bit密钥(Nk=8)的密钥扩展程序与128-bit和192-bit密钥的稍有不同。如果Nk=8且i-4是Nk的整数倍,异或之前对w[i-1]要做一次字节替代(SubWord())变换。
图 11 密钥扩展伪代码
2
附录A中给出了密钥扩展的例子。
5.3 解密
对于AES算法,可以将5.1节中的加密变换逆转,然后以逆序执行即可直接得到解密算法。解密算法中使用的变换-InvShiftRows(),InvSubBytes(),InvMixColumns()和AddRoundKey()-作用在状态上,将在下面的章节中说明。 图12描述了解密算法的伪代码。在图12中,如前面5.2节中所描述的数组w[ ]包含了密钥编排得到的密钥。
2
函数SubWord()和RotWord()会返回一个结果值,即是对函数输入的变换,然而加密和解密中的变换(如ShitfRows(),SubBytes()等等)是对由‘state’指针指向的状态矩阵的变换。
图 12 解密算法的伪代码
3
5.3.1 逆行移位(InvShiftRows( ))变换
逆行移位(InvShiftRows())变换是行移位(ShiftRows())变换的逆变换。状态最后3行中的字节循环移位不同的字节数(位移量)。第一行中r = 0,即不移位。下面的三行将循环移动Nb-shift(r,Nb)字节,其中位移量shift(r,Nb)依赖于行号并由等式(5.4)(见5.1.2节)给出。 明确的,逆行移位变换将按照下述方法进行:
sr',(c?shift(r,Nb))modN?sr,c 0?r?4且0?c?Nb (5.8)
图13描述了逆行移位(InvShiftRows())变换。
3
作用于状态矩阵上的各种变换(如SubBytes(),ShiftRows()等等)由‘state’指针指向其地址。AddRoundKey()使用额外的指针指向轮密钥的地址。
图 13 InvShiftRows()在状态的后三行上循环移位
5.3.2 逆字节替代(InvSubBytes( ))变换
逆字节替代(InvSubBytes())变换是字节替代(SubBytes())变换的逆变换,在状态的每个字节上应用S盒的逆。这是通过应用仿射变换(5.1)的逆,再接着应用GF(28)中的乘法逆得到的。 逆字节替代(InvSubBytes())变换中使用的S盒的逆如图14所示:
图14 S盒的逆:字节xy的替代值(16进制格式)
5.3.3 逆列混合(InvMixColumns( ))变换
逆列混合(InvMixColumns())变换是列混合(MixColumns())变换的逆变换。逆列混合(InvMixColumns())变换在状态上对每一列进行运算,将每一列看作4.3节中描述的4
?1次多项式。将状态的列看作GF(28)上的多项式且被一个固定的多项式a(x)模x?1乘,
4a?1(x)为:
a?1(x)?{0b}x3?{0d}x2?{09}x?{0e}
'?1 (5.9)
正如4.3节中所述,这可以写成矩阵乘法。令s(x)?a(x)?s(x):
'?s0??0e,c?'???s1,c???09'??s2?0d,c?'???s3,c???0b?
0b0e090d0d0b0e0909??s0,c??s?0d???1,c? 0b??s2,c????0e??s3,c?
0?c?Nb
(5.10)
经过该乘法计算后,一列中的4个字节将由下述结果取代:
's00e}?s0,c)?({0b}?s1,c)?({0d}?s2,c)?({09}?s3,c) ,c?({'s109}?s0,c)?({0e}?s1,c)?({0b}?s2,c)?({0d}?s3,c) ,c?({'s20d}?s0,c)?({09}?s1,c)?({0e}?s2,c)?({0b}?s3,c) ,c?({'s30b}?s0,c)?({0d}?s1,c)?({09}?s2,c)?({0e}?s3,c) ,c?({5.3.4 轮密钥加(InvMixColumns( ))变换的逆变换
5.1.4节中所述的轮密钥加(InvMixColumns())变换,其逆变换就是它本身,因为其中
只应用了异或(XOR)运算。
5.3.5 等价的解密变换
在5.3节和图12中描述的直接得到的解密算法中,其各个变换的操作顺序与加密算法不同,但是加密和解密算法中的密钥编排形式相同。然而,AES算法的若干性质允许构造一个等价的解密算法,解密时各个变换的操作顺序与加密(由逆变换取代原来的变换)相同。这是通过改变密钥编排完成的。 允许该等价解密变换的二个关键性质如下:
1. 字节替代(SubBytes())变换和行移位(ShiftRows())变换的顺序不影响结果。即,
先进行字节替代(SubBytes())变换紧接着进行行移位(ShiftRows())变换等价于先进行行移位(ShiftRows())变换紧接着再进行字节替代(SubBytes())变换。对于逆变换InvSubBytes()和InvShiftRows(),该性质也成立。
2. 列混合运算-MixColumns()和InvMixColumns()-是关于列输入的线性变换,
即意味着
InvMixColumns(state XOR Round Key)=
InvMixColumns(state) XOR InvMixColumns(Round Key)
这些性质使得InvSubBytes()变换和InvShiftRows()变换可以交换顺序。AddRoundKey()变换和InvMixColumns()变换的顺序也可以交换,只要将解密中密钥编排得到的密钥列(字)应用InvMixColumns()变换进行修改即可。 等价的解密算法如图12所示,定义为将InvSubBytes()变换和InvShiftRows()变换的顺序反转过来,同时当利用InvMixColumns()变换先修改了1到Nr-1轮的解密密钥编排结果后,将“轮循环”中使用的AddRoundKey()变换和InvMixColumns()变换的顺序反转。解密密钥编排结果的第一和最后Nb字将不使用该方式进行修改。 给出的这些改变,使得等价的解密算法比5.3节和图12中描述的解密算法具有更有效的结构。图15中给出了等价解密算法的伪代码。(字数组dw[ ]中包含了修改过的解密密钥编排结果。图15中也给出了对密钥扩展程序的修改。)
图 15 等价解密算法的伪代码
6.实现方面的问题
6.1 密钥长度要求
AES算法的实现至少需要支持第5节中描述的3种密钥长度:128,192或256 bits(即Nk=4,6或8分别的)。实现可以选择支持两种或三种密钥长度,这将促进算法执行的互用性。
6.2 密钥限制
对于AES算法没有发现弱密钥或半弱密钥,所以对密钥选取没有限制。
6.3 密钥长度,分组大小和轮数的参数化
该标准明确地定义了密钥长度(Nk),分组大小(Nb)和轮数(Nr)允许的取值如图4所示。然而,该标准的未来版本可能包括对这些参数允许取值的改变或增加。因此,当实现者设计AES的实现时可以选择将未来的变化考虑在内。
6.4 针对不同平台的实现建议
很多情况下,实现的可变性可能会提供更好的性能或其它优势。当给定相同的输入密钥和数据(明文或密文)时,任意与该标准说明的算法得到相同输出(密文或明文)的实现都是可以接受的AES实现。 参考文献【3】和参考【1】中列出的其它文章都包含了一些关于如何在不同平台上有效地实现AES算法的建议。
正在阅读:
aes12-30
浅析词汇的泛化现象04-17
知识概要——水资源保护06-01
一年级古诗文读本11-16
大气科学实习报告09-04
危险源清单03-21
公开课演示文稿209-06
施工安全风险识别与预防措施04-07
- exercise2
- 铅锌矿详查地质设计 - 图文
- 厨余垃圾、餐厨垃圾堆肥系统设计方案
- 陈明珠开题报告
- 化工原理精选例题
- 政府形象宣传册营销案例
- 小学一至三年级语文阅读专项练习题
- 2014.民诉 期末考试 复习题
- 巅峰智业 - 做好顶层设计对建设城市的重要意义
- (三起)冀教版三年级英语上册Unit4 Lesson24练习题及答案
- 2017年实心轮胎现状及发展趋势分析(目录)
- 基于GIS的农用地定级技术研究定稿
- 2017-2022年中国医疗保健市场调查与市场前景预测报告(目录) - 图文
- 作业
- OFDM技术仿真(MATLAB代码) - 图文
- Android工程师笔试题及答案
- 生命密码联合密码
- 空间地上权若干法律问题探究
- 江苏学业水平测试《机械基础》模拟试题
- 选课走班实施方案
- 2020届肇庆市高三理综联考试题(附答案)
- 新疆克拉玛依友谊宾馆特大火灾 - 图文
- 为什么黑茶制作工艺是国家二级机密几千种茶凭什么就黑茶有
- 全国通用2020版高考政治一轮复习加练半小时第75练物质和运动绝对运动和相对静止的关系新人教版
- 环卫市场规模有望超千亿 北控水务成立子公司北控环境
- 打假行政处罚案件信息公开表-广州食品药品监督管理局
- 50个java小程序设计
- 天津大学材料断裂行为
- 最新患者病情评估培训总结资料
- 建筑工程合同法全文,建筑工程合同法详细规定
- 《合同法》综合练习题及参考答案
- 驳学习围棋十大好处
- 导数专项训练及答案
- 新生儿气胸35临床分析论文
- 仁轩文学社八周年庆晚会主持稿
- 新疆继续教育网《医患纠纷的防范与法律应对》6
- 湖南省迎丰镇九年级物理全册 15.1两种电荷教案(新版)新人教版
- LNG气化站的消防安全设计
- 2013护士执业资格试卷
- 法学概论专科考核说明