大整數(shù)除法器硬件電路研究與實(shí)現(xiàn)

王德明，駱開慶

(華南師范大學(xué)物理與電信工程學(xué)院∥廣東省心腦血管個(gè)體化醫(yī)療大數(shù)據(jù)工程技術(shù)研究中心，廣州 510006)

公鑰密碼算法已被廣泛應(yīng)用于區(qū)塊鏈、安全芯片、智能卡以及NFC等技術(shù)中以增強(qiáng)安全性，其中一個(gè)必不可少的算法是大整數(shù)除法[1-3]. 與模加、模乘和模冪運(yùn)算相比，除法的使用頻率較低，主要用于CRT中國剩余定理、素?cái)?shù)產(chǎn)生以及蒙哥馬利預(yù)處理等.

傳統(tǒng)的大整數(shù)除法是通過軟件迭代的形式反復(fù)調(diào)用處理器內(nèi)部的8/16/32位通用短整數(shù)硬件除法器[4-5]，繼而實(shí)現(xiàn)大整數(shù)的運(yùn)算，當(dāng)整數(shù)的位數(shù)達(dá)到2 048位甚至4 096位時(shí)，這種做法需要耗費(fèi)大量的時(shí)鐘周期[6]. 由于公鑰協(xié)處理器的主頻較低，如在智能卡片內(nèi)的工作頻率不超過30 MHz，因此，使用軟件實(shí)現(xiàn)大整數(shù)除法將耗費(fèi)過長的計(jì)算時(shí)間，不利于即時(shí)通信，有必要將該算法硬件化，以縮短計(jì)算時(shí)間. 現(xiàn)有關(guān)于硬件除法器的研究主要是基于短整數(shù)的算法和電路，例如數(shù)字遞歸[7]、浮點(diǎn)除法[8]和函數(shù)迭代[9]，此類方法適用于通用處理器內(nèi)部的除法電路，其位寬可以是8、16、32、64位，隨著位寬的增加，電路時(shí)延和面積也在增大，以至于難以直接使用上述方法實(shí)現(xiàn)大整數(shù)硬件電路.

為加快大整數(shù)除法的運(yùn)算速度，本文提出一種適合硬件實(shí)現(xiàn)的低功耗大整數(shù)除法快速算法及其硬件電路，將2個(gè)大整數(shù)分別存儲(chǔ)在SRAM隨機(jī)訪問存儲(chǔ)器中，結(jié)合內(nèi)部控制器和狀態(tài)機(jī)，以期實(shí)現(xiàn)高速數(shù)據(jù)讀取和除法計(jì)算.

1 大整數(shù)除法快速算法

1.1 傳統(tǒng)的不恢復(fù)余數(shù)除法算法

大整數(shù)除法算法可以表示為：

X=D×Q+R,

(1)

其中，X是n位的被除數(shù)，D是m位的除數(shù)，Q和R分別是商和余數(shù). 為避免使用硬件資源消耗多且計(jì)算時(shí)間長的除法運(yùn)算，可采用不恢復(fù)余數(shù)除法算法(算法1)，該算法只需加減法和移位操作即可求出商和余數(shù)[10].

算法1運(yùn)行時(shí)需要在循環(huán)內(nèi)判斷X是正數(shù)還是負(fù)數(shù)，并作出相應(yīng)的減法或者加法，每次移位相減后得到一位商，循環(huán)結(jié)束后應(yīng)根據(jù)符號調(diào)整X的值，從而得到最終的商和余數(shù). 可以看出，完成一次除法需要用到3個(gè)存儲(chǔ)器，分別存放X、Q和R，電路面積較大. 此外，由于X是大整數(shù)，使用寄存器存放將導(dǎo)致較大的功耗和面積. 目前普遍的做法是采用SRAM隨機(jī)存取存儲(chǔ)器存放較大的數(shù)據(jù)，而這種做法的弊端是數(shù)據(jù)只能按字讀取，速度較慢. 假設(shè)存儲(chǔ)器的字長為w位，那么僅僅完成一次移位最少都要耗費(fèi)n/w個(gè)時(shí)鐘周期，當(dāng)循環(huán)次數(shù)較大時(shí)不利于除法的快速計(jì)算.

1.2 適合硬件實(shí)現(xiàn)的低功耗大整數(shù)除法快速算法

