[發明專利]模乘運算的實現方法和裝置

有效

• 申請號: 201110041611.7
• 申請日: 2011-02-21
• 公開（公告）號: CN102646033A
• 公開（公告）日: 2012-08-22
• 發明（設計）人: 潘無窮;荊繼武;劉宗斌
• 申請（專利權）人: 中國科學院研究生院
• 主分類號: G06F7/72
• 分類號: G06F7/72
• 代理公司: 北京德琦知識產權代理有限公司 11018
• 代理人: 謝安昆;宋志強

技術領域

本發明涉及信息安全技術領域，特別涉及模乘運算的實現方法和裝置。

背景技術

RSA算法是由Ron?Rivest、Adi?Shamirh和LenAdleman三人在1977年提出的，提供了加密和簽名等功能，是應用最為廣泛的密碼算法之一。

RSA算法的核心為模乘運算，所謂模乘運算，即指當輸入乘數x、y，模數n時，輸出(x×y)mod?n的結果，mod表示求模運算。

移位-加算法為實現模乘運算的經典算法，具體實現如下：

1)接收輸入的k位乘數x、y，k位模數n，x、y和n均為正整數；

2)令s＝0，i＝k-1；

3)計算(s＜＜1)+x×y[i]，得到計算結果s’，其中，＜＜表示左移，＜＜1即表示左移1位，y[i]表示y的第i位的取值，當i＜0時，y[i]＝0；

計算s’mod?n，得到計算結果s”；

4)確定i的取值是否等于0，如果是，則將s”作為模乘運算的結果輸出，否則，令i＝i-1，s＝s”，然后重復執行步驟3).

需要說明的是，上述以及后續將要出現的各數字在實際應用中均以二進制形式進行表示。

另外，在實際應用中，還可對上述移位-加算法進行一定的改造，從而得到采用高基形式的移位-加算法，具體實現如下：

1)接收輸入的k位乘數x、y，k位模數n，k＝k₁×k₂，x、y、n、k₁和k₂均為正整數；

2)令s＝0，i＝k₂-1；

3)計算(s＜＜k₁)+x×y[(i+1)×k₁-1∶i×k₁]，＜＜表示左移，y[(i+1)×k₁-1∶i×k₁]表示y的第(i+1)×k₁-1位到第i×k₁位中的每位的取值，當i＜0時，y[i]＝0；

計算s’mod?n，得到計算結果s”；

4)確定i的取值是否等于0，如果是，則將s”作為模乘運算的結果輸出，否則，令i＝i-1，s＝s”，然后重復執行步驟3)。

上述兩種方式雖然均可實現模乘運算，但兩者在實際應用均會存在一定的問題，即計算量大，從而導致計算速度慢。

發明內容

有鑒于此，本發明的主要目的在于提供兩種模乘運算的實現方法，能夠降低計算量，進而提高計算速度。

本發明的另一目的在于提供兩種模乘運算的實現裝置，能夠降低計算量，進而提高計算速度。

為達到上述目的，本發明的技術方案是這樣實現的：

一種模乘運算的實現方法，包括：

A、接收輸入的乘數x、y，模數n；其中，x和y的位數均為k，n的位數為j，j≤k，x、y和n均為正整數；

令n’＝n＜＜t，y’＝y＜＜t，t為正整數，＜＜表示左移；

B、計算s＝(x×y’)mod?n’，mod表示求模運算，包括：

B1、令s＝0，i＝k+t-1；

B2、計算s＜＜1+x×y’[i]，得到計算結果s’，y’[i]表示y’的第i位的取值；

B3、計算s’mod?n’，得到計算結果s”；

B4、令s＝s”，如果i等于0，則執行步驟C；否則，令i＝i-1，并返回執行步驟B2；

C、令s”’＝s＞＞t，將s”’作為模乘運算的結果輸出。

一種模乘運算的實現方法，包括：

A、接收輸入的乘數x、y，模數n；其中，x、y和n的位數均為k，且x、y和n均為正整數；

令n’＝n＜＜t，y’＝y＜＜t，t為正整數，＜＜表示左移，并且，k和t均需要能夠被正整數k₁整除；

B、計算s＝(x×y’)mod?n’，mod表示求模運算，包括：

B1、令s＝0，i＝k/k₁+t/k₁-1；

B2、計算s＜＜k₁+x×y’[(i+1)×k₁-1∶i×k₁]，得到計算結果s’，y’[(i+1)×k₁-1∶i×k₁]表示y’的第(i+1)×k₁-1位到第i×k₁位中的每位的取值；