8比特AVR微控制器上高效及抗侧信道攻击的RSA算法的实现

论文摘要

RSA算法是现在应用最广的公钥密码算法,但是一直以来,受限于嵌入式设备的有限资源问题（如CPU运行速度,内存等）,使RSA算法很难在嵌入式设备上高速的运行。近些年来,很多算法被提出用来解决RSA算法的快速软件实现问题：这些算法,从算法实现角度较高层次的一些方法,比如利用中国剩余定理（CRT）,到一些从细节入手的智能优化模运算的方法,比如混合乘算法。在本硕士毕业论文中,我们提出了一种新的基于多精度乘法的混合乘算法,这种新的混合乘算法不仅可以优化内存的访问次数还可以优化寄存器的分配问题。相对于Gura等人提出的原始混合乘算法,新算法的内循环节约了7.8%的运行时间。我们将这种混合乘算法和“分离操作数扫描算法”（SOS）结合起来组成HSOS算法,一种实现大整数模运算的新模乘算法。我们在微控制器Atmega128上的实验表明：对于RSA算法运算中用到的典型长度的操作,HSOS算法胜过任何其他的模乘算法,并且在借助于中国剩余定理和m-ary的模指数算法前提下,一个1024比特的私钥操作可以在76·106时钟周期内完成,这代表着RSA在8-比特微控制器上运行时间的一个新记录。此外,我们还在RSA实现程序中整合了低能耗的抵御侧信道攻击的策略,使之能够抗侧信道攻击,而相对于没有加抵御策略的RSA实现,这些策略的加入仅仅增加了12%的运行时间。基于RSA算法的高效实现和抗侧信道攻击相关知识。本论文的主要贡献及创新之处：1.提出了三种新的混合乘算法的内循环算法,并且每种混合乘内循环算法都比原来的算法运算速度快,相对于原算法完成32比特乘32比特的乘法需要141个时钟周期,我们的第一种算法只需要114个时钟周期就可以完成（图4.3）,第二种算法只需要108个时钟周期就可以完成（图4.4）,而第三种算法仅需要102个时钟周期（图4.5）。2.基于我们新的混合乘算法的内循环算法,我们提出了HSOS算法,一种新的模乘算法。实验表明：对于RSA算法运算中用到的典型长度的操作,HSOS算法胜过任何其他的模乘算法,并且在借助于中国剩余定理和m-ary的模指数算法前提下,一个1024比特的私钥操作可以在76·106时钟周期内完成,这代表着RSA在8-比特微控制器上运行时间的一个新记录（表4.4）；3.在增加低成本的抵御侧信道攻击策略之后,我们高效实现的RSA算法可以抵御简单功耗分析攻击（SPA）以及强大的差分功耗分析攻击（DPA）,并且增加所有的策略后,运行时间仅仅增加了12%。RSA算法在微控制器上的高效安全实现和侧信道攻击及其防御策略一直以来是密码学中基础的重要问题。研究如何高效安全实现密码算法具有重大的理论意义和实用价值,其发展前景非常广阔。

论文目录

• 摘要
• ABSTRACT
• 第一章 引言和主要结果
• 1.1 引言
• 1.2 本文的主要结构
• 第二章 预备知识
• 2.1 RSA公钥密码系统
• 2.1.1 对称密码学和公钥密码学
• 2.1.2 RSA密码算法简介
• 2.1.3 RSA数字签名
• 2.2 模指数算法
• 2.2.1 平方乘算法
• 2.2.2 m-ary算法
• 2.2.3 创新的m-ary算法
• 2.3 大整数的加算法,减算法和比较算法
• 2.3.1 大整数的加算法
• 2.3.2 大整数的减算法
• 2.3.3 大整数的比较算法
• 2.4 多精度的乘法和平方算法
• 2.4.1 教科书算法
• 2.4.2 Comba算法
• 2.4.3 Karastsuba算法
• 2.4.4 三种方法的性能分析
• 2.5 蒙哥马利算法
• 2.5.1 蒙哥马利模乘算法
• 2.5.2 蒙哥马利模指数算法
• 2.5.3 蒙哥马利模约减算法
• 第三章 快速实现RSA算法综述
• 3.1 中国剩余定理
• 3.2 滑动窗口算法
• 3.3 KCM算法
• 3.4 混合乘算法
• 第四章 算法实现
• 4.1 实现语言和所用工具简介
• 4.2 改进的混合乘算法
• 4.3 大整数运算算法的实现
• 4.4 运算时间比较及性能评价
• 第五章 侧信道攻击
• 5.1 测量配置简介
• 5.2 简单功耗分析攻击（SPA）
• 5.3 简单功耗分析（SPA）抵御策略
• 5.4 差分功耗分析攻击（DPA）
• 5.4.1 功耗曲线压缩技术
• 5.4.2 单指数多数据攻击（SEMD）
• 5.4.3 多指数单数据攻击（MESD）
• 5.5 差分功耗分析攻击（DPA）抵御策略
• 第六章 本文贡献和研究展望
• 6.1 本文的贡献
• 6.2 研究展望
• 参考文献
• 致谢
• 攻读硕士学位期间完成论文情况
• 攻读学位期间参与科研项目及国际交流情况
• 学位论文评阅及答辩情况表