用C 語言描述AES256 加密算法
用C 語言描述AES256 加密算法,然后在硬件中加速性能。
高級加密標(biāo)準(zhǔn) (AES) 已經(jīng)成為很多應(yīng)用(諸如嵌入式系統(tǒng)中的應(yīng)用等)中日漸流行的密碼規(guī)范。自從 2002 年美國國家標(biāo)準(zhǔn)技術(shù)研究所 (NIST) 將此規(guī)范選為標(biāo)準(zhǔn)規(guī)范以來,處理器、微控制器、FPGA和 SoC 應(yīng)用的開發(fā)人員就開始利用 AES 來保護(hù)輸入、輸出及保存在系統(tǒng)中的數(shù)據(jù)。我們可在更高抽象層上非常高效地描述算法,就像用于傳統(tǒng)軟件開發(fā)中那樣;但由于涉及到的操作,該算法在 FPGA中實現(xiàn)起來最為高效。開發(fā)人員甚至可在布線中“免費”獲得一些操作。
本文引用地址:http://www.ex-cimer.com/article/201808/385496.htm基于這些原因,AES 是個絕佳的例子,即開發(fā)人員可利用 C 語言描述算法,然后在硬件中加速實現(xiàn),從而受益于賽靈思 SDSoC ? 開發(fā)環(huán)境。本文中我們就是要這樣做,首先熟悉一下 AES 算法,然后在賽靈思 Zynq?-7000 All Programmable SoC 的處理系統(tǒng) (PS) 上實現(xiàn) AES256(256 位秘鑰長度)以建立軟件性能基準(zhǔn),然后再在片上可編程邏輯 (PL)中進(jìn)行加速。為了完全了解可獲得的優(yōu)勢,我們將在 SDSoC 環(huán)境所支持的全部三個操作系統(tǒng)中執(zhí)行這幾個步驟,三個操作系統(tǒng)為:Linux、FreeRTOS 和裸機(jī)。
算法
AES 屬于對稱塊密碼,可采用 128、192 和 256位不同的秘鑰長度。秘鑰長度決定加密或解密數(shù)據(jù)所需的處理步驟數(shù)。顧名思義,塊密碼算法采用的是數(shù)據(jù)塊。AES 算法一次處理 16 字節(jié)的固定模塊。因此,如果我們密碼內(nèi)容少于 16 字節(jié),就必須將未使用的字節(jié)進(jìn)行填充。
由于 AES 是對稱密碼,信息加密和解密都采用相同的做法和秘鑰。相反,非對稱算法(例如RSA)則使用不同秘鑰進(jìn)行數(shù)據(jù)加密和解密。
AES 算法中四個階段中每個階段都代表一個狀態(tài)。四個 AES 階段的組合稱為一個循環(huán)。所需循環(huán)的數(shù)量取決于秘鑰長度。
很簡單,AES 狀態(tài)起始于我們要加密的 16 個字節(jié)。每個新步驟都會對狀態(tài)進(jìn)行更新。處理狀態(tài)之前,我們需要將輸入字節(jié)串變?yōu)槌跏紶顟B(tài),即 4 x 4矩陣(圖 1)。
圖 1 — 16 字節(jié)的初始狀態(tài)轉(zhuǎn)換為 4 x 4 矩陣
現(xiàn)在,我們將最初的 16 個字節(jié)重新編排為 4 x4 矩陣形式的初始狀態(tài),便可研究每個步驟如何操縱它的輸入狀態(tài)。
輪密鑰加(AddRoundKey) : 這是唯一使用加密秘鑰的步驟。我們已經(jīng)注意到,所需的加密算法循環(huán)的數(shù)量取決于秘鑰長度(128、192 或 256 位)。必須對加密秘鑰進(jìn)行秘鑰擴(kuò)展,以確保在每個循環(huán)中不會重新使用秘鑰中的字節(jié)。果然,對于不同的秘鑰長度而言擴(kuò)展秘鑰長度并不相同。擴(kuò)展秘鑰長度為:
擴(kuò)展秘鑰長度(字節(jié))= 16 *(循環(huán) + 1)
這個步驟中的操作很簡單。輸入狀態(tài)字節(jié)與擴(kuò)展秘鑰的 16 個字節(jié)進(jìn)行異或運算。每個循環(huán)使用擴(kuò)展秘鑰的不同部分;循環(huán) 0 使用字節(jié) 0 至 15,循環(huán)1 使用字節(jié) 16 至 31,以此類推。對于每個循環(huán),狀態(tài)的字節(jié) 1 與擴(kuò)展秘鑰的最低有效字節(jié)進(jìn)行異或運算,字節(jié) 2 與“最低有效字節(jié)+1”進(jìn)行異或運算,以此類推。
字節(jié)替換 (SubBytes) : 該步驟利用字節(jié)替換將狀態(tài)值用另一個值替換出去。替換盒中的值是預(yù)先設(shè)定的,而且輸入位于輸出位之間的關(guān)聯(lián)較小。替換盒 (S-box) 是一個 16 x 16 矩陣。我們使用被替代字節(jié)的高四位和低四位作為替代表格中的索引。例如,使用圖 2 中的 S-box 加密,如果第一個初始狀態(tài)字節(jié)為 0 x 69,那么用替代值 0 x F9 代替。狀態(tài)字節(jié)的高四位選擇替代表格的行; 低四位選擇列。注意在圖 2 中,加密和解密使用不同的替換盒,而且盒中內(nèi)容不同。
圖 2 — AES S-box 內(nèi)容
行位移變換 (ShiftRows) :該步驟對每行執(zhí)行循環(huán)字節(jié)移位,以重新排列輸入狀態(tài)矩陣。 我們將每行右旋不同個因數(shù)(圖 3)。第 1 行不變。將第 2 行移動 1 個字節(jié),第 3 行移動 2 個字節(jié),第 4 行移動3 個字節(jié)。解密時執(zhí)行相同操作,但向左旋轉(zhuǎn)而非向右。
圖 3 — 行位移變換 (ShiftRows) 操作
列混合變換 (MixColumns) :這是循環(huán)中最復(fù)雜的步驟,需要進(jìn)行 16 次乘法和 12 次異或運算。逐列對輸入狀態(tài)矩陣進(jìn)行此操作,將輸入狀態(tài)矩陣與固定矩陣相乘以獲得新的狀態(tài)列(圖 4)。列中的每項與矩陣中的一行相乘。將每次乘法結(jié)果進(jìn)行異或運算,以獲得新的狀態(tài)值。第一個要進(jìn)行相乘運算的列和行在圖 4 中加亮顯示。
圖 4 — 用于加密和解密的列混合變換 (MixColumns) 函數(shù)
以下是第一列的列混合變換(MixColumns) 方程:
B1’ = (B1 * 2) XOR (B2 * 3) XOR (B3 * 1) XOR (B4 * 1)
B2’ = (B1 * 1) XOR (B2 * 2) XOR (B3 * 3) XOR (B4 * 1)
B3’ = (B1 * 1) XOR (B2 * 1) XOR (B3 * 2) XOR (B4 * 3)
B4’ = (B1 * 3) XOR (B2 * 1) XOR (B3 * 1) XOR (B4 * 2)
然后,為輸入狀態(tài)中的下一個列采用相同乘法矩陣重復(fù)這個過程,直到處理完所有輸入狀態(tài)列。
既然我們已經(jīng)理解了 AES 加密和解密算法所需的詳細(xì)步驟,那么還需要知道一個循環(huán)中這些步驟的應(yīng)用順序以及我們是否必須為每個循環(huán)應(yīng)用所有步驟。每個 AES 加密循環(huán)都包含全部四個步驟,并按照以下順序:
1. 字節(jié)替換 (SubBytes) ;
2. 行位移變換 (ShiftRows);
3. 列混合變換 (MixColumns) (只針對循環(huán) 1 至N–1);
4. 輪密鑰加 (AddRoundKey)( 使用擴(kuò)展秘鑰)。
當(dāng)然,我們需要能夠反轉(zhuǎn)這個過程,將不可讀的密文變回純文本,讓加密信息有用。為此,我們將步驟進(jìn)行如下排序:
1. 反轉(zhuǎn)行位移變換;
2. 反轉(zhuǎn)字節(jié)替換;
3. 輪密鑰加(使用擴(kuò)展秘鑰);
4. 反轉(zhuǎn)列混合變換(只針對循環(huán) 1 至 N–1)。
執(zhí)行第一輪加密之前,我們需要為加密和解密執(zhí)行初始輪密鑰加 (AddRoundKey) 操作。
可在更高抽象層上高效地描述 AES,就像在傳統(tǒng)軟件開發(fā)中那樣,但在 FPGA 中實現(xiàn)起來最為高效。開發(fā)人員甚至可在布線中“免費”獲得一些操作。
我們看一下擴(kuò)展秘鑰必須使用的算法,以便提供足夠的秘鑰位,用以執(zhí)行相應(yīng)數(shù)量的輪密鑰加(AddRoundKey) 步驟(圖 5)。進(jìn)行秘鑰擴(kuò)展時,16、24 或 32 字節(jié)的秘鑰長度分別需要 44、52 或 60個循環(huán)。擴(kuò)展秘鑰的第一個字節(jié)等于初始秘鑰。這意味著對于我們的 AES256 實例來說,擴(kuò)展秘鑰的最開始的 32 個字節(jié)就是秘鑰本身。秘鑰擴(kuò)展操作在每次迭代中為擴(kuò)展秘鑰生成 32 個附加位。
圖 5 — 秘鑰擴(kuò)展算法
擴(kuò)展秘鑰的第一個字節(jié)等于初始秘鑰。這意味著對于我們的 AES256 實例來說,擴(kuò)展秘鑰的最開始的 32 個字節(jié)就是秘鑰本身。
以下是重要的擴(kuò)展步驟:
RotateWord: 與行位移變換 (ShiftRows) 類似,這個步驟重新組織 32 位字,以使最高有效字節(jié)變?yōu)樽畹陀行ё止?jié)。
SubWord: 這個步驟使用的替換盒與加密時進(jìn)行字節(jié)替換所使用的替換盒相同。
rcon: 該階段對用戶定義的值進(jìn)行 2 次冪運算。
與列混合變換 (MixColumns) 階段類似,rcon 也在有限域 (28) 中執(zhí)行; 因此這個步驟普遍使用預(yù)先計算的查找表。
EK: 從擴(kuò)展秘鑰返回 4 個字節(jié)。
K: 與 EK 類似,從秘鑰返回 4 個字節(jié)。
如何知道我們已經(jīng)正確實現(xiàn)了加密和秘鑰擴(kuò)展算法? AES 的 NIST 規(guī)范包含多個有效實例,可用來檢查我們自己的實現(xiàn)結(jié)果。
創(chuàng)建代碼
為了確保能夠加速 Zynq SoC 的 PL 中 AES 代碼的加密部分,我們必須一開始就要以這個目標(biāo)來開發(fā)代碼(見這里的編碼規(guī)則)。要考慮的第一件事是算法的架構(gòu);我們需要正確對其進(jìn)行分段。AES 很適合這種方案,因為我們可以為每個階段編寫函數(shù),然后再根據(jù)需要調(diào)用。 我們還必須編寫要在自身的文件中進(jìn)行加速的函數(shù)。軟件架構(gòu)包括以下內(nèi)容。
main.c: 該文件包含秘鑰擴(kuò)展算法、加密秘鑰和純文本輸入,以及對 AES 加密函數(shù)的調(diào)用。
aes_enc.c: 該文件執(zhí)行加密。我們將每個階段編寫為單獨的函數(shù),這樣就能根據(jù) AES 循環(huán)的需要進(jìn)行調(diào)用。為確保程序設(shè)計對于處理器上執(zhí)行的程序具有通用性,我們?yōu)榛旌喜襟E的乘法使用查找表。
aes_enc.h: 這個文件包含 aes_funcTIon 的定義以及用來確定大小的參數(shù)(例如 mk、nb 和 nr)。
sbox.h: 這個文件包含用于替換字節(jié)的替換盒、執(zhí)行秘鑰擴(kuò)展的 rcon 函數(shù)的查找表以及用于列混合變換乘法的乘法查找表。
在這個結(jié)構(gòu)中,我們可以選擇 AES 加密函數(shù)( 圖 6) 作為要進(jìn)行加速的函數(shù),只需右鍵點擊該函數(shù)并選擇“ Toggle HW/SW”即可。
圖 6 — 要加速的函數(shù)
為了能確定基準(zhǔn)性能以及通過函數(shù)加速獲得的保存結(jié)果,我們必須對函數(shù)的執(zhí)行進(jìn)行時間控制。為此,我們使用 sds_lib.h 中的sds_clock_counter。
編寫源代碼(在 github 提供)之后,在用 ZynqSoC 中的單個 ARM? Cortex ? -A9 處理器內(nèi)核在軟件中執(zhí)行 AES 算法時,我記錄了 36,662 個處理器周期。
為加速而進(jìn)行的優(yōu)化
加速 AES 算法比前一個問題中的矩陣乘法算法還要稍稍復(fù)雜一些。這是因為 AES 算法的主循環(huán)包含互相依賴的階段。
我加速 AES 算法時所采用的方法是:檢查循環(huán)以找出可以展開的地方; 優(yōu)化存儲器帶寬; 選擇正確的數(shù)據(jù)移動時鐘頻率和硬件功能頻率。
AES 加密函數(shù)的主循環(huán)包含用于執(zhí)行每個 AES步驟的函數(shù)。AES 算法中的每個函數(shù)必須完整執(zhí)行,并在下個函數(shù)運行之前計算出結(jié)果。這種互相依賴性需要我們將精力集中于作為獨立函數(shù)的 AES步驟。這些步驟中存在足夠多的優(yōu)化潛力。
我們可將輪密鑰加 (AddRoundKey) 、字節(jié)替換(SubBytes) 和列混合變換 (MixColumns) 步驟流水線化,以提高性能。在這些函數(shù)中,我們通過將編譯指示放在第一個循環(huán)中來執(zhí)行 HLS Pipeline 命令。我們應(yīng)展開內(nèi)部循環(huán)。這些函數(shù)中有幾個函數(shù)從查找表(通常從 block RAM 構(gòu)建)讀取數(shù)據(jù)。我們需要增加存儲器帶寬,在本例中,我將編譯指示參數(shù)指定為“完成”,這樣可將存儲器內(nèi)容實現(xiàn)為分立寄存器而非BRAM。
在 Zynq SoC 上的 PS 與 PL 之間傳輸數(shù)據(jù)的能力對提升性能而言也非常重要。我所做的第一步是將數(shù)據(jù)移動時鐘網(wǎng)絡(luò)設(shè)定為最高時鐘頻率:200MHz。第二個方案是確保為 PS 與 PL 之間的數(shù)據(jù)傳輸使用直接存儲器訪問。為此,我必須將接口稍加修改,并使用 sds_alloc 函數(shù)按照 DMA 傳輸?shù)囊蟠_保數(shù)據(jù)在存儲器中的連續(xù)性(圖 7)。
圖 7 — PS 與 PL 之間的數(shù)據(jù)移動網(wǎng)絡(luò)
第二個也是最后的優(yōu)化步驟是將硬件功能的時鐘速率設(shè)定在所支持的最高頻率:166.67 MHz。
操作系統(tǒng)支持
當(dāng)我最終將所有內(nèi)容放在一起并構(gòu)建出這個實例時,經(jīng) PL 加速的 AES 代碼在 Linux 上運行16,544 個處理器時鐘周期; 當(dāng)在單獨在軟件中運行
AES 代碼時,只需要 45%(16,544/36,662) 的周期數(shù)量。這可將這個具有互相依賴關(guān)系且相當(dāng)復(fù)雜的算法的執(zhí)行時間縮短 55%。
當(dāng)然,我們也可在 SDSoC 環(huán)境中選擇 BareMetal或 FreeRTOS 操作系統(tǒng)。創(chuàng)建 BareMetal 和 FreeRTOS項目并重新使用代碼能夠在三種操作系統(tǒng)之間進(jìn)行性能對比。對于給定項目而言,操作系統(tǒng)的選擇取決于任務(wù)要求、性能預(yù)算以及響應(yīng)時間。
圖 8 給出了 Zynq SoC 的 PS 和 PL 中三種操作系統(tǒng)的性能( 圖 8)。
圖 8 — Zynq PS 和 PL 中的操作系統(tǒng)性能。FreeRTOS 和 BareMetal 提供類似的縮短效果。
不出意料,F(xiàn)reeRTOS 和 BareMetal 實現(xiàn)了類似的時間縮短效果,因為兩種操作系統(tǒng)都比完整的 LinuxOS 簡單得多。
正如我們的結(jié)果所示,利用 SDSoC 開發(fā)環(huán)境加速 AES 加密,能實現(xiàn)真正的性能提升,而且易于實現(xiàn)—— 無需深入的 FPGA 設(shè)計經(jīng)驗。
『本文轉(zhuǎn)載自網(wǎng)絡(luò),版權(quán)歸原作者所有,如有侵權(quán)請聯(lián)系刪除』
評論