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

有效

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

本發明提供一種基于素數預處理的ECC標量乘法器實現的方法、裝置及存儲設備，用素數預處理代替wNAF中的奇數預處理，使得預處理運算量大幅度降低；將多基鏈編碼思想應用到wNAF標量乘中，將加法鏈查找范圍縮小到wNAF表示序列中的一個非零數，有效降低了構建加法鏈的時間，解決了現有的ECC標量乘法器的實現都存在用于查找、構建等時間過長或硬件面積偏大的問題。

技術領域

本發明涉及密碼學領域，尤其涉及一種基于素數預處理的ECC標量乘法器實現方法及裝置。

背景技術

ECC(橢圓曲線密碼，Elliptic Curve Cryptography)于1987年分別被Miller和Koblitz分別提出，相對于其他公鑰密碼體系，ECC可以實現更小的密鑰長度達到更高的安全強度，正是由于ECC這一特性，其被廣泛應用于安全電子商務、移動通信，電子政務以及區塊鏈領域。基于ECC的簽名方案、驗簽方案、密鑰交換方案被ANSI(美國國家標準學會)、IEEE、ISO和NIST(美國國家標準與技術研究院)等權威組織接受并采用為國際標準，隨著ECC算法的不斷優化，在較大的密鑰加解密情況下，傳統的軟件加、解密方式難以達到所需速度，因此硬件加密卡實現ECC也是常見的方式之一。

ECC硬件實現的核心構成是標量乘法器，其標量乘法器的實現原理是給定一個整數K(標量)和橢圓曲線上的一個點P(基點)，求解另外一個點Q，Q＝KP的操作。

常見的K的表示方法有DA(Doubling and Addition)，NAF(非相鄰表示型，non-adjacent-form)，wNAF(窗口NAF，window non-adjacent-form)、雙基鏈或多基鏈，但是上述方法均有著缺陷:

DA方法實現ECC標量乘法器，由于僅僅是將標量K展開，對非零比特位的數據進行點加處理，雖然這種方法易于并行，但是這樣處理的點加操作巨大。

NAF方法和wNAF方法相比于DA方法實現ECC標量乘法器而言，通過利用額外的寄存器或內存進行預處理的方式一次性處理2位乃至w位的奇數數據，使得在計算過程中標量K的二進制展開中非零比特比率下降，從而減少了點加的運算次數，但是隨著窗口W的增大，預處理的運算數量會以指數形式增加，這樣會導致用于在預處理運算操作上查找花費的時間或用于存放預處理的寄存器數量大增，導致查找時間過長和硬件面積增大。

雙基鏈和多基鏈方法實現ECC標量乘法器，在構成雙基鏈及多基鏈的過程中，將標量K展開為若干2^bin*3^tri*5^qui個部分，并通過加法鏈和三、五和七倍點加速標量乘法，窮舉所有加法鏈生成的方式，選取其最優進行后續的標量乘法，用這種方法構建一條最優的加法鏈耗時很長，構建出來的加法鏈如果冗長，則還會導致計算量和運行時間更長。

綜上所述，現有的ECC標量乘法器的實現都存在用于查找、構建等時間過長或硬件面積偏大的問題。

發明內容

基于上述存在的問題，本發明提供一種基于素數預處理的ECC標量乘法器實現方法、裝置及存儲介質，用以解決現有的ECC標量乘法器的實現都存在用于查找、構建等時間過長或硬件面積偏大的問題。

本發明實施例公開一種基于素數預處理的ECC標量乘法器實現的方法，包括：

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

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

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