抗功耗攻擊的RSA 協(xié)處理器*

蔡梓文，崔 超，肖 勇，趙 云，林偉斌

(南方電網(wǎng)科學(xué)研究院有限責(zé)任公司,廣東 廣州 510663)

隨著通信和網(wǎng)絡(luò)技術(shù)的不斷發(fā)展,國家安全、企業(yè)機(jī)密和個(gè)人隱私均存在泄漏風(fēng)險(xiǎn)；如何防止類似信息泄漏、保護(hù)信息安全已成為業(yè)界所關(guān)注的熱點(diǎn)問題[1]。RSA 由于其安全性高,已成為應(yīng)用最廣泛的非對(duì)稱加密算法。但在RSA 算法的硬件實(shí)現(xiàn)過程中,仍存在一些問題:一方面,為了確保加密算法安全性,RSA 的密鑰長(zhǎng)度一般要選擇1 024 bit 及以上,運(yùn)算速度慢、計(jì)算時(shí)間長(zhǎng)；另一方面,沒有添加保護(hù)手段的RSA 硬件實(shí)現(xiàn)過程中很容易受到功耗分析等技術(shù)的攻擊[2]。

目前,RSA 硬件系統(tǒng)主要是對(duì)模乘算法進(jìn)行改進(jìn)與優(yōu)化[3]；而RSA 抗功耗攻擊的相應(yīng)手段主要是集中在模冪算法中。本文根據(jù)現(xiàn)有的抗功耗攻擊RSA 算法,在模冪運(yùn)算過程中選擇指數(shù)隨機(jī)化掩蓋和添加偽操作的RTL 二進(jìn)制掃描方法；在模乘運(yùn)算中,擬結(jié)合CSA 加法器和2 層Karatsuba 乘法器實(shí)現(xiàn)的基256 免減Montgomery 模乘算法。最后在不消耗過多面積的前提下,設(shè)計(jì)了一種快速、抗功耗攻擊的RSA 協(xié)處理器,并開展功能仿真與綜合分析。

文章第1 節(jié)主要介紹抗功耗攻擊的RSA 算法設(shè)計(jì)；第2 節(jié)詳細(xì)描述抗功耗攻擊的RSA 協(xié)處理器的硬件架構(gòu)設(shè)計(jì)；第3 節(jié)給出了RSA 協(xié)處理器的仿真驗(yàn)證和性能分析。

1 抗功耗攻擊的RSA 算法設(shè)計(jì)

1.1 功耗攻擊

在針對(duì)密碼算法硬件系統(tǒng)的側(cè)信道攻擊方式中,功耗分析攻擊是一種十分有效的方法。目前,功耗分析攻擊主要分為簡(jiǎn)單功耗分析(SPA,Simple Power Analysis)和差分功耗分析(DPA,Differential Power Analysis)[4]。

SPA 攻擊是一種對(duì)密碼設(shè)備運(yùn)行過程中所產(chǎn)生的功耗信息進(jìn)行直接分析的方式。對(duì)于RSA 的二進(jìn)制模冪運(yùn)算而言,當(dāng)掃描到的指數(shù)位是0 時(shí),只執(zhí)行模平方操作；當(dāng)掃描到的指數(shù)位是1 時(shí),執(zhí)行模乘和模平方操作,因此運(yùn)行時(shí)間和功耗信息會(huì)存在明顯差異。

DPA 攻擊是以SPA 為基礎(chǔ)建立的更具有破壞性的方法；通過采用統(tǒng)計(jì)分析方法和糾錯(cuò)技術(shù),DPA可從大量的密文和功耗波形中分析獲取密鑰信息。

1.2 抗功耗分析攻擊的模冪算法

在算法層面,RSA 算法的加解密操作十分簡(jiǎn)單,即采用大數(shù)的模冪運(yùn)算。但對(duì)于RSA 算法的硬件實(shí)現(xiàn)而言,需要綜合考慮消耗面積和計(jì)算速度等；如果先計(jì)算出模冪值再求模,那么會(huì)占據(jù)大量的存儲(chǔ)；所以模冪運(yùn)算可采用二進(jìn)制掃描模冪算法,將模冪運(yùn)算分解成一系列模乘運(yùn)算[5]。

為了能夠防御簡(jiǎn)單功耗分析和差分功耗分析攻擊,根據(jù)現(xiàn)有文獻(xiàn)提出的抗功耗攻擊措施[6],選擇了指數(shù)隨機(jī)化掩碼和添加偽操作的形式。抗SPA和DPA 的模冪算法如下所示:

