《信息安全课件(2010)2-1AES的数学基础》由会员分享，可在线阅读，更多相关《信息安全课件(2010)2-1AES的数学基础（14页珍藏版）》请在金锄头文库上搜索。
1、1 AES算法的数学基础算法的数学基础 主讲人：裴士辉主讲人：裴士辉 e_mail: shihui_pei 电话：电话：13694302598 背景资料背景资料:DES ?1973年年NBS国家标准局 （ 国家标准局 （NIST国家标准与技术研究所）国家标准与技术研究所） ?算法要求： 算法公开，安全性依赖于密钥而不是算法 算法应能测试和验证 不同的设备可以相互通信 算法要求： 算法公开，安全性依赖于密钥而不是算法 算法应能测试和验证 不同的设备可以相互通信 2 背景资料背景资料:DES ?19681974，IBM研制研制 ?1976 被定为联邦标准 并命名为 被定为联邦标准 并命名为DES(
2、Data Encryption Standard) ?1981、1987、1993 分别被分别被NIST再次认证再次认证 DES的安全强度的安全强度 密钥长度问题密钥长度问题 56-bit 密钥有密钥有256= 72,057,584,037,927,936 7.2亿 亿之多 亿 亿之多 技术进步使穷举搜索成为可能技术进步使穷举搜索成为可能 1997年年1月月28日，日，RSA公司发起破译公司发起破译RC4、RC5、 MD2、MD5，以及，以及DES的活动，破译的活动，破译DES奖励奖励 10000美金。明文是：美金。明文是：Strong cryptography makes the world
3、 a safer place. 结果仅搜索了结果仅搜索了 24.6%的密钥空间便得到结果，耗时的密钥空间便得到结果，耗时96天。天。 1998年在一台专用机上年在一台专用机上(EFF)只要几天时间即可只要几天时间即可 1999年在超级计算机上只要年在超级计算机上只要22小时小时! 线性密码分析攻击问题，线性密码分析攻击问题，DES不能抵御线性分析不能抵御线性分析 3 AES产生过程产生过程 1997年年4月月15日，美国日，美国ANSI发起征集发起征集AES（advanced encryption standard）的活动，并为此成立了）的活动，并为此成立了AES工作小组 。此次活动的目的是确
4、定一个非保密的、可以公开技术细节 的、全球免费使用的分组密码算法，以作为新的数据加密标 准。 工作小组 。此次活动的目的是确定一个非保密的、可以公开技术细节 的、全球免费使用的分组密码算法，以作为新的数据加密标 准。 1997年年9月月12日，美国联邦登记处公布了正式征集日，美国联邦登记处公布了正式征集AES候选 算法的通告。 候选 算法的通告。 对对AES的基本要求是： 比三重 的基本要求是： 比三重DES快、 至少与三重 快、 至少与三重DES一样安全、 数据分组长度为 一样安全、 数据分组长度为128比特、密钥长度为比特、密钥长度为128/192/256比特。比特。 AES产生过程产生过
5、程 1998年年8月月12日，在首届日，在首届AES候选会议（候选会议（first AES candidate conference）上公布了）上公布了AES的的15个候选 算法，任由全世界各机构和个人攻击和评论。 个候选 算法，任由全世界各机构和个人攻击和评论。 1999年年3月，在第月，在第2届届AES候选会议（候选会议（second AES candidate conference）上经过对全球各密码机构 和个人对候选算法分析结果的讨论，从 ）上经过对全球各密码机构 和个人对候选算法分析结果的讨论，从15个候选算 法中选出了 个候选算 法中选出了5个。 这 个。 这5个是个是RC6、Ri
6、jndael、SERPENT、Twofish和和 MARS 2000年年10月月2日，日，NIST宣布宣布Rijndael作为新的作为新的AES。 至此，经过 。 至此，经过3年多的讨论，年多的讨论，Rijndael终于脱颖而出。终于脱颖而出。 4 AES设计思想设计思想 Rijndael密码的设计力求满足以下密码的设计力求满足以下3条标准： 抵抗所有已知的攻击。 在多个平台上速度快，编码紧凑。 设计简单。 条标准： 抵抗所有已知的攻击。 在多个平台上速度快，编码紧凑。 设计简单。 AES算法的数学基础算法的数学基础 字节远算字节远算 字运算字运算 5 字节运算：有限域字节运算：有限域GF(2
7、8)上的运算上的运算 1.有限域有限域GF(23) 2.有限域有限域GF(28) 3.有限域有限域GF(28)的加法运算的加法运算 4.有限域有限域GF(28)的乘法运算的乘法运算 有限域有限域GF(23) GF(23)表示域中有表示域中有23个元素，除个元素，除0之外的之外的7个元素由 本原多项式构造。 假定其本原多项式为： 个元素由 本原多项式构造。 假定其本原多项式为： m(x)=x3+x+1 6 有限域有限域GF(23)的多项式表示的多项式表示 GF(23): 000,001,010,011,100,101,110,111 有限域有限域GF(23)的本原多项式的根表示的本原多项式的根表
8、示 定义为本原多项式定义为本原多项式 m(x)=x3+x+1的根，即的根，即 3+ +1=0 和和3=+1 GF(23): 0, 0 0 , 1 1 , 2 2 , 3 3 , 4 4 , 5 5 , 6 6 7 有限域有限域GF(28) 有限域有限域GF(28)表示特征为表示特征为2的具有的具有28元素的有限域。元素的有限域。 这里表示成系数在这里表示成系数在0,1中的多项式的集合：中的多项式的集合： b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0 这样任意的这样任意的8位二进制数就和有限域中的一个多项式 建立了一一对应的关系。 位二进制数就和有限域中的一个多项式
9、建立了一一对应的关系。 加法运算加法运算 在多项式表示中，在多项式表示中，GF(28)上两个元素的和仍然是一 个次数不超过 上两个元素的和仍然是一 个次数不超过7的多项式，其系数等于两个元素对应 系数的模 的多项式，其系数等于两个元素对应 系数的模2加（比特异或）。 由于每个元素的加法逆元等于自己，所以减法和加 法相同。 加（比特异或）。 由于每个元素的加法逆元等于自己，所以减法和加 法相同。 8 乘法运算乘法运算 要计算要计算GF(28)上的乘法，必须先确定一个上的乘法，必须先确定一个GF(2)上的上的 8次不可约多项式；次不可约多项式； GF(28)上两个元素的乘积就是这两个多项式的模乘
10、（以这个 上两个元素的乘积就是这两个多项式的模乘 （以这个8次不可约多项式为模）。 在 次不可约多项式为模）。 在Rijndael密码中，这个密码中，这个8次不可约多项式确定为次不可约多项式确定为 m(x)= x8+x4+x3+x+1 它的十六进制表示为它的十六进制表示为11B。 例题例题 例题例题. 计算计算GF(28)上的两个元素上的两个元素10010001和和 00100010的乘积。 答案： 的乘积。 答案：10000100 9 x乘法乘法 GF(28)上还定义了一个运算，称之为上还定义了一个运算，称之为x乘法， 其定义为 乘法， 其定义为 xb(x)= b7x8+b6x7+b5x6+
11、b4x5+b3x4+b2x3+b1x2+b0x(mod m(x) 如果如果b7=0，求模结果不变， 否则为乘积结果减去 ，求模结果不变， 否则为乘积结果减去m(x)，即求乘积结果与，即求乘积结果与m(x)的异或。 由此得出 的异或。 由此得出x（十六进制数（十六进制数02）乘）乘b(x)可以 先对 可以 先对b(x)在字节内左移一位（最后一位补在字节内左移一位（最后一位补0）， 若 ）， 若b7=1，则再与，则再与1B（其二进制为（其二进制为00011011）做逐比特异或 来实现， 该运算记为 ）做逐比特异或 来实现， 该运算记为b=xtime(a)。 例题例题 例如，例如，5713可按如下方
12、式实现：可按如下方式实现： 5702=xtime(57)=AE； 5704=xtime(AE)=47； 5708=xtime(47)=8E； 5710=xtime(8E)=07； 5713=57(01+02+10) =57+AE+07=FE。 10 练习练习 计算计算GF(28)上的两个元素上的两个元素10010010和和01100010的乘 积。 的乘 积。 AES Logtable 0123456789abcdef 00025150226198751992710451238 2233 1 10042241452141 129 239761138200 248 10528193 2 125
13、19429181 249 1853910677228 166 114 154 2019120 3 10147138533152253618240 1306953147 218 142 4 150 143 219 18954208 206 1481992210 241647013156 5 102 221 2534819161399817937226 15234136 14516 6 126 11072195 163 1823066581074084250 13361186 7431211021155 1599420278212 172 229 243 115 16787 8 175881688
14、0244 234 214 11679174 233 213 231 230 173 232 944215 117 122 23522112458920395176 156 16981160 a 12712246 1112319673236 216673145164 118 123 183 b 204 187629025196177 1345982161 108 1708541157 c 151 178 135 14497190 220 252 188 149 207 205556391209 d83571326065162 1097120421589386242 211 171 e681714
15、6 217353246137 180 124 18438119 153 227 165 f 10374237 222 19749254241399140 128 192 247 1127 11 AES alogtable 0123456789abcdef 0135151751852552646114 150 161 2481953 1952255672216 115 149 164 24726103034102 170 2 2295292228558923538106 190 217 112 144 171 23049 38324541220606820479209 104 184 211 1
16、10 178 205 476212 103 169 224597721598166 24182440120 136 5 131 158 185 208 107 189 220 127 129 152 179 20673219 118 154 6 181 19687249164880240112939105 187 21497163 7 2542543125 135 146 173 23647113 147 174 2333296160 8 251225878210 109 183 194932315086250216365 9 195942266171201641929123744116 156 191 218 117 a 159 186 213 10
