分组密码(全)

1、1第四讲：分组密码第四讲：分组密码分组密码体制分组密码体制代换置换网络代换置换网络DESAES 2分组密码的定义o分组密码（block cipher）是现代密码学中的重要体制之一，其主要任务是提供数据保密性o分组密码加解密速度较快 (对称密码特点)o现代分组密码发展非常快，技术较成熟（公开测评） ，使用广泛o其他密码算法设计领域有广泛应用，例如：可以用于构造伪随机数生成器、流密码、认证码和哈希函数等3 所谓分组密码是将明文分成一组一组，在密钥的控制下，经过加密变换生成一组一组的密文。具体而言，分组密码就是将明文消息序列 划分成等长的消息组在密钥 的控制下按固定的加密算法一组一组进行加密，输出一

2、组一组密文,21immm),(),(22121nnnnmmmmmmnkkkK,21),(),(22121llllcccccc4分组密码加密解密框图分组密码加密解密框图5o分组密码的思想：将明文消息编码表示后的数字序列划分成长为n的组，各组分别在密钥k控制下变换成等长的输出数字序列。o在相同密钥下，分组密码对长为n的输入明文组所实施的变换是等同的，所以只需研究对任一组明文数字的变换规则。这种密码实质上是字长为n的数字序列的代换密码。6分组密码的定义定义定义 一个分组密码体制(P, K, C, E, D)，其中P=C=0,1l ；K=0,1t. 加密变换： E：PKC, 当k K确定时，Ek为P

3、C的一一映射. 解密变换： D: CK P, 当k K确定时，Dk为C P的一一映射. Dk Ek=I7特点特点o明文、密文组长度为明文、密文组长度为n，密钥长度为，密钥长度为t，密钥量，密钥量为为2to密文中的任一位数字与该组明文所有的数字均密文中的任一位数字与该组明文所有的数字均有关有关o每组明文使用相同密钥加密每组明文使用相同密钥加密o本质是本质是0，1，2 2n-1n-1集合上的自映射或置集合上的自映射或置换换8分组密码的发展历史o二十世纪之前的密码算法 算法、密钥保密o二十世纪之后的密码算法 Kerckhoffs假设：密码分析者已有密码算法及实现的全部详细资料. Kerckhoff假

4、设蕴涵着密码的安全性完全依赖于密钥.9分组密码的发展历史o民用o不存在陷门o足够的安全强度o标准化通信需求10分组密码的发展历史o1973年5月美国联邦政府提出提出征求在传输和存储数据中保护计算机数据的密码算法的建议建议；o1975年3月，美国国家标准局(NBS) 首次公布IBM公司提出的算法Lucifer中选；o1977年1月NBS正式向社会公布，采纳IBM公司设计的方案作为非机密数据的数据加密标准 (Data Encryption Standard). DES正式成为美国联邦政府信息处理标准，即FIPS-46标准，同年7月开始生效。o此后，每隔每隔5年年美国国家保密局（NSA）对DES作新

5、的评估，并重新审定审定它是否继续作为联邦加密标准。 11分组密码的发展历史o理论强度理论强度，97年$100000的机器可以在6小时内用穷举法穷举法攻破DES.o实际攻破实际攻破的例子，97年1月提出挑战，有人利用Internet的分布式计算能力，组织志愿军连接了70000多个系统在96天后攻破.这意味着随着计算能力的增长，必须相应地这意味着随着计算能力的增长，必须相应地增加算法密钥的长度。增加算法密钥的长度。12分组密码的发展历史o1997年, 美国标准技术研究所（NIST）对DES进行再次评测并宣布：DES算法的安全强度已经不足以保障联邦政府信息数据的安全性, 所以NIST建议撤销相关标准

6、.o同时, NIST开始征集新的数据加密标准-高级数据加密标准(Advanced Encryption Standard).o新算法的分组长度为128, 支持可变密钥长度128、192、256比特.13分组密码的发展历史o1999年，NIST从提交的15个候选草案中选取了5个优良的算法作为AES的候选算法：MARS、RC6、Rijndael、Serpent和Twofish，o综合评价最终确定Rijndael算法为新的数据加密标准，2001年12月正式公布FIPS-197标准。/aes14分组密码的发展历史o欧洲于2000年1月启动了NESSIE工程, 该工程的目的是评

7、价出包含分组密码, 流密码等在内的一系列安全, 高效和灵活的密码算法.o至2000年9月, 共征集到了17个分组密码算法, 同时将TDES和AES纳入了评估范围，并作为分组密码算法的评测基准评测基准.o经过3年2个阶段的筛选，最终确定下列算法为推荐的分组密码算法：MISTY-64、Camllia-128、AES-128和SHACAL-2。 15分组密码的发展历史o日本政府在2000年成立了密码研究与评估委员会（CRYPTREC）并参考欧洲NESSIE工程的作法对密码算法的安全性和效率等问题进行评估，以备政府使用.o2002年初步拟定了推荐算法的草案, 2003年3月确定了推荐算法名单, 其中分

8、组密码算法包括：(1)分组长度为64比特的算法：CIPHERUNICORN-E、MISTY1和3-key-TDES.(2)分组长度为128比特的算法：Camellia、CIPHERUNICORN-A、Hierocrypt-3、SC2000和Rijndael128.16分组密码体制的设计准则一般包括以下内容： 1混乱原则混乱原则又称混淆原则，是指明文与密钥以及密文之间的统计关系尽可能复杂化，使破译者无法推导出相互间的依赖关系，从而加强隐蔽性。2扩散原则扩散原则扩散原则是让明文中的每一位（包括密钥中的每一位）直接和间接影响输出密文中的许多位，或者让密文中的每一位受制于输入明文以及密钥中的若干位，以

9、便达到隐蔽明文的统计特性。(明文和密钥中任何一比特值得改变，都会在某种程度上影响到密文值的变化，以防止将密钥分解成若干个孤立的小部分，然后各个击破。) 扩散和混淆是由扩散和混淆是由Shannon提出的设计密码系统的两个基本方法，提出的设计密码系统的两个基本方法，目的是抗击敌手对密码系统的统计分析。目的是抗击敌手对密码系统的统计分析。分组密码体制设计准则分组密码体制设计准则173迭代结构迭代结构选择某个较为简单的密码变换，在密钥控制下以迭代方式多次利用它进行加密变换，就可以实现预期的扩散和混乱效果。分组密码体制设计准则分组密码体制设计准则18分组密码算法的基本要求分组密码算法的基本要求 o分组长

10、度足够大分组长度足够大 防止明文穷举法奏效防止明文穷举法奏效o密钥量足够大密钥量足够大 防止密钥穷举法奏效防止密钥穷举法奏效o密码变换足够复杂密码变换足够复杂 使对手除了用穷举法破译外，无其它捷径可走，使对手除了用穷举法破译外，无其它捷径可走，有效对抗统计破译法有效对抗统计破译法19问题与对策问题与对策o分组长度足够大：分组长度足够大：代换网络十分复杂，难以控制与实现代换网络十分复杂，难以控制与实现对策对策 将分组划分为几个小段，分别设计这些小段的代换网络将分组划分为几个小段，分别设计这些小段的代换网络o密钥量足够大密钥量足够大：密码系统十分复杂，同样难以控制与实现密码系统十分复杂，同样难以控

11、制与实现对策对策 概率加权法：设计多个子系统，使用时随机抽取概率加权法：设计多个子系统，使用时随机抽取 乘积密码法：设计多个子系统，对明文多次加密乘积密码法：设计多个子系统，对明文多次加密o密码变换足够复杂：密码变换足够复杂：抗统计破译法的要求，难以简单实现抗统计破译法的要求，难以简单实现 对策对策 扩散法：将每扩散法：将每1位明文和密钥数字的影响扩散到每位明文和密钥数字的影响扩散到每1位密文数字位密文数字 混淆法：使密文与明文、密钥的统计特性复杂化混淆法：使密文与明文、密钥的统计特性复杂化揉面团揉面团乘积密码乘积密码置乱主要实现扩散，非线性代换主要实现混淆置乱主要实现扩散，非线性代换主要实现

12、混淆20SP（替换-置换）oS变换起到混淆的作用oP变换起到扩散的作用21保密系统的安全性分析 及分组密码攻击手段o攻击目的 1. 完全破译：破译使用者使用者的密钥 例：备用钥匙 2. 部分破译：恢复某些密文对应的明文 例：猜测出某些特定格式的明文 信函开头：DEAR *22保密系统的安全性分析 及分组密码攻击手段o攻击种类 被动攻击：守株待兔1. 唯密文攻击：密码分析者有一个或更多的用同一个密钥加密的密文，通过对这些截获的密文进行分析得出明文或密钥.2. 已知明文攻击：除待解的密文外，密码分析者有一些明文和用同一个密钥加密这些明文所对应的密文.23保密系统的安全性分析 及分组密码攻击手段主动

13、攻击：主动出击，先发制人 3. 选择明文攻击：密码分析者可得到所需要的任何明文所对应的密文，这些密文与待解的密文是用同一个密钥加密得来的. 4. 选择密文攻击：密码分析者可得到所需要的任何密文所对应的明文，解密这些密文所使用的密钥与解密待解的密文的密钥是一样的.24保密系统的安全性分析 及分组密码攻击手段o攻击手段 1. 穷举法：当分组长度n较小时，攻击者可以有效地穷举明文空间，得到密钥。 2. 差分分析 3. 线性分析 4. 相关密钥 5. 侧信道攻击 利用一些先验知识（如字典攻击），达到快速攻击的目的；攻击复杂度小于穷举攻击，则理论理论有效2526 DES(Data Encryption

14、Standard)算法 一种用56位密钥来加密64位数据的方法。o发明人：nIBMIBM公司公司 W.TuchmanW.Tuchman和和C.Meyer.C.Meyer.o基础：n19671967年美国年美国Horst FeistelHorst Feistel提出的理论；提出的理论；o产生：n美国国家标准局美国国家标准局19731973年开始研究除国防部外的其它部门的年开始研究除国防部外的其它部门的计算机系统的数据加密标准，于计算机系统的数据加密标准，于19731973年年5 5月月1515日和日和19741974年年8 8月月2727日先后两次向公众发出了征求加密算法的公告，最终日先后两次向

15、公众发出了征求加密算法的公告，最终选定选定DESDES。DES算法概述27 DES技术特点o 分组加密算法：明文和密文为64位分组长度；o 对称算法：加密和解密除密钥编排不同外，使用同一算法；o DES的安全性不依赖于算法的保密，安全性仅以加密密钥的保密为基础；o 密钥可为任意的56位数，具有复杂性，使得破译的开销超过可能获得的利益；o 采用替代和置换的组合，共16轮；o 只使用了标准的算术和逻辑运算，易于实现28DES算法概述o明文和密文分组长度为64比特o算法包含两部分：迭代加解密和密钥编排oFeistel结构（加解密相似）：加密和解密除密钥编排不同外, 完全相同 （思考：1 为什么解密函

16、数不是逆函数？2 为什么不用逆函数来解密）o密钥长度：56比特（DES的密钥空间：256），每7比特后为一个奇偶校验位（第8位），共64比特o轮函数采用混乱和扩散的组合，共16轮29DES算法概述oDES的基本工作原理:用56位的密钥对64位长的数据块进行16轮加密处理由此得到64位长的密文。303132oDES算法的整体结构Feistel结构oDES算法的轮函数oDES算法的密钥编排算法oDES的解密变换33DES算法的整体结构Feistel结构DES是从1975年被美国联邦政府确定为非敏感信息的加密标准，它利用56比特长度的密钥K来加密长度为64比特的明文，得到64比特长的密文. 1997

17、年，由于计算机技术迅速发展，DES的密钥长度已经太短，NIST建议停止使用DES算法作为标准. 目前，二重DES和三重DES仍然广泛使用.34DES算法的整体结构Feistel结构K1K16思考：攻击者可以剥离IP置换和逆置换？35DES算法的整体结构Feistel结构1. 给定明文，通过一个固定的初始置换IP来重排输入明文块P中的比特，得到比特串P0=IP(P)=L0R0，这里L0和R0分别是P0的前32比特和后32比特IP5850423426181026052443628201246254463830221466456484032241685749413325179159514335271

18、9113615345372921135635547393123157初始置换IP36DES算法的整体结构Feistel结构2. 按下述规则进行16次迭代，即1i16 这里 是对应比特的模2加，f是一个函数（称为轮函数）；16个长度为48比特的子密钥Ki(1i16)是由密钥k经密钥编排函数计算出来的.),(LR 1-RL1iiiiiiKRfLi-1 Ri-1F+Li RiKi37DES算法的整体结构Feistel结构IP-1408481656246432397471555236331386461454226230375451353216129364441252206028353431151195

19、92734242105018582633141949175725初始置换的逆置换IP3.对比特串R16L16使用逆置换IP-1得到密文C，即C=IP-1 (R16L16)。（注意注意L L1616和和R R1616的相反顺序的相反顺序）38分组密码的轮函数函数f以长度为32比特串Ri-1作为第一输入，以长度为48比特串Ki作为第二个输入，产生长度为32比特的输出：39分组密码的轮函数Ri-1KiE (Ri-1)B1B2B3B4B5B6B7B8S1S2S3S4S5S6S7S8C1C2C3C4C5C6C7C8f (Ri-1 ,Ki)+PEE扩展密钥加S盒代换P置换40o A=R(32 bits)J

20、=K(48 bits)EE(A)为48 bits+B1 B2 B3 B4 B5 B6 B7 B8 S1S2S3S4S5S6S7S8C1 C2 C3 C4 C5 C6 C7 C8P32 bits F(A,J)B写成8个6比特串DES 的的F函数函数41分组密码的轮函数E扩展扩展：Ri-1根据扩展规则扩展为48比特长度的串；E比特选择表321234545678989101112131213141516171617181920212021222324252425262728292829303132142分组密码的轮函数密钥加密钥加：计算 ，并将结果写成8个比特串，每个6比特，B=B1B2B3B4B5

21、B6B7B8.1()iiE RK43分组密码的轮函数S盒代换盒代换：使用8个S盒S1S8. 每个Si是一个固定的4*16阶矩阵，其元素取015之间的整数.给定长度为6的比特串，如Bj=b1b2b3b4b5b6，Sj(Bj)计算如下: 1) b1b6两个比特确定了Sj的行r的二进制表示（0r3）， 2) b2b3b4b5四个比特确定了Sj的列c的二进制表示（0c15）， 3) Sj(Bj)定义成长度为4的比特串的值Sj(r,c)。由此可以算出Cj=Sj(Bj),1j8.44S1 14413121511831061259070157415213110612119538411481362111512

