Rsa加密算法的實現電路及方法

2023-07-18 22:44:41

專利名稱：Rsa加密算法的實現電路及方法
技術領域：
本發明涉及計算方法的硬體實現領域，尤其涉及RSA加密算法中大數模乘、模冪運算的硬體實現，具體的說是涉及通過集成電路實現採用蒙哥馬利模乘法完成大數模冪運算的硬體電路。
隨著通訊技術的發展，信息的傳輸量越來越大，信息的安全問題也越來越重要，尤其在商業領域，信息傳輸的安全性、完整性和不可抵賴性直接影響到商家的運作模式和經濟利益。在資訊時代，高速計算機和全球化的INTERNET網絡的發展，使世界不同地區的人們可以相互交換信息，信息訪問的合法性顯得日益重要。日益發展的各種信息加密、解密技術適應了時代的要求，良好的加密算法使信息傳輸更可靠、更安全，其中公鑰加密算法能更好的滿足用戶的要求。到目前為止，RSA加密算法是最流行的公開密鑰算法，可用作加密和數字籤名。
RSA加密算法是由R.L.Riverst，A.Shamir，and L.Adleman提出、用三個人名命名的算法。在使用該加密算法的系統中，對於每個用戶而言對應著三個很大的二進位整數M、e和d，一般為512位或1024位，數越大所加密的信息越難破解。這三個二進位整數之間有著特殊的關係，其中M和e是公開的，d是保密的，並由用戶保存，M是模數，e是加密密鑰，d是解密密鑰。當向某用戶發送信息C時，利用對應該用戶的加密密鑰e，對信息C加密再發向該用戶，這裡C為明文，E為密文，加密過程可表示為E＝CemodM；當用戶接到密文信息E後，用對應該用戶的解密密鑰d對其解密可恢復明文信息CC＝EdmodM。
可見採用RSA算法對信息加密和解密都必須進行大數模冪運算，眾所周知模冪運算可分解為多次模乘運算，設加解密涉及的大數為C、A、e，模為M，即C＝AemodM＝(A×A×…×A)modM模乘運算可採用蒙哥馬利模乘運算法硬體實現，其完成的計算記作Mont(A，A，M)。
若模M的二進位數的長度為n位，蒙哥馬利模乘就需要經過n+1輪迭代運算，設其完成的運算結果為P，則P＝Mont(A，A，M)＝A×A×2-(n+1)modM可知經過n+1輪蒙哥馬利模乘運算後，所得結果比模乘多一個因子2-(n+1)，由此需構造蒙哥馬利模乘運算TT＝Mont(P，PP，M)＝A×AmodM其中 PP＝22n+2modM如此完成了加解密所需的大數模冪運算。其中PP的運算即為採用蒙哥馬利模乘算法時的初始預計算。美國專利US 6,061,706公開了一種蒙哥馬利模乘硬體電路，在該電路中它的初始預計算PP＝22n+2modM由用戶完成，給用戶帶來了不便，而且由用戶採用軟體實現該運算，速度沒有硬體實現快。
在模乘計算完成後，其結果可能比模大，因此必須再做一次取模運算，實現結果的歸一化處理。
本發明的目的在於提出一種RSA加密算法中採用蒙哥馬利模乘法實現大數模冪、模乘運算時初始預計算和結果歸一化處理的實現電路及方法。
實現本發明目的的一種大數模冪運算的蒙哥馬利模乘法實現電路，由多級基本處理單元連接而成，模的二進位數長度為n，其初始預計算電路由n+1個預計算單元連接而成，處於預計算鏈最高位n的預計算單元包括觸發器D和全加器FA，低一位預計算單元的計算結果R[n-1]輸入觸發器D，經過一個時鐘後寫入，觸發器D的輸出和數值1以及低一位預計算單元的進位輸出Br[n-1]作為操作數輸入全加器FA，產生本級進位輸出Br[n]；處於預計算鏈的非最高位i(i等於0，1，…，n-1)的預計算單元包括觸發器D、全加器FA、反相器N，以及前後兩個多路器(101和102)，低一位預計算單元的計算結果R[i-1]和模乘結果PV[i]輸入前一級多路器(101)；模M的二進位數第i位的值M[i]經反相器N後和前一級多路器(101)的輸出以及低一位預計算單元的進位輸出Br[i-1]分別同時輸入全加器FA，全加器FA產生本級進位輸出Br[i]，前一級多路器(101)和全加器FA的輸出輸入後一級多路器(102)，後一級多路器(102)輸出預計算結果R[i]；上述預計算單元組成預計算鏈，低一位預計算單元的計算結果R[i]輸入上一位預計算單元的觸發器D，低一位預計算單元的進位輸出Br[i]輸入上一位預計算單元的全加器FA，最底位預計算單元的觸發器D的輸入為0、全加器FA的輸入為1，用於選擇預計算和模乘運算的前一級多路器(101)組的使能信號為En，用於信號輸出選擇的後一級多路器(102)組的使能信號Sel為根據進位產生的控制信號。
實現本發明目的的一種大數模冪運算的蒙哥馬利模乘法實現方法，在多級基本處理單元連接而成的鏈路中實現迭代運算，模的二進位數長度為n，其在初始預計算電路中實現的初始預計算包括以下步驟①計算2nmodM；②左移一位寫入寄存器，再做取模運算；③重複步驟②共n+2次。
本發明有以下優點將預計算和結果歸一化處理電路集成在晶片內，無需用戶輸入預計算數據，方便用戶，提高運算速度；預計算和結果歸一化處理採用同一電路，減少電路面積，降低設計複雜度，降低成本。
下面結合附圖對本發明作進一步詳細說明

