AES密钥扩展新方法-论文.pdf

2 9卷第 1 期 2 0 1 2年 1 月 微 电 子 学 与 计 算 机 MI C R OE L E C T RONI C S& C O MP UTE R Vo 1 2 9 No 1 J a n u a r y 2 0 1 2 AE S密钥扩展新方法 杨小东，王毅 ( 哈尔滨工业大学 深圳研究生院 ， 广东 深圳 5 1 8 0 5 5 ) 摘要： 在分析原有的AE S算法密钥生成改进方法所存在的不足的基础上， 根据单向性思想提出了几种新的 A E S 密钥扩展算法， 从加密强度和运行速度两方面对原有方法进行了改善 通过分析 以及实验数据表明， 该方法既保证 了密钥扩展算法的安全性， 又提高了其运行的效率 关键词：密钥扩展， 单向性， AE S算法， 随机函数 中图分类号 ： TP 3 0 9 7 文献标识码 ： A 文章编号 ：1 o 。 O 7 1 8 0 ( 2 0 1 2 ) 0 1 一O 1 O 2 一O 3 Ne w M e t h o ds o f AES Ke y Ex p a n s i o n YANG Xi a o d o n gW ANG Yi ( S h e n z h e n Gr a d u a t e S c h o o l ，Ha r b i n I n s t i t u t e o f Te c h n o l o g y ，S h e n z h e n 5 1 8 0 5 5 ，Ch i n a ) Ab s t r a c t ：I n t h i s p a p e r ，b a s e d o n t h e a n a l y s i s o f t h e s h o r t c o mi n g s o f t h e o r i g i n a l k e y e x p a n s i o n me t h o d，s o me n e w me t h o d s f o r t h e k e y e x p a n s i o n a l g o r i t h m o f AE S e n c r y p t i o n a l g o r i t h m a r e p r o p o s e d a c c o r d i n g t o t h e o n e wa y p r o p e r t y ，wh i c h i mp r o v e d t h e o r i g i n a l me t h o d i n t wo a s p e c t e n c r y p t i o n s t r e n g t h a n d r u n n i n g s p e e d An a l y s i s a n d e x p e r i me n t a l d a t a i l l u s t r a t e d t h a t t h e p r o p o s e d me t h o d s n o t o n l y g u a r a n t e e d t h e s e c u r i t y o f t h e o r i g i n a l a l g o r i t h m b u t a l s o i mp r o v e d i t s e f f i c i e n c y Ke y wo r d s ：k e y e x p a n s i o n；o n e - wa y p r o p e r t y ；AES a l g o r i t h m；r a n d o m f u n c t i o n 1 引言 AE S作为新一代数据加密标准 ， 其算法本身所 具有的模块性、 对称性等特点使设 计者可 以在修改 其 中的某一部分结构的同时不至于影响其他部分的 正常运行 AE S采用了扩充初始密钥生成子密钥的 方法 ， 通过对其密钥扩展算法 的分析 ， 可知 AE S密 码扩展具有直接高效并且快速的优点 ， 但是也有通 过其中任何一轮子密钥 即可破解全部密钥的缺 陷， 可以通过分析的其中的某一轮子密钥得到前几轮 的 全部密钥 ， 也可通过得到的某一轮子密钥用 固定算 法推导出后一轮以致后面几轮所有的密钥 1 逆向 思维是进行密钥破解分析时需要有的思路， 如能够 找到一种新方法， 使得算法运行中既可以保持在从 前向后生成密钥时所具有的快速性_ 2 ， 又能够使逆 向推导密钥困难异常 ， 就可 以防止各种攻击方法针 对 AE S密钥扩展的弱点， 仅通过截获其中任意一轮 子密钥 即可破解初 始密钥的威胁 这种使得密钥扩 展过程不可逆的思想即称为单向性思路 文献 1 利 用单向性策略提出了一种 AE S密钥扩展改进方法 ， 本文对该算法进行了分析 ， 针对标准算法的不足之 处l_ 3 提出了几种新的改进方法 ， 在保证安全性进一 步提高的同时 ， 也加快了密钥扩展的效率 2 对原有改进算法的分析 文献 1 根据单 向性策略提出了一种 AE S密钥 扩展改进方法 对该算法进行分析： 假设某一轮的密 钥已经被攻击者获取，推算攻击者 已知 w ， W ， Wm ， w 推算 出 w ， w ， W ， w 所需 付出的代价 由于 w 与 w ， w 相关 ， 可通过穷 举法进行暴力攻击 W 的长度为 3 2位 ， 可 以通过 2 弛 次穷举来 确定 W 和 W 确定 W 和 W 之 收稿 日期 ：2 O l 1 一O 5 1 0 ； 修 回 日期 ： 2 0 l 1 一O 6 1 2 基金项目：中央高校基本科研业务费专项资金项 目( HI T NS R I F 2 0 0 9 1 3 4 ) 第 1 期 杨小东， 等： AE S密钥扩展新方法 1 0 3 后 ， 即可利 用 w 和 w 推 出 w ， 利用 W 和 w 推出 wm ， 因此可以全部推出上一轮 的密钥 这是 由第三轮以及其 以后轮数 的密钥推断前边几轮 密钥 的情况 ， 需要经过 2 。 次穷举 如果 已知第二轮 密钥 ， 情况则有所不 同， WO ， w ， w ， W。 是 初始密 钥 ， 四行数组没有任何关系 ， 因此用 w 推出 w。 和 W 之后 ， 还需用 W 推 出 W 和 W。 ， 方可：准出初始 密钥 ， 因此 ， 已知第二轮密钥 ， 推断初始密钥需要 2 。 次穷举 如果攻击者得到了第三轮的子密钥 ， 需要用 2 次穷举来破解初始密钥 ， 如果攻击者得到了第 四 轮的子密钥 ， 则需要用 2 。 次穷举来破解初始密钥 ， 这 已经 同对密码 的暴力攻击没有区别 ， 因此 ， 该方法 对防止第四轮及其以后的子密钥攻击具有强力抗攻 击作用 ， 对第三轮及其之前的子密钥攻击防御较弱 3 算法的改进 针对 AE S密钥扩展算法的不足之处 ， 本文从抗 攻击强度并兼顾程序执行时间方 面做 了改进 ， 提 出 几种新方法 3 1 方 法 1 为减 小计 算 量 ， 取 消 R o o t B y t e ，S u b Wo r d与 Rc o n算法 ， 令 W 每一位元素左移 a 位异或 w 每 一 位元素右移 C位 ， 生成 Wm 对应元素 ， 令 W 左 移 e 位异或 W 右移 g位生成 Wm ， 令 ， 每一位 元素右移 b位异或 w 每一位元素左移 d位， 生成 W 对应元 素， 令 w 每一位元 素右 移 f 位 异或 W 每一位元素左移 h位 ， 生成 W 对应元素 ， 以 此类推 ， 得到需要加密的所有轮次的子密钥 在算法 具体实施过程中， 每一位数左移还是右移 ， ：移动多少 位 ， 均可随机选择 ， 并不局 限于方法 中所指出的具体 位数 其算法原理图如图 1 所示 算 法分 析 ： 根据原 来 的方法进 行研 究 ， W ， W 只与 W 和 W 有关 ， w ， W 只与 W 和 W 有关 ， 每一轮子密钥 内部相关性不大 用 2 船次 穷举可通过 w 推断出 W 和 W卅 ， 用 2 。 次穷举 可通过 W 推断 出 W 和 W ， 推断前一轮密钥 共需要 2 次穷举 此种推断在任何一轮均相 同， 任 何一轮推断前一轮均需要 2 。 次穷举 ， 通过分析 ， 此 种改进算法使得算法运行到第二轮时强度即可与暴 力破解相同 3 2方法 2 方法 1 在改进效果上 明显好于原有的方法 ， 但 是仍未达到经过一轮变换即可使其自身抗：攻击强度 与对密钥直接进行暴力攻击的强度相同的目的 借 图 1方 法 1原 理 图 助具有单 向性或随机性的函数或能提高密钥扩展 的 强度 但凡有规律的单向函数 ， 或多或少具有倒推的 方法与可能性 ， 而随机函数生成的值无法倒推_ 4 对 此 ， 本方案引入随机函数 ， 本方法主要思想是对初始 密钥各数值进行移位后相加 ， 生成 的数值作为随机 函数的种子， 生成下一轮 的各个密钥 以此类推 ， 生 成下面各轮密钥 在算法的具体应用 中， 各轮各个数 值移位的方向， 移位的位数均不 同， 对生成的随机数 也采用不同的密钥分配方法 ， 打乱原有的顺序 ， 加大 生成子密钥 的混乱程度 ， 使得攻击者没有分析 的头 绪 ， 该方法 自身也没有逆向推导的策略 ， 因为其本身 就成为随机函数 其原理图如图 2 所示 图 2 方法 2原理 图 算法分析： 每个元素与前边对应的元素均无关， 因此 ， 如欲推出前面的一轮的密钥 ， 只能对各值均进 行 2 。 次穷举， 推出一轮密钥， 需要经过 2 1 2 8 次穷举 随机性是本方法最大的特点， 其特点使得攻击者无 从下手， 正如 HI V病毒在人体内复制一样， 具有强 大的变异能力， 使任何一种单一的方法均无从下手， 1 0 4 微电子学与计算机 唯有穷举法能成为对付此方法的鸡尾酒疗法 本方 法改进 了策略 2中提 出的方法 ， 使得算法运行一轮 时便需要 2 次穷举方可推 出前一轮密钥 ， 其强度 与暴力破解无异 3 3 方法 3 方法 2虽然在加强密钥强度方 面做 了大量工 作 ， 但是其忽视了程序运行的效率问题 随机数生成 相对 于其它程序而言运行时间很长 ， 攻击密钥 的强 度逐轮增大 ， 但经过一轮加密后 ， 其强度就已经达到 要求， 所 以没有必要付 出效率的降低 的代价来换取 更高攻击强度的子密钥 如能找到一种方法， 在提高 密钥强度的基础上又能减少程序运行时间， 是本文 所追求的最终 目标 在综合各方法的基础上 ， 本文提 出第三种改进方法 ， 对密钥矩阵的初始 4行赋予初 始密钥 ， 这一步不变， 在第 5到第 8 行用另一套与初 始密钥无关的新密钥填充 ， 两套密钥不存在任何关 系， 在新的密钥的基础上 ， 用 AE S固有的设计方法 ， 进行密钥扩展 该方法原理图如图 3所示 算法分析 ： 攻击者可以按照文献 1 提出的方法 进行攻击， 并且会很快推 出经第一轮扩展生成 的密 钥 ， 但是 由算法知 ， 第一轮扩展生成的密钥与初始密 钥无任何关 系 ， 由第 一轮 密钥 推 出子 密钥仍 需要 2 次穷举 ， 其强度仍与暴力攻击相同， 而且该方法 极大节省 了时间， 提高了效率 ， 对 固有 的 AE S算法 亦仅做了一小部分改动 ， 避免了其它问题的发生， 该 方法为一种兼顾安全与效率的好方法 4 各 改进 方法综合分析 通过对各方法的分析， 可以做 出各方法需要攻 击强度与扩展轮数的关系， 如表 1 所示 表中所列程 序运行时间为在 k e i l 环境 中模拟 8 MHz 下各方法 所运行的时间 从表中可 以看出， 方法 2 美 中不足之 处在于其运行时间明显高于前边几种方法 ， 对程序 运行的效率产生了一定影响 方法 1虽然有较快 的 运行速度， 但是其加密强度效果稍差 如果对方法 2 算法的步骤做一定简化 ， 亦可减少程序运行时间， 提 高效率 ， 但强度与速度之间的矛盾是固有的， 加快速 度就会使得安全性降低 ， 做简化处理 ， 需要对其安全 度需重新评估 方法 3 在 AE S固有的密钥扩展方法 上进行改进 ， 不仅加快了程序运行速度 ， 也达到 了 AE S密钥生成算法的安全性指标 ， 是一种较好的改 进 方法 表 1 改进方法对 比表 图 3 方法 3 原理 图 士 对时间没有太多要求 ， 方法 2是一种好方法 ； 如希望 - 口 术 厢 在不影响 AE S整体算法效率的同时， 也使得生成的 本文在原有的对密钥扩展改进算法的分析的基 子密钥具有高强度的抗攻击性， 方法 3 是一种较好 础上 ， 利用单 向性策略， 提出了几种新的密钥扩展算 的密钥扩展改进办法 法 实验表明， 如只欲加强密钥生成的抗攻击强度， ( 下转第 l O 8 页) 1 0 8 微电子学与计算机 2 0 1 2正 表 3 不同方法的准确率与耗时的对比 耗时 ( m s ) 准 确 率 基于元数据的 1 4 8 5 7 4 5 6 Y oo 判定方法 基 于网页内容 的 1 8 7 6 5 5 3 97 3 语义判定方法 本文方法 4 3 4 4 9 9 5 4 另外 ， 使用文 中提 出的方法 ， 分别对相关 度高 的、 相关度低的以及不相关 的网页进行了实验 ， 实验 结果如表 4 所示 可 以分析出： 主题相关度越高的网 页其相关度判定的准确率也越高 ， 由于用户一般不 会关注排名 5 0之后的信息 ， 因此 ， 网页主题相关度 低影响到判定准 确率 的问题几 乎不会对用户造成 影 响 表 4 本文方法针对不 同类型数据 的准确率 主 题 相 关 度 主 题 相 关 度 不 相 关 的 高 的 W eb 数 据 低 的 W eb 数 据 w eb 数 据 准确率 9 8 8 8 1 5 4 5 7 5 结束语 高准确率和低耗时是相互矛盾的 ， 本文提 出的 基于动态匹配的主题相关度算法在很大程度上减少 了这种矛盾 实验结果表明： 从准确率和耗时相统一 的角度 ， 本文提 出的方法达到了较好的效果 展状况统计报告 E B 0I 2 O l 1 - 0 5 一 e 8 1 R e t p ： r e s e a r c h c n n c e ，c n h t m1 王继成 ， 萧嵘， 孙正兴， 等 We b信 息检索研究发展 _ J 计算机研究与发展， 2 0 0 1 ， 3 8 ( 2 ) ：1 8 7 1 9 3 F M e n c z e r ，G P a n t ，P S r i n i v a s a n， e t a 1 e v a l u a t i n g To p i c - D r i v e n We b C r a w l e r s C P r o c e e d i n g s o f t h e 2 4 An n u a l I n t e r n a t i o n a l AC M S I GI R c o n f e r e n c e ， Ne w Or l e a n s ，US A： ACM ，2 0 0 7 Cu t l e r M ， S h i h Yu n g - mi n g ，M e n g W e i y i Us i n g t h e s t r u c t u r e o f HTMI d o c u me n t s t O i mp r o v e r e t r i e v a l c P r o c e e d i n g s o f t h e 1 1 s t I E E E C o n f e r e n c e o n To o l s wi t h AI ， C A，US A：I EE E，2 0 0 9： 4 0 6 4 0 9 韩先培 基于布局特征与语言特征的网页主要 内容块 发现 F J 中文信息学报2 0 0 8 ( 1 ) ： 1 5 2 1 张天广基于 I n t e r n e t 的银行竞争 情报收集 系统 的研 究与实现 【 ) 西安： 西北大学， 2 0 0 9 Yi J ，S u n d a r e s a n NMe t a d a t a b a s e d we b mi n i n g f o r r e l e v a n c e c P r o c e e d i n g s o f t h e I n I E E E 2 0 0 0 I n t e r n a t i o n a l Da t a b a s e En g i n e e r i n g a n d Ap p l i c a t i o n s S y mp o s i u m ( I DE AS 0 0) Yo k o h a ma ： I EE E， 2 0 1 0： 1 1 3 1 21 Bi n g Li u， Ch e e W e e Ch i n， Hwe e To u Ng Mi n i n g t o p i c - s p e c i f i c c o n c e p t s a n d d e f i n i t i o n s o n t h e w e b I t Pr o c e e d i n g