22、97310501512824917511314100613S2 1518146113497213120510313471528141201106911501471110413158126932151381013154211671205149S3 1009146315511312711428137093461028514121115113649815301112125101471101306987415143115212S4 71314306910128511124151281156150347212110149106901211713151314528431506101138945111272

23、14S52124171011685315130149141121247131501510398642111101378159125630141181271142136150910453S61211015926801334147511101542712956113140113891415528123704101131164321295151011141760813S74112141508133129751061130117491101435122158614111312371410156805926111381410795015142312S813284615111109314501271151

24、3810374125611014927114191214206101315358211474108131512903561145分组密码的轮函数P置换1672021291228171152326518311028241432273919133062211425P置换置换：长度为32比特串C=C1C2C3C4C5C6C7C8, 根据固定置换P(*)进行置换，得到比特串P(C).46oDES中其它算法都是线性的，而S盒运算则是非线性的，S盒不易于分析，它提供了更好的安全性；所以，S盒是算法的关键所在。o提供了密码算法所必须的混淆作用；o改变S盒的一个输入位至少要引起两位的输出改变；47 P盒置换：

25、盒置换： P P置换使得一个置换使得一个S S盒的输出对下一轮多个盒的输出对下一轮多个S S盒产生影盒产生影响，形成响，形成雪崩效应雪崩效应：明文或密钥的一点小的变动都引明文或密钥的一点小的变动都引起密文的较大变化起密文的较大变化48雪崩效应 Avalanche Effect 明文或密钥的一比特的变化，引起密文许多比特的改变。如果变化太小，就可能找到一种方法减小有待搜索的明文和密文空间的大小。o如果用同样密钥加密只差一比特的两个明文： 000000000000000.00000000 100000000000000.00000000 3次循环以后密文有21个比特不同；16次循环后有34个比特不

