[發明專利]一種實現伽羅瓦域乘法的裝置及其應用方法

有效

• 申請號: 201410781737.1
• 申請日: 2014-12-16
• 公開（公告）號: CN104407837B
• 公開（公告）日: 2017-09-19
• 發明（設計）人: 王媛;馬強;胡孔陽;劉小明;龔曉華;萬曉佳
• 申請（專利權）人: 中國電子科技集團公司第三十八研究所
• 主分類號: G06F7/52
• 分類號: G06F7/52
• 代理公司: 合肥市浩智運專利代理事務所(普通合伙)34124
• 代理人: 方榮肖

技術領域

本發明屬數字信號處理器技術領域，涉及一種實現伽羅瓦域乘法的裝置及其應用方法，其是對伽羅瓦域乘法的硬件實現。

背景技術

有限域包含有限個元素，且目前有限域乘法被廣泛應用于密碼學領域，許多加密認證算法都利用了有限域乘法。F域為一種至少包含兩個元素的有限域，在F域上有加法和乘法兩種算法操作被定義，且加法和乘法操作均為針對二元的算法操作。伽羅華域(GFQ)為最小的有限域，只包含0和1兩個元素，同時加法和乘法都只進行模2操作，因此加法與異或邏輯等效，可以用一個異或門來實現，而乘法等效于與邏輯，可以用一個與門實現。

有限域可以用非多項式P(x)＝x^m+P_m-1x^m-1+…+P₁+P₀來定義，令α∈GF(2^m)是P(x)的根，即P(α)＝0則稱{1αα²…α^m-1}為多項式的基或標準基，GF(2^m)中每個元素都可以根據多項式來表示，比如對于A＝a_m-1a_m-2…a₁a₀可以表示為其中a_i即為基下的坐標，假設α＝[1α…α^m-1]^T，a＝[a₀ a₁…a_m-1]^T，則A＝α^Ta。

當加羅華域運算擴展應用到很多位時，計算就非常難以實現，同時硬件實現也會變得不太容易。傳統加羅華域乘法的硬件多采用通用處理器實現，因此高數據量的計算效果主要受限于內部結構，這導致了計算性能無法大幅度提高。目前，伽羅華域的研究成果主要針對于算法方面，尤其是關于通用多項式算法的各種優化。然而，至今的算法優化方式實現起來的復雜度比較大，且優化結果也很難達到理想效果。

發明內容

本發明主要針對硬件的處理速度、硬件的實現簡易度以及32位伽羅瓦域乘法算法的易于實現度，提出一種實現伽羅瓦域乘法的裝置及其應用方法，其采用64級32位選擇器組成的易于實現、結構簡單的伽羅瓦域乘法的硬件實現。

本發明是通過以下技術方案實現的：一種實現伽羅瓦域乘法的裝置，其包括：

選擇前段模塊，其包括2個32位第一選擇器、1個第一乘法器和1個第一異或電路；其中一個第一選擇器根據被乘數rn的31位，選擇乘數rm或者0，得到中間結果pp0；該第一乘法器對中間結果pp0進行乘2操作，得到中間結果pp00；該第一異或電路對中間結果pp00和伽羅瓦系數進行異或操作，得到中間結果pp01；另一個第一選擇器根據中間結果pp0的31位選擇中間結果pp00或者中間結果pp01，得到中間結果pp1作為該選擇前段模塊的輸出；

選擇組件模塊，其包括30個選擇組件，每個選擇組件的電路完全相同且前后串接，前一個選擇組件輸出作為后一個選擇組件的輸入，每個選擇組件包括2個32位第二選擇器、1個第二乘法器和2個第二異或電路，在同一個選擇組件中：其中一個第二異或電路對前一級的中間結果ppi和乘數rm進行異或操作，得到中間結果ppi0，其中，i＝1，3，2n-1，…，61，n為正整數，其中一個第二選擇器根據選擇信號，選擇中間結果ppi或者中間結果ppi0，得到中間結果pp(i+1)，該第二乘法器對中間結果pp(i+1)進行乘2操作，得到中間結果pp(i+1)0，另一個第二異或電路對中間結果pp(i+1)0和伽羅瓦系數進行異或操作，得到中間結果pp(i+1)1，另一個第二選擇器根據中間結果pp(i+1)的31位選擇中間結果pp(i+1)0或者中間結果pp(i+1)1，得到中間結果pp(i+2)作為相應選擇組件的輸出；其中，該選擇組件模塊的輸入為中間結果pp1，該選擇組件模塊的輸出為中間結果pp61，其中，第一個選擇組件的第一個第二選擇器的選擇信號為被乘數rn的30位，30個選擇組件的第一個第二選擇器的選擇信號不同；

選擇后段模塊，其包括1個32位第三選擇器和1個第三異或電路，該第三異或電路對該選擇組件模塊的輸出即中間結果pp61和乘數rm進行異或操作，得到中間結果pp610，該第三選擇器根據被乘數rn的0位，選擇中間結果pp61或者中間結果pp610，得到伽羅瓦域乘的輸出rs。

本發明還提供上述實現伽羅瓦域乘法的裝置的應用方法，該應用方法包括以下步驟：

一、選擇前段：