[發明專利]一種快速大數模乘運算電路

無效

• 申請號: 01107655.0
• 申請日: 2001-03-19
• 公開（公告）號: CN1375765A
• 公開（公告）日: 2002-10-23
• 發明（設計）人: 周玉潔;金松;劉英廣
• 申請（專利權）人: 深圳市中興集成電路設計有限責任公司
• 主分類號: G06F7/38
• 分類號: G06F7/38
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明涉及計算方法的硬件實現領域，尤其涉及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＝C^emodM；當用戶接到密文信息E后，用對應該用戶的解密密鑰d對其解密可恢復明文信息C：C＝E^dmodM。

可見，加密、解密過程涉及大數的模冪運算，眾所周知模冪運算可分解為多次模乘運算，大數模乘可以由蒙哥馬利模乘來實現，所以蒙哥馬利模乘是RSA加密算法的核心計算，這種運算很復雜，用軟件實現速度慢，難于滿足應用要求，采用硬件方法實現RSA加密運算可大大降低運算時間。美國專利US?6,061,706提出了一種蒙哥馬利模乘運算硬件電路，由基本處理單元連接而成，在時鐘信號控制下進行迭代運算，但該電路完成模長為n位的蒙哥馬利模乘運算需要2n+11個時鐘周期，運算時間較長。

本發明的目的在于提出一種新的運算時間較短的可用集成電路實現的快速大數蒙哥馬利模乘運算電路。

設所需計算模的二進制數長度為n位，本發明的蒙哥馬利模乘法實現電路，由PE0，PE1，…，PEn+1共n+2個基本處理單元(PE)連接而成，在最高位基本處理單元之后還連接一個觸發器D100，在時鐘信號控制下進行迭代運算。

處于所述蒙哥馬利模乘電路中間位的基本處理單元PEi包括加法器ADDi、五個觸發器D和兩個與門，這里i＝1，2，…n；操作數A經過觸發器D?105后輸向高一位基本處理單元，同時又跟操作數B[i]相與后輸入加法器ADDi；中間參數Q經過觸發器D106后輸向高位PEi+1，同時又跟模數M[i]相與后輸入加法器ADDi；兩位進位信號C1[i]、C0[i]和運算結果P[i]，分別經過觸發器D104、108、107后同時輸向加法器ADDi；加法器ADDi是兩位加法器，進位中的高位C1[i]輸向加法器的高位；輸入數據經加法器運算后，得到一位結果數據P[i-1]和兩位進位數據C0[i+1]、C1[i+1]。

處于所述模乘電路最低位的基本處理單元PE0包括加法器ADD0、三個觸發器D、三個與門和一個異或單元，操作數A和操作數B[0]相與后再和運算結果P[0]經異或單元運算后產生中間參數Q，中間參數Q輸入觸發器D102，經過觸發器D102后一路輸向高位基本處理單元PE1，另一路再與模數M[0]相與后輸入加法器ADD0；同時操作數A經過觸發器D101后一路輸向高位PE1，一路跟操作數B[0]相與后輸入加法器ADD0；運算結果P[0]經過觸發器D103后輸向加法器ADD0；加法器ADD0將三個輸入信號相加，產生進位信號C[1]輸向高位基本處理單元PE1。

處于所述模乘電路最高位的基本處理單元PEn+1包括加法器ADDn+1和三個觸發器D，兩位進位信號C1[n+1]、C0[n+1]和運算結果P[n+1]，分別經過觸發器D109、110、111后同時輸向加法器ADDn+1，加法器ADDn+1將三個輸入信號相加，輸出一位進位信號Co[n+2]和運算結果P[n]。