26、同。o如果用只差一比特的两个密钥加密同样明文： 3次循环以后密文有14个比特不同，16次循环后有35个比特不同49已知主密钥为64位（其中每个字节的第8位作为奇偶校验位）。略去奇偶校验位，DES的密钥由64位减至56位，对这56位密钥进行如下置换（置换选择1，pc-1） 经置换后的56位密钥，被分成左右两部分，每部分28位。子密钥生成57494133251791585042342618102595143352719113605244366355473931231576254463830221466153453729211352820124LRPC1变换表50循环左移 每轮中，这两部分分别循环左

27、移l位或2位。下表给出了每轮移动的位数。轮轮12345678910111213141516位位数数1122222212222221子密钥生成51压缩置换（也称为置换选择2 ，pc-2 ）：将56位密钥压缩成48位。 置换：例如，原第14位在输出时移到了第1位。 压缩：第9、18、22、25以及第35、38、43、54均被略 去。1417112415328156211023191242681672720132415231374755304051453348444939563453464250362932子密钥生成PC2变换表52子密钥生成53DES算法的密钥编排算法根据密钥K来获得每轮中所使用的

28、子密钥Ki:KPC-1C0D0C1D1C16D16LS1LS1LS2LS16LS2LS16PC-2PC-2K1K1654oPC-1(Permuted Choice)：n负责取出由用户提供的56bits密钥（即去除第8，16，24，32，40，48，56，64位），并置换n将56bits分成左右两半，并分别存到C0和D0中o计算第i个子密钥ki （i=1,2,3,., 16)n将Ci-1和Di-1分别循环左移指定位数，对应的结果分别存到Ci和Di中n将Ci和Di整合后，进行压缩置换（PC-2）：o抛弃8位，得到48位的子密钥；并置换2021-10-11主讲： 赵洋 课程：信息安全概论5455DE