算法1抗SPA 和DPA 的二進(jìn)制模冪

這個(gè)算法能夠防御SPA 和DPA 攻擊,通過隨機(jī)數(shù)ran[0]的比特值判斷是否執(zhí)行偽操作,而且執(zhí)行的偽操作是X=M*1 modN,其結(jié)果不進(jìn)行寄存器存儲(chǔ),在減少偽操作計(jì)算量的同時(shí)也能消除模冪算法中不同比特值執(zhí)行的功耗差異。

1.3 高基Montgomery 模乘算法

由上述分析可知:RSA 的模冪運(yùn)算是通過迭代多次模乘運(yùn)算來實(shí)現(xiàn)。因此在實(shí)際硬件設(shè)計(jì)中,限制RSA 算法運(yùn)算速度的瓶頸是模乘運(yùn)算,也就是說模乘運(yùn)算是RSA 算法的核心運(yùn)算。

在現(xiàn)存模乘算法中,蒙哥馬利(Montgomery)模乘被廣泛認(rèn)為是最高效的模乘算法,只需要通過簡(jiǎn)單的移位和加法操作,而不需要涉及求模過程中耗費(fèi)時(shí)間的除法運(yùn)算,因此很適合用于RSA 的硬件系統(tǒng)設(shè)計(jì)。

在大部分的RSA 硬件實(shí)現(xiàn)中,一般選擇基2 的Montgomery 模乘算法,該方法需要n次循環(huán)才能得到模乘結(jié)果,因此需要的運(yùn)算時(shí)間很長(zhǎng)。在高級(jí)Montgomery 模乘的基礎(chǔ)上,折中考慮運(yùn)算速度和面積消耗,選擇基256 的免減Montgomery 模乘算法,如下面所示:

算法2基256 的免減Montgomery 模乘算法

算法2 主要由3 個(gè)大數(shù)加法和3 個(gè)大數(shù)乘法組成。以1 024 位RSA 密鑰長(zhǎng)度為例,該算法會(huì)循環(huán)執(zhí)行第二步4 次,同時(shí)為了保證結(jié)果S小于N以及免去減法判斷操作,第3 步需要執(zhí)行2 次,所以最后的結(jié)果是S=A·B·2-(m＋2)modN。

1.4 兩層Karatsuba 大數(shù)乘法

由上面模乘算法可知,模乘運(yùn)算過程中,會(huì)涉及到256 bit×1 024 bit 的乘法運(yùn)算,直接選擇256 bit×256 bit 的乘法會(huì)耗費(fèi)比較多的硬件資源,因此選擇2層Karatsuba 算法實(shí)現(xiàn)256 bit 乘法,算法如下所示:

算法3兩層Karatsuba 大數(shù)乘法

由算法3 可以看出,當(dāng)執(zhí)行256 bit×256 bit 的乘法運(yùn)算時(shí),不會(huì)直接例化256 bit 的乘法器,而是在面積和速度2 個(gè)方面均衡考慮,選擇了64 bit 的乘法和512 bit 的加法。

2 RSA 協(xié)處理器的硬件設(shè)計(jì)

選擇密鑰長(zhǎng)度為1 024 bit,按照自頂向下的設(shè)計(jì)理念,通過模塊化和層次化的設(shè)計(jì)方法,以進(jìn)行抗功耗攻擊的RSA 協(xié)處理器硬件設(shè)計(jì)；在不消耗過多面積的基礎(chǔ)上提高了RSA 系統(tǒng)的運(yùn)算速度,并能夠防御簡(jiǎn)單功耗攻擊和差分功耗攻擊。

2.1 RSA 協(xié)處理器總體架構(gòu)設(shè)計(jì)

RSA 協(xié)處理器的總體架構(gòu)如圖1 所示,整個(gè)設(shè)計(jì)主要由模冪控制器,模乘模塊,大數(shù)乘法器,大數(shù)加法器和存儲(chǔ)模塊5 個(gè)部分組成。

圖1 RSA 協(xié)處理器的總體架構(gòu)

