第三章 分组密码 3.1 分组密码概述 3.2 DES 3.3 AES 3.4 分组密码运行模式

一、分组密码概述

分组密码概述 分组密码是许多系统安全的一个重要组成部分。 可用于构造 伪随机数生成器 流密码 消息认证码(MAC)和杂凑函数 消息认证技术、数据完整性机构、实体认证协议以 及单钥数字签字体制的核心组成部分。

应用中对于分组码的要求 安全性 运行速度 存储量(程序的长度、数据分组长度、高速缓 存大小) 实现平台(硬、软件、芯片) 运行模式

分组密码概述 明文序列 x1, x2,…, xi,… 加密函数E: Vn×KVn 这种密码实质上是字长为m的数字序列的代换密码。 解密算法 加密算法 密钥k=(k0, k1,…, kt-1 ) 明文 x=(x0, x1,…, xm-1) 密文 x=(y0, y1,…, ym-1)

分组密码概述 通常取n=m。 若n>m，则为有数据扩展的分组密码。 若n<m，则为有数据压缩的分组密码。

分组密码设计问题 分组密码的设计问题在于找到一种算法， 能在密钥控制下从一个足够大且足够好的 置换子集中，简单而迅速地选出一个置换， 用来对当前输入的明文的数字组进行加密 变换。

分组密码设计准则 混淆：人们所设计的密码应使用使得密钥和明文以及密文之间的依赖关系相当复杂以至于这种依赖性对密码分析者来说是无法利用的。 扩散：人们所设计的密码应使得密钥的每一位数字影响密文的许多位数字以防止对密钥进行逐段破译，而且明文的每一位数字也应影响密文的许多位数字以便隐藏明文数字统计特性。

分组密码算法应满足的要求 分组长度n要足够大： 密钥量要足够大： 由密钥确定置换的算法要足够复杂： 防止明文穷举攻击法奏效。 尽可能消除弱密钥并使所有密钥同等地好，以防止密 钥穷举攻击奏效。 由密钥确定置换的算法要足够复杂： 充分实现明文与密钥的扩散和混淆，没有简单的关系 可循，要能抗击各种已知的攻击。

分组密码算法应满足的要求 加密和解密运算简单： 数据扩展： 差错传播尽可能地小。 易于软件和硬件高速实现。 一般无数据扩展，在采用同态置换和随机化加密技 术时可引入数据扩展。 差错传播尽可能地小。

分组密码的实现原则 软件实现的原则：使用子块和简单的运算。如将分组n化分为子段，每段长为8、16或32。在以软件实现时，应选用简单的运算，使作用于子段上的密码运算易于以标准处理器的基本运算，如加、乘、移位等实现，避免用以软件难于实现的逐比特置换。 硬件实现的原则：加密解密可用同样的器件来实现。

代换网络 fk：AA＇ k是控制输入变量，在密码学中则为密钥。 代换是输入集A到输出A’上的双射变换： 实现代换fk的网络称作代换网络。双射条件保证 在给定k下可从密文惟一地恢复出原明文。

代换网络 代换fk的集合： S={fkkK} K是密钥空间。如果网络可以实现所有可 能的2n!个代换，则称其为全代换网络。 全代换网络密钥个数必须满足条件： ＃{k}2n!

代换结构

代换网络 密码设计中需要先定义代换集S，而后还需定 义解密变换集，即逆代换网络S-1，它以密文y 作为输入矢量，其输出为恢复的明文矢量x。 要实现全代换网络并不容易。因此实用中常 常利用一些简单的基本代换，通过组合实现 较复杂的、元素个数较多的代换集。实用密 码体制的集合S中的元素个数都远小于2n!。

代换盒(S盒) 在密码设计中，可选 n=rn0，其中r和n0都为正整 数，将设计n个变量的代换网络化为设计r个较小的 子代换网络，而每个子代换网络只有n0个输入变量， 称每个子代换网络为代换盒(Substitution Box) S盒 x5 x4 x3 x2 x1 x0 y3 y2 y1 y0 DES的S盒

DES的S1-盒的输入和输出关系 x5 x0 x5 x4 x3 x2 x1 x0 1 0 1 0 1 1 0 0 1 0 1 0 1 1 0 0 列号 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 行号 0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 3 15 12 8 2 4 9 1 7 5 11 2 14 10 0 6 13 (y3 , y2, y1 , y0)=(0,0,1,0)

S盒的设计准则 迄今为止，有关方面未曾完全公开有关DES的S盒的设计准 则。Branstead等曾披露过下述准则： P1 S盒的输出都不是其输入的线性或仿射函数。 P2 改变S盒的一个输入比特，其输出至少有两比特产生变 化，即近一半产生变化。 P3 当S盒的任一输入位保持不变，其它5位输入变化时(共 有25 =32种情况)，输出数字中的0和1的总数近于相等。 这三点使DES的S盒能够实现较好的混淆。