29、S算法的密钥编排算法1. 给定64比特密钥K，根据固定的置换PC-1来处理K得到PC-1（K）=C0D0，其中C0和D0分别由最前和最后28比特组成PC-157494133251715850423426102595143351911360524463554739312376254463830146615345372113528201256DES算法的密钥编排算法2. 对1i16， DES的每一轮中使用K的56比特中的48个比特，具体选取位置由下表确定57轮轮 35127103625589334350601844112149343542413591761415301347236122962537

30、281439546321532038317轮轮 4351159499425817273444257605150331819262552431455562142831753631346202112612338475374221554轮轮 51960433358264211118575141443534172310936275029394661121554374728304563457223120215566238轮轮 634427174210265060241352557191815152595849113413233045636238213112145520472954615453953462

31、2轮轮 75257111265910344451251994132503536434233601828714294746225156361394311338536255202337306轮轮 8364160501043591857359358255251341949272617442125461133130620624745235515282237463947211453轮轮 1105134604917335729194233526254458591362718412228395437447305532329612138631520451413625531轮轮 2243265241925495

32、91113460271817365051585719103314203146296339222845152153133055712376554472358轮轮 15262501136334944182535581951424160910175243345738135575320634621639451437541231561302915447轮轮 161859423572541361017275011433433521294435264930547624512553813613137629464232853222176339轮轮 13583417433365211505723551189442

