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

有效

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

1.一種橢圓曲線點乘硬件快速實現方法，其具體步驟如下：

(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)主狀態機同時做以下五個運算：

調用乘法模塊求基點x坐標值和寄存器Z₁中值的乘積，將乘積結果存放在寄存器Z₃中；調用乘法模塊求寄存器Z₃、Z₄中值的乘積，將結果存放在寄存器Z₄中；將寄存器Z₅與Z₆中的值相加后求平方，其結果存放在寄存器Z₁中；將寄存器X₂中的值求四次方，其結果存放在寄存器X₂中；將寄存器Z₂中的值求四次方，其結果存放在寄存器X₁中；

6c)主狀態機同時做以下三個運算：

主狀態機調用乘法模塊求b與寄存器X₁中值的乘積，再將乘積結果與寄存器X₂中值相加，其結果存放在寄存器Z₂中，其中，b是二進制橢圓曲線Weierstrass方程的一個系數；將寄存器Z₅中值求平方，其結果存放在寄存器X₁中；將寄存器Z₃、Z₄中值相加，其結果存放在寄存器X₂中；

6d)發出一個完成信號給步驟(8)；

(7)基點乘法2運算

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

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

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

調用乘法模塊求基點x坐標值和寄存器Z₂中值的乘積，將乘積結果存放在寄存器Z₃中；調用乘法模塊求寄存器Z₃、Z₄中值的乘積，將結果存放在寄存器Z₄中；將寄存器Z₅與Z₆中值相加后求平方，其結果存放在寄存器Z₂；將寄存器X₁中值求四次方，其結果存放在寄存器X₂中；將寄存器Z₁中值求四次方，其結果存放在寄存器X₁中；

7c)主狀態機同時做以下三個運算：

主狀態機調用乘法模塊求b與寄存器X₂中值的乘積，再將乘積結果與寄存器X₁中值相加，其結果存放在寄存器Z₂中，其中，b是二進制橢圓曲線Weierstrass方程的一個系數；將寄存器Z₅中值求平方，其結果存放在寄存器X₁中；將寄存器Z₃和Z₄中值相加，其結果存放在寄存器X₂中；

7d)發出一個完成信號給步驟(8)；

(8)判斷重復條件

主狀態機在收到6d)或7d)發出的任意一個完成信號之后，完成以下步驟：

8a)控制當前判斷位向下移一位；

8b)根據當前判斷位是否還在隨機數內，檢查隨機數最低位是否已經根據步驟(5)完成了判斷，如果完成了判斷，則執行步驟(9)，否則，重復執行步驟(4)；

(9)獲取點乘的x坐標值

主狀態機通過對存放在寄存器X₁、Z₁中的X坐標值和Z坐標值進行除法運算，得到了點乘的x坐標值；

(10)基點乘法3運算

10a)主狀態機調用存放在寄存器X₁、Z₁、X₂、Z₂中的值；

10b)主狀態機同時做以下三個乘法運算：

調用乘法模塊求寄存器Z₁中值和基點x坐標值的乘積，其結果存放在寄存器Z₃中；調用乘法模塊求寄存器Z₂中值和基點x坐標值的乘積，其結果存放在寄存器Z₄中；調用乘法模塊求寄存器Z₁、Z₂中值的乘積，其結果存放在寄存器Z₅中；

10c)主狀態機同時做以下四個運算：

將基點x坐標值和點乘x坐標值相加，其結果存放在寄存器Z₁中；將寄存器Z₃、X₁中值相加，其結果存放在寄存器Z₃中；將寄存器Z₄、X₂中值相加，其結果存放在寄存器Z₄中；將基點x坐標值平方后與基點y坐標值相加，其結果存放寄存器Z₂中；

10d)主狀態機同時做以下三個乘法運算：

調用乘法模塊求寄存器Z₃、Z₄中值的乘積，其結果存放在寄存器Z₃中；調用乘法模塊求寄存器Z₅、Z₂中值的乘積，其結果存放在寄存器Z₄中；調用乘法模塊求寄存器Z₅中值和基點x坐標值的乘積，其結果存放在寄存器Z₅中；

10e)主狀態機將寄存器Z₃與Z₄中值相加，其結果存放在寄存器Z₃中；

10f)主狀態機調用求逆模塊，對寄存器Z₅中值進行一次求逆，將求逆結果存放在寄存器Z₅中；

10g)主狀態機調用一個乘法模塊求寄存器Z₅、Z₃中值的乘積，將乘積結果存放在寄存器Z₃中；

10h)主狀態機調用一個乘法模塊求寄存器Z₄、Z₃中值的乘積，將乘積結果存放在寄存器Z₃中；

10i)主狀態機將寄存器Z₃的值與基點的y坐標值相加，得到點乘y坐標值；

(11)輸出：將得到的點乘的x坐標值和y坐標值通過數據輸出端口進行輸出操作。