[發明專利]一種基于素數預處理的ECC標量乘法器的實現方法及裝置

有效

• 申請號: 202010598636.6
• 申請日: 2020-06-28
• 公開（公告）號: CN111756538B
• 公開（公告）日: 2023-10-13
• 發明（設計）人: 黃海;那寧;邢琳;劉志偉;于斌;趙石磊;彭天彬;陶宏敬
• 申請（專利權）人: 哈爾濱理工大學
• 主分類號: H04L9/30
• 分類號: H04L9/30
• 代理公司: 哈爾濱市偉晨專利代理事務所(普通合伙) 23209
• 代理人: 榮玲

1.一種基于素數預處理的ECC標量乘法器實現的方法，其特征在于，包括：

Step1.輸入標量K、基點P，根據內存大小和所需硬件面積的需求選擇wNAF表示序列的窗口大小w，并設置一個空的result點，用于存放每輪循環的結果；

Step2.生成標量K的wNAF表示序列，序列位數為B,將標量K表示成的形式，其中，位數B可選用NIST推薦的15條曲線之一位數；

Step3.對wNAF表示序列中的奇數進行2^w下所有的素數預處理操作；

Step4.對result點進行倍點操作得到新result點；通過移位執行的方式，使標量K生成的整個wNAF表示序列依次從第B-1處的地方一直執行到第0處；

Step5.若移位執行到wNAF表示序列中非零數K_B是素數，則進行對應素數的預處理點查找，若序列中非零數K_B是非素數，則查找最近的素數s對應的預處理點Q1；

Step6.計算非零數K_B與最近的素數s的差a，若a不等于0，則構建多基鏈a＝2^bin*3^tri*5^qui*7^set，查找多基鏈中次數為1的項用預處理點代替，計算Q2＝aP，其中，bin代表二倍點次數存放鏈表、tri代表三倍點次數存放鏈表、qui代表五倍點次數存放鏈表、set代表七倍點次數存放鏈表；若a等于0,則Q2＝NULL；

Step7.將Q1和Q2點加得到標量乘結果Q，并將Q與Step4倍點操作后得到的result點進行點加操作，再次更新result點存儲的結果作為標量乘結果；

Step8.重復Step4至Step7，移位執行B次，全部移位執行完成后輸出最終的標量成結果。

2.如權利要求1所述的方法，其特征在于，所述生成標量K的wNAF表示序列，其位數為B,將標量K表示成的形式，其中，位數B可選用NIST推薦的15條曲線之一位數，包括：

Step2.1令i＝0

Step2.2若標量K≥1，重復執行step2.3至step2.5；

Step2.3若K mod 2＝1，則k_i＝K mod 2^w,K＝K-k_i；

Step2.4若K mod 2＝0，則K＝K/2，ki＝0；

Step2.5令i＝i+1；

Step2.6返回K的wNAF表示序列D{k_B-1,k_B-2,…,k₁,k₀}。

3.如權利要求1所述方法，其特征在于，所述對wNAF表示序列中的奇數進行2^w下所有的素數預處理操作，包括：

Step3.1首先對基點P的倍點計算，得到倍點結果2P；

Step3.2令i＝1，預處理點P_pre＝P；

Step3.3判斷i是否大于2^w-1，若是，則返回所有預處理的預處理點；否則繼續判斷i是否為素數，若是，則將P_pre存儲用于預計算，若不是，則令P_pre＝P_pre+2P，i＝i+2；

Step3.4，繼續判斷Step3.3中i是否大于2^w-1，若是，則返回所有預處理的預處理點，否則，重復執行Step3.1-Step3.4直至i大于2^w-1條件成立。

4.如權利要求1所述方法，其特征在于，所述倍點操作，具體為：該點乘以2，所述點加操作為兩點相加。