33、7414249191016074520392221281553384144662313633730626147512轮轮 144218127524936603441519352585711252633359504454294236512623722556130537284721144645312063轮轮 1125149103531943176034571850411159449525142332739142145453294722754615385545286623130123713轮轮 1295033591952327144184123425604357583635261711236155

34、5383713316542030622239291253461514632128轮轮 9573352422355110492716050174443261141191893659446535523226112543937154772014293831636213645轮轮 1041173626511935593311504434157271060253258494355303720764563382321623134461132215474628532959DES算法的密钥编排算法3. 计算Ci=LSi(Ci-1)和Di=LSi(Di-1)，且Ki=PC-2(CiDi)，LSi表示循环左移两个

35、或一个位置, 具体地, 如果i=1,2,9,16就移一个位置，否则就移两个位置, PC-2是另一个固定的置换.60DES算法的密钥编排算法PC-2141711241532815621102319124268167272013241523137475530405145334844493956345346425036293261初始置换IP和逆初始置换IP-1o初始置换IPn将64 bit明文的位置进行置换，得到一个乱序的64 bit明文组n而后分成左右两段，每段为32 bit，以L0和R0表示o逆初始置换IP-1。将16轮迭代后给出的64 bit组进行置换，得到输出的密文组。输出为阵中元素按行读

36、得的结果。62初始置换IP和逆初始置换IP-14084816562464323974715552363313864614542262303754513532161293644412522060283534311511959273424210501858263314194917572558501234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157IP置换表IP-1置换表63DES的解密变换DES的解密与加密一样使用相同的算

37、法，它以密文y作为输入，但以相反的顺序使用密钥编排K16,K15,K1, 输出的是明文x为什么？64o在经过所有的替代、置换、异或和循环移动之后，获得了这样一个非常有用的性质：加密和解密可使用相同的算法。oDES解密结构与其加密结构是对称相似的，使得能用相同的函数来加密或解密每个分组。 二者的唯一不同之处是密钥的次序相反。这就是说，如果各轮的加密密钥分别是K1，K2，K3，K16，那么解密密钥就是K16，K15，K14，K1。为各轮产生密钥的算法也是循环的。密钥向右移动，每次移动位数为0，1，2，2，2，2，2，2，1，2，2，2，2，2，2，1。DES的解密变换65 iiiikRfRL,1

38、DES的解密变换66子密钥子密钥子密钥IPIP子密钥子密钥子密钥子密钥DES的解密变换67 已知明文m=computer，密钥k=program，用ASCII码 表示为： m=01100011 01101111 01101101 01110000 01110101 01110100 01100101 01110010 k=01110000 01110010 01101111 01100111 01110010 01100001 01101101 因为k只有56位，必须插入第8，16，24，32，40，48，56，64位奇偶校验位，合成64位。而这8位对加密过程没有影响。DES举例68m经过IP

39、置换后得到 L0= 11111111 10111000 01110110 01010111 R0= 00000000 11111111 00000110 10000011密钥k通过PC-1得到 C0= 11101100 10011001 00011011 1011 D0= 10110100 01011000 10001110 0110再各自左移一位，通过PC-2得到48位 k1=00111101 10001111 11001101 00110111 00111111 00000110R0（32位）经E作用扩展为48位， 10000000 00010111 11111110 10000000 1

