基為64的可擴(kuò)展模乘法器設(shè)計(jì)

摘 要： 針對(duì)Tenca提出的基為8的Montgomery模乘器，采用基為64的改進(jìn)設(shè)計(jì)，使其在不同運(yùn)算長(zhǎng)度下，運(yùn)算速度比Tenca的設(shè)計(jì)平均提高了48%。同時(shí)對(duì)硬件設(shè)計(jì)進(jìn)行了優(yōu)化，縮短了關(guān)鍵路徑的延遲。該設(shè)計(jì)具有良好的可擴(kuò)展性，能夠支持任意位數(shù)的模乘運(yùn)算，可廣泛應(yīng)用于不同性能和面積需求的公鑰密碼協(xié)處理器設(shè)計(jì)。
關(guān)鍵詞： Montgomery乘法器；高基；可擴(kuò)展

模乘運(yùn)算在公鑰密碼系統(tǒng)中(例如RSA算法、橢圓曲線密碼算法（ECC）以及ElGamal算法等)有著廣泛的應(yīng)用。Montgomery模乘算法利用易于硬件實(shí)現(xiàn)的加法和移位操作來(lái)實(shí)現(xiàn)大整數(shù)的模乘運(yùn)算，避免了復(fù)雜的除法運(yùn)算，從而大大提高了模乘運(yùn)算的效率[1]。
本文提出一種高速可擴(kuò)展的Montgomery乘法器設(shè)計(jì)方案，該方案是在Tenca提出的Booth-8 Montgomery模乘法器的基礎(chǔ)上，采用Booth-64編碼進(jìn)行改進(jìn)，使速度平均提高了48%。同時(shí)對(duì)數(shù)據(jù)通路進(jìn)行了優(yōu)化，使得流水線數(shù)據(jù)通路的平均延遲大大降低。


其中，k表示基，X為模乘運(yùn)算的乘數(shù)，Y是被乘數(shù)，M是模數(shù)。其中，操作數(shù)長(zhǎng)度為N，部分積用為S表示，Y、M和S分成NW個(gè)BPW bit的字進(jìn)行運(yùn)算，xj表示X的第j bit，Sk(i)表示第i個(gè)字的第k位，Ca、Cb表示進(jìn)位，q_yj、q_Mj分別是在計(jì)算部分積過(guò)程中Y和M的系數(shù)。
核心數(shù)據(jù)路徑采用流水線組織結(jié)構(gòu)，每一級(jí)之間用寄存器隔開(kāi)。每個(gè)MMcell單元完成一輪外循環(huán)，每個(gè)時(shí)鐘輸入Y、M、SS、SC的一個(gè)字參與運(yùn)算，并把Y、M和計(jì)算出來(lái)的SS、SC傳遞該下一級(jí)。為了能使數(shù)據(jù)路徑可伸縮，加入了兩個(gè)FIFO分別用來(lái)存儲(chǔ)SS和SC。如圖1所示，NS是流水線級(jí)數(shù)，由面積和時(shí)間需求來(lái)決定。