Feistel密码结构 乘积密码指顺序地执行两个或多个基本密码系统，使得最后结果的密码强度高于每个基本密码系统产生的结果. Feistel还提出了实现代换和置换的方法。其思想实际上是Shannon提出的利用乘积密码实现混淆和扩散思想的具体应用。

Feistel网络示意图

Feistel密码结构 输入是分组长为2w的明文和一个密钥K。将每组明文分成左右两半L0和R0，在进行完n轮迭代后，左右两半再合并到一起以产生密文分组。第i轮迭代的输入为前一轮输出的函数： 其中Ki是第i轮用的子密钥，由加密密钥K得到。一般地，各轮子密钥彼此不同而且与K也不同。

Feistel密码结构 Feistel网络的实现与以下参数和特性有关： ① 分组大小: 分组越大则安全性越高，但加密速度就越慢。 ② 密钥大小：密钥越长则安全性越高，但加密速度就越慢。③ 轮数：单轮结构远不足以保证安全性，但多轮结构可提供足够的安全性。典型地，轮数取为16。 ④ 子密钥产生算法：该算法的复杂性越大，则密码分析的困难性就越大。 ⑤ 轮函数：轮函数的复杂性越大，密码分析的困难性也越大。

Feistel密码结构 在设计Feistel网络时，还有以下两个方面需要考虑： ① 快速的软件实现：在很多情况中，算法是被镶嵌在应用程序中，因而无法用硬件实现。此时算法的执行速度是考虑的关键。 ② 算法容易分析：如果算法能被无疑义地解释清楚，就可容易地分析算法抵抗攻击的能力，有助于设计高强度的算法。

Feistel解密结构 Feistel解密过程本质上和加密过程是一样的，算法使用密文作为输入，但使用子密钥Ki的次序与加密过程相反，即第1轮使用Kn，第2轮使用Kn-1，……，最后一轮使用K1。这一特性保证了解密和加密可采用同一算法。

Feistel加解密过程

Feistel密码结构 在加密过程中： 在解密过程中

Feistel密码结构 所以解密过程第1轮的输出为LE15‖RE15，等于加密过程第16轮输入左右两半交换后的结果。容易证明这种对应关系在16轮中每轮都成立。一般地，加密过程的第i轮有 因此

3.2 美国数据加密标准—DES（Data Encryption Standard）

美国制定数据加密标准简况 目的 通信与计算机相结合是人类步入信息社会的一个阶梯， 它始于六十年代末，完成于90年代初。计算机通信网的形 成与发展，要求信息作业标准化，安全保密亦不例外。只 有标准化，才能真正实现网的安全，才能推广使用加密手 段，以便于训练、生产和降低成本。

美国制定数据加密标准简况 美国NBS在1973年5月15公布了征求建议。1974年8月27日NBS再次出公告征求建议，对建议方案提出如下要求： (1)算法必须提供高度的安全性 (2)算法必须有详细的说明,并易于理解 (3)算法的安全性取决于密钥,不依赖于算法 (4)算法适用于所有用户 (5)算法适用于不同应用场合 (6)算法必须高效、经济 (7)算法必须能被证实有效 (8)算法必须是可出口的

美国制定数据加密标准简况 IBM公司在1971年完成的LUCIFER密码 (64 bit分组，代 换-置换，128 bit密钥)的基础上，改进成为建议的DES体 制 1975年3月17日NBS公布了这个算法，并说明要以它作为 联邦信息处理标准，征求各方意见。 1977年1月15日建议被批准为联邦标准[FIPS PUB 46]，并 设计推出DES芯片。 1981年美国ANSI 将其作为标准，称之为DEA[ANSI X3.92] 1983年国际标准化组织(ISO)采用它作为标准，称作DEA- 1

美国制定数据加密标准简况 NSA宣布每隔5年重新审议DES是否继续作为联邦标准， 1988年（FIPS46-1）、1993年（FIPS46-2），1998年不再重 新批准DES为联邦标准。 虽然DES已有替代的数据加密标准算法，但它仍是迄今为止 得到最广泛应用的一种算法，也是一种最有代表性的分组加 密体制。 1993年4月，Clinton政府公布了一项建议的加密技术标准， 称作密钥托管加密技术标准EES(Escrowed Encryption Standard)。算法属美国政府SECRET密级。

美国制定数据加密标准简况 DES发展史确定了发展公用标准算法模式，而EES的制定 路线与DES的背道而驰。人们怀疑有陷门和政府部门肆意 侵犯公民权利。此举遭到广为反对。 1995年5月AT&T Bell Lab的M. Blaze博士在PC机上用45分 钟时间使SKIPJACK的 LEAF协议失败，伪造ID码获得成 功。1995年7月美国政府宣布放弃用EES来加密数据，只将 它用于语音通信。 1997年1月美国NIST着手进行AES（Advanced Encryption Standard）的研究，成立了标准工作室。2001年Rijndael 被批准为AES标准。

