论文部分内容阅读
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算法在微控制器上的高效安全实现和侧信道攻击及其防御策略一直以来是密码学中基础的重要问题。研究如何高效安全实现密码算法具有重大的理论意义和实用价值,其发展前景非常广阔。