[發明專利]一種蒙哥馬利模乘方法及其電路

有效

• 申請號: 201310100944.1
• 申請日: 2013-03-26
• 公開（公告）號: CN103226461A
• 公開（公告）日: 2013-07-31
• 發明（設計）人: 王德明;丁顏玉;丁一;路崇;段志奎;譚洪舟
• 申請（專利權）人: 中山大學
• 主分類號: G06F7/72
• 分類號: G06F7/72
• 代理公司: 廣州粵高專利商標代理有限公司 44102
• 代理人: 禹小明

技術領域

本發明涉及公鑰加密領域，更具體地，涉及一種蒙哥馬利模乘方法及其電路。

背景技術

公鑰加密利用的是非對稱密碼，使用兩個獨立擔憂存在著某種數學聯系的密鑰：公鑰和私鑰。通信的各方保密各自的私鑰，公開其公鑰，發送者使用接收者的動搖加密，接收者使用只有自己制動的私鑰解密。公鑰加密還可以用于解決數字簽名的問題。

RSA是一種公鑰加密算法，既可以作為數據加解密也可以用來數字簽名和驗證，這使得該算法得到了廣泛的應用，例如網絡信息安全、智能卡、安全芯片以及手機移動通信等。RSA算法的安全依賴于大數分解的難易性，隨著計算機的飛速發展，512位密鑰長度的RSA加密算法安全性受到威脅，因此高安全的應用中必須將密鑰長度增加到1024位甚至2048位。密鑰長度的增加使硬件電路設計變得復雜，需要占用更多的硬件資源開銷，面積功耗都會大幅上升，速度也會下降。RSA加密最關鍵的計算步驟就是模乘，根據運算公式C=M^EmodN，需要不斷重復模乘操作以得到運算結果，模乘算法的優劣決定了整個加密運算時間的長短。

現有設計大部分采用蒙哥馬利模乘算法優化加解密時間，然而一味的提高模乘速度會使得功耗和面積增加，這對面積和功耗受限制的芯片設計帶來巨大的挑戰。而且傳統的模乘算法是在軟件中實現，這將取決于處理器的速度，每個操作都需要取指令、譯碼以及執行指令，大大降低了算法執行速度。隨著集成電路的發展，模乘算法大多采用硬件實現，其最關鍵的電路便是多項式乘加器。但由于乘加器功耗大，現有做法普遍是用多個時鐘實現，非常速度慢。

發明內容

本發明旨在至少在一定程度上解決上述技術問題。

本發明的首要目的是提供一種高速低功耗的蒙哥馬利模乘方法。

本發明的進一步目的是提供一種高速低功耗的蒙哥馬利模乘電路。

本發明第一個目的技術方案為：

一種蒙哥馬利模乘方法，模長度為k，k=sw，其中w為算法每次處理的字長大小，s為算法for循環所需的次數；輸入參數包括a、b和模數n，r為一存儲器，r的高k位為存放輸入參數a和輸出結果的r2，r的低k位為存放輸入參數b的r1，t為多項式臨時計算結果，r32、z1、c、x1、x2、n0'為中間變量，i和j為循環變量，其運算步驟為：

計算r2=MonPro(a,b,n)=a*b*2^-k?mod?n；

將t和i賦零值；

將中間變量r32賦值為r的第s個字，其中，r32表示存儲器r的第32為地址的數據；

令i為0開始外循環；

將t的第i個字與r32相乘，乘積結果與t的第i個字相加，結果的低k位賦給z1，高k位賦給c；

接著將z1與n0'相乘，乘積結果的低k位賦給z1，高k位賦給c，其中，n0`通過預先計算獲取，n0'=-n0^-1mod(2³²)，n0是指模數n的低32位值，n從外部輸入；

令x2=z1；令x1等于r的第i個字；

令j為0開始內循環；

將x1與r的第i個字相乘后的結果和x2與n的第i個字相乘后的結果相加，相加結果再加上c和t的第i+j個字，最終結果的低k位賦給t的第i+j個字，高k位賦給c；并令t的第i+s個字等于c，然后循環變量j加1，當j小于s時重復內循環，當j大于或者等于s時退出內循環；

循環變量i加1，當i小于s時重復外循環，當i大于或者等于s時退出外循環；

判斷t的高k位是否大于n，若是則將r2=r2-n，否則將t的低k位賦給r2；

根據r2輸出模乘結果。

在本方法中，多項式乘加器公式的運算只需要一個時鐘周期，運算速度得到大大的提升。而且本發明的蒙哥馬利模乘方法采用一體化設計集成相關操作，使得多項式乘加器公式只需要做兩次加法以及兩次乘法，時間復雜度為O（s²），大大簡化了運算的復雜度，進一步提升運算的速度，降低系統功耗。

本發明第二個目的技術方案為：

一種蒙哥馬利模乘電路，所述蒙哥馬利模乘采用權利要求1所述的方法實現，所述電路包括依次連接的接口電路、SRAM存儲器、蒙哥馬利模乘控制器、臨時寄存器和多項式乘加器；

接口電路與外部總線連接，將輸入參數a、b寫進SRAM存儲器的r中，并將計算完畢后的輸出結果讀出；