一種素域橢圓曲線加密的點乘加速電路的製作方法
2023-05-07 09:12:41 3
專利名稱：一種素域橢圓曲線加密的點乘加速電路的製作方法
技術領域：
本發明提供一種素域橢圓曲線加密算法的點乘加速電路硬體結構，屬於對複雜計算的硬體加速領域。
背景技術：
橢圓曲線密碼(ECC)是1985年由N.Koblitz和V.Miller提出的。橢圓曲線密碼屬於公鑰密碼體制，它的安全性建立在橢圓曲線離散對數問題(ECDLP)的困難性之上，而現在求解E⑶LP最好的算法具有全指數時間複雜度，這意味著對於達到期望的安全程度，橢圓曲線密碼可以使用較RSA密碼更短的密鑰。由於密鑰短的優點使得橢圓曲線加解密不僅速度快，而且還能節省能源、帶寬和存儲空間。具體到橢圓曲線的加密算法的整個計算過程，點乘運算是最耗時的部分。本技術領域亟待改進這一部分的加速電路硬體結構。
發明內容
本發明針對傳統硬體或者軟體算法上點乘運算效率低下的問題，提供了一種點乘加速電路結構，能夠明顯提高點乘運算的速度並能減少硬體使用資源。本發明提供一種素域橢圓曲線加密的點乘加速電路，用於計算Q = k.Ρ，其中k為計算點乘的次數，P點是橢圓曲線上的一個點，Q點是橢圓曲線上的另一個點，其特徵在於:包括初始化寄存器、點加運算模塊、點減運算模塊、倍點運算模塊、移位寄存器、比較器、二選一選擇器和結果寄存器，點加運算模塊、點減運算模塊、倍點運算模塊和移位寄存器並行執行；所述初始化寄存器，輸入端輸入Q點初始化的值，Q點初始化的值為橫縱坐標都為零，輸出端分別接到點加運算模塊和點減運算模塊；所述點加運算模塊，用於計算Q=Q+P，輸入端接到初始化寄存器的輸出端，輸出端接到二選一選擇器；所述點減運算模塊，用於計算Q=Q-P,輸入端接到初始化寄存器的輸出端，輸出端接到二選一選擇器；所述倍點運算模塊，輸入端輸入橢圓曲線上P點坐標，即P點的橫縱坐標，輸出端為P點經過倍點P=2P之後的值；所述移位寄存器，輸入值為隨機數k經過NAF編碼之後的值NAF (k)，將NAF (k)右移兩位後的結果通過輸出端接到比較器和二選一選擇器；所述二選一選擇器，用於根據NAF (k)的低兩位k[1(l]選擇輸出，k[1(l] = 01時輸出點加運算模塊輸出結果到結果寄存器，k[10]=ll時輸出點減運算模塊輸出結果到結果寄存器；所述比較器，輸入值為移位寄存器的輸出和0，比較後產生控制信號經輸出端接入到結果寄存器或點加運算模塊、點減運算模塊、倍點運算模塊和移位寄存器；所述結果寄存器，輸入端接到二選一選擇器的輸出端，在比較器的控制信號下從輸出端輸出Q點的橫縱坐標。而且，執行流程採用狀態機實現控制。採用傳統的對k的二進位NAF計算點乘算法中，點加和倍點運算是全串行的，隨著位寬m的增加，計算時間成線性增加。本發明給出了一種全並行的點乘電路,利用了點加運算Q=Q+P、倍點運算P=2P和NAF移位的並行計算特徵，採用全並行的方式，大大提高了運行速度，同時實現過程簡單。本發明利用了點乘次數k的新的NAF表示方法，使得k的二進位表示中的非零元素的個數減少，所以計算點加的次數就會減少。假設一個m位的k，經過NAF編碼之後，點加的平均計算時間約為mA/3(A代表點加運算時間)。而且通過對NAF (k)的右移操作和對NAF(k)是否為「O」的判斷，來控制點加和倍點的運算次數。當k的值為「O」時點加運算將會自動終止，節省了運算時間。本發明的加速電路比固定地執行2m次點操作要靈活得多，同時算法可以實現任意位長的點乘運算，電路結構上只需要一個2m位的移位器和相應的控制電路，資源需求少，適合在FPGA或者ASIC中實現。
圖1是本發明實施例點乘運算的原理圖；圖2是本發明實施例狀態機控制點乘運算的狀態圖；圖3是本發明實施例點乘電路的結構圖。
具體實施例方式下面結合附圖與具體實施方式
對本發明作進一步詳細說明:通用的橢圓曲線 滿足Weierstrass方程，y2 = x3+ax+b,並且有:a、b e Zp, Zp為素域，Δ = 4a3+27b2幸Omodp, p為素數,初始化橢圓曲線參數a和b後,確定了本發明中的橢圓曲線E。素域點乘表示形式一般為:Q = k.P其中k為計算點乘的次數，點P是橢圓曲線上位寬為m的點。傳統素域點乘算法中採用的點乘次數k的NAF方法為:輸入:一個正整數k輸出:NAF(k)1、i = O ；2、當k彡I時，重複執行步驟3至步驟5 ；3、若k是奇數,則kj — 2- (kmod4), k — ^kiCki代表k值相應地第i位，i從O開始加，即從k的最低位開始賦值，通過步驟5中i的每次加1，最終得到NAF (k)的最高位的值);4、否則，ki —O; 5、k — k/2, i — i+1 ；6、返回(kg，V2,...，k1； k0)，即k值經過NAF編碼之後得到的二進位數值，最低位記做1 ,最高位記做kg。NAF方法是將二進位表示的k值進行重新編碼，編碼後的k值用二進位表示每一位會有三種情況± I和O，經過NAF編碼之後，二進位表示的k值中非零元素的個數會減少，在此基礎上，相應的需要計算點加的次數就會減少，從而達到了提高速度的目的。利用二進位NAF計算點乘算法如下:輸入:一個正整數k，P e E(Fp) (P是橢圓曲線上的一個點)。輸出:kP。1、用上面的NAF算法計算NAF (k)。2、Q=O;3、對於i從m-Ι到0，重複執行步驟3.1至3.33.1Q=2Q03.2若匕=1，則0=0+卩。3.3 若 Iii=-1，則 Q=Q-P。4、返回(Q)。由上面的二進位NAF計算點乘的算法可看出，3.1、3.2和3.3這三個步驟是相互關聯的，只能採用串行的執行順序，在速度上受了很大的制約。本發明將二進位NAF計算點乘的算法進行改進，使得點加和倍點運算可以同時執行，在速度上有很大的提高。同時，通過對k的移位操作來控制對k的低位的判斷，硬體實現具有簡潔性。如圖1所示，本發明的點乘二進位算法如下:輸入:k= Gv1…，kAkl (下標2代表二進位表示)，P為有限域(素域或二進位域)上的任意一點。輸出:kP運算過程如下:1、計算 NAF (k)；2、Q = 0;3、k關O情況下，重複執行步驟3.1至3，4 ;3.1 若 k[10] = 01，則 Q=Q+P ；3.2Sk[1(l]=lUjQ=Q-P;3.3P=2P ；3.4k = k >> 2，即將 k 右移 2 位；4、若k = O,則執行步驟5 ；5、返回(Q)。點Q的初始值是零，在步驟3中，發揮硬體電路中並行的特點，在狀態機的控制下來實現點加、點減、倍點和移位的運算，最終通過NAF(k)和零值相等來退出步驟3，輸出Q點的結果。這樣就完成了一次點乘運算。本發明實施例提供的點乘加速電路結構包括:一個初始化寄存器，輸入端輸入Q點初始化的值，即Q點的橫縱坐標都為零(q_x=0, q_y=0 ),輸出端分別接到點加運算模塊和點減運算模塊。
點加運算模塊，具體可設計為包括模加、模減、模乘和模逆模塊。為了計算點加，有公式:
權利要求
1.一種素域橢圓曲線加密的點乘加速電路，用於計算Q = k.P，其中k為計算點乘的次數，P點是橢圓曲線上的一個點，Q點是橢圓曲線上的另一個點，其特徵在於:包括初始化寄存器、點加運算模塊、點減運算模塊、倍點運算模塊、移位寄存器、比較器、二選一選擇器和結果寄存器，點加運算模塊、點減運算模塊、倍點運算模塊和移位寄存器並行執行； 所述初始化寄存器，輸入端輸入Q點初始化的值，Q點初始化的值為橫縱坐標都為零，輸出端分別接到點加運算模塊和點減運算模塊； 所述點加運算模塊，用於計算Q=Q+P，輸入端接到初始化寄存器的輸出端，輸出端接到二選一選擇器； 所述點減運算模塊，用於計算Q=Q_P，輸入端接到初始化寄存器的輸出端，輸出端接到二選一選擇器； 所述倍點運算模塊，輸入端輸入橢圓曲線上P點坐標，即P點的橫縱坐標，輸出端為P點經過倍點P=2P之後的值； 所述移位寄存器，輸入值為隨機數k經過NAF編碼之後的值NAF (k)，將NAF (k)右移兩位後的結果通過輸出端接到比較器和二選一選擇器； 所述二選一選擇器，用於根據NAF (k)的低兩位k[1(l]選擇輸出，k[1(l] = Ol時輸出點加運算模塊輸出結果到結果寄存器，k[10]=ll時輸出點減運算模塊輸出結果到結果寄存器； 所述比較器，輸入值為移位寄存器的輸出和0，比較後產生控制信號經輸出端接入到結果寄存器或點加運算模塊、點減運算模塊、倍點運算模塊和移位寄存器； 所述結果寄存器，輸入端接到二選一選擇器的輸出端，在比較器的控制信號下從輸出端輸出Q點的橫縱坐標。
2.如權利要求1所述素域橢圓曲線加密的點乘加速電路，其特徵在於:執行流程採用狀態機實現控制。
全文摘要
一種素域橢圓曲線加密的點乘加速電路，用於計算Q＝k·P，其中k為計算點乘的次數，P點是橢圓曲線上的一個點，Q點是橢圓曲線上的另一個點；包括初始化寄存器、點加運算模塊、點減運算模塊、倍點運算模塊、移位寄存器、比較器、二選一選擇器和結果寄存器，其中點加運算模塊、點減運算模塊、倍點運算模塊和移位寄存器並行執行。本發明通過對NAF(k)的右移操作和對NAF(k)是否為「0」的判斷，來控制點加和倍點的運算次數，NAF(k)為k的非相鄰表示型數值。當k的值為「0」時點加運算將會自動終止，節省了運算時間。本發明的加速電路比固定地執行2m次點操作要靈活得多，算法在實現任意位長的點乘運算時只需要一個2m位的移位器和相應的控制電路，資源需求少，適合在FPGA或者ASIC中實現。
文檔編號H04L9/06GK103078732SQ20131000608
公開日2013年5月1日 申請日期2013年1月8日 優先權日2013年1月8日
發明者江先陽, 周正, 李彬, 唐從學 申請人:武漢大學