美国制定数据加密标准简况 DES（Data Encryption Standard）算法于1977年得到美国政府的正式许可，是一种用56位密钥来加密64位数据的方法。这是IBM的研究成果。 DES是第一代公开的、完全说明细节的商业级现代算法，并被世界公认。

DES 算法 分组长度为64 bits (8 bytes) 密文分组长度也是64 bits。 密钥长度为64 bits，有8 bits奇偶校验，有效密钥长 度为56 bits。 算法主要包括：初始置换IP、16轮迭代的乘积变换、 逆初始置换IP-1以及16个子密钥产生器。

DES算法框图 输入 64 bit明文数据 初始置换IP 标准数据加密算法 乘积变换 （16轮迭代） 逆初始置换IP-1 输出 标准数据加密算法

初始置换IP 将64 bit明文的位置进行置换，得到一个乱序的64 bit明文组，而后分成左右两段，每段为32 bit，以L0和R0表示，IP中各列元素位置号数相差为8，相当于将原明文各字节按列写出，各列比特经过偶采样和奇采样置换后，再对各行进行逆序。将阵中元素按行读出构成置换输出。 逆初始置换IP-1。将16轮迭代后给出的64 bit组进行置 换，得到输出的密文组。输出为阵中元素按行读得的 结果。 IP和IP-1在密码意义上作用不大，它们的作用在于打 乱原来输入x的ASCII码字划分的关系。

（1）IP置换表和IP-1逆置换表。输入的64位数据按IP表置换进行重新组合，并把输出分为L0和R0两部分，每部分各32位，其IP表置换如表2-3所示。 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7

40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31 38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29 36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27 34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25

密钥产生器 乘积变换框图 Li-1(32bit) Ri-1(32bit) 选择扩展运算 E 48 bit寄存器 按bit模2加密 选择压缩运算 S 32 bit寄存器 置换运算 P 按bit模2和 Li (32bit) Ri (32bit) 乘积变换框图 密钥产生器

Li = Ri-1 Ri= Li⊕f(Ri-1 ,Ki) （i=1,2,3, …,16）

乘积变换 它是DES算法的核心部分。将经过IP置换后的数据分成32 bit的左右两组，在迭代过程中彼此左右交换位置。 每次迭代时只对右边的32 bit进行一系列的加密变换，在此 轮迭代即将结束时，把左边的32 bit与右边得到的32 bit逐位 模2相加，作为下一轮迭代时右边的段，并将原来右边未经 变换的段直接送到左边的寄存器中作为下一轮迭代时左边 的段。 在每一轮迭代时，右边的段要经过选择扩展运算E、密钥加 密运算、选择压缩运算S、置换运算P和左右混合运算。

乘积变换 选择扩展运算E。将输入的32 bit Ri-1扩展成48 bit的输出，令s 表示E原输入数据比特的原下标，则E的输出是将原下标s0或 1(mod 4)的各比特重复一次得到的，即对原第32, 1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29各位都重复一次,实现数据扩 展。将表中数据按行读出得到48 bit输出。 密钥加密运算。将子密钥产生器输出的48 bit子密钥ki与选择 扩展运算E输出的48 bits数据按位模2相加。 选择压缩运算S。将前面送来的48 bit数据自左至右分成8组， 每组为6 bit。而后并行送入8个S一盒，每个S盒为一非线性代 换网络，有4个输出，运算S的框图在图4-4-6中给出。 p.186 图4-4-6 选择压缩运算S 置换运算P。对S1至S8盒输出的32 bit数据进行坐标置换，如图 4-4-7所示。置换P输出的32 bit数据与左边32 bit即Ri-1逐位模2 相加，所得到的32 bit作为下一轮迭代用的右边的数字段。并 将Ri-1并行送到左边的寄存器，作为下一轮迭代用的左边的数 字段。 子密钥产生器。将64 bit初始密钥经过置换选择PC1、循环移位 置换、置换选择PC2给出每次迭代加密用的子密钥ki，参看图 4-4-8。在64 bit初始密钥中有8位为校验位，其位置号为8、16、 32、48、56和64。其余56位为有效位，用于子密钥计算。将 这56位送入置换选择PC1，参看图4-4-9。经过坐标置换后分 成两组，每级为28 bit，分别送入C寄存器和D寄存器中。在各 次迭代中，C和D寄存器分别将存数进行左循环移位置换，移 位次数在表4-4-2中给出。每次移位后，将C和D寄存器原存数 送给置换选择PC2，见图4-4-10。置换选择PC2将C中第9、18、 22、25位和D中第7、9、15、26位删去，并将其余数字置换位 置后送出48 bit数字作为第i次迭代时所用的子密钥ki。 p.186 p.186 图4-4-7 置换运算P 图4-4-8 子密钥产生器框图 表4-4-2 移位次数表 第i次迭代 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 循环左移次数 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1 p.187 图4-4-9 置换选择PC1 至此，我们已将DES算法的基本构成作了介绍，加密过程可归 结如下：令IP表示初始置换，KS表示密钥运算，i为迭代次数 变量，KEY为64 bit密钥，f为加密函数，表示逐位模2求和。

