[發明專利]一種適合SM2算法的快速模約減方法和介質

有效

• 申請號: 201711383428.9
• 申請日: 2017-12-20
• 公開（公告）號: CN108418687B
• 公開（公告）日: 2022-02-08
• 發明（設計）人: 何德彪;陳泌文;謝翔;李升林;孫立林
• 申請（專利權）人: 矩陣元技術（深圳）有限公司
• 主分類號: H04L9/30
• 分類號: H04L9/30
• 代理公司: 上海專利商標事務所有限公司 31100
• 代理人: 施浩

1.一種適合SM2算法的快速模約減方法，其特征在于，針對SM2橢圓曲線公鑰算法推薦參數計算模約減，用于SM2算法的快速實現，方法包括：

通過數據轉換得到轉換數據，將512比特數模SM2橢圓曲線推薦參數問題轉化為計算若干個256比特數的線性組合；

通過拆分負數項和多倍項將轉換數據拆分，并用拆分數據表示轉換數據，以使每個256比特數易于表示；

通過重組整合拆分數據，降低加法或減法個數；

通過計算若干個256比特數的和，完成512比特數模SM2橢圓曲線推薦參數模約減的計算；

其中，數據轉換的步驟進一步包括：

步驟1.1，將c modp₂₅₆進行轉化，

其中p₂₅₆＝2²⁵⁶-2²²⁴-2⁹⁶+2⁶⁴-1，輸入整數且可表示為c＝(c_2t-1,...,c₂,c₁,c₀)，

其中t＝8

步驟1.2，將步驟1.1中的I₂modp₂₅₆進行轉化，

I₂modp₂₅₆＝([(c₁₅,c₁₄,c₁₃,c₁₂,c₁₁,c₁₀,c₉,0,0,0,0,0,0,0,0,0)]modp₂₅₆+[(0,0,0,0,0,0,0,c₈,0,0,0,0,0,0,0,0)]modp₂₅₆-c₈p₂₅₆modp₂₅₆)modp₂₅₆

＝([(c₁₅,c₁₄,c₁₃,c₁₂,c₁₁,c₁₀,c₉,0,0,0,0,0,0,0,0,0)]modp₂₅₆+[(c₈,0,0,0,c₈,-c₈,0,c₈)]modp₂₅₆)modp₂₅₆

＝(I₃modp₂₅₆+R₂modp₂₅₆)modp₂₅₆；

步驟1.3，將步驟1.2中的I₃modp₂₅₆進行轉化，

I₃modp₂₅₆＝([(c₁₅,c₁₄,c₁₃,c₁₂,c₁₁,c₁₀,0,0,0,0,0,0,0,0,0,0)]modp₂₅₆+[(0,0,0,0,0,0,c₉,0,0,0,0,0,0,0,0,0)]modp₂₅₆-2³²c₉p₂₅₆modp₂₅₆-c₉p₂₅₆modp₂₅₆)modp₂₅₆

＝([(c₁₅,c₁₄,c₁₃,c₁₂,c₁₁,c₁₀,0,0,0,0,0,0,0,0,0,0)]modp₂₅₆+[(c₉,0,0,c₉,0,-c₉,c₉,c₉)]modp₂₅₆)modp₂₅₆

＝(I₄modp₂₅₆+R₃modp₂₅₆)modp₂₅₆

步驟1.4，將步驟1.3中的I₄modp₂₅₆進行轉化，

I₄modp₂₅₆＝([(c₁₅,c₁₄,c₁₃,c₁₂,c₁₁,0,0,0,0,0,0,0,0,0,0,0)]modp₂₅₆+[(0,0,0,0,0,c₁₀,0,0,0,0,0,0,0,0,0,0)]modp₂₅₆-2⁶⁴c₁₀p₂₅₆modp₂₅₆-2³²c₁₀p₂₅₆modp₂₅₆-c₁₀p₂₅₆modp₂₅₆)modp₂₅₆

