第8讲-AES候选算法

第8讲AES-Rijndael上海交通大学郑东[e-mail]候选算法背景DES已走到了它生命的尽头56比特密钥实在太小DES的软件实现效率低（设计主要针对硬件实现）1997年4月15日美国国家标准和技术研究所（NIST）征集AES（AES—AdvancedEncryptionStandard）算法并成立了AES工作组。目的是为了确定一个非保密的、公开披露的、全球免费使用的加密算法，用于保护下一世纪政府的敏感信息。也希望能够成为保密和非保密部门公用的数据加密标准（DES）。AES候选算法要求---比三重DES快，至少还要一样的安全，---应当具有128比特分组长度和256比特密钥长度（不过必须支持128和192比特的密钥）---还应该具有较大的灵活性。AES候选算法（续2）评选过程中采用的方法1.用量化的或定性的尺度作为选择的标准；2.选择一种以上的算法；3.选择一个备用算法；4.考虑公众的建议以改进算法。AES候选算法（续3）1998年8月20日，NIST在第一阶段讨论（AES1）中宣布了由12个国家提出的15个候选算法1999年3月开始的第二阶段讨论（AES2），1999年8月NIST选出5个算法候选:MARS、RC6、Rijndael、Serpent和Twofish。AES候选算法-过程在宣布最后的5个候选算法后，NIST再次恳请公众参与对这些算法的评论。公众对这五种候选算法的评阅期于2000年5月15日结束。NIST发布的AES主页[2]提供了大量的关于算法描述、源程序、有关AES3的论文以及其他公众评论的信息。2000年4月开始进行第三阶段（AES3）的评选，AES3共收到37篇提交给NIST的论文，并采用了其中的24篇。在这一阶段的讨论中，这些算法得到了非常深入的分析。NIST的AES小组综合所有公众对候选算法的评价和分析作了一个非常彻底的评论。AES候选算法-过程经过长时间的评审和讨论之后，NIST在2000年5月宣布选择Rijndael作为AES的算法。该算法的开发者提出以下几种发音供选择ReignDah1，Raindoll和RhineDah1。AES候选算法结果NIST最终选择了Rijndael作为AES的标准，因为全面地考虑，Rijndael汇聚了安全，性能好，效率高，易用和灵活等优点。Rijndael使用非线性结构的S-boxes，表现出足够的安全余地；Rijndael在无论有无反馈模式的计算环境下的硬，软件中都能显示出其非常好的性能；它的密钥安装的时间很好，也具有很高的灵活性；Rijndael的非常低的内存需求也使它很适合用于受限的环境；AES候选算法-结果Rijndael的操作简单，并可抵御时间和能量攻击，此外，它还有许多未被特别强调的防御性能；Rijndael在分组长度和密钥长度的设计上也很灵活，算法可根据分组长度和密钥长度的不同组合提供不同的迭代次数，虽然这些特征还需更深入地研究，短期内不可能被利用，但最终，Rijndael内在的迭代结构会显示良好的潜能来防御入侵行为。AES(Rijndael)算法结构Rijndael:可变块长、可变密钥长度根据AES的要求，分组长度指定为128位，密钥长度为128，192或256位，相应的迭代轮数R为10、12和14。AES框架PlainTextInitialRoundAddRoundKeyStandardRoundByteSubShiftRowMixColumnAddRoundKeyFinalRoundByteSubShiftRowAddRoundKeyCipherTextNr-1RoundsCipherKeyExpansionExpandedKeySelectionRoundKey1RoundKey2…RoundKeyNr-1RoundKeyNr128比特明文轮密钥加字节替换行移位列混合轮密钥加...列混合轮密钥加行移位字节替换行移位轮密钥加字节替换128比特密文(加密过程)轮密钥加逆行移位逆字节替换轮密钥加逆列混合128比特密文...轮密钥加逆字节替换逆行移位逆列混合轮密钥加逆字节替换逆行移位(解密过程)128比特明文第1轮第9轮第10轮第1轮第9轮第10轮密钥扩展主密钥AES轮函数Rijndael的轮函数每一轮迭代的结构都一样，由下述4个不同的变换构成，只是最后一轮省略了列混合变换。1.字节替换（ByteSub）：对数据的每一字节应用一个非线性变换。2.行移位(ShiftRow)：对每一行的字节循环重新排序。3.列混合（MixColumn）：对矩阵的列应用一个线性变换。4.轮密钥加(AddRoundKey)：把轮密钥混合到中间数据。AES轮函数（续）AES轮函数（续）76543210bbbbbbbb111110000111110000111110000111111000111111000111111000111111000176543210aaaaaaaa011000111.字节替换=+替换盒表示替代表是一个16×16的矩阵。表中纵向的x取自状态矩阵中的高4比特，横向的y取自低4比特。替代的过程如下表，x行和y列的数据就用来替代的数据y0123456789ABCDEF0637C777BF26B6FC53001672BFED7AB761CA82C97DFA5947F0ADD4A2AF9CA472C02B7FD9326363FF7CC34A5E5F171D83115304C723C31896059A071280E2EB27B275409832C1A1B6E5AA0523BD6B329E32F84553D100ED20FCB15B6ACBBE394A4C58CF6D0EFAAFB434D338545F9027F503C9FA8751A3408F929D38F5BCB6DA2110FFF3D28CD0C13EC5F974417C4A77E3D645D1973960814FDC222A908846EEB814DE5E0BDBAE0323A0A4906245CC2D3AC629195E479BE7C8376D8DD54EA96C56F4EA657AAE08CBA78252E1CA6B4C6E8DD741F4BBD8B8AD703EB5664803F60E613557B986C11D9EEE1F8981169D98E949B1E87E9CE5528DFxF8CA1890DBFE6426841992D0FB054BB16字节替换表AES轮函数（续）2.行移位运算（ShiftRow）：这是状态中字节的循环移位运算。这个运算可以表示成为Bi,j=Ai,(i+j)mod4行移位3.列混合变换:将状态的每一列视为上多项式,然后乘以固定多项式,并模除.其中,(a(x)存在关于的逆元.变换公式如下:8(2)GF()Sx()ax41x32(){03}{01}{01}{02}axxxx41x'()()()SxaxSx变换的矩阵表示:列混合变换运算结果:轮密钥“加”运算:对状态和每轮的子密钥进行简单的异或操作。每轮子密钥是通过密钥调度算法从主密钥中产生，子密钥长度等于分组长度。轮密钥加运算需要用到4个导出的32比特子密钥。AES子密钥生成Rijindael算法每一轮需要用到Nb比特的子密钥，共有Nr轮，另外，第一次轮密钥加的时候也需要用一轮子密钥，于是总共需要比特的子密钥，对于AES-128来说就是用1408比特的密钥AES子密钥生成(续)第i-1轮的16个字节的子密钥被分成4组来处理，每组4个字节。最后一组的4个字节先执行一个字节的循环左移，由S盒（这个S盒与字节替代时的S盒是一样的）来进行替代处理，然后这4个字节结果中的第一个字节和轮常数相异或，这个常数是由表3.14预先定义的。最后，为了得到第i轮密钥，把得到的4个字节的结果和轮密钥的最初4个字节按位相异或，得到i轮密钥的最初4个字节，然后又和密钥的下面的4个字节按位相异或，得到i轮密钥的下面4个字节，以此类推。AES子密钥生成(续)+++++轮密钥轮密钥i12345678910αi01020408102040801B36AES解密过程在解密过程中，用的是字节替换的逆变换：逆字节替换，行移位的逆变换：逆行移位，列混合的逆变换：逆列混合，以及轮密钥加的逆变换（即是其本身）。