[發明專利]優化的蒙哥馬利模乘硬件

有效

• 申請號: 201410037782.6
• 申請日: 2014-01-26
• 公開（公告）號: CN103761068B
• 公開（公告）日: 2017-02-01
• 發明（設計）人: 劉紅明;周玉潔;朱念好
• 申請（專利權）人: 上海交通大學
• 主分類號: G06F7/72
• 分類號: G06F7/72
• 代理公司: 上海新天專利代理有限公司31213
• 代理人: 張澤純

技術領域

本發明涉及公鑰密碼技術，具體涉及一種優化的蒙哥馬利模乘方法、模平方方法和模乘硬件。

背景技術

隨著信息技術的發展與應用，網上交易如網上銀行、電子商務和電子政務也變得越來越普遍，其安全問題也越來越受到人們的重視。為了提高網上交易的安全性，傳統的分組密碼算法逐漸被公鑰密碼算法替代。公鑰密碼算法的優點是安全性高，缺點是加密速度比分組密碼慢很多，所以人們一直在研究如何提升公鑰密碼算法的運算速度。目前，公鑰密碼算法主要有兩種，一種是RSA，另外一種就是橢圓曲線密碼ECC（Elliptic?Curve?Cryptography）。上述兩種公鑰密碼算法都需要使用模乘計算（A*B?mod?N）。

實現模乘算法的方法有很多種,其中蒙哥馬利算法是使用最廣泛的方法。在1996年,Koc總結了蒙哥馬利算法的五種實現方法，分別為SOS（Separated?operand?scanning）,CIOS(Coarsely?integrated?operand?scanning),FIOS(Finely?integrated?operand?scanning),FIPS(Finely?integrated?product?scanning),CIHS(Coarsely?integrated?hybrid?scanning)。其中FIOS易于硬件實現而得到廣泛應用。

原始FIOS算法描述

目前，大多數的模乘器都是基于蒙哥馬利算法及其變形算法設計的，沒有很好的考慮性能與面積的平衡，要么性能很好，但是面積很大，要么相反。

發明內容

基于上述問題，本發明提供一種優化的蒙哥馬利模乘方法、模平方方法和模乘硬件，在減少面積的同時又提高了模乘的性能，。

為實現上述目的，本發明的技術解決方案如下：

一種優化的蒙哥馬利模乘方法，其特點在于，乘數A、乘數B和模數N都是n位的二進制數，w為每次處理的字長，s為模數N的字長個數，n0為w位的常數，中間變量m、中間變量S均為w位的二進制數，中間變量C為（w+1）位的二進制數，最終結果T為n位的二進制數，i、j為循環變量，運算前，標量C、S、T均賦值0，該方法包括以下步驟：

步驟1、令i為0開始外循環；

步驟2、將A的第0個字與B的第0個字相乘，乘積結果再與T的第0個字相加，將相加結果的低w位賦給S，高（w+1）位賦給C；

步驟3、將S與n0相乘后，取低w位賦給m；

步驟4、將m與N的第0個字相乘，乘積結果與（C,S）組成的（2w+1）位二進制數相加后，低w位賦給S，高（w+1）位賦給C；

步驟5、令j為1開始內循環；

步驟6、將m與N的第j個字相乘，乘積結果與C的第j個字相加后，再與T的第j個字相加，相加結果的低w位賦給S，高（w+1）位賦給C；

步驟7、將A的第j個字與B的第j個字相乘，乘積結果與（C,S）組成的（2w+1）位二進制數相加，相加結果的低w位賦給S，高（w+1）位賦給C，并將S賦給T的第（j-1）個字，循環變量j加1，重復內循環直至j等于（s-1），退出內循環；

步驟8、將T的第s個字與C進行相加，相加結果的低w位賦給S，高（w+1）位賦給C；

步驟9、將s賦給T的第（s-1）個字，將C的低w位賦給T的第s個字，循環變量i加1，重復內循環直至i等于（s-1），退出外循環；

步驟10、如果T>N，則將T減N之后再賦值給T。

一種優化的蒙哥馬利模平方方法，其特點在于，乘數A、乘數B和模數N都是n位的二進制數，w為每次處理的字長，s為模數N的字長個數，n0為w位的常數，中間變量m、中間變量S為w位的二進制數，中間變量C為（w+1）位的二進制數，最終結果T為n位的二進制數，i、j為循環變量，運算前，標量C、S、T均賦值0，該方法包括如下步驟：

步驟1、令i為0開始外循環；

步驟2、將A的第0個字與B的第0個字相乘，乘積結果再與T的第0個字相加，將相加結果的低w位賦給S，高（w+1）位賦給C；

步驟3、將S與n0相乘后，取低w位賦給m；

步驟4、將m與N的第0個字相乘，乘積結果與（C，S）組成的（2w+1）位二進制數相加后，低w位賦給S，高（w+1）位賦給C；

步驟5、令j為1開始內循環；