《密码学基础》课件 （张薇） 第3、4章　AES、序列密码

高级加密标准4学时AES概述Rijndael加密算法主要内容了解高级加密标准的设计思想掌握AES算法的运算过程教学目的1997年4月15日，（美国）国家标准技术研究所（NIST）发起征集高级加密标准AES的活动，目的是确定一个非保密的、可以公开技术细节的、全球免费使用的分组密码算法，作为新的数据加密标准。1997年9月12日，美国联邦登记处公布了正式征集AES候选算法的通告。第一节AES

概述第一节AES概述对AES的基本要求：比三重DES快至少与三重DES一样安全数据分组长度为128比特密钥长度为128/192/256比特。AESBackground第一节AES

概述1998年8月，首届AES会议，指定15个候选算法。1999年3月22日，第二次AES会议，候选名单减少为5个：RC6，Rijndael，SERPENT，Twofish和MARS。2000年4月13日，第三次AES会议，对这5个候选算法的各种分析结果进行了讨论。2000年10月2日，NIST宣布了获胜者—Rijndael算法，2001年11月出版了最终标准FIPSPUB197。AESBackground第一节AES

概述Rijndael加解密过程第六节高级加密标准AES唯一的非线性运算，代替表（S盒）可逆，由两个变换构成：首先在GF(28)中模m(x)取乘法逆，m(x)=x8+x4+x3+x+1，0映射到自身；然后经过一个仿射变换字节代替（Bytesub）第二节Rijndael加密算法逆运算（InvByteSub）先经过仿射变换的逆变换作用之后，再在GF(28)中模m(x)取乘法逆。字节代替（Bytesub）第二节Rijndael加密算法行移位（ShiftRow）第二节Rijndael加密算法状态行移位不同的位移量第0行不移动第1行循环左移C1字节第2行循环左移C2字节第3行循环左移C3字节，逆运算（InvShiftRow）

后面3行分别循环左移：

Nb-C1字节

Nb-C2字节

Nb-C3字节行移位（ShiftRow）第二节Rijndael加密算法Rijndael加密程序S=B⊕K0；Fori=1toNr-1 S=ByteSub(S)；

S=ShiftRow(S)；

S=MixColumn(S)；

S=Ki⊕S；S=ByteSub(S)；S=ShiftRow(S)；S=KNrS；Rijndael算法第二节Rijndael加密算法注：最后一圈无列混合Rijndael解密程序S=KNr⊕C；S=InvShiftRow(S)；S=InvByteSub(S)；S=KNr⊕

S；Fori=Nr-1to1 S=KiS；

S=InvMixColumn(S)；

S=InvShiftRow(S)；

S=ByteSub(S)；

S=K0⊕S；Rijndael算法第二节Rijndael加密算法将16字节初始密钥扩展为156字节（44字）的扩展密钥；扩展密钥的前四个字直接由输入密钥中复制，即w[0]~w[3]；w[i]的值依赖于w[i-1]和w[i-4]密钥扩展算法第二节Rijndael加密算法（迭代圈数为10时）对于下标为4的倍数的密钥字，其产生方法更为复杂，表示为函数g包括的运算步骤有：字循环（RotWord）：使一个字中的4个字节循环左移一个字节字节代换（SubWord）：利用S盒对输入字中的每个字节进行代替字循环与字节代换的结果再与轮常量Rcon[j]相异或密钥扩展算法第二节Rijndael加密算法无弱密钥或补密钥能有效抵抗差分分析和线性分析迭代圈数大于6时可抗截断差分分析圈数大于7时可抗Square攻击密钥量大，穷举攻击较困难Rijndael的安全性第二节Rijndael加密算法第一节序列的随机性２学时序列的随机性随机性的概念及参数随机性假设伪随机数发生器线性同余发生器用密码编码产生随机数BBS发生器主要内容掌握随机性的含义及衡量方法理解随机性假设的含义掌握线性同余发生器的原理及参数选择理解如何用密码产生随机数理解BBS发生器的原理教学目的随机序列：不能重复产生的序列几个相关概念真随机——不能重复产生密码学意义上的随机——不能预测伪随机——看起来是随机的，并能通过许多随机性测试第一节序列的随机性真随机数发生器（TRNG）：利用物理方法实现的随机数发生器，它是自然界随机的物理过程（所产生物理现象的不确定性）的反映，即使算法等重要信息被暴露，都无法猜测其结果如何产生真随机数1．若序列的周期为偶数，则在一个周期内，0、1的个数相等；若周期为奇数，则在一个周期内，0、1的个数相差1。2．在一个周期内，长度为l的游程数占游程总数的1/2l，且对于任意长度，0游程与1游程个数相等。3．所有异相自相关函数值相等。Golomb随机性假设第一节序列的随机性伪随机数发生器——将一个短的随机数“种子”扩展为较长的伪随机序列的确定算法。线性同余发生器（Linearcongruentialgenerator）用加密方式产生随机数BBS发生器伪随机数发生器第一节序列的随机性评价线性同余发生器有以下准则：（1）完整周期：即在一个周期中，０至m-1之间的数都出现。（2）满足随机性测试。（3）可以高效地实现。线性同余法的优点：方便，快速；缺点：除初值外，其它数字都用确定算法产生。第一节序列的随机性线性同余发生器线性同余发生器先后被JimReeds和JoanBoyar破译后者还破译了二次同余发生器Xn=(ax2n-1+bxn+c)modm和三次同余发生器Xn=ax3n-1+bx2n-1+cxn-1+d线性同余发生器NIST为银行电子支付系统建议的标准算法，被PGP采纳，在Internet中使用。方法：用三重DES的EDE模式产生，使用两个密钥K1，K2两个驱动随机数：初始化时，设DT0为初始时刻的日期和时间(64bit)，V0为种子密钥(64bit)输出：64bit的随机数Ri和更新后的Vi+1伪随机数发生器第一节序列的随机性（3）ANSIX9.17伪随机数产生器