為降低電路面積，提高算法計(jì)算效率，本文提出適合硬件實(shí)現(xiàn)的低功耗大整數(shù)除法快速算法(算法2)，運(yùn)用該算法，可以有效地提高并行度、降低移位操作所需時(shí)間，且除了最終處理需要使用2個(gè)存儲(chǔ)器之外，被除數(shù)每一次循環(huán)產(chǎn)生的商和余數(shù)均存放在同一個(gè)存儲(chǔ)器中，特別適合硬件實(shí)現(xiàn). 計(jì)算時(shí)在被除數(shù)X的最高位添加1位的0，并將其分成2個(gè)部分，分別是X′和X″，其中X′的長度和除數(shù)D一致. 此時(shí)，移位運(yùn)算的長度不再是原來的n位，而是除數(shù)D的長度，因此，每次移位時(shí)，可先讀取X″[n-m-j]并將其移進(jìn)X′中. 與算法1相比，算法2可以降低一半的移位時(shí)間，并且移位時(shí)可同時(shí)執(zhí)行加減操作，大幅提高并行度，即移位和加減法可以在同一個(gè)時(shí)鐘內(nèi)完成. 執(zhí)行完一次循環(huán)后，根據(jù)X′的符號決定商為1或0，并將商寫進(jìn)X″[n-m-j]，從而節(jié)省硬件資源. 全部循環(huán)完成后，X″就是商，余數(shù)則存放到D，全部計(jì)算過程只需1個(gè)n位的存儲(chǔ)器和1個(gè)m位的存儲(chǔ)器.

完成移位后需要做大整數(shù)加減法運(yùn)算，當(dāng)數(shù)據(jù)長度較大時(shí)很難在一個(gè)時(shí)鐘完成，為降低加減法電路的面積和延時(shí)，可考慮以字為單位進(jìn)行計(jì)算. 假設(shè)w為存儲(chǔ)器的字長，且n和m均能被w整除，則被除數(shù)、除數(shù)、商和余數(shù)可以表示為：

(2)

(3)

那么，完成一次大整數(shù)加減法需要m/w個(gè)時(shí)鐘周期，完成一次除法的時(shí)間數(shù)量級為(n-m+1)·m/w. 假設(shè)被除數(shù)是1 024位，除數(shù)是512位，存儲(chǔ)器字長為32位，則一次除法大約需要8 208個(gè)時(shí)鐘周期，對于13.56 MHz主頻的時(shí)鐘來說，需要花費(fèi)0.6 ms的計(jì)算時(shí)間. 若采用軟件計(jì)算，數(shù)據(jù)的讀寫、移位和加減法需要經(jīng)過多個(gè)時(shí)鐘周期，花費(fèi)時(shí)間將是硬件的幾十倍，對片內(nèi)工作頻率較低的芯片來說難以接受.

圖1顯示了被除數(shù)、除數(shù)、商和余數(shù)的存放位置. 其中，存儲(chǔ)器的字長為w，被除數(shù)X一共有n/w個(gè)字，存放在RAMX存儲(chǔ)器中；除數(shù)D一共有m/w個(gè)字，存放在RAMD存儲(chǔ)器中. 在除法運(yùn)算的過程中，RAMX存儲(chǔ)器的高位存放每一輪循環(huán)產(chǎn)生的臨時(shí)余數(shù)，低位存放商. 完成除法運(yùn)算后，余數(shù)R存放在RAMD中；原被除數(shù)的高位清零，低位存放商Q，一共有(n-m)/w個(gè)字. 可以看到，利用算法2可以高效利用存儲(chǔ)器實(shí)現(xiàn)分時(shí)復(fù)用，大幅降低了存儲(chǔ)電路面積.

圖1 變量與存儲(chǔ)器的對應(yīng)關(guān)系

1.3 適合硬件實(shí)現(xiàn)的低功耗大整數(shù)除法快速算法性能分析

當(dāng)除法器硬件電路的頻率確定后，運(yùn)算時(shí)間可以用時(shí)鐘周期來表示. 除法器運(yùn)算時(shí)間與存儲(chǔ)器字長有關(guān)，由圖2可知:存儲(chǔ)器的字長越長，完成一次除法所需的運(yùn)算時(shí)間越短. 例如,當(dāng)存儲(chǔ)器的字長為8位時(shí)，完成一次1 024位除以512位的操作需要3萬多個(gè)時(shí)鐘周期，而采用32位存儲(chǔ)器時(shí)需要8 000多個(gè)時(shí)鐘周期，采用64位時(shí)只需要4 000多個(gè)時(shí)鐘周期.

圖2 除法器運(yùn)算時(shí)間與字長的關(guān)系

由圖3可以看出:存儲(chǔ)器消耗的電流隨著存儲(chǔ)器大小和字長的增加而增加. 例如,對于4 096位的存儲(chǔ)器，采用8位字長，電流大約73 μA；采用32位字長則上升到110 μA；采用64位字長的電流更大，高達(dá)153 μA. 此外，字長增大將導(dǎo)致存儲(chǔ)器的面積增加，因此，不能通過無限制增加存儲(chǔ)字長w來縮小單次除法的運(yùn)算時(shí)間.

