8比特AVR微控制器上高效及抗側信道攻擊的RSA算法的實現(xiàn).pdf

1、RSA算法是現(xiàn)在應用最廣的公鑰密碼算法，但是一直以來，受限于嵌入式設備的有限資源問題（如CPU運行速度，內存等），使RSA算法很難在嵌入式設備上高速的運行。近些年來，很多算法被提出用來解決RSA算法的快速軟件實現(xiàn)問題：這些算法，從算法實現(xiàn)角度較高層次的一些方法，比如利用中國剩余定理(CRT)，到一些從細節(jié)入手的智能優(yōu)化模運算的方法，比如混合乘算法。在本碩士畢業(yè)論文中，我們提出了一種新的基于多精度乘法的混合乘算法，這種新的混合乘算法不僅可

2、以優(yōu)化內存的訪問次數(shù)還可以優(yōu)化寄存器的分配問題。相對于Gura等人提出的原始混合乘算法，新算法的內循環(huán)節(jié)約了7.8％的運行時間。我們將這種混合乘算法和“分離操作數(shù)掃描算法”(SOS)結合起來組成HSOS算法，一種實現(xiàn)大整數(shù)模運算的新模乘算法。我們在微控制器Atmega128上的實驗表明：對于RSA算法運算中用到的典型長度的操作，HSOS算法勝過任何其他的模乘算法，并且在借助于中國剩余定理和m-ary的模指數(shù)算法前提下，一個1024比特的

3、私鑰操作可以在76.106時鐘周期內完成，這代表著RSA在8-比特微控制器上運行時間的一個新記錄。此外，我們還在RSA實現(xiàn)程序中整合了低能耗的抵御側信道攻擊的策略，使之能夠抗側信道攻擊，而相對于沒有加抵御策略的RSA實現(xiàn)，這些策略的加入僅僅增加了12％的運行時間。
　　 基于RSA算法的高效實現(xiàn)和抗側信道攻擊相關知識。本論文的主要貢獻及創(chuàng)新之處：
　　 1．提出了三種新的混合乘算法的內循環(huán)算法，并且每種混合乘內循環(huán)算法都

4、比原來的算法運算速度快，相對于原算法完成32比特乘32比特的乘法需要141個時鐘周期，我們的第一種算法只需要114個時鐘周期就可以完成(圖4.3)，第二種算法只需要108個時鐘周期就可以完成(圖4.4)，而第三種算法僅需要102個時鐘周期(圖4.5)。
　　 2．基于我們新的混合乘算法的內循環(huán)算法，我們提出了HSOS算法，一種新的模乘算法。實驗表明：對于RSA算法運算中用到的典型長度的操作，HSOS算法勝過任何其他的模乘算法，并

5、且在借助于中國剩余定理和m-ary的模指數(shù)算法前提下，一個1024比特的私鑰操作可以在76.106時鐘周期內完成，這代表著RSA在8-比特微控制器上運行時間的一個新記錄（表4.4)；
　　 3．在增加低成本的抵御側信道攻擊策略之后，我們高效實現(xiàn)的RSA算法可以抵御簡單功耗分析攻擊(SPA)以及強大的差分功耗分析攻擊(DPA)，并且增加所有的策略后，運行時間僅僅增加了12％。
　　 RSA算法在微控制器上的高效安全實現(xiàn)和側