其中決定RSA 計(jì)算速度的核心部分是模冪單元,模冪單元經(jīng)由模冪控制器由狀態(tài)轉(zhuǎn)換控制調(diào)度模乘運(yùn)算模塊來實(shí)現(xiàn)；由上面一節(jié)可知模冪運(yùn)算可以由多次迭代模乘運(yùn)算來完成,因此實(shí)質(zhì)上模乘運(yùn)算模塊是RSA 算法的核心,該模塊通過模乘控制器,利用有限狀態(tài)機(jī)調(diào)用大數(shù)乘法器和大數(shù)加法器來實(shí)現(xiàn)Montgomery 模乘；存儲(chǔ)器模塊用于存放控制數(shù)據(jù)、狀態(tài)數(shù)據(jù)和一些中間運(yùn)算結(jié)果。

2.2 模乘運(yùn)算模塊硬件結(jié)構(gòu)

根據(jù)算法2 設(shè)計(jì)的Montgomery 模乘器硬件結(jié)構(gòu)如圖2 所示,模乘運(yùn)算模塊包括模乘控制器,大數(shù)加法器和大數(shù)乘法器,其中實(shí)現(xiàn)模乘運(yùn)算最重要的是大數(shù)乘法器。

圖2 模乘運(yùn)算模塊的硬件結(jié)構(gòu)

可以看出,模乘運(yùn)算模塊包括大數(shù)加法、大數(shù)乘法、移位、取模以及判斷操作,由于下一運(yùn)算步驟的值與上一運(yùn)算步驟的值有關(guān)聯(lián),因此沒有考慮并行處理。同時(shí),為了能夠在面積和速度進(jìn)行均衡選擇,只用了1 個(gè)大數(shù)加法器和1 個(gè)大數(shù)乘法器,其中的移位操作選擇取高位加拼接完成,取模操作選擇取低位完成。

2.3 大數(shù)乘法器硬件結(jié)構(gòu)

大數(shù)乘法器的硬件結(jié)構(gòu)如圖3 所示。

圖3 大數(shù)乘法器的硬件結(jié)構(gòu)

從算法3 可知,乘法器采取“分而治之”的思想,選擇2 層Karatsuba 算法來實(shí)現(xiàn),把256 bit 的輸入數(shù)據(jù)各自分解為4 個(gè)64 bit 的數(shù)據(jù)進(jìn)行運(yùn)算,在大數(shù)乘法器的硬件實(shí)現(xiàn)過程里,只需要例化1 個(gè)66 bit 的乘法器和4 個(gè)512 bit 的加法器,通過串行計(jì)算,總共需要9 個(gè)周期即可完成256 bit 的大數(shù)乘法操作。

2.4 大數(shù)加法器硬件結(jié)構(gòu)

經(jīng)過綜合分析,不直接采用1 280 bit 加法器,而是選擇CSA 加法器,把1 280 bit 的輸入值拆分成10 個(gè)128 bit 的數(shù)據(jù)再進(jìn)行加法,CSA 加法器的硬件結(jié)構(gòu)如圖4 所示。

圖4 CSA 加法器的硬件結(jié)構(gòu)

3 功能仿真和性能分析

3.1 功能仿真

選擇Verilog 語言對(duì)抗功耗攻擊的RSA 協(xié)處理器進(jìn)行RTL 代碼的設(shè)計(jì)實(shí)現(xiàn)；然后使用Mentor 公司的Modelsim 工具對(duì)RTL 代碼進(jìn)行了功能仿真；最后把得到的結(jié)果與采用標(biāo)準(zhǔn)函數(shù)庫的軟件模型的輸出結(jié)果進(jìn)行大量的重復(fù)比較,從而驗(yàn)證該RSA 協(xié)處理器功能上的正確性。圖5 為抗功耗攻擊的RSA 協(xié)處理器模冪運(yùn)算的RTL 仿真結(jié)果,圖6 為采用軟件標(biāo)準(zhǔn)函數(shù)庫的模冪運(yùn)算輸出結(jié)果。

圖5 RSA 協(xié)處理器模冪運(yùn)算的RTL 仿真結(jié)果

圖6 模冪運(yùn)算的軟件輸出結(jié)果

以其中一組數(shù)據(jù)為例,從圖5 和圖6 中可以知道,硬件RTL 代碼的結(jié)果Y3 信號(hào)和軟件代碼的結(jié)果A 是完全相同的,從而驗(yàn)證了結(jié)果的準(zhǔn)確性以及硬件設(shè)計(jì)的正確性。同時(shí),在仿真時(shí)鐘周期為10 ns的條件下,還能從圖5 中看出完成一次完整的1 024位的加密過程,大概需要9 084 610 ns,即約908 461個(gè)時(shí)鐘周期。

3.2 側(cè)信道分析