＝([(c₁₅,c₁₄,c₁₃,c₁₂,c₁₁,0,0,0,0,0,0,0,0,0,0,0)]modp₂₅₆+[(c₁₀,0,c₁₀,0,0,0,c₁₀,c₁₀)]modp₂₅₆)modp₂₅₆

＝(I₅modp₂₅₆+R₄modp₂₅₆)modp₂₅₆；

步驟1.5，將步驟1.4中的I₅modp₂₅₆進行轉化，

I₅modp₂₅₆＝([(c₁₅,c₁₄,c₁₃,c₁₂,0,0,0,0,0,0,0,0,0,0,0,0)]modp₂₅₆+[(0,0,0,0,c₁₁,0,0,0,0,0,0,0,0,0,0,0)]modp₂₅₆-2⁹⁶c₁₁p₂₅₆modp₂₅₆-2⁶⁴c₁₁p₂₅₆modp₂₅₆-2³²c₁₁p₂₅₆modp₂₅₆-c₁₁p₂₅₆modp₂₅₆)modp₂₅₆

＝([(c₁₅,c₁₄,c₁₃,c₁₂,0,0,0,0,0,0,0,0,0,0,0,0)]modp₂₅₆+[(c₁₁,c₁₁,0,0,c₁₁,0,c₁₁,c₁₁)]modp₂₅₆)modp₂₅₆

＝(I₆modp₂₅₆+R₅modp₂₅₆)modp₂₅₆；

步驟1.6，將步驟1.5中的I₆modp₂₅₆進行轉化，

I₆modp₂₅₆＝([(c₁₅,c₁₄,c₁₃,0,0,0,0,0,0,0,0,0,0,0,0,0)]modp₂₅₆+[(0,0,0,c₁₂,0,0,0,0,0,0,0,0,0,0,0,0)]modp₂₅₆-2¹²⁸c₁₂p₂₅₆modp₂₅₆-2⁹⁶c₁₂p₂₅₆modp₂₅₆-2⁶⁴c₁₂p₂₅₆modp₂₅₆-2³²c₁₂p₂₅₆modp₂₅₆-c₁₂p₂₅₆modp₂₅₆)modp₂₅₆

＝([(c₁₅,c₁₄,c₁₃,0,0,0,0,0,0,0,0,0,0,0,0,0)]modp₂₅₆+[(2c₁₂,0,0,c₁₂,c₁₂,0,c₁₂,c₁₂)]modp₂₅₆)modp₂₅₆

＝(I₇modp₂₅₆+R₆modp₂₅₆)modp₂₅₆；

步驟1.7，將步驟1.6中的I₇modp₂₅₆進行轉化，

I₇modp₂₅₆＝([(c₁₅,c₁₄,0,0,0,0,0,0,0,0,0,0,0,0,0,0)]modp₂₅₆+[(0,0,c₁₃,0,0,0,0,0,0,0,0,0,0,0,0,0)]modp₂₅₆-2¹⁶⁰c₁₃p₂₅₆modp₂₅₆-2¹²⁸c₁₃p₂₅₆modp₂₅₆-2⁹⁶c₃p₂₅₆modp₂₅₆-2⁶⁴c₁₃p₂₅₆modp₂₅₆-2³²c₁₃p₂₅₆modp₂₅₆-c₁₃p₂₅₆modp₂₅₆)modp₂₅₆

＝([(c₁₅,c₁₄,0,0,0,0,0,0,0,0,0,0,0,0,0,0)]modp₂₅₆+[(2c₁₃,0,c₁₃,c₁₃,2c₁₃,-c₁₃,c₁₃,2c₁₃)]modp₂₅₆)modp₂₅₆

＝(I₈modp₂₅₆+R₇modp₂₅₆)modp₂₅₆；

步驟1.8，將步驟1.7中的I₈modp₂₅₆進行轉化，

I₈modp₂₅₆＝([(c₁₅,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)]modp₂₅₆+[(0,c₁₄,0,0,0,0,0,0,0,0,0,0,0,0,0,0)]modp₂₅₆-2¹⁹²c₁₄p₂₅₆modp₂₅₆-2¹⁶⁰c₁₄p₂₅₆modp₂₅₆-2¹²⁸c₁₄p₂₅₆modp₂₅₆-2⁹⁶c₁₄p₂₅₆modp₂₅₆-2⁶⁴c₁₄p₂₅₆modp₂₅₆-2³²c₁₄p₂₅₆modp₂₅₆-c₁₄p₂₅₆modp₂₅₆)modp₂₅₆

