一種高性能超標量橢圓曲線密碼處理器晶片的製作方法
2023-10-08 12:47:14 2
專利名稱：一種高性能超標量橢圓曲線密碼處理器晶片的製作方法
技術領域：
本發明涉及信息安全、加密解密技術、晶片技術領域，特別是高性能橢圓曲線密碼處理器晶片。
背景技術：
作為當今世界上應用最廣泛的，同時也是第一個真正意義上的公鑰密碼體制，RSA是基於大數分解的困難問題，具有數學原理簡單(主要是依賴於費馬小定理，以及P不等於NP的假設)，實現相對容易的優點，但是其單位安全強度較低，加密解密的運算量過大。橢圓曲線公鑰密碼體製作為近年來學術界深入研究的問題，也越來越被工業界所認識和推崇，具有單位安全強度高(160位的橢圓曲線密鑰與1024位的RSA密碼具有相同的安全性)，運算量相對較少，加密解密速度快的優點，因此可以預見，在信息安全領域，橢圓曲線具有非常廣闊的市場應用前景。 但是，橢圓曲線密碼體制的應用目前面臨如下幾個方面的問題，首先是性能大部分橢圓曲線密碼體制的實現都是採用軟體或者單片機，這兩種方法性能過低，無法滿足高性能加密解密的要求，而且尚未出現廣泛應用的以專用集成電路方式實現的橢圓曲線密碼處理器晶片；其次，在橢圓曲線密碼體制的實現中，有限域乘法部件的低性能一直是一個瓶頸，有限域乘法運算的性能過低嚴重製約了橢圓曲線密碼晶片的廣泛應用；最後，專用的橢圓曲線密碼的指令集尚未出現，通用處理器和專用處理器都不支持有限域算術運算，急需一種支持有限域算術運算的指令集標準，這也大大推動橢圓曲線公鑰密碼體制的廣泛應用。
發明內容
本發明的目的是設計一種高性能超標量橢圓曲線密碼處理器晶片，實現高速的有限域乘法運算，和高性能橢圓曲線加密解密算法，以及提出一種晶片所支持的包含有限域運算的橢圓曲線密碼指令集，很好的解決了上述制約橢圓曲線公鑰密碼體制廣泛應用所面臨的關出問題。本發明的整體技術方案如圖I所示本發明設計了一種高性能超標量橢圓曲線密碼處理器晶片，包括一個指令R0M，一個數據RAM，多個普通算術部件(包括普通算術乘法器和加法器)，多個有限域算術部件(包括有限域高速乘法器和有限域加法器)，一個保留站(Reservation Station),寄存器狀態寄存器(Register Status),和一個 ROB (ReorderBuffer)，以及一個8級指令流水線，實現了寄存器重命名和指令多發射，指令動態調度，指令亂序執行和順序生效，充分利用指令間並行性，實現了單時鐘周期的多指令執行，成倍提高了指令吞吐率和運算性能。本發明所述的處理器中包含的高性能乘法器，採用有限域乘法所包含的大量有限域加法運算並行執行的方法，將有限域乘法原本需要的2n個單位時間延遲降低為log(n)個單位時間延遲，大大提高了有限域乘法的運算速度。
本發明所述的處理器支持的一種包含有限域算術運算的橢圓曲線密碼指令集，用這種新的密碼指令集可以很方便地編程實現橢圓曲線的密碼體制中的加密解密算法，以及RSA密碼算法。這種指令集不但很好的滿足了橢圓曲線密碼體制的需要，也為將來的密碼指令集的標準化提供很好的支持。下面分別介紹本發明各技術部分
I、超標量密碼處理器微體系結構
本發明所設計的密碼處理器為超標量多發射處理器，其包含的一個8級指令流水線，兩個普通加法器，兩個普通乘法，兩個有限域乘法部件，兩個有限域加減運算，和兩個邏輯運算部件，以及指令ROM和數據RAM，和包含32個寄存器的寄存器文件(基本兼容MIPSR4000的寄存器和尋址方式)。八級流水線分別包含取指令(IF, Instruction Fetch),指令解碼(ID, Instruction Decoding)，指令發身寸(Issue),取操作數(R0, Read Operands),執行指令(EX, Execution),執行結果生效(Commit),存儲器讀寫(MEM,Memory Access),和 寄存器寫回(WB, Write Back)。處理器實現了指令雙發射技術，forwarding技術(包含指令猜測預取)，亂序執行，寄存器重命名，以及順序生效技術。所有涉及都在寄存器傳輸級完成。這樣，處理器在每個時鐘周期可以完成多條指令的執行。在並未提高主頻的情況下，功耗沒有大幅提升的情況下，處理器的指令吞吐率增加數倍，具備現代處理器的各項技術特徵和優勢。2、高速有限域算術乘法運算部件
有限域乘法運算部件的速度往往是整個處理器中的性能瓶頸，普通取模乘法需要先對兩個操作數做普通乘法，然後再做取模操作。這需要2*n次累加操作和η次移位(其中η是操作數的位寬)，因此關鍵路徑需要2η個單位時間延遲。本發明包含的高速有限域運算部件首先對η次取模累加操作分解成相鄰操作數做移位帶模相加並行執行，得到η/2個和數，接著再對這η/2個操作數相鄰兩個做帶模移位相加操作(這時移兩位)，如此繼續，直到得到最終結果。這樣，該高速算術乘法器將單位時間延遲由2*η降低到了 log(n)。通過有限域取逆運算，該乘法器同樣可做高速帶模除法運算。3、橢圓曲線密碼處理器指令集體系結構
本發明的橢圓曲線指令集採用精簡指令系統RISC模式，所有訪問存儲器的指令單獨出來，而算術邏輯運算指令和分支指令全部操作數都為寄存器或者立即數。體系結構包括32個32位寄存器RO，…，R31，其中RO永遠為0，R31存儲子程序返回地址等等，此外指令編碼統一位寬為32位。橢圓曲線密碼處理器指令集包含除了浮點運算外所有RISC常用指令，包括算術指令21條，分支跳轉指令14條，NOP指令I條，數據訪存指令12條，邏輯運算指令8條，寄存器MOV指令8條，基本兼容MIPS R2000的處理器指令集，此外，指令集還包括有限域算術運算指令26條，分別是
設置素數特徵有限域特徵指令；(特徵不可設置為2)
8位，16位和32位特徵非2有限域加法；
8位，16位和32位特徵非2有限域減法；
8位，16位和32位特徵非2有限域乘法；
8位，16位和32位特徵非2有限域減法；以及模2的12條算術運算指令和一條有限域取逆指令。這樣處理器得以對有限域上算術運算支持。4、橢圓曲線和RSA密碼固件程序
本發明還利用第三部分所敘述的橢圓曲線指令集開發了若干橢圓曲線操作固件程序，主要包含橢圓曲線上的倍點操作(Point Doubling)和點加操作(Point Addition)。倍點操作是在橢圓曲線上的一個點與同一個點相加，得出一個新的點。點加操作是將橢圓曲線上的兩個點相加，得到一個新的點。所有點都採用雅可比坐標系，用三個坐標分量來表示二位坐標系的點(包括無窮遠點)。同時本發明RSA加密解密算法的實現。本發明的優勢在於，首先，本發明所述的密碼處理器晶片使用超標量技術大幅提高了指令吞吐率，使得能夠單指令周期完成多條指令的執行，換言之，在沒有提高處理器主頻的情況下，處理器性能得到成倍提升；其次，本發明所述的密碼處理器所包含的高速有限 域乘法部件將橢圓曲線運算中最慢的有限域乘法的運算時間從個單位時間延遲降低為個單位時間延遲(其中為操作數位寬)，換言之，如果兩個位寬32位的操作數做有限域乘法，運算時間從64個單位時間延遲下降為5個單位時間延遲，性能提高了 11. 6倍；第三，本發明所述的處理器晶片支持有限域算術運算，這種新的指令集不但方便橢圓曲線密碼算法的編程實現，同時也為密碼指令集的標準化提供了支持。發明附圖
圖1，本發明各部分邏輯關係；
圖2，高速有限域乘法器(操作數位寬為8的情形);
圖3，移位相加部件；
圖4，橢圓曲線密碼處理器的微體系結構；(FF Adder為有限域加法運算部件，FFMultiplier是有限域乘法運算部件)；
圖 5.保留站(Reservation Station)的結構；
圖6寄存器狀態表(Register Status)的結構。具體實施方法
I.橢圓曲線密碼處理器微體系結構
本發明所設計的處理器晶片採用了帶有寄存器重命名的動態指令調度技術，同時支持猜測多發射(Speculation Multi-Issue)。該處理器所採用的方法是,採用RISC標準的8級流水線，包含指令預取(IF, Instruction Fetch),指令解碼(ID, Instruction Decoding),指令發射(Issue),取操作數(R0,Read Operands),執行指令(EX, Execution),執行結果生效(Commit),存儲器讀寫(MEM,Memory Access),和寄存器寫回(WB,Write Back)。圖 4處理器流水線的整體邏輯框圖，其中包括指令隊列，數據和指令總線(Data and InstructionBus),多個乘法器和加法器及其保留站(Reservation Station),多個有限域加法器和乘法器及其保留站，存儲器和寄存器文件(Register File)，存儲器包含多個指令ROM和數據RAM,數據RAM擁有其獨立的保留站，而寄存器文件也擁有一個緩衝隊列，等到寄存器數據生效。下面來對流水線分別逐級描述。指令預取(IF,Instruction Fetch)
在指令預取IF階段，指令按照指令寄存器PC (Program Count)從指令ROM中取出相應的指令，本發明所述晶片支持多條指令預取，例如每次取兩條為InstR0M[PC]和InstR0M[PC+4]，但是如果遇到InstROM[PC]是分支指令，那麼其下一條指令未必是InstROM[PC+4]。在本發明中，根據局部性原則，每次取InstR0M[PC]和InstR0M[PC+4]指令，如果預測錯誤，將要進行流水線重載。這樣的好處是密碼運算很少遇到分支語句。同時，IF階段將PC更新，如果每次預取η條指令，那麼PC更新為PC+4n。指令解碼(ID,Instruction Decoding)
指令解碼階段將預取的指令翻譯成操作，例如加法操作，乘法操作，有限域加法操作，以及訪存操作等等，以及將操作數的寄存器號，數據地址，和立即數提取翻譯出來，然後存入指令隊列(Instruction Queue)。如果指令隊列(Instruction Queue)滿了，將告知上一階段IF不再預期指令,知道指令隊列(Instruction Queue)又出現空餘空間。指令隊列(Instruction Queue)的長度為64,是一個單向循環隊列。注意,在指令隊列中的代碼都是經過指令解碼的。指令發射(Issue)
將指令隊列頭的指令，按照操作不同，在有空餘空間的情況下發射到相應的操作部件的保留站中去，例如加法指令發射到某個加法器的保留站中，有限域乘法操作就發射到有限域乘法的保留站中去，如果某操作的各個部件的保留站全部滿了，那麼將不能發射。圖5給出了保留站(Reservation Station)的結構,保留站的每一行包含6個域0peration域存儲相應的操作，兩個操作數寄存器Ri和Rj的值存儲在Valuei和Value j，另外兩個域Qi和Qj分別將存儲以此Ri和Rj正在等待的保留站號，在此階段這四個域為空，最後一個域Busy設置為0，表示當前指令並沒有被執行。同時更新目的操作數寄存器編號插入ReorderBuffer的隊列尾，等待該操作完成來更新相應寄存器的值。取操作數(R0,Read Operands)
在這一階段，首先試圖從寄存器文件中讀出操作數寄存器Ri和Rj的操作數。讀出Ri和Rj值的時候需要查詢寄存器狀態寄存器(Register Status)。如圖6所示，寄存器狀態寄存器為32個通用寄存器配置一個域，存儲以改寄存器為目標寄存器的保留站號，表示該寄存器的值還沒有準備好不可以讀取，否則置O。如果Ri的狀態寄存器值為0，那麼讀取Ri的值到保留站中的Valuei域中，如果Ri的狀態寄存器值為n，說明該寄存器鎖定，於是將Qn讀入保留站Qi中，Rj也做相應的操作。這樣，保留站每一行中Valuei和Qi只有一個有效，Valuej和Qj也只有一個有效。事實上，將寄存器的值讀入保留站實際上已經實現了寄存器重命名(Register Renaming)，避免了所有WAR和WAW危險。執行指令(EX,Execution)
如果某保留站中的某條指令的一行的Valuei和Valuej都生效了，並且該保留站的運算部件空閒，就可以開始執行該條指令^fValuei和Valuej導入運算部件的輸入端，設置保留站該行的BUSY域為1，同時設置該指令的目的寄存器的狀態為該保留站的序號。當指令執行完成，BUSY域置為O。在此階段，每個部件的保留站中的指令不必按順序執行，只要操作數全部準備即可開始，另外不同保留站的指令互不幹擾，可以同時開始執行。這就實現了指令的亂序執行和並行處理，充分開發了指令級並行，具備了超標量處理器的特徵。存儲器讀寫(MEM,Memory Access)
該階段僅僅針對訪存指令，對於Store指令，如果在存儲器的保留站中某行中的EX階段中計算得到的存儲器地址和相應的寄存器都已經準備好，就可以將該寄存器的值寫入相應的存儲器地址。然而，對於Load指令，將從存儲器中讀出的值寫日ROB等待生效。但是，如果當時已經在ROB隊尾，同樣可以用forwarding技術直接更新相應的保留站行的相應Value域。寄存器寫回(WB,Write Back)
在這一階段，將運算結果按照目的寄存器的指示寫入ROB中相應的行中，等待Commit階段生效。如果該結果當時已經在ROB的隊尾，說明該寄存器的值立即可以生效，可以用forwarding技術將值直接寫入相應的保留站行value域中，不必等待Commit階段。執行結果生效(Commit)
將已經準備好的ROB中的隊尾寄存器寫入寄存器文件，運算結果生效，清除ROB該行，設置寄存器狀態為O。注意，ROB中的數據全部按照程序的順序生效。在這裡，實現了程序指令執行結果的順序生效，保持了寄存器的一致性和程序運行結果的正確性。 這樣我們完整描述了超標量密碼處理器的流水線結構，處理器實現了帶有寄存器重命名的動態指令調度，多發射，亂序執行，指令集並行執行，以及指令的順序生效。充分發揮了超標量處理器的技術優勢，是的處理器在一個時鐘周期可以完成多條指令，提高指令的吞吐率。2.高速有限域乘法(帶模乘法)運算部件
高速有限域乘法運算部件是用於做帶摸乘法，其功能是給定η位的操作數A和B，此時的有限域特徵值為P，在log(n)個單位時間延遲的情況下做出帶摸乘法。圖2給出了在位寬η為8的情況下的有限域乘法器，其中最基本部件是移位加法器。如圖2所示，移位加法部件將第二個操作數Y向做m次移位操作再與第一個操作數X相加。基於此部件，圖3中，第一個操作數A乘以第2個操作數B的最低位B
之積與A乘以第二個操作數B的第二位B[l]之積做移位相加，移位次數為1，然後取模。換言之，移位相加的兩個操作數要麼是A要麼是0，取決於B
和B [I]是為I或為O。以此類推，在第一個階段，如果B的位寬為η,B的奇數位和偶數位決定下做η/2個並行的移位相加，同時取模，得到的η/2個和再兩兩相鄰的做移位相加，此時移位長度為2。如此重複下去，直到得出唯一的和，即n/2~k=l，此時結束操作，所得即為帶模積。這樣，乘法器值需要k = log (η)個延遲即可完成整個乘法運算，性能大大提高。例如，加入位寬為32位，一般帶摸乘法需要64個單位延遲，使用高速帶模乘法部件只需要5個單位延遲，運算耗時減小到原來的7. 81 %，運算效率提高1180%。3.橢圓曲線密碼處理器指令集體系結構
指令集首先支持RISC中的56條常用指令，包括算術指令21條，分支跳轉指令14條，NOP指令I條，數據訪存指令12條，邏輯運算指令8條，寄存器MOV指令8條，基本兼容MIPSR2000的處理器指令集，以及26條有限域算術運算指令，如下
SETP :設置有限域特徵值，預設設置特徵為2 ；
ADDP 32位模P加法運算；
ADDffP : 16位模P加法運算；
ADDBP 8位模P加法運算；
SUBP 32位模P減法運算；
SUBffP : 16位模P減法運算；
SUBBP 8位模P減法運算；MULP 32位模P乘法運算；
MULffP 16位模P乘法運算；
MULBP 8位模P乘法運算；
DIVP 32位模P除法運算；
DIVffP : 16位模P除法運算；
DIVBP 8位模P除法運算；
ADDB 32位模2加法運算；
ADDffB 16位模2加法運算；
ADDBB 8位模2加法運算；
SUBB 32位模2減法運算；
SUBffB 16位模2減法運算；
SUBBB 8位模2減法運算；
MULB 32位模2乘法運算；
MULffB 16位模2乘法運算；
MULBB 8位模2乘法運算；
DIVB 32位模2除法運算；
DIVffB 16位模2除法運算；
DIVBB 8位模2除法運算；
INV:有限域中的取逆運算；
指令編碼採用三操作數模式，所有指令都是32為編碼，寄存器的配置支持MIPSR4000指令集的體系結構，支持該指令集所有存儲器尋址方式。同時有一個指令寄存器PC (Program Counter)存儲當前指令在指令存儲器中的地址。4.固件程序
使用本發明的橢圓曲線處理器指令集，編寫橢圓曲線上的倍點(Point Doubling)和點加(Point Adding)的固件程序，固件程序分為有限域特徵為2和有限域特徵為p兩中方式。首先特徵為P的倍點和點加運算。假設特徵為P的有限域上的橢圓曲線為I = x3+ax+b,a,b e P特徵有限域，給定曲線上的兩個點P = (x1； Y1)，點的坐標分量全部都是特徵P的有限域上,倍點為2P = (x3, y3),那麼
X3 = [ (y2_yi) / (χ2_χι) ]2_x「x2 y3 = [ (y2_yi) / (χ2_χι) ] * (χι~χ3) ι
給定曲線上的兩個點P = (X1, Yi)和Q = (x2, J2)，倍點為P+Q = (x3，y3)，那麼
X3= (3*X!2+a)/ (2*y1)-2x1
X3 = [ (3*X!2+a) / (2*7!)]* (X1-X3) yi
其中所有的算術運算全部是特徵P有限域上的算術運算。接著來考慮特徵2的有限域上的橢圓曲線倍點和點加運算。假設特徵為P的有限域上的橢圓曲線為y+x*y = x3+a*x2+b,a,b e p特徵有限域，給定曲線上的兩個點P = (X1,Yi)，點的坐標分量全部都是特徵P的有限域上，倍點為2P = (x3, y3),那麼
X3 = [ (Υ2+Υι) / (x2+xi) ]2+ (Υ2+Υι) / (x2+xi) +xi+x2+a
y3 = [ (y2+yi) / (χ2+χι) ] * (xrx3) +χ3+Υι給定曲線上的兩個點P = (X1, Yi)和Q = (x2, J2)，倍點為P+Q = (x3，y3)，那麼
X3 = x^+b/x/
X3 = X12+ [ (ya+Yi) / (X2+Xi) ] *x3+x3
其中所有的算術運算全部是特徵2有限域上的算術運算。本發明還開發了本橢圓曲線指令集的RSA加密解密算法。給定明文P和密文C，以及公鑰和私鑰對(m，η)，其中m為公鑰，η為私鑰，那麼加密過程為pm = c
解密過程為cn = P
其中所有乘方運算都是有限域上的乘法運算。
這些固件程序中的有限域運算都使用本發明中的帶模運算指令，以及處理器中的有限域算術運算部件實現。
權利要求
1.高性能超標量橢圓曲線密碼處理器晶片，主要包括ー個指令ROM，一個數據RAM，多個普通算木部件(包括普通算術乘法器和加法器)，多個有限域算木部件(包括有限域高速乘法器和有限域加法器)，ー個保留站(Reservation Station),寄存器狀態寄存器(Register Status),和一個ROB(Reorder Buffer),以及一個8級指令流水線,其特徵在於實現了寄存器重命名和指令多發射，指令動態調度，指令亂序執行和順序生效，充分利用了指令間並行性，實現了單時鐘周期的多指令執行，成倍提高了指令呑吐率和運算性能。
2.根據權利要求I所述的橢圓曲線密碼超標量處理器晶片，包含高速有限域乘法器把有限域乘法所需的大量有限域加法運算並行執行，其特點是首先對η個累加操作分解成相鄰操作數做移位帶模相加並行執行，得到η/2個和數，接著再對這η/2個操作數相鄰兩個做帶模移兩位相加操作，以此類推，直到僅剩唯一的操作數，即是最終乘積。
3.根據權利要求I所述的橢圓曲線密碼超標量處理器晶片，其特徵在於實現了ー種包含有限域運算指令的橢圓曲線密碼指令集，這些指令包括設置素數特徵有限域特徵指令，8位，16位和32位特徵為非2的素數有限域加法、有限域減法、有限域乘法、有限域除法運算指令，以及特徵為2的上述有限域算木運算指令，和一條有限域取逆指令。
4.根據權利要求I所述的橢圓曲線密碼超標量處理器晶片，其特徵在於使用橢圓曲線密碼指令集，實現了橢圓曲線上的倍點(Point Doubling)和點加(Point Addition)算法的高速固件程序，以及RSA加密解密算法的高速固件程序。
全文摘要
本發明設計了一種高性能超標量橢圓曲線密碼處理器晶片，如圖所示，本發明涉及信息安全、加密解密技術、晶片技術領域，本發明所設計的晶片利用現代處理器超標量技術，充分利用指令集成倍提高了運算性能，其中的高速有限域乘法器大大提高了有限域乘法的運算效率，很好的解決了橢圓曲線密碼處理器的性能瓶頸，本發明的處理器所支持的一種包含有限域算術運算的指令集，不僅使橢圓曲線密碼算法的實現更加方便，也為今後的密碼指令集標準化做了必要準備，本發明在金融，通信和國防等需要信息安全的領域有著廣闊的應用前景。
文檔編號G06F21/00GK102682232SQ20111044062
公開日2012年9月19日 申請日期2011年12月26日 優先權日2011年12月26日
發明者丁丹 申請人:丁丹