采用OSR 側(cè)信道攻擊平臺(tái)對(duì)提出的抗攻擊RSA 協(xié)處理器進(jìn)行防護(hù)性能的側(cè)信道分析驗(yàn)證。如圖7 所示,實(shí)驗(yàn)設(shè)備包括中天XC7A200T 開發(fā)板、力科WAVERUNNER 610Zi 示波器、智能采集平臺(tái)、高精度三軸平臺(tái)、電磁探頭及放大器等。

圖7 側(cè)信道攻擊平臺(tái)

首先對(duì)未添加抗攻擊設(shè)計(jì)的RSA 硬件實(shí)現(xiàn)進(jìn)行側(cè)信道采集,使用電磁探頭獲取芯片進(jìn)行加密運(yùn)算時(shí)泄露的功耗信息。圖8 清晰地反映出加密時(shí)由于密鑰每一位的不同而體現(xiàn)出的功耗差別。當(dāng)出現(xiàn)功耗尖峰時(shí),表示此時(shí)在進(jìn)行模乘和模平方；而未出現(xiàn)功耗尖峰時(shí),則表示此時(shí)只進(jìn)行模平方。因此,可以通過分析腳本對(duì)采集到的功耗曲線進(jìn)行區(qū)分,從而根據(jù)是否有尖峰輕松判斷出密鑰的每一位是1 還是0。

圖8 未加抗攻擊的RSA 功耗波形

而所提出的抗攻擊RSA 協(xié)處理器添加了基于指數(shù)隨機(jī)化掩碼和偽操作的防護(hù)。指數(shù)隨機(jī)化掩碼使得整個(gè)模冪運(yùn)算中的指數(shù)都是隨機(jī)變化的,而存在于整個(gè)循環(huán)中的偽操作會(huì)打亂功耗曲線,使得攻擊者無法對(duì)齊運(yùn)算時(shí)間與數(shù)據(jù),更難以區(qū)分函數(shù)或相關(guān)性系數(shù)并以此分析出有用的信息。

用同樣的方法對(duì)所提出的抗攻擊RSA 協(xié)處理器進(jìn)行側(cè)信道攻擊,得到功耗曲線如圖9 所示。可以看出在加密開始后,曲線沒有出現(xiàn)明顯尖峰,泄露信息得到了有效隱藏,攻擊者無法分辨當(dāng)前操作,也難以通過功耗曲線的相關(guān)性分析破解出密鑰。

圖9 本文提出的抗攻擊RSA 功耗波形

3.3 性能分析

提出的抗功耗攻擊RSA 協(xié)處理器能夠以FPGA或者ASIC 實(shí)現(xiàn)。完成硬件設(shè)計(jì)后,在SMIC 0.13 μm工藝庫和100 MHz 時(shí)鐘頻率的前提下,對(duì)其進(jìn)行DC 綜合,結(jié)果顯示所耗費(fèi)的面積約為310 k 門,其吞吐率為110 kbit/s。

表1 是所實(shí)現(xiàn)的RSA 協(xié)處理器跟其他文獻(xiàn)的性能比較。從對(duì)比結(jié)果可以看出,雖然所設(shè)計(jì)的RSA 協(xié)處理器耗費(fèi)面積較大,但是吞吐率以及能達(dá)到的頻率也較高,而且能夠防御SPA 和DPA 的攻擊。在可抗攻擊的設(shè)計(jì)里,頻率吞吐率與速度的比值是最高的,說明此設(shè)計(jì)的單位面積性能最好。而文獻(xiàn)[3]和[8]的設(shè)計(jì)雖然性能十分優(yōu)秀,但缺少抗攻擊防護(hù)。綜上,所提出的抗功耗攻擊RSA 協(xié)處理器擁有最好的綜合性能。

表1 抗功耗攻擊的RSA 協(xié)處理器性能比較

4 結(jié)論

設(shè)計(jì)了一款抗功耗攻擊的RSA 協(xié)處理器。該處理器通過指數(shù)隨機(jī)化掩蓋和添加偽操作的方法,可有效防御簡(jiǎn)單功耗分析和差分功耗分析攻擊；結(jié)合CSA 加法器和2 層Karatsuba 乘法器實(shí)現(xiàn)的基256 免減Montgomery 模乘器,能夠在不消耗過多面積的基礎(chǔ)上提高RSA 的運(yùn)算速度。跟其他類似工作相比較,本系統(tǒng)的性能資源消耗比具有一定優(yōu)勢(shì)。