（应用数学专业论文）aes算法研究及其在智能卡中的应用.pdf

东北大学硕士学位论文 a e s 算法研究及其在智能卡中的应用 摘要 现代社会广泛使用的d e s 及d e s 类加密算法已经不能够提供足够的安全 性 而现今使用的大多数密码产品都使用d e s 算法 因此人们急切地需要更加 安全的加密算法 而对刚刚颁布的高安全的a e s 加密算法 就是人们首选的代 替d e s 算法的加密算法 大多数密码产品生产部门已经开始加紧了对a e s 产品 的开发进程 现今对a e s 产品的开发还是起步阶段 很多工作需要我们来做 本文主要研究了a e s 算法的安全性 a e s 算法的实现问题 a e s 算法在智 能卡中的应用三方面的问题 在第二章我们主要讨论a e s 算法设计原理及其安 全性问题 深入分析了a e s 算法的s p n 结构和宽轨迹策略 讨论其方法的优劣 以期能为设计新的算法而提供借鉴 讨论a e s 算法的安全性 总结最新的a e s 分析结果 分析其优劣并提出见解 第三章讨论a e s 算法实现问题 主要是讨 论软件实现方法 并提出了新的实现方案 第四章研究a e s 算法在智能卡上的 应用 把a e s 算法可设计成适合智能卡的哈希算法 设计了智能卡信息混合传 输系统 使智能卡的安全性显著增强 关键词 a e s r i j n d a e l 智能卡 软件实现 硬件实现 东北大学硕士学位论文 a b s t r a c t o na e s a l g o r i t h ma n d i t sa p p l i c a t i o n si n s m a r tc a r d s a b s t r a c t t h ed e s d a t ae n c r y p t i o ns t a n d a r d a n dd e s l i k ea l g o r i t h m s w h i c hi s e x t e n s i v e l yu s e di nm o r d e ms o c i e t y c o u l d n ts u p p l ya d e q u a t es e c u r i t yf o rs e n s i t i v e d a t a w h e r e a sm a j o r i t yc r y p t o g r a p h i cp r o d u c t su s e dn o w d a y su s ed e sa n dd e s l i k e a l g o r i t h m sf o rt h e i re n c y p t i o na l g o r i t h m s p e o p l en e e dm u c hm o r es e c u r ee n c r y p t i o n a l g o r i t h m sa n dc r y p t o g r a p h i ep r o d u c t se a g e r l y t h eh i g hs e c u r ee n c r y p t i o na l g o r i t h m a e s a d v a n c e de n c r y p t i o ns t a n d a r d c a nb eu s e dt os u b s t i t u t et h ed e sa n d d e s l i k ee n c r y p t i o na l 鲫h m s r e s e a r c h i n ga n de x p l o i t i n gt h ea e sc r y p t o g r a p h i c p r o d u c t sw i l lb et h em e g at o p i ci nt h ec r y p t o l o g yc o m m u n i t y ag r e a tm a n yw o r k s n e e d t o b e d o n e t h i sa r t i c l er e s e a r c h e st h r e e p r o b l e m s t h ea e sa l g o r i t h ms e c u r i t y a e s a l g o r i t h mi m p l e m e n t i n gp r o b l e ma n dt h ea e sa p p l i c a t i o n si ns m a r tc a r d i nc h a p t e r t o ww em o s t l yd i s c u s sa e s a l g o r i t h md e s i g nt h e o r ya n di t ss e c u r i t yp r o b l e m s w h i c h p r o f o u n d l ya n a l y s et h es p n s t r u c t u r ea n dw i d et r a i ld e s i g ns t r a t e g yo fa e sa n d s u m m a r i z eu l t r a m o d e r na e s a n a l y t i cr e s u l t s i nc h a p t e rt h r e e w ed i s c u s s i m p l e m e n t i n gp r o b l e m s o fa e s a l g o r i t h m w h i c hp r i m a r i l y d i s c u s ss o f t w a r e i m p l e m e n t a t i o nm e a n s w er e n d e r an e wi m p l e m e n t i n gm e a n i nc h a p t e rf o u r w e r e s e a r c ht h ea p p l i c a t i o n so fa e si ns m a r tc a r d s i nt h i sc h a p t e r w ed i s i g nah y b r i d d a t at r a n s m i s s i o ns y s t e mw h i c hc a l lb eu s e di ns m a r tc a r d ss e c u r e l y k e yw o r d s a e s r i j n d a e l s m a r tc a r d s o f t w a r ei m p l e m e n t a t i o n h a r d w a r ei m p l e m e n t a t i o n 1 1 i 一 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的 论文中取 得的研究成果除加以标注和致谢的地方外 不包含其他人已经发表或 撰写过的研究成果 也不包括本人为获得其他学位而使用过的材料 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意 学位论文作者签名 庆毫淼磅 日 期 一c 彦 i 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留 使用学 位论文的规定 即学校有权保留并向国家有关部门或机构送交论文的 复印件和磁盘 允许论文被查阅和借阅 本人同意东北大学可以将学 位论文的全部或部分内容编入有关数据库进行检索 交流 如作者和导师不同意网上交流 请在下方签名 否则视为同意 学位论文作者签名 j 导师签名 签字日期 一 4 签字日期 东北大学硕士学位论文 第一章绪论 第一章绪论 i i 课题的目的和意义 现代加密算法大致可分为对称加密算法和非对称加密算法 从1 9 7 6 年美国 数据加密标准算法 d e s 公布以来 到2 0 世纪末 d e s 算法或其变形基本上主 宰了对称算法的研究与开发进程 随着密码分析水平 芯片处理能力和计算技术 的不断进步 以前广泛使用的d e s 算法及其变形的安全强度已经难以适应新的安 全需要 其实现速度 代码大小和跨平台性均难以继续满足新的应用需求 在这 种形势下 迫切需要设计一种更强有力的算法作为新一代分组加密标准 因此 a e s 应运而生 a e s 算法以其简洁 高效 安全和原则性的设计 击败了来自世界各地的密 码团体提供的密码算法 就像从d e s 算法颁布以来人们一直热衷于研究d e s 算法 一样 a e s 算法的研究已经成为当今密码学界所关注的重要课题 也将成为今后 一二十年密码学界的重要研究对象 a e s 和d e s 算法都是作为商用的对称加密算法 其主要加密的是敏感但非机 密的数据 主要使用在银行业 行政部门和工业界等 而在现今这些部门使用的 密码产品和系统中 大都使用d e s 算法作为对称加密算法 因此对这些产品和系 统用a e s 算法更新挠代将是人们迫切需要解决的课题 鉴于a e s 算法的重要性 其安全问题一直是人们热衷研究的课题 从 r i j n d a e l a e s 算法被选为a e s 标准以来 a e s 算法分析已成为密码分析界的 重要研究课题之一 在实现a e s 算法方面 有很多的东西需要考虑 既要使之实 现快速安全且花费最低 特别是应用在像智能卡这样的存储空间和运算速度都很 有限的系统中 更应该考虑到速度 空间和造价之间的权衡 随着信息化时代的 到来 在人们的生活中 智能卡的使用已经越来越广泛 智能卡带给人们的便利 和使用的安全性使人们更加热衷于智能卡的使用 而其安全性也是人们关注的问 题 设计一个高效 安全的智能卡适用的a e s 实现方案 将不只具有理论价值 更会带来很大的经济价值 我们首先深入分析了a e s 算法的设计策略及安全性 并使用安全高效的a e s 算法加强智能卡的安全性 主要是设计安全高效的实现方案 将其应用到智能卡 h 1 东北大学硕士学位论文 第一章绪论 1 2 课题研究概况 从1 9 9 7 年人们开始关注a e s r i j n d a e l 算法以来 对a e s 算法的安全性 和实现方案的研究一直是密码学界关注的焦点 一个加密算法 首先我们关注的是它的安全性 并研究其设计策略 以资借 鉴 其次我们会关注其在各种系统和环境下的实现问题 以求更好地应用 在这 两方面 人们做了不少的工作 1 2 1a e s 算法安全性研究 r i j n d a c l a e s 算法自面世以来 特别是被选为a e s 算法以来 其安全性 备受人们的关注 对其设计策略的研究也随之而起 a e s 算法应用宽轨迹策略 而设计 时至今日宽轨迹策略的研究也开始兴起 很多依此方法设计的算法应用 而生 而其安全性的研究自2 0 0 0 年此算法被选为a e s 算法以来一直得到密码学 界的重视 传统的密码分析方法如线性和差分密码分析方法为分析a e s 算法安 全性的重要方法 但还没有什么对a e s 算法的威胁 一些专门针对a e s 算法的 分析方法如s q u r e 和代数分析方法也是人们研究的对象 对简化的a e s 算法 这些方法有一些新发现 但对完整版的a e s 算法还没有有效的破解方法 1 2 2a e s 算法实现方法研究 密码算法实现可分为硬件实现和软件实现两种 前者主要偏重于提高速度 而后者则侧重于实现的廉价和需要空间小 本文主要研究其软件实现方案及其应 用 1 硬件实现 我们所谓的硬件实现是指用硬件描述语言将a e s 算法进行系统设计和编 码 然后用适当的e d a 工具进行仿真和综合 最后用a s i c 或f p g a 等恰当的 方式来实现 a e s 算法正处在应用的蓬勃发展阶段 就硬件实现而言 国外许 多公司都相继推出了自己的商用a e si p i n t e l l e c t u a lp r o p e r t y 核 有的公司己 经开发出了基于这些p 核的硬件产品 对国内来说 虽然有关a e s 算法的硬件产 品还很少 但越来越多的国内公司和研究机构己经把目光投入到a e s 的硬件实 现当中 相关的研究项目也如雨后春笋般出现 一般商用的a e si p 核的获得都需要付费 但有许多大学和机构提供免费使 东北大学硕士学位论文 第一章绪论 用的p 核 还有如o p e n c o r e s 这样的自由i p 核提供者也提供有免费的下载 其中 美国的g m u 和n s a 等大学和机构在a e s 生效之前就提供有关于a e s 的口核以供测试 其中g m u 大学的核性能优越 所以下面以g m u 大学的a e s 核 i z 为代表进行介绍 它具有以下特点 a 支持n i s t 所要求的三种不同密钥长度 b 加密和解密功能采用了资源共享 c 密钥扩展与加密 或解密 并行进行 d 在有限的电路面积下具有很高的速度 吞吐量 外部接口简单通用 基于以上的优点 它可应用于i p s e c s s kv p n 等安全协议 人们在硬件设 计的时候大多将g m u 大学的1 p 核作为参考 而在a e s 生效以后的i p 核设计中 也大都是以这些特点为主要目标来开发的 各大公司所提供的商用i p 核在性能 上与各大学和研究机构所提供的相似 只是在外部接口上有所不同 2 软件实现 所谓的软件实现 就是算法经过编成 在8 位处理器或3 2 位处理器等上运 行 a e s 有很多软件实现方法 通过把有限域g f 2 5 上的运算化成多项式的 运算来执行 把g f 25 中元素乘0 2 的运算结果用表存储 然后把g f 28 中的乘法运算转化成乘0 2 的幂的运算 这样通过查0 2 表就可以计算结果 另一 种方法是把g f 2 5 中的非零元表示成生成元的幂 然后生成两张表 通过查 表来实现乘法运算 这方面的研究也是人们追逐的热点 1 3 论文主要工作及结构安排 本文主要研究了a e s 算法设计策略和安全性 研究其实现方法并在智能卡 上实现 由于d e s 及其d e s 类算法已经不能够提供足够的安全性 而现今使用 的大多数密码产品都是使用d e s 算法的 人们急切地需要更加安全的加密算法 从而对剐刚颁布的高安全的a e s 加密算法 就是人们首选的代替d e s 产品的加 密算法 对a e s 产品的开发将是密码学界的很重要的课题 现今对a e s 产品的 开发还是起步阶段 很多工作需要我们来做 论文的章节安排如下 第一章概述课题的重要性 总结前人的工作 第二章讨论a e s 算法设计原理及其安全性 3 东北大学硕士学位论文第一章绪论 第三章总结前人实现方案并提出新的实现方案 第四章讨论a e s 算法在智能卡上的应用 4 东北大学硕士学位论文 第二章a e s 算法及其安全性分析 第二章a e s 算法及其安全性分析 2 0 0 0 年1 0 月2 日 美国国家标准局 n i s t 宣布 比利时密码学家j o a n d a e m e n 和v i n c e n tr i j m e n 设计的 r i j n d a e l 算法 以安全性好 运算速度快 存 储要求低 灵活性强最终当选a e s a d v a n c e de n c r y p t i o ns t a n d a r d 该算法对目 前的各种密码攻击方法是免疫的 这标志着信息技术有了新的安全工具 为计算 机网络和电子商务的发展提供了强有力的保障 2 1a e s 加密算法简介 a e s 算法与r i j n d a e l 算法基本相同 其之间的区别仅在于各自所支持的分组 长度和密码密钥长度的范围不同 r i j n d a e l 算法是具有可变分组长度和可变密钥 长度的分组密码 其分组长度和密钥长度均可独立地设定为3 2 比特的任意倍数 最小值为1 2 8 比特 最大值为2 s 6 比特 a e s 将分组长度固定为1 2 8 比特 而 且仅支持1 2 8 1 9 2 或2 5 6 比特的密钥长度 首先明文作为初始状态 然后经过一系列密钥依赖变换 最后把最终状态作 为密文 一个状态s 可形象地表示为4 4 的字节矩阵 s i j a o 1 2 3 图2 1 0 o 1 0 2 o 3 0 0 1 g 1 2 1 3 舯 0 2 1 2 2 2 3 2 0 3 g 3 2 3 3 3 图2 1 指标 i j 在一个4 4 字节矩阵中的位置 f i g 2 1t h ep o s i t i o no fi n d e x 蛳 i na4 4b y t e sm a t r i x 加密过程分为四个阶段 密钥扩展 k e y e x p a n s i o n 轮密钥加 a d d r o u n d k e y n 1 轮 对应1 2 8 1 9 2 2 5 6 位密钥长度 n 分别为1 0 1 2 1 4 1 轮变换 r o u n d 及最后一轮轮变换 f i n a l r o t m d 轮变换包括字节代换 s u b b y t e 行移位 s h i f t r o w 列混淆 m i x c o l u m n 和轮密钥加 a d d r o u n d k e y 四个过程 最后一轮变换包括字节代换 行移位和轮密钥加三 个过程 用伪c 代码表示如下 a e s s t a t e c i p h e r k e y 巧 东北大学硕士学位论文 第二章a e 算法及其安全性分析 k e y e x p a n s i o n c i p h e r k e y e x p a n d k e y 密钥扩展 a d d r o u n d k e y s t a t e r o t m d k e y 轮密钥加 f o r i l i n i r o u n d s t a t e e x p a n d k e y i 轮变换 f i n a l r o u n d s t a t e e x p a n d k e y n 最后一轮变换 r o u n d s t a t e r o u n d k e y 轮变换 s u b b y t e s t a t e 字节代换 s h i f t r o w s t a t e f 行移谴 m i x c o l u m n s t a t e 列混淆 a d d r o u n d k e y s t a t e r o u n d k e y 轮密钥加 f i n a l r o u n d s t a t e r o u n d k e y 最后一轮变换 s u b b y t e s t a t e s h i f l r o w s t a t e a d d r o u n d k e y s t a t e r o u n d k e y 解密过程是加密的拟过程 a e s 算法的加解密流程图如图2 2 所示 东北大学硕士学位论文第二章a e s 算法及其安奎l 生分析 从被加密文件中顺序 加密流程 解密流程 图2 2 a e s 算法加 解密流程图 图2 4t h ef l o wc h a r to f a e s e n c r y p t l o n d e c r y p f i o n 2 2 算法所使用的主要变换 1 字节代换 s u b b y t e 字节代换是一个非线性字节替换 它对每一状态字节独立地进行运算 这个 变换是可逆的 并且它是由两个变换复合而成 这两个变换是 a 对所有的子字节在有限域g f 2 8 中求其乘法逆 且规定t 0 0 的逆为 0 0 0 1 的逆仍然为 0 1 东北大学硕士学位论文第二章a e s 算法及其安全性分析 b 在g f 2 上作如下仿射变换 2 1 这两个变换合用s u b b y t e s t a t e 来记 在这个变换中在有限域g f 2 8 中求 其乘法逆的方法如下 将g f 2 5 中的元素看作次数小于8 且系数取自g f 2 的多 项式 并执行既约多项式m o x 8 x4 x 3 x 1 下的模乘运算 由此可定义乘法 的逆 2 行移位变换 s h i f t r o w s t a t e 4 4 字节矩阵 的第一行保持不变 第2 3 4 行分别循环左移1 2 3 个字节 3 列混淆变换 m i x c o l u m n m i x c o l u m n 过程称为列混合变换 在该变换中 将状态的每列视为有限域 g f 2 8 中的的多项式且被一个固定的多项式c x 0 3 x 3 0 1 x2 0 1 x 0 2 的模x4 1 乘 将其用矩阵形式表示为 j 乙 o s l o s 2 o s 3 o s o l s l 1 s 2 j s 3 1 s o 2 s 1 2 s 2 2 s 3 2 s o 3 s 1 3 s 3 s 3 2 2 乘积矩阵中的每个元素s 是系数矩阵中第i 行元素c o e f m i x i 与s t a t e 矩阵 中第j 列元素s t a t e j 的乘积之和 这里的加法与乘法都定义在有限域g f 28 上 加法即按位异或操作 乘法遵循g f 2 6 上的多项式乘法规则 4 轮密钥加 a d d r o u n d k e y 在这个变换中 s t a t e 的调整通过与一个轮密钥进行逐位异或而得到 轮密 钥记作r o u n d k e y i 0 i 2 k e y e x p a n s i o n k 4 以 w 4 4 1 f o rn t 一4 6 f o r0 o j m j f b 坪 o i 4 i w i c i k i d f o r0 以0 4 1 j 咎 玷 s s s s 啦 啦 玷 轴 s s s s 鼬跏跏跏 咿 邶 加 蛐 s s s s 东北大学硕士学位论文第二章a e s 算法及其安奎陛分析 i f am o d 以 o w o j l w o u 一甄l o s w d u i o r c o n u n f o r i 1 i 4 w i u w i i os w i 1m o d4 i j 1 e l s e f o r i o i 4 i w i u w i l j m 0 w i i 1 盯 表2 1 4 或6 时的密钥扩展 t a b l e2 1k e y e x p a n s i o ni nn k 4o r6 k e y e x p a n s i o n c k 4 以 w n 删 1 f o r 机 8 f o rg 0 j t0 t b r i 0 i 4 i w i j k i d f o r 0 l j 4 1 0 i f o r o o dm 0 w o u w o d 札 a s w 1 i j 1 o r c o n j 以 f o r i 1 i 4 i w i 彻 w i t ds w i ir o o d4 j 1 i 东北大学硕士学位论文 第二章a e s 算法及其安全性分析 e l s e e l s e f o r i 0 i 4 十 w i t i w t i l j n o w i j 一1 f o r i 1 i 4 i w i 踟 w i d t o w i j 一1 列表2 2 i 8 时的密钥扩展 t a b l e2 2k e y e x p a n s i o ni nm 8 2 3s p n 结构及宽轨迹策略 a e s 算法使用s p n 结构和宽轨迹设计方法 这种结构和方法的设计使a e s 算法的安全性和高效得到很好的发挥 2 3 1s p n s u b s tir u tio na n dp e r m u t a tio nn e t w o r k 结构 分组密码设计主要采用了两种结构 f e i s t e l 网络和s p n 结构 最初的设计 中 主要采用f e i s t e l 结构及其变形 f e i s t e l 结构的主要优点是解密容易实现 设 计主要是构造好的s 盒 典型代表是d e s s p n 是继f e i s t e l 结构之后的另一种 分组密码的总体结构 它的特点是层次清晰 便于分析 a e s 算法就是采用这 种结构的典范 现代分组密码设计原理没有变 即还是遵循仙农提出的两个准则 混乱和扩散 众所周知 结构决定功能 流行的s p n 正是采用功能明确的三个 模块 代替层 s u b s t i t u t i o nl a y e r 卜用来实现混乱作用 置换层 p e r m u t a t i o nl a y e r 或称扩散层 d i f f u s i o nl a y c r 一用来实现扩散作用 密钥加层 k e ya d d i t i o n 卜 实现数据和密钥的混合 1 1 东北大学硕士学位论文 第二章a e s 算法及其安全 生分析 一个采用s p n 结构的分组密码是一个密钥交替分组密码 它具有下面一些 性能 a 交替性 该定义为独立于密钥的轮函数与密钥加法的交替使用 在轮 函数开始之前和最后一轮之后也都应用密钥加法 b 简单的密钥加法 轮密钥通过简单x o r 运算与中间状态相加 一轮 的s p n 结构一般由与密钥加法 替换和线性变换三层构成 若一个非零输入差分的s 盒称为差分活动s 盒 给定了一个非零输出掩码 值的s 盒称为线性活动s 盒 则对于s p n 结构 在差分概率和差分活动的s 盒 的数目之间 有紧密的联系 当差分活动的s 盒数目最多时 差分概率达到最小 反之达到最大 因此 分支数的概念被引用 从差分分析的观点来看 分支数指 两轮s p n 结构差分活动的s 盒的最少数目 从线性分析角度来看 指两轮s p n 结构线性活动s 盒的最小数目 对于s p n 结构 线性变换的设计影响分支数的 多少 a e s 算法的s p n 结构采用了宽轨迹策略 经过两轮轮函数 分支数达到 2 5 2 3 2 宽轨迹策略 t h ew id e t r a iid e s i g ns t r a t e g y 宽轨迹策略是一种用于设计密钥交替分组密码轮变换的手段 它同时兼备高 效率与抗差分和线性密码分析两种特性 其把轮变换分成两种可逆步骤 1 r 一个局部的非线性变换 所谓局部性是指任何一位输出比特只依赖于 有限数量的输入比特 并且邻近的输出比特只依赖于邻近的输入比特 2 a 一个可提供高度扩散性的线性混合变换 因此轮变换p 可表示为 p 7 a 2 4 在之前的密码设计中 如d e s 着重于y 步骤的设计 主要是设计出好的 s 一盒 但是这种着重y 步骤的设计很容易增加软件实现重中程序的大小和硬件实 现中芯片的面积大小 宽轨迹策略则主要重视了a 步骤的设计 其主要目的就是 设计一种变换 使得这种变换不存在过多的非活跃s 盒 从而可抗击线性和差 分分析 作为宽轨迹设计的结果 a e s 的轮函数由三个起不同作用的步骤构成 依 据宽轨迹策略而设计的密码中 相当多的资源花费在后两个线性步骤上 以提供 1 2 东北大学硕士学位论文 第二章a e s 算法及其安全性分析 高的多轮扩散性 为了达到更好的效果 a e s 算法把 步骤分为两个不同步骤 f 1 e 提供高的局部扩散性 2 玎 提供高的全局分散性 从而 2 4 式变为 p 2 yo 石o0 2 5 在a e s 算法中 这三种步骤分别对应了不同的变换 a s u b b y t e 非线性步骤y 并行地对每个状态字节进行操作 b s h i f t r o w 换位步骤玎 换位每个字节的位置 提供全局分散性 f c l m i x c o l u m n 混合步骤0 对列进行操作 每列包含4 个字节 宽轨迹策略允许达到差分特征概率的可证明上界 这样的概率特征可成为轨 迹 降低轨迹的概率 即限制差分传播的概率是宽轨迹策略的设计策略 抵抗差 分分析的安全性证明的第一步是确定足够大的轮数使得所有的差分轨迹都小于 2 1 r 日n d a e l 的轮函数强调了多轮轨迹能达到的相关性和概率的上限 通过建立 在m d s 码上的混乱函数结合字节变换这样的轮函数 已经证明在四轮差分轨迹 下活动的s 盒数限定在2 5 以下 既然在一个活动的s 盒下差分传播概率最多是 2 6 因而八轮差分轨迹的概率最多是2 3 相似的结论应用到线性分析 我们 可以看到八轮的线性相关性贡献低予2 k e l i h e r 建议一个找到s p n 结构的最 大线性逼近概率的上界的方法 此方法应用到a e s 七轮或更多轮大约将产生2 的最大逼近概率上界 应用到九轮或更多轮的a e s 将产生2 的线性逼近上 界 但都只是理论分析 不具有可操作性 从而可看出a e s 算法有很好的抵抗差分和线性分析的能力 2 4 安全性研究 2 4 1 密码分析分类 常用的密码分析攻击有 1 唯密文攻击 c i p h c r t e x t o n l ya t t a c k 2 已知明文攻击 k n o w p a i n t e x ta t t a c k 3 选择明文攻击 c h o s e p l a i n t c x ta t t a c k 1 3 东北大学硕士学位论文 第二章a e s 算法及其安全性分析 4 自适应选择明文攻击 a d a p t i v e c h o s e n p l a i n t e x ta t t a a c k 5 选择密文攻击 c h o s e n c i p h e r t e x ta t t a c k 6 选择密钥攻击 c h o s e n k e ya t t a c k 2 4 2 蛮力攻击 现有的蛮力攻击手段有穷尽密钥搜索攻击 字典攻击 查表攻击和时间一 存储权衡密钥攻击 这些攻击手段可以作用于任何一种密码算法 攻击的复杂度 只依赖于分组长度和密钥长度 而它们的复杂程度是随着密钥长度增加成指数增 长的 对于a e s 算法 密钥长度最小也是1 2 8 比特 就算是每秒钟能够完成 2 5 6 d e s 的密钥长度为5 6 即一秒钟就攻破d e s 个密钥的搜索 要完成a e s 的密钥搜索 最少需要的时间大约是1 4 9 万亿年 这在时间和空间上都是不可行 的 因此在现在和将来一段时间里 r i j n d a e l 算法对强力攻击是免疫的 2 4 3 差分与线性密码分析 差分与线性密码分析方法是迄今己知的攻击迭代密码算法普遍适用且最有 效的方法 差分密码分析差分密码分析实质上是一种选择明文攻击 其基本思想 是通过分析明文对的特定差分对密文对差分的影响来恢复某些密钥比特 所以其 本质是研究明文对的差分 密码算法中间过程输出对的差分及密文对差分之间的 关系 线性密码分析是一个已知明文攻击 其中使用大量的明文密文对来确定密 钥位的值 线性密码攻击的本质是找出密码算法的有效线性逼近及各轮线性逼近 之间的关系 对于a e s r i j n d a e l 算法 文献 2 5 i 正n t 不存在可预测的扩散率大于2 1 的 4 一轮差分轨迹 同样可以证明不存在相关系数大于2 3 的4 一轮线性轨迹 因 此 4 轮的r i j n d a e l 算法就可以有效的抵抗差分密码分析和线性密码分析 2 4 4s q u a r e 攻击 s q u a r e 攻击是迄今为止对a e s 算法威胁最大的密码分析方法 这个攻击也 称为 渗透攻击 这种攻击是一种针对具有a l e s 轮结构密码的选择明文攻击 它的实施与非线性步骤中s 盒的选择和密钥扩展都无关 它对于一个至多6 到7 轮的a e s 简化版本 对a e s 1 9 2 和a e s 2 5 6 版本 的攻击要比密钥穷举攻击方 法更快 n f e r g u s o n 等人优化了这种攻击的工作因子 7 1 优化的算法可攻击到9 一1 4 东北走学硕士学位论文g 章a e s 算法及其安全性分析 轮的a e s 算法 2 4 5 碰撞攻击 这种攻击方法是g i l b e r t 和m i n i e r 在 3 5 y 9 提出的 其可对一种简化到7 轮 的a e s 算法进行攻击 尽管这种攻击的工作因子提高了 但仍比只对a e s 1 2 8 的穷举密钥搜索方法更有效 2 4 6 一些新的分析理论 一 k x 三晕c 2 2 回x k k x c 4 厶k x 1 5 东北大学硕士学位论文 第二章a b s 算法及其安全性分析 算法 可以通过两个这种类型的方程来利用计算的中间结果 第一个方程可以将 5 轮以后的中间变量作为明文字节函数 第二个方程可将6 到1 0 轮以后的中间 变量作为明文字节函数 结合两个方程可以得到一个含有2 个位置变量的方程 通过充符这个方程2 次之后 从信息论的意义上来说 就有足够的信息能解出 位置变量 但到目前为止 还没有有效的方法来解此方程组 2 x s l 方法 c o u r t o i sa n dp i e p r z y e k 3 6 通过研究发现 在a e s 算法中使用的s 盒可以通过 一系列隐含的二次布尔方程表达 用字母x 1 t x 表示输入的位 用字母y 1 一y 表示输出的位 则存在如下形式的等式 f x l x 8 y 1 y8 0 2 7 其中函数f 为二次方程 从理论上来说 只需要8 个像 2 7 式的方程就能够定义s 盒 但是c o u r t o i s e l p i e p r z y c k 经研究发现 能够构建多于所需要的方程个数 此外 他们还宣称这 些特定的方程可以有助于简化解决问题的复杂性 他们发现一个算法 该算法 在处理这个问题的时间复杂度低于指数 可是有很多的研究者怀疑他们计算的 正确性 无论如何 在假设他们的计算方法正确的前提下 破解密码的复杂性 的最好估计是2 步 这就意味着 他们的攻击仅仅可以破解a e s 算法为2 5 6 位 的密钥 a e s 一2 5 6 因为相应的穷尽密钥搜索攻击的复杂度为2 现在还不清 楚a e s 算法的什么属性影响到该攻击的复杂性 这种攻击方法对a e s 的影响不 会太大 因为即使这种攻击方法完全正确 a e s 的安全性也比d e s 好得多 3 嵌入法 m u r p h y 和r o b s h a w 3 4 定义了分组密码b e s 它是萍j 1 2 8 字节为一组而不是1 2 8 位为一组的对象来处理 按照m u r p h y 和r o b s h a w 的观点 b e s 算法的代数结构 甚至比a e s 密码的代数结构更简单 此外 a e s 算法能够被嵌a b e s 密码中 也就是说有如下映射妒 a e s t x 2 伊 b e s 排 妒 2 8 在这个方程中 k 代表密钥 x 代表明文 m u r p h y 和r o b s h a w 通过研究得 出b e s 的一些性质 但是b e s 的属性不能转换为a e s 密码的性质 m u r p h y 和 r o b s h a w 相信 如果将x s l 方法应用到b e s 则解决步骤的复杂性将比直接将 x s l 方法应用到r i j n d a e l 密码的复杂性大大降低 4 对偶密码攻击 1 6 东北大学硕士学位论文 第二章a h s 算法及其安全性分析 e l a db a r k a n 和e t ib i h a m 在文献 2 7 中介绍了对偶密码的概念 它基本是 嵌 入 技术的归纳 其基本内容为 如果取三个可逆映射艟和h 则存在一个双 密文d u a l 满足 a e s 女 x f 1 d u a l2 i h p 2 9 在这个方程中 k 代表密文密钥 p 代表明文 这个方程表示对于一个给定 的明文和密钥对偶密码产生相同的密文文本 从这个意义上来说 对偶密码等价 于原来的密文 因此 可以实现和分析对偶密码而不是原来的密文 在文献 2 7 中确定了r i j n d a e l 密码中的2 4 0 个对偶密码 到现在 还没有关于双密文有何漏 洞的报导 一个类似的概念 称为r i j n d a e l g f t 已经证明 对于抵抗差分和 线性密码分析 r i j n d a e l g f 族密码系统的密文都具有相同的安全性 2 4 7 小结 以上我们对a e s 算法现有的分析方法进行了总结和分析 并对一些新的分析 思想进行了探讨 并据此可看出到目前为止还没有有效的对完整舨的a e s 算法的 攻击方法 1 7 东北大学硕士学位论文第三章a e s 算法实现方案 第三章a e s 算法实现方案设计 本章主要讨论a e s 算法的软件实现方法 对算法硬件实现问题这里不进行 讨论 由于大多数智能卡都使用8 位处理器 因此主要讨论a e s 算法在8 位处 理器上的实现问题 3 1x t i m e 表示方法 3 1 1 加密算法 a e s 算法中的运算大部分都是在域g f 28 上元素的加法和乘法运算 而 乘法只是变元与常量的乘积 域g f 28 中两个元素的运算通常通过转化为次 数不超过7 的域g f 2 上的多项式运算来实现 由于g f 28 中的每一个元 素都能够写成g f 2 4 中元素0 2 的不同幂次的和 若我们定义一个函数x t i m e x 其输出为0 2 与x 的乘积 则g f 28 中的元素x 与一个常数的运算可 通过重复调用x t i m e 函数来实现 但这种实现方法容易受到时问攻击的威胁 为 了防止时间攻击 我们定义一张表m 其中m x 0 2 x 于是实现x t i m e 函数就 是实现查表m 也就是说与常数的乘法运算可通过重复查表m 来实现 用这种方法对a e s 算法各步骤进行实现的方案如下 s u b b y t c 步骤 这个步骤分两部分 第一部分为一个有限域g f 28 上的 字节求逆运算 第二部分为一个仿射变换 对求逆运算我们可通过一张表来实现 也就是把所有g f 2 8 上的元素的 的逆做成一张1 6 1 6 字节的表 然后通过查表来实现求逆运算 然后再进行仿射 变换 仿射变换用伪c 代码描述如下 p r o c e d u r ea f f i n e 而 屯 屯 k 鼍 x i 是一个字节x 的8 位 0 i s 7 y o x ox o r x o r x o r 魄x o r x x o r l y 1 x ox o rtx o r 而x o r x o r 而x o r l y 2 x o r 置x o r 吃x o r x o rx 7 1 8 东北大学硕士学位论文 第三章a e s 算法实现方案 y 3 x o r x o rx 2x o r 鼍x o r y 4 x ox o r x o rx 2 x o rx 3 x o r y 5 x o rx 2 x o rbx o r x o rx 5x o r l y 6 x 2x o rx 3x o rx 4x o r 巧x o r 魄x o r l y 1 x 3x o rx 4x o rx 5 x o rx 6x o rb r e t u m y o y l y 2 y 3 y 4 y 5 y 6 y 7 当然可以把求逆运算和仿射变换合成在一起来制成一张1 6 1 6 字节的表 s h i f l r o w 步骤通过状态各字节存储位置移动来实现 而a d d r o u n d k e y 则通过 简单的位异或就可以实现 对m i x c o l u m n 步骤 通过x t i m e 函数实现 过程如 下 t m p a 0 e a 1 o a 2 o a 3 l a 是一列 t m e t 0 o a 1 t m x t i m e t m a o t m t m p t m a 1 1 o a 2 t m x t i m e t m a 1 1 t m o t m p t m a 2 o a 3 t m x t i m e t m a 2 t m o t m p t m a 3 e a o t m x t i m e t m a 3 t m o t m p 表3 1m i x c o l 咖实现步骤 t a b l e 3 1m i x c o l u m ni m p l e m e n t i n gs t e p s 对密钥扩展 在单个运算中实现密钥扩展有可能会占用智能卡过多的r a m 内存 因此可使用缓存来存储扩展密钥 而不是每次都生成密钥 3 1 2 解密算法 解密可通过把i n v a d d r o u n d k e y h a v s h i f l r o w i n v s u b b y t e i n v m i x c o l u m n 与 加密相似的方法来处理 但是这里要重点指出的是 由于i n v m i x c o l m n n 过程在 结构上与加密相似 不同之处在于调用了i n v m i x c o l u n m 而不是m i x c o l u m n m i x c o l u m 的系数只能为0 1 0 2 0 3 而i n v m i x c o l u m n 的系数只能为0 9 0 e 0 b 和0 d 在8 位处理机上实现系数较大的乘法显然需要更多的运算时间 从而 导致性能降低 使用表查询是一种改善性能的办法 不过这种办法将增加额外的 表开销 1 9 东北大学硕士学位论文 第三章a e s 算法实现方案 p b a r r e t o 发现了m i x c o l u m n 多项式c x 与i n v m i x c o l u m n 多项式d x 之间满 足如下的关系 d x 0 4 x2 0 5 c x m o dx4 o i 3 1 用矩阵来表示 则上述关系变成 o e o bo d0 9 0 9 昭衄0 d 0 d0 9 o 层0 曰 o b9 d0 9o e 0 20 3 0 1 0 2 0 10 1 0 30 1 0 1 0 1 0 30 1 0 20 3 0 1 0 2 3 2 因而 h v m i x c o l u m 可通过一个简单的预处理步骤和一个m i x c o l u m n 步骤 来实现 列表3 2 给出了该预处理步骤的算法 如果由实现这一预处理步骤所造 成的性能上的少许下降可以让人接受的话 就不需要定义额外的表 u x t i m e x t i m e a 0 o a 2 a 是一列 v x t i m e x t i m e a 1 1 0 a 3 a o a o u a 1 a 1 1 o v a 2 a 1 1 o u a 3 a 3 0 v 列表3 2 实现解密的预处理步骤 t a b l e3 2 t h ep m t