32 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 E变换的算法是从Ri-1的32位中选取某些位，构成48位，即E将32位扩展为48位。变换规则根据E位选择表，如表2-5所示。

选择压缩运算S 48 bit 寄存器 32 bit 寄存器 S1 S2 S3 S4 S5 S6 S7 S8 6 bit 选择函数组

乘积变换 置换运算P。对S1至S8盒输出的32 bit数据进行坐 标置换，置换P输出的32 bit数据与左边32 bit即Ri- 1逐位模2相加，所得到的32 bit作为下一轮迭代用 的右边的数字段。并将Ri-1并行送到左边的寄存器， 作为下一轮迭代用的左边的数字段。 子密钥产生器。将64 bit初始密钥经过置换选择 PC1、循环移位置换、置换选择PC2给出每次迭代 加密用的子密钥ki，

16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25

子密钥产生器框图 密钥（64 bit ） 置换选择1，PC1 Ci(28 bit) Di(28 bit) 置换选择2，PC2 ki 除去第8,16, ,64位(8个校验位) 置换选择1，PC1 Ci(28 bit) Di(28 bit) 循环左移ti+1bit 循环左移ti+1bit 置换选择2，PC2 ki

DES的安全性 互补性。DES算法具有下述性质。若明文组x逐位取 补，密钥k逐位取补，即y=DESk(x), 则有 弱密钥和半弱密钥。DES算法在每次迭代时都有一 个子密钥供加密用。如果给定初始密钥k，各轮的子 密钥都相同，即有 k1=k2= … =k16 就称给定密钥k为弱密钥(Weak key)。

DES的安全性 若k为弱密钥，则有 DESk(DESk(x))=x DESk-1(DESk-1(x))=x

DES的安全性 密文与明文、密文与密钥的相关性。 Meyer[1978]详细研究了DES的输入明文与密文及密钥与 密文之间的相关性。表明每个密文比特都是所有明文比 特和所有密钥比特的复合函数，并且指出达到这一要求 所需的迭代次数至少为5。Konheim[1981]用2检验证明， 迭代8次后输出和输入就可认为是不相关的了。

DES的安全性 S盒设计。 DES靠S盒实现非线性变换。 密钥搜索机。 对DES安全性批评意见中，较为一致的看法是DES的 密钥短了些。IBM最初向NBS提交的建议方案采用112 bits密钥，但公布的DES标准采用64 bits密钥。有人认 为NSA故意限制DES的密钥长度。采用穷搜索对已经 对DES构成了威胁．

DES算法的安全性 DES算法正式公开发表以后，引起了一场激烈的争论。1977年Diffie和Hellman提出了制造一个每秒能测试106个密钥的大规模芯片，这种芯片的机器大约一天就可以搜索DES算法的整个密钥空间，制造这样的机器需要两千万美元。

1993年R.Session和M.Wiener给出了一个非常详细的密钥搜索机器的设计方案，它基于并行的密钥搜索芯片，此芯片每秒测试5×107个密钥，当时这种芯片的造价是10.5美元，5760个这样的芯片组成的系统需要10万美元，这一系统平均1.5天即可找到密钥，如果利用10个这样的系统，费用是100万美元，但搜索时间可以降到2.5小时。可见这种机制是不安全的。

DES的56位短密钥面临的另外一个严峻而现实的问题是：国际互联网Internet的超级计算能力。1997年1月28日，美国的RSA数据安全公司在互联网上开展了一项名为“密钥挑战”的竞赛，悬赏一万美元，破解一段用56位密钥加密的DES密文。

一位名叫Rocke Verser的程序员设计了一个可以通过互联网分段运行的密钥穷举搜索程序，组织实施了一个称为DESHALL的搜索行动，成千上万的志愿者加入到计划中，在计划实施的第96天，即挑战赛计划公布的第140天，1997年6月17日晚上10点39分，美国盐湖城Inetz公司的职员Michael Sanders成功地找到了密钥，在计算机上显示了明文：“The unknown message is: Strong cryptography makes the world a safer place”。

1998年7月电子前沿基金会（EFF）使用一台25万美圆的电脑在56小时内破译了56比特密钥的DES。 1999年1月RSA数据安全会议期间，电子前沿基金会用22小时15分钟就宣告破解了一个DES的密钥。 尽管DES有这样那样的不足，但是作为第一个公开密码算法的密码体制成功地完成了它的使命，它在密码学发展历史上具有重要的地位。

