[發明專利]一種基于改進的Montgomery模乘算法的可擴展模乘器電路

有效

• 申請號: 201410145671.7
• 申請日: 2014-04-14
• 公開（公告）號: CN103914277B
• 公開（公告）日: 2017-02-15
• 發明（設計）人: 韓軍;竇仁峰;曾凌云;曾曉洋
• 申請（專利權）人: 復旦大學
• 主分類號: G06F7/72
• 分類號: G06F7/72
• 代理公司: 上海正旦專利代理有限公司31200
• 代理人: 陸飛,王潔平

技術領域

本發明屬于公鑰密碼學集成電路設計技術領域，具體涉及一種基于改進的商流水Montgomery模乘算法的可擴展模乘器電路結構。

背景技術

近些年來，隨著計算機技術與互聯網技術的不斷發展，云計算的時代正在悄悄來臨。隨著云計算技術的不斷深入，如何保障用戶的數據安全與隱私，成為了一個重要的挑戰。高安全的數據加密與身份驗證是云計算發展的必然。無論是對于數據加密還是身份驗證，公鑰密碼學，由于其非對稱加密特性，使得其在這些應用中扮演了重要的角色。模乘是公鑰密碼學中最為核心的運算。如何進行高性能的模乘器設計，是解決云計算的相關挑戰的重要技術基礎。

隨著物聯網、移動互聯網、無線通信應用技術的不斷發展，無線接入設備越來越多，對于無線接入點的接入認證任務也越來越重。由其對于移動多媒體流應用，頻繁的切換接入點會帶來較差的用戶體驗。如何解決低延時的接入認證，是解決上述問題的基礎。目前的接入認證主要也是基于公鑰密碼學，所以低延時的模乘器設計成為了解決挑戰的關鍵技術。

隨著密碼攻擊與破解技術的不斷提升，較小的秘鑰寬度已經很難保證加密后的數據具有足夠的安全性。隨著秘鑰寬度的不斷增加，帶來了計算量的大幅提升。在安全性增加的同時，為了實現可以接受的運算時間，高性能的模乘器設計是首先需要考慮的。與此同時，為了滿足不同的安全性需求，加密協議中的位寬往往是可以變化的，如ECC-256、ECC-521、RSA-1024、RSA-2048等。為了滿足不同協議的需求，可擴展的模乘器設計是技術關鍵。

發明內容

為了克服現有技術的不足，本發明的目的在于提供一種基于改進的商流水Montgomery模乘算法及基于該算法的高性能可擴展的電路，其有助于解決當前云計算、移動無線接入等技術領域面臨的挑戰。

本發明首先對原有的商流水Montgomery模乘算法進行改進，提出了一種可以減小Montgomery域數據位寬的改進的算法。所述改進的Montgomery模乘算法基于原始商流水Montgomery模乘算法增加了一個用于運算的參數????????????????????????????????????????????????，該參數通過下面方法獲得：

新增的參數用于

其中，M為模乘中的模數，k為模乘的基；改進算法中的與原始算法中的相同；S_n+1與S_n+2為迭代運算中的運算結果，Q_n為第n次迭代的Q值。具體見說明書附錄部分的附錄2和附錄4。

與原始商流水Montgomery模乘算法要求相比，其位寬可以減少k-1比特；由于高性能模乘設計幾乎都是采用高基的實現方法，而高基實現方法中，k值較大，通常為幾十或幾百的量級。所以，k-1比特的減少對于硬件設計來說是一個比較大的改進，可以較大的減少系統中運算單元與寄存器堆等的數據位寬，從而使得系統的開銷得到減小，并有利于達到更好的時序性能，實現更高的工作頻率。

在改進的算法的基礎上，本發明還提出了一種基于改進的Montgomery模乘算法的可擴展模乘器電路。該電路結構主要由部分積產生電路、第一級流水線進位保存加法器（PCSA）壓縮樹、第二級PCSA壓縮樹、部分積反饋電路、模乘器擴展相關電路和時序控制器構成；其中：

所述部分積產生電路由單個部分積產生電路構成，其在時序控制器的控制信號下，根據寄存器B（附錄2中的參數B）、寄存器B+M₂（附錄2中的參數B和參數的累加結果）、寄存器M₂（附錄2中的參數）、寄存器M₁（附錄2中的參數）、以及寄存器A（附錄2中的參數A）和寄存器Q（附錄2中的參數Q_i）的輸出，產生相應的操作數高半部分或者低半部分的的部分積并送給第一級PCSA壓縮樹的輸入端；作為部分積產生電路的輸入

所述第一級PCSA壓縮樹在時序控制器產生的控制信號控制下對部分積產生電路所產生的部分積進行壓縮，并將壓縮后的結果送到流水線寄存器進行寄存；

所述第二級PCSA壓縮樹在時序控制器產生的控制信號控制下，對寄存后的部分積、部分積反饋電路產生的部分積、以及加法器產生的進位信號進行壓縮，并把壓縮后的結果送到相應的結果寄存器進行保存；