现代密码学 第6讲AES.ppt

2020 3 5 1 3 6AES算法 Rijndael 1997年4月15日 美国ANSI发起征集AES advancedencryptionstandard 的活动 并为此成立了AES工作小组 1997年9月12日 美国联邦登记处公布了正式征集AES候选算法的通告 对AES的基本要求是 比三重DES快 至少与三重DES一样安全 数据分组长度为128比特 密钥长度为128 192 256比特 1998年8月12日 在首届AES候选会议 firstAEScandidateconference 上公布了AES的15个候选算法 任由全世界各机构和个人攻击和评论 1999年3月 在第2届AES候选会议 secondAEScandidateconference 上经过对全球各密码机构和个人对候选算法分析结果的讨论 从15个候选算法中选出了5个 分别是RC6 Rijndael SERPENT Twofish和MARS 2000年4月13日至14日 召开了第3届AES候选会议 thirdAEScandidateconference 继续对最后5个候选算法进行讨论 2000年10月2日 NIST宣布Rijndael作为新的AES 经过3年多的讨论 Rijndael终于脱颖而出 Rijndael由比利时的JoanDaemen和VincentRijmen设计算法的原型是Square算法 它的设计策略是宽轨迹策略 widetrailstrategy 算法有很好的抵抗差分密码分析及线性密码分析的能力 2020 3 5 3 3 6 1Rijndael的数学基础和设计思想 1 有限域GF 28 GF 2 上的8次不可约多项式可扩展为有限域GF 28 加法定义两个多项式的模2加两个多项式的对应系数的异或乘法定义为两个多项式的模乘特别不可约多项式m x x8 x4 x3 x 1 2020 3 5 4 多项式加法系数表示法 GF 28 中任一多项式 bi 0 1 b7x7 b6x6 b5x5 b4x4 b3x3 b2x2 b1x b0 b7b6b5b4b3b2b1b0 一个字节 多项式加法 对应系数模2加 异或 如多项式 x6 x4 x2 x 1 x7 x 1 x7 x6 x4 x2 modm x 二进制表示为01010111 10000011 11010100十六进制表示 57 83 D4 多项式系数表示法 b x b7x7 b6x6 b5x5 b4x4 b3x3 b2x2 b1x b0 b7b6b5b4b3b2b1b0 x b x b7x8 b6x7 b5x6 b4x5 b3x4 b2x3 b1x2 b0 x modm x m x x8 x4 x3 x 1b7 0b6x7 b5x6 b4x5 b3x4 b2x3 b1x2 b0 x b6b5b4b3b2b1b00b x 在字节内左移一位 最后一位补0 b7 1 b x 在字节内左移一位 最后一位补0 与 1B 00011011 逐比特异或x的幂乘运算可以重复应用xtime来实现 多项式乘法 1B 00011011 例如 57 13 可按如下方式实现 57 02 xtime 57 AE 10101110 57 04 xtime AE 47 01000111 57 08 xtime 47 8E 57 10 xtime 8E 07 57 13 57 01 02 10 57 AE 07 FE 1B 00011011 57 01010111 10101110 01011100 01000111 10001110 10001110 00011100 00000111 00000111 57 01010111 13 00010011 000000010000001000010000 01 02 10 57 13 57 01 02 10 2020 3 5 7 2 系数在GF 28 上的多项式 模取M x x4 1 系数在GF 28 上的任意多项式可表示为a3x3 a2x2 a1x a0 aiGF 28 系数对应4个字节构成的向量 加法定义如下对应系数相加 4字节向量的逐比特异或 设a x a3x3 a2x2 a1x a0 b x b3x3 b2x2 b1x b0 c x a x b x c3x3 c2x2 c1x c0 由于xjmod x4 1 xjmod4 所以c0 a0b0 a3b1 a2b2 a1b3 c1 a1b0 a0b1 a3b2 a2b3 c2 a2b0 a1b1 a0b2 a3b3 c3 a3b0 a2b1 a1b2 a0b3 注意 M x 不是GF 28 上的不可约多项式 非0多项式乘法逆元不一定存在 在Rijndael密码中 只限于乘一个固定的有逆元的多项式 乘法定义 x 或x的幂 模乘多项式c x x b x modx4 1除a1 01 外 其他所有ai 00 c x a x b x 对字节构成的向量进行字节循环移位 2020 3 5 10 定理系数在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 1mod x4 1 a3x3 a2x2 a1x a0 h2x3 h1x2 h0 x h3 xmod x4 1 a3x3 a2x2 a1x a0 h1x3 h0 x2 h3x h2 x2mod x4 1 a3x3 a2x2 a1x a0 h0 x3 h3x2 h2x h1 x3mod x4 1 c x a x b x 2020 3 5 12 3 设计思想 Rijndael密码的设计力求满足以下3条标准 抵抗所有已知的攻击 在多个平台上速度快 编码紧凑 设计简单 当前的大多数分组密码 其轮函数是Feistel结构 Rijndael没有这种结构 Rijndael轮函数是由3个不同的可逆均匀变换 Rijndael State ExpandedKey AddRoundKey State ExpandedKey for i 1 i Nr i Round State ExpandedKey Nb i FinalRound State ExpandedKey Nb Nr Round State RoundKey ByteSub State ShiftRow State MixColumn State AddRoundKey State RoundKey FinalRound State RoundKey ByteSub State ShiftRow State AddRoundKey State RoundKey 2020 3 5 14 3 6 2算法说明 分组和密钥长度可变 各自可独立指定为128 192 256比特 状态算法中间的结果也需要分组 称之为状态 状态可以用以字节为元素的矩阵阵列表示 该阵列有4行 列数Nb为分组长度除32种子密钥以字节为元素的矩阵阵列描述 阵列为4行 列数Nk为密钥长度除32 1状态 种子密钥和轮数 Nb 6和Nk 4的状态密钥阵列 轮数Nr与Nb和Nk对应关系 2 轮函数 ByteSub 非线性代换是可逆的 由以下两个变换的合成得到 首先 将字节看作GF 28 上的元素 映射到自己的乘法逆元 00 映射到自己 其次 对字节做如下仿射变换 2020 3 5 17 字节代换示意图 2020 3 5 18 例子 95 的乘法逆为 8a 二进制表示为 10001010 结果为 00101010 十六进制表示为 2a 2020 3 5 19 ShiftRow 将状态阵列的各行进行循环移位 移位量与分组长度的关系 0行 不动 状态阵列的每个列a x 与一个固定的多项式c x 进行模x4 1乘法后混淆为b x 记为c x 是模x4 1可逆的多项式 03 x3 01 x2 01 x 02 MixColumn b x c x a x 逆d x 0B x3 0D x2 09 x 0E 2020 3 5 22 AddRoundKey 密钥加 轮密钥与状态进行逐比特异或 轮密钥长度等于分组长度Nb 密钥加运算的逆运算是其自身 2020 3 5 23 3 密钥编排 密钥编排指从种子密钥得到轮密钥的过程 由密钥扩展和轮密钥选取两部分组成 当Nk 6时 扩展算法如下KeyExpansion byteKey 4 Nk W Nb Nr 1 for i 0 i Nk i W i Key 4 i Key 4 i 1 Key 4 i 2 Key 4 i 3 for i Nk i Nb Nr 1 i temp W i 1 if i Nk 0 temp SubByte RotByte temp Rcon i Nk W i W i Nk temp RotByte 返回4字节字 由输入的字循环移位得到 即当输入字为 a b c d 时 输出字为 b c d a SubByte 返回4字节字 其中每一个字节都是用Rijndael的S盒作用得到 轮常数Rcon i Nk 密钥扩展 比特数等于分组长度乘 轮数加1 Nb 32 Nr 1 2020 3 5 25 前10个轮常数Rcon i Rcon i RC i 00 00 00 RC 1 01 1RC i x RC i 1 xi 1modx8 x4 x3 x 1 当Nk 6时 扩展算法如下 KeyExpansion byteKey 4 Nk W Nb Nr 1 for i 0 i Nk i W i Key 4 i Key 4 i 1 Key 4 i 2 Key 4 i 3 for i Nk i Nb Nr 1 i temp W i 1 if i Nk 0 temp SubByte RotByte temp Rcon i Nk elseif i Nk 4 temp SubByte temp W i W i Nk temp 2020 3 5 27 轮密钥选取 第1轮轮密钥取扩展密钥的前Nb个字 第2轮轮密钥取接下来的Nb个字 如此下去 第i个轮密钥 轮密钥缓冲字W Nb i 到W Nb i 1 InvRound State RoundKey InvByteSub State InvShiftRow State InvMixColumn State AddRoundKey State InvMixColumn Key InvRound State RoundKey InvShiftRow State InvByteSub State AddRoundKey State RoundKey InvMixColumn State InvShiftRow InvByteSub InvByteSub InvShiftRow AddRoundKey key InvMixColumn InvMixColumn AddRoundKey InvMixColumn Key Round State RoundKey ByteSub State ShiftRow State MixColumn State AddRoundKey State RoundKey InvFinalRound State RoundKey InvByteSub State InvShiftRow State AddRoundKey State RoundKey InvFinalRound State RoundKey InvShiftRow State InvByteSub State AddRoundKey State RoundKey FinalRound State RoundKey ByteSub State ShiftRow State AddRoundKey State RoundKey Rijndael State ExpandedKey AddRoundKey State ExpandedKey for i 1 i Nr i Round State ExpandedKey Nb i FinalRound State ExpandedKey Nb Nr DeRijndael State ExpandedKey AddRoundKey State ExpandedKey Nb Nr for i Nr 1 i 1 i InvRound State InvMixColumn ExpandedKey Nb i InvFinalRound State ExpandedKey 设加密算法的初始密钥加 第1轮 第2轮 第Nr轮的子密钥依次为k 0 k 1 k 2 k Nr 1 k Nr