二重DES 用DES进行两次加密，但这是否就意味着两重 DES加密的强度等价于112 bit密钥的密码的强度？ 答案是否定的。 中途相遇攻击法(Meet-in-the-Middle Attack) 由Diffie和Hellman[1977]最早提出，可以降低搜 索量其基本想法如下。若有明文密文对(xi,yi)满足 yi=Ek2[Ek1[xi]] 则可得 z=Ek1[xi]=Dk2[yi]

二重DES 图4-14-1 中途相遇攻击示意图 z E D xi yi k1 k2

中途相遇攻击 给定一已知明密文对(x1,y1)，可按下述方法攻击。 以密钥k1的所有256个可能的取值对此明文x1加密，并 将密文z存储在一个表中； 从所有可能的256个密钥k2中依任意次序选出一个对给 定的密文y1解密，并将每次解密结果z在上述表中查 找相匹配的值。一旦找到，则可确定出两个密钥k1和 k2； 以此对密钥k1和k2对另一已知明文密文对(x2, y2)中的明 文x2进行加密，如果能得出相应的密文y2就可确定k1和 k2是所要找的密钥。

中途相遇攻击 对于给定明文x，以两重DES加密将有264个可能的密文。 可能的密钥数为2112个。所以，在给定明文下，将有2112/264 =248个密钥能产生给定的密文。 用另一对64bits明文密文对进行检验，就使虚报率降为248-64=2-16。 这一攻击法所需的存储量为256×8 Byte，最大试验的加密次数2×256 =257。这说明破译双重DES的难度为257量级。

三重DES加密 加密：y=Ek1[Dk2[Ek1 [x]]] 解密：x=Dk1[Ek2[Dk1[y]]] 称其为加密-解密-加密方案，简记为EDE(encrypt- decrypt-encrypt)。 此方案已在ANSI X9.17和ISO 8732标准中采用，并在 保密增强邮递(PEM)系统中得到利用。 破译它的穷举密钥搜索量为21125×1035量级，而用差 分分析破译也要超过1052量级。此方案仍有足够的安 全性。

3.3 高级加密标准 AES

AES提出 1997年1月，美国NIST向全世界密码学界 发出征集21世纪高级加密标准（AES— —Advanced Encryption Standard）算法 的公告，并成立了AES标准工作研究室， 1997年4月15日的例会制定了对AES的评 估标准。

AES的要求 （1）AES是公开的； （2）AES为单钥体制分组密码； （3）AES的密钥长度可变，可按需要增大； （5）AES可以自由地使用，或按符合美国国家 标准（ANST）策略的条件使用；

算法衡量条件 满足以上要求的AES算法，需按下述条件判断优劣 a. 安全性 b. 计算效率 c. 内存要求 d. 使用简便性 e. 灵活性。

AES的评审 1998年4月15日全面征集AES算法的工作结束。1998年8 月20日举行了首届AES讨论会，对涉及14个国家的密码 学家所提出的候选AES算法进行了评估和测试，初选并 公布了15个被选方案，供大家公开讨论。 CAST-256， RC-6， CRYPTON-128，DEAL-128， FROG， DFC， LOKI-97， MAGENTA， MARS， HPC, RIJNDAEL， SAFER+， SERPENT， E-2， TWOFISH。 这些算法设计思想新颖，技术水平先进，算法的强度都 超过3-DES，实现速度快于3-DES。

AES的评审 1999年8月9日NIST宣布第二轮筛选出的5个候选算法为： MARS(C.Burwick等,IBM）， RC6TM（R. Rivest等,RSA Lab.)， RIJNDEAL(J. Daemen,比)， SERPENT(R. Anderson等，英、以、挪威)， TWOFISH(B. Schiener)。 2000年10月2日，NIST宣布Rijndael作为新的AES

AES算法设计思想 抵抗所有已知的攻击； 在多个平台上速度快，编码紧凑； 设计简单。 Rijndael没有采用Feistel结构，轮函数由3个不同的可逆均匀变换构成的，称为3个层 均匀变换是指状态的每个bit都用类似的方法处理

轮函数的3层 线性混合层 非线性层 密钥加层 确保多轮之上的高度扩散； 将具有最优的“最坏情况非线性特性”的S盒并行使用； 单轮子密钥简单的异或到中间状态上，实现一次性掩盖。

算法说明 分组和密钥长度可变，各自可独立指定为128、192、256比特。 状态 种子密钥 算法中间的结果也需要分组，称之为状态，状态可以用以字节为元素的矩阵阵列表示，该阵列有4行，列数Nb为分组长度除32 种子密钥 以字节为元素的矩阵阵列描述，阵列为4行，列数Nk为密钥长度除32

1. Rijndael数学基础 定义一个由 组成的字节b可表示为系数为{0，1}的二进制多项式： 定义在 上的加法定义为二进制多项式的加法，且其系数模2。 定义 在 上的乘法（用符号·表示）定义为二进制多项式的乘积模一个次数为8的不可约二进制多项式，此不可约多项式为（十六进制为‘11B’） 上面定义的乘法在 上满足结合律，且有一个本原元（‘02’）。