基于上述分析，本文擬采用32位字長來設(shè)計(jì)存儲(chǔ)器.

圖3 存儲(chǔ)器大小與電流的關(guān)系

2 低功耗大整數(shù)除法器硬件電路

基于算法2，設(shè)計(jì)了大整數(shù)除法器硬件電路(圖4)，其中，clk為大整數(shù)除法器硬件電路的時(shí)鐘信號，控制存儲(chǔ)器的讀寫時(shí)序以及寄存器的工作；rst為復(fù)位信號，用于寄存器的清零操作；en為除法器使能信號，該值為高電平時(shí)，除法器開始工作；func為功能選擇信號，有8種不同的計(jì)算功能，包括不同位寬的除法和求模功能. 通過datain可以從外部接口電路寫數(shù)據(jù)到RAMX和RAMD存儲(chǔ)器中，當(dāng)除法器運(yùn)算完畢，可以從dataout獲取存儲(chǔ)器存放的商或余數(shù).

圖4 大整數(shù)除法器硬件電路結(jié)構(gòu)

如圖4所示：(1)外部電路與除法器之間傳輸數(shù)據(jù)需要通過輸入輸出接口，除法運(yùn)算前需要將被除數(shù)和除數(shù)寫進(jìn)存儲(chǔ)器RAMX和存儲(chǔ)器RAMD中，其中,存儲(chǔ)器RAMX是一個(gè)字長為32位、深度為128的隨機(jī)存儲(chǔ)器，存儲(chǔ)器RAMD則是一個(gè)字長為32位、深度為64的存儲(chǔ)器. 為了獲得更高的吞吐率，存儲(chǔ)器均采用雙端口結(jié)構(gòu)，可以在上升沿的時(shí)候讀取數(shù)據(jù)，下降沿的時(shí)候?qū)懭霐?shù)據(jù)，1個(gè)時(shí)鐘周期內(nèi)就可以完成1次讀寫操作. 此外，為了同時(shí)讀寫2個(gè)存儲(chǔ)器，應(yīng)單獨(dú)設(shè)計(jì)2套接口電路，同時(shí)提供地址和數(shù)據(jù). (2)為了獲得除法或者求模結(jié)果，電路在狀態(tài)機(jī)和計(jì)數(shù)器的控制下，將存儲(chǔ)器RAMX中的數(shù)據(jù)取出，經(jīng)過處理后存放到寄存器R1，該值用來形成加法器的輸入?yún)?shù)A. 存儲(chǔ)器RAMD中的數(shù)據(jù)取出后，經(jīng)過邏輯電路處理后直接形成加法器的輸入?yún)?shù)B. 加法器將根據(jù)上一輪加減法的結(jié)果，判斷X是正數(shù)還是負(fù)數(shù). 如果是正數(shù)，則執(zhí)行減法操作；如果是負(fù)數(shù)，則執(zhí)行加法操作. 加法器的結(jié)果將寫回存儲(chǔ)器RAMX中，作為臨時(shí)保存的數(shù)據(jù). 全部計(jì)算完畢后，存儲(chǔ)器RAMX將存放商，存儲(chǔ)器RAMD將存放余數(shù).

下面給出除法計(jì)算過程舉例，以理解算法2的計(jì)算過程. 假設(shè)X是16位的被除數(shù)，D是8位的除數(shù)，在計(jì)算時(shí)，將X分成2個(gè)部分(X′和X″)，其中，X′是8位的臨時(shí)寄存器，X″用來存放每一輪計(jì)算產(chǎn)生的商，每輪計(jì)算后均需要左移一次，將X″的最高位移位到X′的最低位，經(jīng)過9輪計(jì)算后，最終得到商和余數(shù)，分別寫到X和D中(圖5).

圖5 除法計(jì)算過程舉例

除法電路需要用到32位的加法運(yùn)算單元，從而實(shí)現(xiàn)移位相減或相加的計(jì)算. 加法器分為行波進(jìn)位加法器、CSA加法器和超前進(jìn)位加法器. 其中，行波進(jìn)位加法器原理較為簡單，設(shè)計(jì)復(fù)雜度小，具有面積小和功耗低的優(yōu)勢，但延時(shí)太大；CSA加法器可以將3個(gè)數(shù)相加的和用2個(gè)數(shù)來表示，但實(shí)際上并沒有真正解決2個(gè)數(shù)相加產(chǎn)生1個(gè)輸出的問題，因此不能用在大整數(shù)除法器硬件電路中；而超前進(jìn)位加法器的進(jìn)位是各自獨(dú)立且同時(shí)產(chǎn)生的，雖然邏輯復(fù)雜度較高，但高一位的進(jìn)位不依賴低位的進(jìn)位產(chǎn)生與傳送，運(yùn)算速度快，延時(shí)小，因此，本文擬采用超前進(jìn)位加法器降低電路延時(shí).

