在ecc中實現位數自適應模乘運算的方法及模乘運算器的製造方法
2023-06-11 15:00:01 1
在ecc中實現位數自適應模乘運算的方法及模乘運算器的製造方法
【專利摘要】本發明公開了一種在ECC中實現位數自適應模乘運算的方法，包括：基於零位檢測模塊獲取輸入數據的位數；根據輸入數據的位數選擇與輸入數據相接近的模乘運算檔位；基於模乘運算檔位所關聯的64位KOA並行乘法器對所述輸入數據進行運算。本發明還公開了一種ECC模乘運算器，包括：零位檢測模塊，用於獲取輸入數據的位數；模乘運算檔位選擇模塊，用於根據輸入數據的位數選擇與輸入數據相接近的模乘運算檔位；模乘運算模塊，用於基於模乘運算檔位所關聯的64位KOA並行乘法器對所述輸入數據進行運算。通過本發明實施例，在原始的KOA算法進行改進，使其自動的根據輸入乘數的位數進行計算調整，以達到最優的計算效果。
【專利說明】在ECC中實現位數自適應模乘運算的方法及模乘運算器
【技術領域】
[0001]本發明涉及橢圓曲線加密算法(ECC)【技術領域】，具體涉及一種在ECC中實現位數自適應模乘運算的方法及模乘運算器。
【背景技術】
[0002]ECC加密算法是單位比特安全性能最高的非對稱加密算法，由於硬體實現ECC算法速度比軟體快很多，很多智慧卡晶片、閱讀器晶片及安全晶片中，均有ECC算法的實現電路。隨著該算法的應用廣泛，ECC算法實現的位數需要也不一樣，不同標籤晶片在ECC加密算法位數選擇也不盡相同，為了保證安全模塊的廣泛使用性，在同一個安全模塊內實現多位數的ECC加密算法。但是為了保證ECC加密算法的高速性，在基本模塊的實現上需要使關鍵模塊具有長度自適應性。
[0003]ECC加密算法中最關鍵的基本的運算為模乘運算，其決定了 ECC加密算法具體實現時的運算速度。對於橢圓曲線中模乘算法也有三種，通常實現模乘算法主要直接相乘求模算法、KOA模乘算法和Montgomery模乘算法三種以及相關算法的改進。對於直接相乘求模的算法來說，雖然實現和算法都比較直接簡單，但其在實現上佔用的時間和面積也是最多的。而Montgomery模乘算法雖然高效，但是當我們只需要計算一次模乘時，需要的額外操作較多，比較適合RSA算法的模冪操作，ECC的標量乘算法並不一直使用模乘計算，中間還會用到其它的操作，並且每一個循環周期內都需要各種操作的組合，接下來要進行其它操作時，因此該算法在模乘算法上並不能取得高效的性能。
[0004]通常採用KOA乘法器來實現模乘算法。乘法器按運算周期來分，主要有串行乘法器、全並行乘法器和串並乘法器三種。對於串行乘法器來說，它通過不斷的移位運算進行實現，該算法是以犧牲運算速度來獲取較小的實現面積，其實現面積為0(m)其實現速度也為O(Hl)。第二種是全並行乘法器，該乘法器是在先分別求出部分積然後再對每一部分的部分積進行累加的操作，該算法是以犧牲面積來獲取最快的運算速度，其實現面積為0(m2)，而運算速度則為0(1)。第三種方法是串並混合乘法器，是以上兩種方法的折中，其實就是以串行乘法器的思想調用底層並行乘法器加以實現。其面積及計算速度都介於前面兩者中間。
[0005]KOA乘法器從理論上講，是通過多次的分治處理可以將基礎乘法器的數目減至到
一位，這樣算法的複雜度可以降低至。但隨著分治算法的進行，輔助操作隨之增力口，故一般分治的次數不會太多，因此必須根據實際需要進行合理設計。對於乘法器來說，串行乘法器和並行乘法器都不能在面積和速度上有很好的折合，因此目前通常採用串並乘法器來實現模乘器。但是位數越大的乘法器，消耗的時間越長。對於進行乘法操作的位數不是固定的情況，當位數較低時，傳統的方法是採用高位補O法，補齊為最高位時再輸入乘法器進行計算。但這無疑產生了極大的時間浪費，特別是位數低於最高位一半時，乘法器花了一半的時間在計算無用的數。
【發明內容】
[0006]針對以上幾種實現算法的不足，本發明提出了在ECC中實現位數自適應模乘運算的方法及ECC模乘運算器，在原始的KOA算法進行改進，使其自動的根據輸入乘數的位數進行計算調整，以達到最優的計算效果。
[0007]本發明提供了一種在ECC中實現位數自適應模乘運算的方法，所述方法包括如下步驟:
[0008]基於零位檢測模塊獲取輸入數據的位數；
[0009]根據輸入數據的位數選擇與輸入數據相接近的模乘運算檔位；
[0010]基於模乘運算檔位所關聯的64位KOA並行乘法器對所述輸入數據進行運算。
[0011 ] 所述64位KOA並行乘法器包括至少兩個或者以上串並在一起的64位KOA乘法器。
[0012]所述64位KOA乘法器由9個16位乘法器構成。
[0013]所述64位KOA並行乘法器至少滿足512位乘法運算。
[0014]相應的，本發明實施例還提供了一種ECC模乘運算器，包括:
[0015]零位檢測模塊，用於獲取輸入數據的位數；
[0016]模乘運算檔位選擇模塊，用於根據輸入數據的位數選擇與輸入數據相接近的模乘運算檔位；
[0017]模乘運算模塊，用於基於模乘運算檔位所關聯的64位KOA並行乘法器對所述輸入數據進行運算。
[0018]所述64位KOA並行乘法器包括至少兩個或者以上串並在一起的64位KOA乘法器。
[0019]所述64位KOA乘法器由9個16位乘法器構成。
[0020]所述64位KOA並行乘法器至少滿足512位乘法運算。
[0021]本發明可以實現512位數以下的長度自適應KOA模乘算法，該算法以全並行的結構設計了 64位的基礎乘法器模塊，根據硬體特點以及常見的橢圓曲線位數值，也可以設計不同的模乘運算檔位，比如192、256、320、384、448、512。乘法器對輸入的數據進行位數判斷，自適應的選擇這六檔中最適當的長度進行計算。通過這種自適應的方法，在各種位數的情況下，尤其是計算較低位數時，顯著的提高了乘法器的運算速度。
[0022]本發明的在硬體上，利用串並混合乘法器來實現，利用KOA算法原理，把乘法運算的位數進行分治，採用全並行的64位基礎乘法器模塊來實現。而對於這64位的基礎乘法器模塊，採用KOA的方法，將64位的乘法器由9個16位的乘法器構成，另外加上若干加法電路，就可以利用16位的乘法器來實現64位並行乘法器。為了滿足模乘算法最高位512位的要求，實現的模乘器必須滿足512位乘法運算，對於最高位情況，利用64位的基礎乘法器，通過串行的方式來實現最高為512的乘法器。
[0023]為了滿足模乘算法的長度自適應，根據常見的橢圓曲線加密算法ECC的位數值，把不同位數的模乘算法劃分為6個檔，通過一個狀態機來控制整個運算的流程，同時利用一個組合邏輯電路和一個寄存器來標識輸入數據的位數，根據輸入位數，利用組合邏輯電路和寄存器的狀態來決定調用哪幾個64位乘法器，當輸入的位數較少時，狀態機根據寄存器表示的狀態，跳過後面所有狀態的操作，輸出運算結果。該發明雖然在犧牲掉一小部分組合邏輯電路的面積，但能在長度自適應的同時快速的實現橢圓曲線模乘算法。
【專利附圖】
【附圖說明】[0024]為了更清楚地說明本發明實施例或現有技術中的技術方案，下面將對實施例或現有技術描述中所需要使用的附圖作簡單地介紹，顯而易見地，下面描述中的附圖僅僅是本發明的一些實施例，對於本領域普通技術人員來講，在不付出創造性勞動的前提下，還可以根據這些附圖獲得其它的附圖。
[0025]圖1是本發明實施例中的在ECC中實現位數自適應模乘運算的方法流程圖；
[0026]圖2是本發明實施例中的ECC模乘運算器結構示意圖；
[0027]圖3是本發明實施例中的ECC模乘運算器功能原理結構示意圖；
[0028]圖4是本發明實施例中的512位KOA乘法器結構原理示意圖；
[0029]圖5是本發明實施例中的ECC模乘運算中程序運行流程圖。
【具體實施方式】
[0030]下面將結合本發明實施例中的附圖，對本發明實施例中的技術方案進行清楚、完整地描述，顯然，所描述的實施例僅僅是本發明一部分實施例，而不是全部的實施例。基於本發明中的實施例，本領域普通技術人員在沒有作出創造性勞動前提下所獲得的所有其它實施例，都屬於本發明保護的範圍。
[0031]圖1示出了在ECC中實現位數自適應模乘運算的方法流程圖，包括如下步驟:
[0032]S101、基於零位檢測模塊獲取輸入數據的位數；
[0033]S102、根據輸入數據的位數選擇與輸入數據相接近的模乘運算檔位；
[0034]S103、基於模乘運算檔位所關聯的64位KOA並行乘法器對所述輸入數據進行運
笪
[0035]這裡的64位KOA並行乘法器包括至少兩個或者以上串並在一起的64位KOA乘法器。64位KOA乘法器由9個16位乘法器構成。該64位KOA並行乘法器至少滿足512位乘
法運算。
[0036]相應的，圖2還示出了本發明實施例中的ECC模乘運算器結構示意圖，包括:
[0037]零位檢測模塊，用於獲取輸入數據的位數；
[0038]模乘運算檔位選擇模塊，用於根據輸入數據的位數選擇與輸入數據相接近的模乘運算檔位；
[0039]模乘運算模塊，用於基於模乘運算檔位所關聯的64位KOA並行乘法器對所述輸入數據進行運算。
[0040]需要說明的是，該64位KOA並行乘法器包括至少兩個或者以上串並在一起的64位KOA乘法器。該64位KOA乘法器由9個16位乘法器構成。該64位KOA並行乘法器至少滿足512位乘法運算。
[0041]本發明可以實現512位數以下的長度自適應KOA模乘算法，該算法以全並行的結構設計了 64位的基礎乘法器模塊，根據硬體特點以及常見的橢圓曲線位數值，也可以設計不同的模乘運算檔位，比如192、256、320、384、448、512。乘法器對輸入的數據進行位數判斷，自適應的選擇這六檔中最適當的長度進行計算。通過這種自適應的方法，在各種位數的情況下，尤其是計算較低位數時，顯著的提高了乘法器的運算速度。當然根據根據這種串並原理，其可以滿足不同位數的長度適應性KOA模乘運算，也不限於512位數的運算。
[0042]本發明的在硬體上，利用串並混合乘法器來實現，利用KOA算法原理，把乘法運算的位數進行分治，採用全並行的64位基礎乘法器模塊來實現。而對於這64位的基礎乘法器模塊，採用KOA的方法，將64位的乘法器由9個16位的乘法器構成，另外加上若干加法電路，就可以利用16位的乘法器來實現64位並行乘法器。為了滿足模乘算法最高位512位的要求，實現的模乘器必須滿足512位乘法運算，對於最高位情況，利用64位的基礎乘法器，通過串行的方式來實現最高為512的乘法器。
[0043]為了滿足模乘算法的長度自適應，根據常見的橢圓曲線加密算法ECC的位數值，把不同位數的模乘算法劃分為6個檔，通過一個狀態機來控制整個運算的流程，同時利用一個組合邏輯電路和一個寄存器來標識輸入數據的位數，根據輸入位數，利用組合邏輯電路和寄存器的狀態來決定調用哪幾個64位乘法器，當輸入的位數較少時，狀態機根據寄存器表示的狀態，跳過後面所有狀態的操作，輸出運算結果。該發明雖然在犧牲掉一小部分組合邏輯電路的面積，但能在長度自適應的同時快速的實現橢圓曲線模乘算法。
[0044]相應的，圖3示出了本發明實施例中的ECC模乘運算器功能原理結構示意圖，主要包括一個控制狀態機、I個寄存器組、2個零位檢測模塊以及乘法位數選擇模塊、數據選擇模塊、64位KOA並行乘法器模塊。本發明主要利用狀態機來控制整個算法的計算流程，通過零位檢測模塊來判斷輸入數據的位數，根據輸入數據位數，利用乘法位數選擇模塊來選擇與輸入數據位數相接近的檔，並和數據選擇模塊共同利用控制狀態機來控制當前模乘算法的執行，合理的跳出不需要執行的算法狀態，通過寄存器和64位KOA並行乘法器暫存運算結果和計算。當運算結束後通過接口輸出運算結果。
[0045]具體來說，零位檢測器來判斷輸入位數，通過乘法位數選擇模塊和數據選擇模塊進行模乘算法運算的檔的選擇，根據檔的選擇，通過狀態機調用64位KOA並行乘法器模塊串行實現模乘算法，在位數不固定的情況下，每次都能合理選擇串行乘法的位數，跳出後面無須執行的狀態，實現長度自適應的快速模乘算法。
[0046]圖4示出了本發明實施例中的512位KOA乘法器結構原理圖，該64位KOA乘法器由9個16位乘法器構成。該64位KOA並行乘法器至少滿足512位乘法運算。利用串並混合乘法器來實現，利用KOA算法原理，把乘法運算的位數進行分治，採用全並行的64位基礎乘法器模塊來實現。而對於這64位的基礎乘法器模塊，採用KOA的方法，將64位的乘法器由9個16位的乘法器構成，另外加上若干加法電路，就可以利用16位的乘法器來實現64位並行乘法器。為了滿足模乘算法最高位512位的要求，實現的模乘器必須滿足512位乘法運算，對於最高位情況，利用64位的基礎乘法器，通過串行的方式來實現最高為512的乘法器。
[0047]在乘法器具體的實現過程中，定義wire類型的數組isZero[0..4]，每一位反映寬度為64位的兩個乘數的輸入的數據段是否全為0，例如isZero[4]表示最高64位，由組合邏輯電路確定該數組的值。用wire類型的數組isSkip [0..4]表示寬度為64位的兩個乘數部分計算可否跳過。則有，當isSkip[i+l]為I且isZero[i]為I時，isSkip[i]為I。此處組合邏輯電路大約佔整個乘法器面積的1/20，不會太影響乘法器的面積。完成整個乘法器的計算需要一個小狀態機，用來控制數據流程。在設計中，我們將狀態機的計算順序加以優化，使得狀態機可以根據isSkip的值正確的跳過一些狀態操作。例如，若isZero[0..4]=01111，也就是說，輸入的兩個乘數最高256位都為0，192-256位不全為0，isSkip [0..4]=01111當前乘法器最佳長度為256位。狀態機經過多次狀態轉換後，會根據isSkip的值，跳過後面所有狀態的操作，輸出運算結果。其狀態流程圖如圖5所示。
[0048]本領域普通技術人員可以理解上述實施例的各種方法中的全部或部分步驟是可以通過程序來指令相關的硬體來完成，該程序可以存儲於一計算機可讀存儲介質中，存儲介質可以包括:只讀存儲器(ROM，Read Only Memory)、隨機存取存儲器(RAM，RandomAccess Memory)、磁碟或光碟等。
[0049]以上對本發明實施例所提供的在ECC中實現位數自適應模乘運算的方法及模乘運算器進行了詳細介紹，本文中應用了具體個例對本發明的原理及實施方式進行了闡述，以上實施例的說明只是用於幫助理解本發明的方法及其核心思想；同時，對於本領域的一般技術人員，依據本發明的思想，在【具體實施方式】及應用範圍上均會有改變之處，綜上所述，本說明書內容不應理解為對本發明的限制。
【權利要求】
1.一種在ECC中實現位數自適應模乘運算的方法，其特徵在於，所述方法包括如下步驟: 基於零位檢測模塊獲取輸入數據的位數； 根據輸入數據的位數選擇與輸入數據相接近的模乘運算檔位； 基於模乘運算檔位所關聯的64位KOA並行乘法器對所述輸入數據進行運算。
2.如權利要求1所述的在ECC中實現位數自適應模乘運算的方法，其特徵在於，所述64位KOA並行乘法器包括至少兩個或者以上串並在一起的64位KOA乘法器。
3.如權利要求2所述的在ECC中實現位數自適應模乘運算的方法，其特徵在於，所述64位KOA乘法器由9個16位乘法器構成。
4.如權利要求3所述的ECC中實現位數自適應模乘運算的方法，其特徵在於，所述64位KOA並行乘法器至少滿足512位乘法運算。
5.一種ECC模乘運算器，其特徵在於，包括: 零位檢測模塊，用於獲取輸入數據的位數； 模乘運算檔位選擇模塊，用於根據輸入數據的位數選擇與輸入數據相接近的模乘運算檔位； 模乘運算模塊，用於基於模乘運算檔位所關聯的64位KOA並行乘法器對所述輸入數據進行運算。
6.如權利要求5所述的ECC模乘運算器，其特徵在於，所述64位KOA並行乘法器包括至少兩個或者以上串並在一起的64位KOA乘法器。
7.如權利要求6所述的ECC模乘運算器，其特徵在於，所述64位KOA乘法器由9個16位乘法器構成。
8.如權利要求7所述的ECC模乘運算器，其特徵在於，所述64位KOA並行乘法器至少滿足512位乘法運算。
【文檔編號】G06F7/72GK103970504SQ201410191201
【公開日】2014年8月6日 申請日期:2014年5月7日 優先權日:2014年5月7日
【發明者】胡建國, 黃晴晴, 李仕仁, 譚宇泉, 白小楠 申請人:廣東順德中山大學卡內基梅隆大學國際聯合研究院, 中山大學, 胡建國