40、1010100 00000110DES举例69再和k1作异或运算得到（分成8组） 101111 011001 100000 110011 101101 111110 101101 001110通过S盒后输出位32比特， 01110110 00110100 00100110 10100001S盒的输出又经过P置换得到 01000100 00100000 10011110 10011111计算L1和R1 结果是： 00000000 11111111 00000110 10000011 1 0 1 1 1 0 1 1 1 0 0 1 1 0 0 0 1 1 1 0 1 0 0 0 11001000迭

41、代16次以后，得到密文： 01011000 10101000 01000001 10111000 01101001 11111110 10101110 00110011DES举例70高级加密标准AES 美国国家标准和技术协会（NIST）征集并进行了几轮评估、筛选，才产生了高级加密标准（Advanced Encryption Standard，简称AES）。 1997年4月，NIST向全世界发起征集AES的活动，对AES的基本要求是：强度相当于三重DES、但应该比三重DES更有效、数据分组长度为128bit、密钥长度为128/192/256bit，而且能在全世界范围内免费使用 2000年10月，

42、Rijndael算法最终被选择作为高级加密标准AES。Rijndael算法是由比利时的密码学家Joan Daemen和Vincent Rijmen设计的，算法的原型是Square算法。711997年4月15日，美国ANSI发起征集AES（advanced encryption standard）的活动，并为此成立了AES工作小组。此次活动的目的是确定一个非保密的、可以公开技术细节的、全球免费使用的分组密码算法，以作为新的数据加密标准。1997年9月12日，美国联邦登记处公布了正式征集AES候选算法的通告。对AES的基本要求是： 比三重DES快、至少与三重DES一样安全、数据分组长度为128比特

43、、密钥长度为128/192/256比特。721998年8月12日，在首届AES候选会议（first AES candidate conference）上公布了AES的15个候选算法，任由全世界各机构和个人攻击和评论，这15个候选算法是CAST256、CRYPTON、E2、DEAL、FROG、SAFER+、RC6、MAGENTA、LOKI97、SERPENT、MARS、Rijndael、DFC、Twofish、HPC。1999年3月，在第2届AES候选会议（second AES candidate conference）上经过对全球各密码机构和个人对候选算法分析结果的讨论，从15个候选算法中选出

44、了5个。73这5个是RC6、Rijndael、SERPENT、Twofish和MARS。2000年4月13日至14日，召开了第3届AES候选会议（third AES candidate conference），继续对最后5个候选算法进行讨论。2000年10月2日，NIST宣布Rijndael作为新的AES。至此，经过3年多的讨论，Rijndael终于脱颖而出。（以安全性、性能、大小、实现特性为标准） 2001年：正式发布AES标准Rijndael 由比利时的Joan Daemen和Vincent Rijmen设计，算法的原型是Square算法。74757677Rijndael Rijndael

45、 算法是由两位算法是由两位比利时的密码专家发明的，比利时的密码专家发明的，它很快而且所需的内存不它很快而且所需的内存不多，且算法非常可靠多，且算法非常可靠Rijndael Rijndael 算法的设计策算法的设计策略是针对差分和线性分析略是针对差分和线性分析提出来的，是一个分组迭提出来的，是一个分组迭代密码，具有可变的分组代密码，具有可变的分组长度和密钥长度长度和密钥长度Rijndael Rijndael 汇聚了安全性汇聚了安全性能、效率、可实现性和灵能、效率、可实现性和灵活性等优点活性等优点78破译时间破译时间宇宙年龄宇宙年龄10101111年年79AESAES的算法结构的算法结构采用采用S

46、quareSquare结构结构10/12/14轮迭代轮迭代80AESAES的数据结构的数据结构按按列列填填充充81基本运算基本运算o字节代换字节代换SubByteso行移位行移位ShiftRowso列混合列混合MixColumnso轮密钥加轮密钥加AddRoundKeySquareSquare结构结构（方形结构）（方形结构）有有10/12/1410/12/14轮迭代轮迭代AESAES的算法结构的算法结构最后最后1 1轮没有列混合轮没有列混合82o采用乘积密码迭代，实现扩散与混淆。采用乘积密码迭代，实现扩散与混淆。o每一轮都使用代换和混淆技术并行地处理每一轮都使用代换和混淆技术并行地处理整个数据

