[發明專利]一種實現AES算法中S盒和逆S盒替換的方法

有效

• 申請號: 201310261809.5
• 申請日: 2013-06-27
• 公開（公告）號: CN103391186A
• 公開（公告）日: 2013-11-13
• 發明（設計）人: 李樹國;覃曉草
• 申請（專利權）人: 清華大學
• 主分類號: H04L9/06
• 分類號: H04L9/06
• 代理公司: 西安智大知識產權代理事務所 61215
• 代理人: 賈玉健

技術領域

本發明屬于信息安全技術領域，特別涉及一種實現AES算法中S盒和逆S盒替換的方法。

背景技術

AES算法是一種對稱分組密碼算法，應用于金融、電子政務、電子商務及國民經濟的各個領域，目前已經研制了系列芯片、智能IC卡、智能密碼鑰匙、加密卡、加密機、加密U盤、硬盤以及正在研究的金融IC卡等安全產品。而AES算法中的S盒替換與逆S盒替換是該算法唯一的非線性變換，因此S盒替換與逆S盒替換是AES算法的核心部分，同時這也是提高AES算法性能的主要瓶頸。

現有的S盒替換與逆S盒替換普遍采用的是查表法實現。所謂查表法中的“表”指的是AES算法中的兩個盒子，分別用于加密時的S盒替換與解密時的逆S盒替換。當前，普遍的查表法不管是S盒替換還是逆S盒替換，都是根據輸入值通過AES算法標準規定的表格來查出對應的輸出值。這種查表法原理簡單，實現容易，但是這種方法實際上是一個大的256選一多路選擇器，其電路的延時較長，面積較大，是一種低效的實現方式。

發明內容

為了克服上述現有技術的缺點，本發明的目的在于提供一種實現AES算法中S盒和逆S盒替換的方法，減小了時延、面積和功耗。

為了實現上述目的，本發明采用的技術方案是：

一種實現AES算法中S盒和逆S盒替換的方法，包括如下步驟：

步驟一，根據AES算法標準中給出的S盒與逆S盒，寫出輸出變量的真值表，由于S盒與逆S盒都是8位輸出變量，可以得到16個真值表；

步驟二，將每個真值表都表示為一個最小項表達式，得到16個最小項表達式；

步驟三，對每個最小項表達式進行邏輯化簡得到化簡后的函數表達式；

步驟四，在化簡后得到的16個函數表達式中，將表達式改寫為“與非與非”即為“與或”的兩次取反的形式；

步驟五，將改寫后的16個函數表達式之間能夠公用的邏輯電路單元單獨提出來，使得這些函數表達式實現電路資源得以公用，上述公用單元提取后的表達式與提取前的表達式相比，公用單元提取后的表達式對應的電路面積變小，扇出變少，從而使得延時減小。

所述步驟三中邏輯化簡采用改進的Q-M化簡法實現，具體包括如下步驟：

第一步：將函數表示成最小項表達式；

第二步：找出函數的全部質蘊涵項；

第三步：找出必要質蘊涵項，輸出結果；

第四步：去除必要質蘊涵項以及各個必要質蘊涵項所對應的最小項后，得到一個新的表；

第五步：在新的表中找到包含最小項個數最多的那一個質蘊涵項，若是有多個質蘊涵項包含最小項個數最多，則任選其一，輸出這個質蘊涵項；

第六步：去除第五步輸出的這個質蘊涵項以及該質蘊涵項所對應的最小項后，得到一個新的表；

第七步：重復第五步和第六步，直到沒有能夠再合并的最小項為止，循環結束。

與現有技術相比，本發明的有益效果是：在優化Q-M化簡法基礎上，提出了一種實現AES算法中S盒替換和逆S盒替換的表達式方法，用C語言編程實現了改進的Q-M化簡法，借助于計算機來求得函數表達式的邏輯化簡結果，這種表達式方法相比于普遍使用的查表法，其延時減小了8.5%，面積減小了27.4%，功耗減小了17%。

附圖說明

圖1是按照本發明一種有效實現AES算法中S盒替換與逆S盒替換的電路結構圖。

具體實施方式

下面結合圖1和實施例詳細說明本發明的實施方式。

本發明利用改進的Q-M化簡法，求得AES算法中S盒替換和逆S盒替換的函數表達式的邏輯化簡結果，從而有效實現了AES算法中S盒替換和逆S盒替換。

具體包括如下步驟：

1）據AES算法標準中給出的S盒與逆S盒，寫出輸出變量的真值表，由于S盒與逆S盒都是8位輸出變量，可以得到16個真值表；

2）將每個真值表都表示為一個最小項表達式，得到16個最小項表達式；

3）采用改進的Q-M化簡法對每個最小項表達式進行邏輯化簡得到化簡后的函數表達式。

由于S盒與逆S盒的輸入變量有8個，通過手工進行邏輯化簡獲取S盒替換和逆S盒替換的表達式幾乎是做不到的，因此用C語言編程實現了改進的Q-M化簡法，借助于計算機來求得函數表達式的邏輯化簡結果。

4）在化簡后得到的16個函數表達式中，將表達式改寫為“與非與非”即為“與或”的兩次取反的形式而不是單純的“與或”的形式。這是基于“與非”門的延時要小于“與”門的延時的事實，本發明的實驗結果也驗證了這一點。