[發明專利]橢圓曲線標量乘的并行處理方法及系統

無效

• 申請號: 201110279971.0
• 申請日: 2011-09-20
• 公開（公告）號: CN102446088A
• 公開（公告）日: 2012-05-09
• 發明（設計）人: 鄔可可;李慧云;徐國卿
• 申請（專利權）人: 中國科學院深圳先進技術研究院
• 主分類號: G06F9/38
• 分類號: G06F9/38;G06F15/16
• 代理公司: 廣州華進聯合專利商標代理有限公司 44224
• 代理人: 吳平

【技術領域】

本發明涉及數據加密技術，特別是涉及一種橢圓曲線標量乘的并行處理方法及系統。

【背景技術】

隨著1980年代中期Miller和Koblitz分別獨立地提出了橢圓曲線密碼體制(elliptic?curve?cryptosystems，簡稱ECC)，相對于其它的公鑰密碼體制，橢圓曲線密碼只需要較短的私鑰即可達到較高的安全級別，因此近年來備受關注。

橢圓曲線密碼體制中，標量乘的計算將是最為關鍵的處理過程，通常標量乘可通過逐比特的二進制方法計算得到，即給定一個標量和橢圓曲線點，標量乘是由一系列的橢圓曲線點的點加和點倍操作完成，其運行的軌跡依賴于標量的二進制比特表達式。

然而，這一逐比特的標量乘計算方法并不能夠適應日益普及的并行計算系統，以優化標量乘的計算過程，因此，并行的標量乘計算被提出并應用于并行計算系統中，例如，Aoki、Lzu和Takagi介紹了基于SIMD處理器結構的高效并行點操作；Lzu提出了雙處理器架構的表達式；Aoki等介紹了基于2個或者3個處理器的并行處理過程，采用改進的雅可比坐標來開發了快速并行表達式；Longa和Miri的替換乘方法允許更高效的優選并行操作的開發，從而提出了能夠在3個或者4個處理器中執行的快速并行表達式，但是，上述并行的標量乘計算僅局限于指令級別的并行化，不能夠基于任務級別的進行并行計算，這將造成上述并行的標量乘計算只能在少量的處理器中進行，并不能夠適應較大規模的并行處理過程。

【發明內容】

基于此，有必要提供一種能適應大規模的并行處理過程的橢圓曲線標量乘的并行處理方法。

此外，還有必要提供一種能適應大規模的并行處理過程的橢圓曲線標量乘的并行處理系統。

一種橢圓曲線標量乘的并行處理方法，包括如下步驟：

將標量劃分成等長的子標量；

分布所述劃分得到的子標量至處理器中；

在所述處理器中對所述分布的子標量和橢圓曲線進行并行計算得到對應的子標量乘；

整合所述并行計算得到的子標量乘。

優選地，所述將標量劃分成等長的子標量的步驟為：

根據所述處理器的數量確定所述標量對應的遞歸次數；

按照所述遞歸次數對所述標量進行遞歸折半得到等長的子標量。

優選地，所述根據所述處理器的數量確定所述標量對應的遞歸次數的步驟為：

以2為底，以處理器的數量為真數計算得到遞歸次數。

優選地，所述以2為底，以處理器的數量為真數計算得到遞歸次數的步驟之前還包括：

獲取標量的比特長度；

根據所述標量的比特長度計算得到所述標量對應的最優遞歸次數，并由所述最優遞歸次數計算得到處理器的數量閾值；

判斷所述處理器的數量是否小于所述數量閾值，若否，則將所述遞歸次數設為最優遞歸次數，若是，則

進入以2為底，以處理器的數量為真數計算得到遞歸次數的步驟。

優選地，所述整合所述并行計算得到的子標量乘的步驟為對所述子標量乘進行兩兩遞歸點加計算。

一種橢圓曲線標量乘的并行處理系統，包括：

劃分裝置，用于將標量劃分成等長的子標量；

分布裝置，用于分布所述劃分得到的子標量至處理器中；

處理器，用于對所述分布的子標量和橢圓曲線進行并行計算得到對應的子標量乘；

處理器還用于整合所述并行計算得到的子標量乘。

優選地，所述劃分裝置包括：

次數確定模塊，用于根據所述處理器的數量確定所述標量對應的遞歸次數；

折半模塊，用于按照所述遞歸次數對所述標量進行遞歸折半得到等長的子標量。

優選地，所述次數確定模塊還用于以2為底，以處理器的數量為真數計算得到遞歸次數。

優選地，所述次數確定模塊包括：

長度獲取單元，用于獲取標量的比特長度；

運算單元，用于根據所述標量的比特長度計算得到所述標量對應的最優遞歸次數，并由所述最優遞歸次數計算得到處理器的數量閾值；

判斷單元，用于判斷所述處理器的數量是否小于所述數量閾值，若否，則將所述遞歸次數設為最優遞歸次數，若是，則通知運算單元；

所述運算單元還用于以2為底，以處理器的數量為真數計算得到遞歸次數。

優選地，所述處理器還用于對所述子標量乘進行兩兩遞歸點加計算。