圖1A是處於預計算鏈最高位的預計算單元電路示意圖；圖1B是非預計算鏈最高位的預計算單元電路示意圖；圖2是產生選擇信號Sel的電路示意圖3是預計算鏈電路結構示意圖；圖4是鏈長為4的預計算電路示意圖。
在預計算PP＝22n+2modM中指數2n+2是兩次蒙哥馬利模乘的迭代次數，將上式寫成如下形式PP＝(2n×2×…×2)modM＝(…((2nmodM)×2modM)…×2)modM其中…代表n次(×2modM)運算。
所以PP的運算過程可分解為1.計算2nmodM；2.左移一位寫入寄存器，再做取模運算；3.重複步驟2共n+2次。
因為二進位數2n長度為n+1位，且最高位為1，其它位為0；模M取為奇數，長度為n位，即M的最高位和最低位是1；則2M的長度是n+1位，且至少最高位和次低位兩位為1，所以有2M＞2n＞M則 2nmodM＝2n-M該二進位運算可以通過零與減數的補數相加得到0+M補其中 M補＝M+1將該結果左移一位即完成乘以2的運算，寫入寄存器後再求模輸出，即完成運算2n+1modM然後再左移一位寫入寄存器，接著再求模輸出，即運算2n+2modM…………這樣再經過n次運算後完成22n+2modM
圖1A和圖1B的兩種電路是預計算鏈中的兩種處理單元。圖1A所示的電路用於預計算鏈的最高位，圖中的D代表D觸發器，FA代表全加器，Br是全加器的進位輸出，R是處理單元的計算結果。該電路的運作過程是這樣的下一級的計算結果R[n-1]輸入D觸發器，經過一個時鐘後寫入D觸發器；D觸發器的輸出和數值1以及下一級全加器的進位輸出Br[n-1]作為操作數輸入全加器FA，Br[n]是本級產生的進位輸出，用於產生選擇預計算鏈輸出結果的控制信號。圖1B所示的電路用於預計算鏈的非最高位i位，其電路比圖1A多兩個多路器101和102，PV是模乘結果，M[i]是模M的二進位數第i位的值，前一級多路器101用於信號輸入選擇，選擇預計算和模乘運算；後一級多路器102用於信號輸出選擇，該多路器102的使能信號根據進位產生，若進位位為1，說明結果數據(在寄存器D中)大於模值M，這時輸出數據要減掉模M；若進位位為0，說明結果數據小於模值M，輸出數據可以直接輸出。圖1B的運作過程與圖1A相同。
圖2所示是一多路器，用於選擇計算結果。該多路器的使能是模長ML，ML的值是模的二進位數據長度減1，如模為1011，則ML為3。預計算鏈中各全加器的輸出進位Br[i]輸入多路器，多路器的輸出同Ctrl信號相或得到控制信號Sel，Ctrl信號來自運算核的控制電路，在第一次時鐘脈衝寫入時為1(即第一次左移一位時)，以後為0。
圖3是預計算鏈電路結構示意圖，由如圖1A和圖1B所示的兩種預計算單元組成。預計算鏈的長度根據模M的長度決定若模M的長度為n，則需要n+1個預計算單元，模M[i]經過一組反向器後，它的每一位分別輸向對應計算鏈單元全加器的一個操作數輸入端，在最高位輸入「1」；D觸發器組Di的輸出數據和模乘結果數據PV[i]共同輸入各多路器Si，多路器Sn-1…S1S0的選通信號En，選擇模乘結果PV[n-1]、PV[n-2]、……、PV[1]、PV
和最低位的「0」分別輸入相應全加器。多路器組Seln-1…Sel1Sel0的輸出分別輸入上一位預計算單元的D觸發器，這樣每次寫入D觸發器時，預計算結果值左移一位。在模乘運算完成後，信號En為高，模乘結果PV[n-1]、PV[n-2]、……、PV[1]、PV
經過多路器組Sn-1…S1S0輸到全加器，其結果小於2M，但可能大於M，若大於M要對模乘結果求模後輸出，若小於M則直接輸出，如此完成結果歸一化過程。
圖4是模乘為3位的預計算鏈電路示意圖，圖中最低位的預計算單元，因在右移過程中，最低位為0，所以D觸發器可以省掉。根據前面的推導過程，該預計算鏈有4個預計算單元，每一位的輸出連向上一位的D觸發器的輸入，數據PV[2]、PV[1]、PV
是模乘結果的輸出，模M以補數形式輸入，在全加器中完成與數據R[2]、R[1]、R
的減法運算。假設模M等於5，則n為3，即計算22×3+2mod5首先計算第一步(23mod5)×2將D觸發器清零，運算0+M補，這時要取全加器的輸出結果，控制信號Ctrl使Sel為1，經過一個時鐘後，預計算鏈的輸出結果分別左移一位並寫入D觸發器組D2D1D0。接下來計算(((23mod5)×2)mod5)×2這時Ctrl為0，不參與控制，信號Sel與Br[3]等價，計算mod5，再經過一個時鐘後，使結果左移一位寫入D觸發器組D2D1D0。如此反覆，3個時鐘後完成運算。
R＝22n+2modM在模乘運算結束後，其二進位結果的各位為PV[2]、PV[1]、PV
，該值可能大於M，且小於2M，這樣需要對該值取模，本電路的後處理功能就完成模乘結果的取模運算。當模乘結束後，輸入多路器使能信號EN為1，選通模乘結果PV[2]、PV[1]、PV
輸出並使PV＜M。
權利要求
1.一種RSA加密算法的實現電路，其大數模冪運算採用蒙哥馬利模乘法，由多級基本處理單元連接而成，模的二進位數長度為n，其特徵在於其初始預計算電路由n+1個預計算單元連接而成，處於預計算鏈最高位n的預計算單元包括觸發器D和全加器FA，低一位預計算單元的計算結果R[n-1]輸入觸發器D，經過一個時鐘後寫入，觸發器D的輸出和數值1以及低一位預計算單元的進位輸出Br[n-1]作為操作數輸入全加器FA，產生本級進位輸出Br[n]；處於預計算鏈的非最高位i(i等於0，1，…，n-1)的預計算單元包括觸發器D、全加器FA、反相器N，以及前後兩個多路器(101和102)，低一位預計算單元的計算結果R[i-1]和模乘結果PV[i]輸入前一級多路器(101)；模M的二進位數第i位的值M[i]經反相器N後和前一級多路器(101)的輸出以及低一位預計算單元的進位輸出Br[i-1]分別同時輸入全加器FA，全加器FA產生本級進位輸出Br[i]，前一級多路器(101)和全加器FA的輸出輸入後一級多路器(102)，後一級多路器(102)輸出預計算結果R[i]；所述預計算單元組成所述預計算鏈，低一位預計算單元的計算結果R[i]輸入上一位預計算單元的觸發器D，低一位預計算單元的進位輸出Br[i]輸入上一位預計算單元的全加器FA，最底位預計算單元的觸發器D的輸入為0、全加器FA的輸入為1，用於選擇模乘運算和結果歸一化的前一級多路器(101)組的使能信號為En，用於信號輸出選擇的後一級多路器(102)組的使能信號Sel為根據進位產生的控制信號。
2.根據權利要求1所述的RSA加密算法的實現電路，其特徵在於所述後一級多路器(102)組的使能信號Sel的產生電路為一多路器(103)，各預計算鏈模乘結果PV[n-1]、PV[n-2]、……、PV[1]、PV
和最低位的「0」輸入所述多路器(103)，該多路器的輸出同來自運算核控制電路的Ctrl信號相或產生控制信號Sel，所述Ctrl信號在第一次時鐘脈衝寫入時為1(即第一次左移一位時)，以後為0；所述多路器(103)的使能信號ML的值是模的二進位數據長度減1。
3.根據權利要求1所述的RSA加密算法的實現電路，其特徵在於所述預計算鏈的最低位預計算單元的觸發器D可以不要。
4.根據權利要求1所述的RSA加密算法的實現電路，其特徵在於所述預計算鏈可以在一個獨立的集成電路塊中實現，也可以與多級基本處理單元連接而成的鏈路集成在同一集成電路塊中。
5.一種RSA加密算法的實現方法，其大數模冪運算採用蒙哥馬利模乘法，在多級基本處理單元連接而成的鏈路中實現迭代運算，模的二進位數長度為n，其特徵在於其初始預計算在多級預計算單元連接而成的鏈路中實現，包括以下步驟①計算2nmodM；②左移一位寫入寄存器，再做取模運算；③重複步驟②共n+2次。
6.根據權利要求4所述的RSA加密算法的實現方法，其特徵在於其步驟①通過零與減數的補數相加實現。
7.根據權利要求4所述的RSA加密算法的實現方法，其特徵在於在模乘運算完成後，設置使能信號En為高，模乘結果PV[n-1]、PV[n-2]、……、PV[1]、PV
經過多路器組Sn-1…S1S0輸到全加器，若模乘結果大於M則對模乘結果求模後輸出，否則直接輸出。
全文摘要
一種RSA加密算法的實現電路及方法,模的二進位數長度為n,其初始預計算電路由n+1個預計算單元連接而成,預計算單元包括觸發器D、全加器FA、反相器N,以及前後兩個多路器,用於選擇預計算和結果歸一化的前一級多路器組的使能信號為En,在模乘運算完成後,信號En為高,完成結果歸一化過程。用於信號輸出選擇的後一級多路器組的使能信號Sel為根據進位產生的控制信號。本發明將預計算和結果歸一化處理電路集成在晶片內,方便用戶,提高了運算速度。
文檔編號G06F7/38GK1375764SQ0110765
公開日2002年10月23日 申請日期2001年3月19日 優先權日2001年3月19日
發明者周玉潔, 金松, 劉英廣 申請人:深圳市中興集成電路設計有限責任公司