47、分组。整个数据分组。o无论是加密还是解密，除了最后一轮少了无论是加密还是解密，除了最后一轮少了列混合运算外，其它各轮都是按照相同顺列混合运算外，其它各轮都是按照相同顺序依次执行四种基本运算（解密时为四种序依次执行四种基本运算（解密时为四种基本运算的逆运算）。基本运算的逆运算）。o解密算法完全是加密算法的倒推，加、解解密算法完全是加密算法的倒推，加、解密原理清晰，便于理解。密原理清晰，便于理解。o和其它分组密码相同，轮密钥在解密时颠和其它分组密码相同，轮密钥在解密时颠倒顺序使用。倒顺序使用。AESAES结构特点结构特点83AES的加密过程1 1AESAES的加密算法描述的加密算法描述 在在AES

48、AES中，将明中，将明文和密文长度固定为文和密文长度固定为128bit128bit，密钥长度可密钥长度可以使用以使用128128、192192和和256bit256bit三者中的任意一种三者中的任意一种。 明文及加密过程的中间结果都称为状态明文及加密过程的中间结果都称为状态StateState，状态，状态StateState被表示成矩阵，矩阵的每个元素是一个字节，并看成是有限域被表示成矩阵，矩阵的每个元素是一个字节，并看成是有限域GF(28)中中的一个元素，矩阵的行数为的一个元素，矩阵的行数为4 4，列数为，列数为NbNb。密钥被表。密钥被表示成示成4 4行行NkNk列的矩阵，列的矩阵，NkN

49、k等于密钥长度比特数除以等于密钥长度比特数除以3232，加密的，加密的轮数用轮数用NrNr表示。表示。 当当NkNk等于等于4 4时，整个算法由时，整个算法由1010轮组成。每轮由轮组成。每轮由4 4个变换模块个变换模块组成，分别是：组成，分别是：字节代换（字节代换（ByteSubByteSub）、行移位（）、行移位（ShiftRowShiftRow）、）、列混合（列混合（MixColumnMixColumn）、密钥加（）、密钥加（AddRoundKeyAddRoundKey），），最后一轮略最后一轮略有不同，没有列混合。加密框图如图所示有不同，没有列混合。加密框图如图所示 84AESAES加

50、密算法框图加密算法框图85加密过程描述如下：(1) 初始轮密钥加。给定一个明文M和种子密钥K0，将它们以矩阵排列并进行异或加法运算； (2) Nr-1轮迭代。对前Nr-1轮中的每一轮，用S盒进行一次字节代换操作（ByteSub）；对代换的结果做行移位操作（ShiftRow）；接着做列混合变换（MixColumn）；再进行AddRoundKey操作。轮迭代中的密钥Ki由种子密钥K0通过密钥扩展算法产生；(3) 最后一轮变换。在最后一轮中与前面各轮稍有不同，依次进行ByteSub、ShiftRow和AddRoundKey操作。862加密轮变换(1) 字节代换（ByteSub） 字节代换ByteSu

51、b (State)是一个关于字节的非线性变换，可以使用S盒查表得到输出。 AES定义了一个S盒，是由1616个字节组成的方形表，包含了8位值所能表示的256种可能的变换。对于已知的某一字节作为S盒的输入，把该字节的高4位作为行号，低4位作为列号，查表取出S盒中对应行列交叉点的元素作为输出。例如，S(8C)=64，S(B3)=6D。87o字节代换示意图88o利用利用S S盒将中盒将中间态间态s s中的每中的每个字节非线个字节非线性变换为另性变换为另一个字节。一个字节。o实现每个字实现每个字节数据中各节数据中各位的混淆。位的混淆。8990【例】设当前的State为计算ByteSub (State)

52、。 查表知S(51)=D1，S(67)=85，依次类推，所有字节查表完成可得725477736106879264422769436751FC402058845671931091851725477736106879264422769436751FFACABFBFADFC91(2) 行移位（ShiftRow） 在行移位变换中，状态矩阵State中的每一行将以字节为单位，循环左移不同的位移量。State的第一行保持不变，第二行循环左移一个字节，第三行循环左移两个字节，第四行循环左移三个字节。92o行移位示意图93行移位运算行移位运算ShiftRows ShiftRows 中间态中间态s s中各行的循

53、环左移中各行的循环左移第第0 0行不移位行不移位第第1 1行循环左移行循环左移1 1个字节个字节第第2 2行循环左移行循环左移2 2个字节个字节第第3 3行循环左移行循环左移3 3个字节。个字节。行移位运算打行移位运算打乱了中间态乱了中间态s s中中各字节的位置各字节的位置关系，在功能关系，在功能上相当于置乱上相当于置乱操作，可以实操作，可以实现扩散效果。现扩散效果。94【例】设当前的State为计算ShiftRow (State)按行移位变换方法可得402058845671931091851FFACABFBFAD2058404568107193918514020588456719310918

