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

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

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

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

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