3 大整數(shù)除法器硬件電路的功能和性能分析

本文提出的大整數(shù)除法器硬件電路具有8種大整數(shù)除法和求模功能(表1)，當(dāng)功能選擇信號(func)從000到011時(shí)，可以實(shí)現(xiàn)除法和求模運(yùn)算，其中，X代表被除數(shù)，D代表除數(shù)，在計(jì)算之前，應(yīng)將輸入數(shù)據(jù)寫入存儲(chǔ)器RAMX和RAMD中，激活硬件加速器，完成除法后，商和余數(shù)均存放到存儲(chǔ)器RAMX中. 本文提出的大整數(shù)除法器硬件電路最高可支持4 096位的被除數(shù)和2 048位的除數(shù). 當(dāng)除數(shù)較小時(shí)，可以選擇合適的位寬，減少計(jì)算時(shí)間. 除法運(yùn)算可用于1 024位或2 048位 的RSA-CRT，模運(yùn)算可用于模乘或素?cái)?shù)生成的預(yù)計(jì)算. 這些運(yùn)算可廣泛應(yīng)用于RSA公鑰密碼算法和ECC橢圓曲線密碼算法.

表1 大整數(shù)除法和求模功能Table 1 The division and modulus function for big integers

下面采用0.13 μm CMOS工藝，對大整數(shù)除法器硬件電路進(jìn)行評估. 由于除法器主要針對智能卡或NFC設(shè)備設(shè)計(jì)，因此，本文使用了3種不同的頻率來分析：13.56 MHz(非接觸式智能卡)、30 MHz(接觸式智能卡的最大頻率)和125 MHz(電路可工作的最大頻率). 由功耗和面積的評估結(jié)果(表2)可知：(1)功耗隨著頻率的增加而增加. (2)在3種頻率(13.56、30、125 MHz)下，總功耗分別約為117、201、715 μW，遠(yuǎn)遠(yuǎn)低于智能卡或NFC設(shè)備提供的總功率(3～50 mA)[11]. (3)除法電路面積最大的是RAM存儲(chǔ)器，這是由于需要存放較大的整數(shù)，所以這部分面積是難以節(jié)省的，即使采用軟件計(jì)算，也需要將被除數(shù)和除數(shù)存放在內(nèi)存中;除了存儲(chǔ)器以外，除法器的邏輯控制電路面積并不大.

表2 大整數(shù)除法器硬件電路的頻率、功耗和面積之間的關(guān)系Table 2 The relationship among frequency, power consumption and area

通過使用自動(dòng)布局布線和版圖設(shè)計(jì)工具，可以得到大整數(shù)除法器硬件電路的版圖(圖6). 利用版圖工具可知大整數(shù)除法器硬件電路的總面積為0.12 mm2. 由圖可知：與控制電路的小面積相比，存儲(chǔ)器占據(jù)了大部分版圖，這意味著該算法具有相對較低的邏輯復(fù)雜度.

為了體現(xiàn)本文的低功耗大整數(shù)除法快速算法及其硬件電路在面積和功耗方面的優(yōu)勢，把本文的大整數(shù)除法器與Iterative除法器[1]、Radix-16除法器[4]、Binary64除法器[12]及Radix-8除法器[13]進(jìn)行對比. 為了公平比較，在功耗方面，采用每兆赫的功

圖6 大整數(shù)除法器硬件電路版圖

耗來評估大整數(shù)除法器硬件電路是否具有低功耗的優(yōu)勢；在除法器硬件電路的面積方面，使用每位占用的面積進(jìn)行評估. 由比較結(jié)果(表3)可知：大整數(shù)除法器的硬件電路占用極低的功耗和面積，每兆赫茲消耗的功耗為10 μW，總面積為0.12 mm2，其中每位占用的面積為120 μm2.

表3 不同除法器的性能對比Table 3 The comparison of power consumption and area between the proposed hardware circuit and others

4 結(jié)論

本文提出了一種基于不恢復(fù)余數(shù)除法算法的低功耗除法器硬件電路，該電路可廣泛應(yīng)用于公鑰密碼算法的計(jì)算中. 所提出的低功耗大整數(shù)除法快速算法及其硬件電路支持多種位寬的除數(shù)和被除數(shù)，可為公鑰協(xié)處理器提供除法和求模運(yùn)算功能，最高可支持4 096位的被除數(shù)以及2 048位的除數(shù). 使用0.13 μm CMOS工藝,對該大整數(shù)除法器硬件電路進(jìn)行評估和驗(yàn)證，結(jié)果表明：該電路的主頻最高可達(dá)125 MHz，總面積為0.12 mm2，每兆赫茲消耗的功耗為10 μW.