定义 在 上的二进制多项式b(x)的乘法逆为满足方程式 的二进制多项式a(x)，记为 定义 函数xtime(x)定义为 上的x·b(x)。其运算如下：若b7 =0，则x·b(x)的结果就是把字节b左移一位；若b7 =1，则结果需异或‘1B’。 定义 有限域 上的多项式是系数取自 元素的多项式，这样，一个4字节向量与一个次数小于4的多项式相对应。 定义 上的多项式的加法定义为相应项系数相加。 因为在域 上的加是简单的按位异或，所以在域 上的两向量的加也就是简单的按位异或。

定义 上的多项式 和 相乘模 的积（表示为 ）为 ，其系数由下面4个式子得到： 利用该定义有 。

可将上述计算表示为

注意到M(x)不是GF(28)上的不可约多项式（甚至也不是GF(2)上的不可约多项式），因此非0多项式的这种乘法不是群运算。不过在Rijndael密码中，对多项式b(x)，这种乘法运算只限于乘一个固定的有逆元的多项式a(x)= a3x3+a2x2+a1x+a0。

定理3.1 系数在GF(28)上的多项式a3x3+a2x2+a1x+a0是模x4+1可逆的，当且仅当矩阵 在GF(28)上可逆。

证明：a3x3+a2x2+a1x+a0是模x4+1可逆的，当且仅当存在多项式h3x3+h2x2+h1x+h0 (a3x3+a2x2+a1x+a0)(h3x3+h2x2+h1x+h0)=1 mod(x4+1) 因此有 (a3x3+a2x2+a1x+a0)(h2x3+h1x2+h0x+h3)=x mod (x4+1) (a3x3+a2x2+a1x+a0)(h1x3+h0x2+h3x+h2)=x2 mod (x4+1) (a3x3+a2x2+a1x+a0)(h0x3+h3x2+h2x+h1)=x3 mod(x4+1)

将以上关系写成矩阵形式即得 （证毕）

算法说明 算法的输入、输出和种子密钥可看成字节组成的一维数组。 下标范围 输入输出：0－4Nb-1， 种子密钥：0－4Nk-1

Nb=6和Nk=4的状态密钥阵列 按此顺序放入和读出 按此顺序放入

分组和阵列中元素对应关系 分组下标n 阵列位置(i,j) 轮数Nr与Nb和Nk对应关系 Nb=4 Nb=6 Nb=8 Nk=4 10 12 i=n mod 4, j=[n/4];n=i+4j 轮数Nr与Nb和Nk对应关系 Nb=4 Nb=6 Nb=8 Nk=4 10 12 14 Nk=6 Nk=8

轮函数 字节代换 行移位 列混合 密钥加

字节代换 非线性代换，独立地对状态的每个字节进行，并且代换表(S盒)可逆，记为ByteSub(State),分两步 将字节作为GF(28)上的元素映射到自己的逆元 将字节做如下的GF(2)上变换

字节代换

AES的S盒 y 1 2 3 4 5 6 7 8 9 a b c d e f x 63 7c 77 7b f2 6b 6f c5 30 01 1 2 3 4 5 6 7 8 9 a b c d e f x 63 7c 77 7b f2 6b 6f c5 30 01 67 2b fe d7 ab 76 ca 82 c9 7d fa 59 47 f0 ad d4 a2 af 9c a4 72 c0 b7 fd 93 26 36 3f f7 cc 34 a5 e5 f1 71 d8 31 15 04 c7 23 c3 18 96 05 9a 07 12 80 e2 eb 27 b2 75 09 83 2c 1a 1b 6e 5a a0 52 3b d6 b3 29 e3 2f 84 53 d1 00 ed 20 fc b1 5b 6a cb be 39 4a 4c 58 cf d0 ef aa fb 43 4d 33 85 45 f9 02 7f 50 3c 9f a8 51 a3 40 8f 92 9d 38 f5 bc b6 da 21 10 ff f3 d2 cd 0c 13 ec 5f 97 44 17 c4 a7 7e 3d 64 5d 19 73 60 81 4f dc 22 2a 90 88 46 ee b8 14 de 5e 0b db e0 32 3a 0a 49 06 24 5c c2 d3 ac 62 91 95 e4 79 e7 c8 37 6d 8d d5 4e a9 6c 56 f4 ea 65 7a ae 08 ba 78 25 2e 1c a6 b4 c6 e8 dd 74 1f 4b bd 8b 8a 70 3e B5 66 48 03 f6 0e 61 35 57 b9 86 c1 1d 9e e1 f8 98 11 69 d9 8e 94 9b 1e 87 e9 ce 55 28 df 8c a1 89 0d bf e6 42 68 41 99 2d 0f B0 54 bb 16

