[發明專利]一種減少預計算的標量乘算法

在審

• 申請號: 202210229644.2
• 申請日: 2022-03-07
• 公開（公告）號: CN114611051A
• 公開（公告）日: 2022-06-10
• 發明（設計）人: 楊曉秋;田新雨;孫海旭
• 申請（專利權）人: 哈爾濱理工大學
• 主分類號: G06F17/10
• 分類號: G06F17/10
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明是一種減少預計算的標量乘算法。提供一種降低橢圓曲線標量乘計算復雜度的算法，實現該算法的步驟如下：第一步，輸入標量k和窗口寬度w；第二步，預計算出f(i)＝f(i?1)+f(i?2),i＞＝2，其中f(0)＝P,f(1)＝2P，并且預計算時最大值不超過(2^w?1)P,例如當窗口寬度w為4時，預計算{1P,2P,3P,5P,8P,13P}；第三步，利用wNAF算法確定k鏈中的值，判斷k對2取余是否為0，若為0，則e_i＝0，若不為0，則e_i＝k mod 2^w，k＝k?e_i，k＝k/2，此輪運算結束，下一輪繼續判斷k對2取余是否為0，直至得到整個k鏈；第四步，通過第三步得到的k鏈進行標量乘計算Q＝k*P得到標量乘Q。相比較wNAF標量乘算法，此算法不僅減少了預計算的個數還降低了計算復雜度，有助于橢圓曲線密碼系統的有效實現。

技術領域

本發明涉及的減少預計算標量乘是一種可以降低標量乘計算復雜度的算法。

背景技術

橢圓曲線密碼算法的安全性主要來源于橢圓曲線離散對數問題(Elliptic CurveDiscrete Logarithm Problem,ECDLP)的難解性。與RSA相比，ECC加密性能更高且所需的密鑰長度更短并且具有單比特密鑰最高的安全強度。

正整數k和橢圓曲線有限域上的點P,求橢圓曲線上另一個點的運算。標量乘法包含兩方面的內容：第一，有效率的運算；第二，有足夠的安全性。在橢圓曲線密碼體制的實現過程中，標量乘法有著至關重要的作用。標量乘法的運算是通過點加、倍點運算來實現的，他的運算效率直接影響著ECC的性能。因此，如何提高標量乘法運算的效率。是ECC研究的一個重點。

計算標量乘是一個耗時的操作。本算法是基于wNAF算法改進的一種橢圓曲線標量乘算法，減少了預計算的個數，并且占用的內存空間更少，進而降低了標量乘的計算復雜度。

發明內容

發明的目的在于提供一種減少預計算的標量乘算法，目的是降低標量乘的計算復雜度。

本發明的實現包括以下步驟。

第一步，輸入標量k和窗口寬度w；

第二步，預計算出f(i)＝f(i-1)+f(i-2),i＞＝2，其中f(0)＝P,f(1)＝2P，并且預計算時最大值不超過(2^w-1)P,例如當窗口寬度w為4時，預計算{1P,2P,3P,5P,8P,13P}；

第三步，利用wNAF算法確定k鏈中的值，判斷k對2取余是否為0，若為0，則e_i＝0，若不為0，則e_i＝k mod 2^w，k＝k-e_i，k＝k/2，此輪運算結束，下一輪繼續判斷k對2取余是否為0，直至得到整個k鏈；

第四步，通過第三步得到的k鏈進行標量乘計算Q＝k*P得到標量乘Q。

作為本發明的進一步改進，所述的第一步，w窗口寬度范圍是{2，3，4，5，6，7，8，9，10，11}。通常當w＝4時，在此算法中降低得計算復雜度更加明顯。

作為本發明的進一步改進，所述的第二步，對于預計算數列，每個數都是前兩個數之和，只需要點加運算就能完成預計算，當窗口寬度為4時，由第三步得到的k鏈中，非零數值是由{P,3P,5P,...,15P}組成，共存儲8個點，本發明中已經預計算出{1P,2P,3P,5P,8P,13P}，共存儲6個點，減少了預計算的個數。

作為本發明的進一步改進，所述的第四步，通過第二步的預計算，會產生差值，但是差值很小為P,只需一次點加運算就能彌補差值，例如k鏈中存在非零數值7P時，7P＝8P-P。