54、51FFBACAFBFADFFACABFBFAD953) 列混合(MixColumn) 列混合变换将State乘以一个固定的矩阵A，对State逐列进行变换，每一列中的每个字节被变换成一个新值，直到4列都变换完毕。 相乘后得到的乘积矩阵，其中每个元素均是一行和一列中所对应元素的乘积之和。这里的乘法和加法都是定义在有限域GF(28)上的。96o列混合运算示意图97【例】设当前的State为计算MixColumn (State)205840456810719391851FFBACAFBFAD059221039503697519205840456810719391851020101030302010

55、10103020101010302EBEFDDBDFEBCBDFFBACAFBFAD9899100(4) 密钥加（AddRoundKey）密钥加是将轮密钥Ki简单地与状态State进行逐比特异或。【例】列混合后的结果Ai-1与轮密钥Ki分别为0592210395036975191EBEFDDBDFEBCBDAi6360664774677244774477FBBDDFACCEKi求轮密钥加后的结果求轮密钥加后的结果C Ci i。66457482477962966396736360664774677244774477059221039503697519FEDDDFDAFEFBBDDFACCEEBE

56、FDDBDFEBCBDCi101o密钥加运算示意图1023密钥扩展算法由密钥扩展算法将种子密钥扩展成为扩展密钥的计算过程如下当种子密钥长度为128bit时，这里的Nk4，其中：temp=SubByte (RotByte (Wi-1) Rconi RotByte ( )表示循环左移一个字节，如W=(a0,a1,a2,a3)，则RotByte (W)= (a1,a2,a3,a0)；SubByte( )是S盒的字节代换；Rconi为轮常数 )0mod( 1)0mod( kkkkNiiWNiWNitempNiWiW103【例】在AES加密算法中，假定种子密钥K0长度为128bit，它的值为K0= 06

57、 07 08 09 0A 0B 0C 0D 0E 0F 00 01 02 03 04 05计算第一轮的子密钥K1的值。05010090400008030007020006),(32100DCFBEAWWWWK其中其中W0 = 06 07 08 09W1 = 0A 0B 0C 0DW2 = 0E 0F 00 01W3 = 02 03 04 05104根据密钥扩展算法可计算出W4 = SubByte (RotByte (W3) Rcon1 W0= SubByte(03 04 05 02) Rcon1 W0= (7B F2 6B 77) (01 00 00 00) (06 07 08 09)= 7C

58、 F5 63 7EW5 = W1 W4 = (0A 0B 0C 0D) (7C F5 63 7E) = 76 FE 6F 73W6 = W2 W5 = (0E 0F 00 01) (76 FE 6F 73) = 78 F1 6F 72W7 = W3 W6 = (02 03 04 05) ( 78 F1 6F 72) = 7A F2 6B 77777273766663215778767),(76541EBFFFFFEFACWWWWK105 AES算法的整个解密过程与加密过程类似，要依次完成：初始密钥加，Nr-1轮解密逆变换，最后一轮逆变换操作。 解密轮变换使用前面加密轮变换的逆变换函数，解密算法

59、中的一轮与加密算法的一轮有类似的结构，依次进行逆字节代换，逆行移位，逆列混合和密钥加。 oAES的解密算法完全由加密算法倒推而来。o与加密算法相比，主要的不同之处有两点。n四种基本运算用它们的逆运算取代。n轮密钥颠倒顺序使用。AES的解密过程106InvByteSub ( )是ByteSub ()的逆变换，通过查表4-12逆S盒来实现。InvShifRow( )是ShifRow()的逆变换，对State的各行进行一定量的循环移位（Nb=4）。 第0行不移位； 第1行循环右移1个字节； 第2行循环右移2个字节； 第3行循环右移3个字节。InvMixColumn( )是MixColumn( )的逆

60、变换，可由如下矩阵乘法定义107 AES算法举例算法举例 设明文分组长度和密钥长度均为128比特，则Nb=Nk=4，Nr=10。已知用16进制表示的输入信息和种子密钥信息分别如下： B32 43 f6 ad 88 5a 30 8d 31 31 98 a2 e0 37 07 34 K2b 7e 15 16 28 ae d2 a6 ab f7 15 88 09 cf 4f 3c1. 首先计算子密钥。 2. 求第一轮加密结果。其它各轮的加密结果可以依照上述方法计算。经10轮加密，最后得到密文 1081) 该算法对密钥的选择没有任何限制，还没有发现弱密钥和半弱密钥的存在。2) 可抗击穷举密钥的攻击。因