逆字节代换InvSubBytes() 逆字节替代变换是字节第替代变换的逆变换，在状态的每个字节上应用逆S盒。这是通过应用字节替代变换中的仿射变换的逆变换，再对所得结果应用有限域的乘法逆运算得到的。

AES的逆S盒 y 1 2 3 4 5 6 7 8 9 a b c d e f x 52 09 6a d5 30 36 a5 38 bf 1 2 3 4 5 6 7 8 9 a b c d e f x 52 09 6a d5 30 36 a5 38 bf 40 a3 9e 81 f3 d7 fb 7c e3 39 82 9b 2f ff 87 34 8e 43 44 c4 de e9 cb 54 7b 94 32 a6 c2 23 3d ee 4c 95 0b 42 fa c3 4e 08 2e A1 66 28 d9 24 b2 76 5b a2 49 6d 8b d1 25 72 f8 f6 64 86 68 98 16 d4 a4 5c cc 5d 65 B6 92 6c 70 48 50 fd ed b9 da 5e 15 46 57 a7 8d 9d 84 90 d8 ab 00 8c bc d3 0a f7 e4 58 05 b8 b3 45 06 d0 2c 1e 8f ca 3f 0f 02 c1 af bd 03 01 13 8a 6b 3a 91 11 41 4f 67 dc ea 97 f2 cf ce f0 b4 e6 73 96 ac 74 22 e7 ad 35 85 e2 f9 37 e8 1c 75 df 6e 47 f1 1a 71 1d 29 c5 89 6f b7 62 0e aa 18 be 1b fc 56 3e 4b c6 d2 79 20 9a db c0 fe 78 cd 5a f4 1f dd a8 33 88 07 c7 31 b1 12 10 59 27 80 ec 5f 60 51 7f a9 19 b5 4a 0d 2d e5 7a 9f 93 c9 9c ef a0 e0 3b 4d ae 2a f5 b0 c8 eb bb 3c 83 53 99 61 17 2b 04 7e ba 77 d6 26 e1 69 14 63 55 21 0c 7d

上述S-盒对状态的所有字节所做的变换记为 ByteSub (State) 图3.19 字节代换示意图

行移位 将状态阵列的各行进行循环移位，不同行的移位量不同 0行：不动 1行：循环左移C1字节 2行：循环左移C2字节 3行：循环左移C3字节 记为：ShiftRow(State)

图3.20 行移位示意图

行移位 移位量与分组长度的关系 Nb C1 C2 C3 4 1 2 3 6 8

逆行移位InvShiftRows() 逆行移位变换是行移位变换的逆变换，它对状态的每一行进行循环右移，其中第一行保持不变，第二行循环右移1个字节，第三行循环右移2个字节，第四行循环右移3个字节。

列混合 将每列视为GF(28)上多项式，与固定的多项式c(x)进行模x4+1乘法,要求c(x)模x4+1可逆。 表示为MixColumn(State)

c(x)是与x4+1互素的，因此是模x4+1可逆的。列混合运算也可写为矩阵乘法。设b(x)= c(x) a(x)，则

图3.21 列混合运算示意图

逆列混合InvMixColumns() 逆列混合变换是列混合变换的逆，它将状态矩阵中的每一列视为系数在 上的次数小于4的多项式与同一个固定的多项式 d(x)相乘。 d(x)满足 (‘03’x3+‘01’x2+‘01’x+‘02’) d(x)=‘01’ 由此可得 d(x)=‘0B’x3+‘0D’x2+‘09’x+‘0E’

同样，逆列混合可以写成矩阵乘法形式

密钥加 轮密钥与状态进行逐比特异或。 轮密钥由种子密钥通过密钥编排算法得到 轮密钥长度与分组密钥长度相同 表示为AddRoundKey(State,RoundKey)

AES加密过程的伪代码 Cipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*Nr+1]) begin byte state[4,Nb] state = in AddRoundKey(state, w[0, Nb-1]) for round = 1 step 1 to Nr-1 SubBytes(state) ShiftRows(state) MixColumns(state) AddRoundKey(state, w[round*Nb, (round+1)*Nb-1]) end for AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1]) Out = state end

轮函数的伪C代码 Round(State,RoundKey) { ByteSub(State); ShiftRow(State); MixColumn(State); AddRoundKey(State,Roundkey); }

结尾轮的轮函数 Round(State,RoundKey) { ByteSub(State); ShiftRow(State); AddRoundKey(State,Roundkey); }

AES解密过程的伪代码 InvCipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*Nr+1]) begin byte state[4,Nb] state = in AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1]) for round = Nr-1 step -1 downto 1 InvShiftRows(state) InvSubBytes(state) AddRoundKey(state, w[round*Nb, (round+1)*Nb-1]) InvMixColumns(state) end for SubBytes(state) ShiftRows(state) AddRoundKey(state, w[0, Nb-1]) Out = state end

