加密密算法RC.ppt

加密解密算法RC实现的调研报告 仲力王宇旸 概述 密码学有对称密码学和公钥密码学两大分支 目前我们重点调研了对称密码学 在对称密码学中 加密方和解密方使用相同的密钥 DES和AES是目前最主要的对称加密算法 在公钥密码学中 加密方和解密方使用不同的密钥 RSA和ECC是目前最主要的公钥加密算法 内容安排 对称密码学DES 5min AES 5min 对称密码学综述 10min 公钥密码学RSA 5min 椭圆曲线密码学 ECC 5min 小结和进一步的调研方向 5min 对称密码学 DES算法 DES算法特征 DES设计时只考虑方便硬件实现 因此很方便用硬件实现 但难以用软件有效的实现 DES使用64位分组和56位密钥 DES算法是Feistel结构 因此加密算法和解密算法是相同的 只是子密钥的使用次序相反 DES算法最耗时的部分是16轮的f R K 函数的计算 f函数的计算有四个步骤 1 扩充 置换函数e 2 48bitXor 3 8个不同的S Box 6bit输入4bit输出 查表 4 置换P函数 扩充 置换函数e S Box范例 S1 置换函数P F R K 函数中四种运算的分析 Xor软件硬件都很容易做置换函数e和P软件很难有效的实现 而硬件只需要定制相应的数据通路 很容易实现 S Box运算软硬件均可用查表实现 但软件只能串行地查8个表 而硬件可以并行查表 数据长度不规整 6 4 48bit 不利于软件有效实现 DES小结 DES难以用软件有效的实现 但很容易用硬件实现3DES算法要做3次DES运算 软件实现的速度更低 AES算法 Rijndael AES算法 AES是NIST从5种候选算法 MARS RC6 Rijndael Serpent TwoFish 中评选出来的 能够高速的在各种软硬件平台上实现是重要的选择标准 最终Rijndael当选 AES使用128位分组 128 192或256位密钥 使用不同长度的密钥时算法执行的轮数不同 AES不是Feistel结构的 其加解密算法不相同 AES算法中主要的运算 AddRoundKey是一个128bit分组和128bit子密钥的Xor操作 SubBytes是16次S Box操作 AES使用的一个8bit输入8bit输出的S Box ShiftRows是3次32bit的循环移位操作 分别是循环左移8位 16位和24位 AES算法中主要的运算 MixColumns是1个矩阵乘法运算 两个4 4的8bit方阵相乘 其中一个方阵是常数 用到的加法和乘法是定义在有限域GF 28 上的 加法实际是Xor 乘法可以通过移位和Xor操作方便的实现 对软件也可以通过查表法加速实现 AES中运算的特点 AES所有的操作数长度都是8bit的2n倍 并且没有复杂的位运算 因此很容易在各种平台上 8位 32位 64位机 智能卡等 用软件有效的实现 研究表明 AES算法有很高的指令集并行性 ILP 可以很好的利用现代CPU的流水线 超标量等技术 AES也很容易用硬件实现 对称密码学算法硬件实现综述 硬件实现的指标 吞吐率 Throughput 消耗的硬件资源 Area 效能 Efficiency Throughput Area 延迟 Latency 硬件实现的4种不同的设计目标 最小化资源消耗在无限的资源下最大化吞吐率在固定的资源下最大化吞吐率最大化效能 对称加密算法的工作模式 常用的工作模式有ECB CTR CBC CFB OFB ECB和CTR是非反馈模式 CBC CFB OFB是有反馈模式 ECB模式 CBC模式 工作模式对硬件实现的影响 非反馈模式中 不同的分组之间的加密运算时可以并行执行的 因此可以用流水线技术极大的提高吞吐率 反馈模式中 各个分组的加密运算必须相继串行计算 无法从流水线技术中得到好处 硬件实现可以采用的结构 BasicArchitectureLoopUnrollingInternalPipeliningExternalPipeliningHybridPipelining BasicArchitecture LoopUnrolling InternalPipelining ExternalPipelining 4种结构的速度比较 speedba 1 rounds clock period speedul speedba 1 t 1 t k 其中t m r ck roundinternalpipelining 理想情况下 clock period可以比basic结构提高k倍 仅对非反馈模式有效 对k roundexternalpipelining 理想情况下 速度比相同clock period的basic结构提高k倍 仅对非反馈模式有效 4种结构的area比较 Basic结构消耗的area最少 Internalpipelining只比Basic结构增加了少量的area 用于pipelinestage间的寄存器 k roundunrolling externalpipeling大约会增加k倍的area 其他影响硬件实现的因素 是否需要在一块芯片 或FPGA 上同时实现加解密算法Feistel结构的算法 同时实现加解密算法比只实现加密算法增加的area不到10 非Feistel结构的算法area增加较多 AES算法会增加60 的area 对于RC系统 如果需要同时实现加解密算法 有两种方法 1 使用动态可重构 2 在一个配置里同时实现加解密功能 方法2在加解密功能切换速度比1快 但会消耗更多的area 而1可以利用这些area对吞吐率进行优化 其他影响硬件实现的因素 是否要实现子密钥生成算法如何实现子密钥生成算法算好所有的子密钥存在寄存器中 以后不再重复计算 loopunrolling externalpipelining结构必须使用这种方式 on the fly的计算方式 可以省去保存子密钥的寄存器 NIST对5种AES候选算法硬件实现的评估 Rijndael和Serpent的吞吐率和效能都很高 RC6和Twofish的吞吐率效能处于平均水平 但可以在很小的area上实现 MARS的吞吐率 效能都是最差的 不太适合硬件实现 主要原因有异种的循环结构 大的S Box等 公钥密码学 公钥密码学 公钥密码算法应满足的条件产生一对密钥 KU KR 在计算上是容易的已知公钥KU和明文M 计算密文C是容易的用私钥KR解密接收到的密文C是是容易的已知公钥KU 攻击者要确定私钥KR在计算上是不可行的已知公钥KU和密文C 攻击者要恢复明文M在计算上是不可行的 公钥密码学 在公钥密码学概念提出后的几十年中 只有两个满足这些条件的算法 RSA 椭圆曲线密码体制 为人们普遍接受 公钥密码学的安全性一般要依赖于某种计算难题 RSC基于大数因数分解难题ECC基于椭圆曲线上的离散对数难题公钥密码学算法要比对称密码学算法慢几个数量级 RSA简介 RSA是目前使用最广泛的公钥密码学算法 RSA 密钥产生选择两个素数 p和q计算n pq计算z p 1 q 1 选择e使得 gcd e z 1且e z确定d使得d emodz 1且d z公钥KU e n 私钥KR d n 为了保证安全性 RSA算法实际使用的密钥长度多达几百至上千bit 密钥产生 密钥产生需要做以下工作 确定两个大素数p和q选择e 并计算d目前选择素数一般是随机挑选一个奇数n 再用Miller Rabin等概率算法判断n是否是素数 求e和d一般使用扩展Euclid算法 随机选择e z 用扩展Euclid算法求gcd z e 并且当gcd z e 1时 扩展Euclid算法还能同时求出d RSA 加解密运算加密算法为C Memodn解密算法为M Cdmodn 实现RSA算法 密钥产生算法远没有加解密算法常用 故一般只考虑用硬件加速加解密算法 即加速模幂 modularexponentiation 运算 高速实现模幂运算是一个数学问题 有很多相关的研究 实现RSA算法 模幂运算可以分解为多个模乘运算如何分解 用最少的模乘来实现模幂如计算x4 可以计算x4 x x x x 这需要4次模乘 也可以x2 x x x4 x2 x2 只需要两次模乘 这是一个加法链问题 对序列a0 a1 ar 其中a0 1 ar e 对任意的k 都存在i j k使得ai aj ak 求满足上述提条件的最短序列 实现RSA算法 已证明加法链问题是NP完全问题有多种求次优解的启发式算法 BinaryMethodm aryMethodFactorMethodPowerTreeMethod 实现RSA算法 实现模乘运算 有以下路线先作乘 再取模Blakley smethodMontgomery smethod目前高速的RSA硬件实现一般都使用Montgomery方法或其变种 并利用中国剩余定理 CRT 来加速解密 椭圆曲线密码学简介 椭圆曲线密码学目前越来越被重视和RSA相比 ECC最诱人之处在于 它可以使用比RSA短得多的密钥得到相同的安全性一个很粗略的估计 160位的ECC大约和1024位的RSA有着相同的安全性 椭圆曲线密码学简介 椭圆曲线由方程y2 x3 ax c上的所有点和一个无穷远点O构成 椭圆曲线可以定义在任何域上 如实数域 复数域 密码学中用到的椭圆曲线都是定义在有限域上的 椭圆曲线算数定义了椭圆曲线上的加法运算 实数域上的椭圆曲线加法 椭圆曲线乘法 椭圆曲线乘法由加法定义 P k Q为k个Q相加 椭圆曲线密码学基于如下性质进行加密 给定Q和k 容易计算P k Q 但给定P和Q 求k在计算上不可行 有限域上的椭圆曲线 有限域上的椭圆曲线没有直观的几何意义 但加法 乘法的定义和实数域上的椭圆曲线类似 密码学中使用Zp域上的素曲线和GF 2n 上的二元曲线 GF 2n 上的椭圆曲线特别适合硬件实现 可以用异常少的门电路来得到快速且功能强大的密码体制 小结 加解密算法是非常常用算法 为了获得高的吞吐率 很值得用硬件来加速 加解密算法都是计算密集型的 一般控制流简单 很适合用硬件实现 不少加解密算法中都有大量的有限域运算或复杂的位运算 硬件