[發明專利]橢圓曲線點乘硬件快速實現方法

有效

• 申請號: 201110191950.3
• 申請日: 2011-07-08
• 公開（公告）號: CN102306091A
• 公開（公告）日: 2012-01-04
• 發明（設計）人: 李小平;劉彥明;董慶寬;陳峙屹;張志強
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G06F7/72
• 分類號: G06F7/72
• 代理公司: 陜西電子工業專利中心 61205
• 代理人: 田文英;王品華

技術領域

本發明涉及通信技術領域，更進一步涉及密碼學領域中的橢圓曲線點乘硬件快速實現方法。該方法可以用于固定點與非固定點的點乘運算，從而提高橢圓曲線數字簽名(ECDSA)，橢圓曲線加解密(ECIES)，橢圓曲線密鑰分配(ECDH)和橢圓曲線密鑰對生成的運算速度。?

背景技術

目前，國內外在對于基于橢圓曲線點乘運算上主要有兩種方法，梳法和蒙哥馬利點乘方法。?

微軟公司在其專利申請文件“橢圓曲線點乘法”(公開號CN?101507176A，申請號200680031543.3，申請日2006.6.29)中提出一種新的用梳法表示k的點乘計算方法，通過將奇整數k轉換成二進制，然后再將該二進制配置成梳比特列，并且提出了一種更高效的比已知的梳法保存更少點的梳法變形，梳法變形在抗簡單能量分析攻擊上具體比較好的表現。這種方法存在的明顯不足是，只能適合于固定點的點乘運算，應用范圍窄。而且該方法在運算時還需要進行預計算，從而增加在系統外的開銷，使得其應用范圍有一定的限度。?

清華大學在其專利申請文件“橢圓曲線密碼系統的倍點系統”(公開號CN101262345A，申請號200810055618.2，申請日20081.4)與“橢圓曲線密碼系統的點加系統”(公開號CN?101221491A，申請號200810055610.6，申請日2008.1.4)中公開了一種新型的倍點和點加系統，將點乘運算分解為點加和倍點運算，分別投影到仿射坐標系和雅格比投影坐標系，然后在不增加面積的情況下，以流水線結構將點加和倍點組合在一起，從而達到在一個基本層面優化橢圓曲線的點乘性能。該方法存在的不足是，這種點乘運算的組合方法在進行點乘運算時，其復雜度將隨k值的增加而增加，而且在點乘運算速度過慢的問題上沒有很大的改進。?

發明內容

本發明的目的在于克服上述現有技術的不足，提出了一種適用于硬件實現的快速點乘方法。該方法可以使點乘運算在滿足通用性的前提下能夠以較小的面積和較快的?速度來完成運算，從而提高了ECDSA，ECIES，橢圓曲線密鑰對的生成和ECDH的運算速度。?

本發明實現的思路是，基于Lopez和Dahab兩位學者提出的基于蒙哥馬利算法的橢圓曲線點乘算法，利用硬件并行運算的特點，在資源消耗量沒有明顯的增加的情況下，將點乘運算中比較耗時的步驟進行拆分，重新組合形成一個新的比較節省時間的點乘硬件實現方法。?

本發明的具體實現步驟如下：?

(1)數據輸入：通過數據輸入端接收來自外部一個隨機數和一個二進制域橢圓曲線基點；?

(2)獲取隨機數；?

(3)獲取兩倍基點的x坐標值：通過乘法組合運算獲取兩倍基點的x坐標值，在標準投影坐標下將基點、兩倍基點的X坐標值、Z坐標值分別存放在寄存器X₁、Z₁、X₂、Z₂中；?

(4)調用寄存器中的值：主狀態機調用上一次運算結束后存放在寄存器X₁、Z₁、X₂、Z₂中的值；?

(5)判斷位操作：主狀態機從隨機數的最高位開始往低位進行逐位判斷，若隨機數當前判斷位的值為1，則執行步驟(6)，若為0，則執行步驟(7)；?

(6)基點乘法1運算?

6a)主狀態機同時做以下四個乘法運算：?

調用乘法模塊求寄存器X₁、Z₁中值的乘積，其結果存放在寄存器Z₃中；調用乘法模塊求寄存器X₂、Z₂中值的乘積，其結果存放在寄存器Z₄中；調用乘法模塊求寄存器X₁、Z₂中值的乘積，其結果存放在寄存器Z₅中；調用乘法模塊求寄存器X₂、Z₁中值的乘積；其結果存放在寄存器Z₆中；?

6b)主狀態機同時做以下五個運算：?