＝([(c₁₅,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)]modp₂₅₆+[(2c₁₄,c₁₄,c₁₄,2c₁₄,c₁₄,-c₁₄,2c₁₄,2c₁₄)]modp₂₅₆)modp₂₅₆

＝(I₉modp₂₅₆+R₈modp₂₅₆)modp₂₅₆；

步驟1.9，將步驟1.8中的I₉modp₂₅₆進行轉化，

I₉modp₂₅₆＝([(c₁₅,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)]modp₂₅₆-2²²⁴c₁₅p₂₅₆modp₂₅₆-2¹⁹²c₁₅p₂₅₆modp₂₅₆-2¹⁶⁰c₁₅p₂₅₆modp₂₅₆-2¹²⁸c₁₅p₂₅₆modp₂₅₆-2⁹⁶c₁₅p₂₅₆modp₂₅₆-2⁶⁴c₁₅p₂₅₆modp₂₅₆-2³²c₁₅p₂₅₆modp₂₅₆-c₁₅p₂₅₆modp₂₅₆)modp₂₅₆

＝[(3c₁₅,c₁₅,2c₁₅,c₁₅,c₁₅,0,2c₁₅,2c₁₅)]modp₂₅₆

＝R₉modp₂₅₆；

根據上述步驟1.1至步驟1.9的轉換過程，最后用轉換數據(R₁,R₂,...,R₉)表示c modp₂₅₆：

c modp₂₅₆＝(R₁+R₂+R₃+R₄+R₅+R₆+R₇+R₈+R₉)modp₂₅₆；

其中，重組整合拆分數據的過程中確保對應位置相的和不發生變化，其步驟進一步包括：

c modp₂₅₆＝(R₁+t2+t3+R₄+R₅+T₁+T₂+T₃+T₄+T₅+T₆+T₇+T₈-s₂-s₃-s₇-s₈)modp₂₅₆

＝[(c₇,c₆,c₅,c₄,c₃,c₂,c₁,c₀)+(c₈,0,0,0,c₈,0,0,c₈)+(c₉,0,0,c₉,0,0,c₉,c₉)+(c₁₀,0,c₁₀0,0,0,c₁₀,c₁₀)+(c₁₁,c₁₁,0,0,c₁₁,0,c₁₁,c₁₁)++2(c₁₄,0,c₁₅,c₁₄,c₁₃,0,c₁₅,c₁₄)+2(c₁₂,0,0,0,0,0,c₁₄,c₁₃)+(0,0,0,c₁₂,c₁₂0,c₁₂,c₁₂)+(c₁₃,0,c₁₃,c₁₃,0,0,c₁₃,0)+(c₁₃,c₁₄,c₁₄，0,c₁₄,0,0,0)+(c₁₅,c₁₅,0,c₁₅,c₁₅,0,0,0)+(c₁₅,0,0,0,0,0,0,c₁₅)+(c₁₅,0,0,0,0,0,0,c₁₅)-(0,0,0,0,0,c₈,0,0)-(0,0,0,0,0,c₉,0,0)-(0,0,0,0,0,c₁₃,0,0)-(0,0,0,0,0,c₁₄,0,0)]modp₂₅₆

＝[s₀+s₁+s₄+s₅+s₆+2s₉+2s₁₀+s₁₁+s₁₂+s₁₃+s₁₄+2s₁₅-s₂-s₃-s₇-s₈]modp₂₅₆；

根據上述拆分過程，最后用重組整合數據表示c modp₂₅₆：

c modp₂₅₆＝[s₀+s₁+s₄+s₅+s₆+2s₉+2s₁₀+s₁₁+s₁₂+s₁₃+s₁₄+2s₁₅-s₂-s₃-s₇-s₈]modp₂₅₆。