每一时刻要进行三次加密，相当于9次DES加密，由两个伪随机数驱动。伪随机数发生器第一节序列的随机性用K1，K2对DT0加密，结果与V0相加，再对其加密，得到R0BlumBlumShub产生器（BBS发生器）:

利用数论方法产生伪随机数选择两个大素数p，q，满足p≡q≡3mod4；计算其乘积n=pq；选择随机数s，(s,n)=1；通过以下公式迭代计算序列{Bi}伪随机数发生器第一节序列的随机性BBS发生器在密码学意义上是相对安全的，但计算量比较大。伪随机数发生器第一节序列的随机性第二节序列密码的原理2学时序列密码的基本概念加密方式密钥序列生成器线性反馈移位寄存器与m序列线性反馈移位寄存器移位寄存器的周期及m序列序列的线性复杂度与B-M算法主要内容明文符号序列与密钥符号序列逐个加密密钥序列z=z1z2…的第i个符号加密明文序列m=m1m2…的第i个符号，即若密钥序列重复使用，则称为周期序列密码，否则，就是一次一密密码。序列密码的加密方式第二节序列密码的基本概念由密钥流生成器生成第i个密钥取决于第i时刻密钥生成器的内部状态和初始密钥。对序列密码的安全性有两个基本要求：根据密钥序列以前的状态，不能很容易地推导出后续状态，即密钥序列要有足够高的随机性；传输密钥的秘密信道必须足够安全。序列密码中的密钥密码的安全性主要取决于所用密钥的随机性，所以设计序列密码的核心问题是设计随机性较好的密钥流生成器设计密钥流生成器的关键：寻找状态转移函数和输出函数，使输出的密钥序列有良好的伪随机性。密钥流生成器第二节序列密码的基本概念Rueppel将密钥流生成器分为两部分：驱动部分和非线性组合部分。驱动部分控制生成器的状态，并为非线性组合部分提供周期长、统计性能良好的序列；非线性组合部分利用这些序列组合出满足要求的密钥序列。密钥流生成器第二节序列密码的基本概念根据密钥序列的产生方法，可将序列密码可分为两类：同步序列密码（SynchronousStreamCipher）：状态转移函数与明文字符无关自同步序列密码（Self-SynchronousStreamCipher）：状态转移函数与明文字符相关。在同步流密码中，只要发送端和接收端有相同的种子或实际密钥和内部状态，就能产生出相同的密钥流，此时，认为发送端和接收端的密钥生成器是同步的。序列密码的分类第二节序列密码的基本概念衡量密码体制安全性的方法计算安全性（computationalsecurity），又称实际安全性（practicalsecrecy）：利用已有的最好的方法破译该系统所需要的努力超过了敌手的破译能力。可证明安全性（provablesecurity）：能用严格的数学方法证明破译该体制等价于某个困难问题。无条件安全性（unconditionalsecurity）或完善保密性（perfectsecrecy）：在信息论意义上是安全的。理论保密的密码体制定理若某一密码系统的明文数、密文数和密钥数都相等，则该密码体制完全保密的充要条件是：将某一明文加密成某一密文的密钥只能有一个；所有密钥都是等概率的。理论保密的密码体制组成：一系列存储单元、若干个乘法器和加法器通过电路连接而成。假设共有n个存储单元（此时称该移位寄存器为n级），每个存储单元可存储一比特信息，在第i时刻各个存储单元中的比特序列(aiai+1…ai+n-1)称为移位寄存器的状态，为初始状态。线性反馈移位寄存器第三节线性反馈移位寄存器与m序列给定初态（101），按照反馈函数可求出各个时刻的状态及输出.状态在第5时刻开始重复，因此输出序列的周期是4，输出序列为1011101110111011……线性反馈移位寄存器（LFSR）第三节线性反馈移位寄存器与m序列定理5-1

n级LFSR的周期≤2n