解密算法的轮函数 InvRound (State, RoundKey) { InvByteSub (State); InvShiftRow (State); InvMixColumn (State); AddRoundKey (State, RoundKey) }

密钥编排 轮密钥的比特数等于分组长度乘以轮数加1 种子密钥被扩展为扩展密钥 轮密钥从扩展密钥中按顺序选取

字替代函数SubWord（）的输入为一个4字节的字，对每一个字节应用S盒得到输出字。 函数RotWord（）接受字 作为输入，执行循环移位后返回字 轮常数字数组Rcon[i]的值为 ，其中i从1开始，而不是0， 是有限域GF(28)上x(x记为{02})的指数幂。

3.4 分组码的运行模式

填充(Padding) 给定加密消息的长度是随机的，按64 bit分组时， 最后一组消息长度可能不足64 bit。可以填充一 些数字，通常用最后1字节作为填充指示符 （PI）。它所表示的十进制数字就是填充占有 的字节数。数据尾部、填充字符和填充指示符 一起作为一组进行加密。 数据 填 充 PI

主要工作模式 电码本(ECB) 密码反馈链接(CBC) 密码反馈(CFB) 输出反馈(OFB) 即使有了安全的分组密码算法，也需要采用适 当的工作模式来隐蔽明文的统计特性、数据的格 式等，以提高整体的安全性，降低删除、重放、 插入和伪造成功的机会。 电码本(ECB) 密码反馈链接(CBC) 密码反馈(CFB) 输出反馈(OFB)

电码本ECB模式 直接利用加密算法分别对分组数据组加密。 在给定的密钥下，同一明文组总产生同样的密文 组。这会暴露明文数据的格式和统计特征。 明文数据都有固定的格式，需要以协议的形式定 义，重要的数据常常在同一位置上出现，使密码 分析者可以对其进行统计分析、重传和代换攻击。

电码本ECB模式

电码本ECB模式 ECB的最大特性是同一明文分组在消息中重复出现的话，产生的密文分组也相同。 ECB在用于短数据（如加密密钥）时非常理想，因此如果需要安全地传递DES密钥，ECB是最合适的模式。 ECB的最大特性是同一明文分组在消息中重复出现的话，产生的密文分组也相同。 ECB用于长消息时可能不够安全，如果消息有固定结构，密码分析者有可能找出这种关系。

密码分组链接CBC模式 为了解决ECB的安全缺陷，可以让重复的明文分组产生不同的密文分组，CBC（cipher block chaining）模式就可满足这一要求。 加密算法的输入是当前明文分组和前一次密文分组的异或，因此加密算法的输入不会显示出与这次的明文分组之间的固定关系，所以重复的明文分组不会在密文中暴露出这种重复关系。

CBC模式示意图

CBC的优缺点 优点：能隐蔽明文的数据模式，在某种程度上能防止数据纂改，诸如重放、嵌入和删除等。 缺点：会出现传播错误，对同步差错敏感（增加或丢失一个或多个比特）。

CBC的错误传播 1. 明文有一组中有错，会使以后的密文组都受影 响，但经解密后的恢复结果，除原有误的一组外， 其后各组明文都正确地恢复。 2.若在传送过程中，某组密文组yi出错时，则该组 恢复的明文x’i和下一组恢复数据x’i+1出错。再后 面的组将不会受yi中错误比特的影响。

k-比特密码反馈CFB模式 若待加密消息必须按字符(如电传电报)或按比特处 理时，可采用CFB模式。 CFB实际上是将加密算法DES作为一个密钥流产 生器，当k＝1时就退化为前面讨论的流密码了。 CFB与CBC的区别是反馈的密文长度为k，且不是 直接与明文相加，而是反馈至密钥产生器。

CFB模式示意图

密码反馈CFB模式 CFB的优点 CFB的缺点 它特别适于用户数据格式的需要。 能隐蔽明文数据图样，也能检测出对手对于密 文的篡改。 对信道错误较敏感，且会造成错误传播。 CFB也需要一个初始矢量，并要和密钥同时进 行更换。

输出反馈OFB模式 将分组密码算法作为一个密钥流产生器，其输出的k- bit密钥直接反馈至分组密码的输入端，同时这k-bit 密钥和输入的k-bit明文段进行对应位模2相加。 克服了CBC和CFB的错误传播所带来的问题。 对于密文被篡改难以进行检测 不具有自同步能力，要求系统要保持严格的同步

比较和选用 ECB模式，简单、高速，但最弱、易受重发攻击， 一般不推荐。 CBC适用于文件加密，但较ECB慢。安全性加强。 当有少量错误时，也不会造成同步错误。 OFB和CFB较CBC慢许多。每次迭代只有少数bit 完成加密。若可以容忍少量错误扩展，则可换来 恢复同步能力，此时用CFB。在字符为单元的流 密码中多选CFB模式。 OFB用于高速同步系统，不容忍差错传播。