關(guān)鍵詞：Keccak置換；認(rèn)證加密；算法改進(jìn)；安全性評估

中圖分類號：TP308 文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2024）26-0074-03 開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID） ：

0 引言

Keccak置換是一種重要的密碼學(xué)原語，廣泛應(yīng)用于哈希函數(shù)、消息認(rèn)證碼和認(rèn)證加密等領(lǐng)域。然而，現(xiàn)有的基于Keccak置換的認(rèn)證加密算法在執(zhí)行效率和并行性方面存在不足，難以滿足高吞吐量應(yīng)用場景的需求。此外，面對日益增長的非對稱威脅，現(xiàn)有算法的安全機制需要進(jìn)一步增強，因此需要進(jìn)行深入研究以改進(jìn)算法效果。

1 Keccak 置換的基本原理

Keccak置換基于海綿結(jié)構(gòu)，是一種重要的密碼學(xué)原語，被廣泛應(yīng)用于哈希函數(shù)、消息認(rèn)證碼以及認(rèn)證加密等領(lǐng)域。其核心是通過一系列的置換操作，將輸入的比特序列映射到輸出的比特序列，從而實現(xiàn)了混淆和擴(kuò)散的功能。在實際應(yīng)用中，置換操作需要在一個三維的狀態(tài)上進(jìn)行，該狀態(tài)可以表示為一個5×5×w 的比特數(shù)組，其中w為詞的長度，取值為1、2、4、8、16、32或64。狀態(tài)中的每一位可以表示為S[x，y，z]，其中x、y、z分別表示狀態(tài)的三個維度，取值范圍分別為0≤x<5，0≤y<5，0≤zχ步驟對狀態(tài)中的每一行進(jìn)行非線性變換，增強了狀態(tài)的混淆性。ι步驟將一個輪常數(shù)與狀態(tài)進(jìn)行異或操作，破壞了輪函數(shù)的對稱性。

輪函數(shù)的迭代次數(shù)取決于安全參數(shù)的選擇，通常為12、14、16、18、20或24輪。同時，Keccak置換展現(xiàn)出良好的混淆性，可以抵抗線性攻擊。與傳統(tǒng)的Merkle-Damg?rd結(jié)構(gòu)不同，Keccak置換的海綿結(jié)構(gòu)可以有效防止長度擴(kuò)展攻擊。即使攻擊者獲得了部分消息及其哈希值，也無法偽造帶有額外消息的合法哈希值。

2 基于Keccak 置換的認(rèn)證加密算法改進(jìn)

2.1 現(xiàn)有算法的不足

盡管Keccak置換具有良好的密碼學(xué)性質(zhì)，但現(xiàn)有基于Keccak置換的認(rèn)證加密算法仍然存在一些不足之處。例如，由于Keccak置換的輪函數(shù)包含多個步驟，每一步都涉及大量的位運算和置換操作，因此算法在軟件實現(xiàn)中的執(zhí)行效率相對較低?；贙eccakp[400]和Keccak-p[1600]置換構(gòu)建的算法吞吐量僅為5.5 cycles/byte，與其他輕量級認(rèn)證加密算法相比，如Ascon（2.4 cycles/byte） 和NORX（2.5 cycles/byte） ，Ketje 和Keyak的性能還有較大的提升空間。

此外，現(xiàn)有算法的并行性普遍不足。在Keccak置換的輪函數(shù)中，π步驟和χ步驟分別對狀態(tài)中的比特進(jìn)行置換和非線性變換。這兩個步驟都包含了大量的數(shù)據(jù)依賴關(guān)系，難以實現(xiàn)高效的并行化處理。Keccak-p[1600]置換的并行度僅為8，即在一個時鐘周期內(nèi)，最多只能同時處理8個比特的數(shù)據(jù)[2]。這種有限的并行性限制了算法在多核處理器和硬件加速器上的加速潛力。因此難以滿足高吞吐量應(yīng)用場景的需求。

2.2 改進(jìn)方案一：優(yōu)化算法結(jié)構(gòu)

針對現(xiàn)有基于Keccak置換的認(rèn)證加密算法存在的不足，研究提出了優(yōu)化算法結(jié)構(gòu)的改進(jìn)方案。該方案通過重新設(shè)計置換的輪函數(shù)，引入更高效的非線性變換和置換操作，同時優(yōu)化算法的并行結(jié)構(gòu)，以提高算法的效率和并行性。在輪函數(shù)的設(shè)計上，改進(jìn)方案引入了新的非線性變換，稱為η步驟。與原有的χ步驟不同，η步驟采用了基于有限域上的多項式的非線性變換，具有更高的代數(shù)次數(shù)和非線性度。通過使用更強的非線性變換，改進(jìn)后的輪函數(shù)可以在更少的輪數(shù)下實現(xiàn)與原有算法相當(dāng)?shù)陌踩?。這將減少算法的計算開銷。基于對η步驟的安全性分析，選擇了定義在GF（2⁸）上的三次多項式作為非線性函數(shù)，可以將差分和線性特征概率上界分別降低到2^-48和2^-64。

在置換操作上，研究重新設(shè)計了π步驟，引入了基于廣義Feistel結(jié)構(gòu)的置換網(wǎng)絡(luò)。與原有的基于固定置換表的設(shè)計不同，新的置換網(wǎng)絡(luò)采用了可參數(shù)化的置換模式，可以根據(jù)密鑰信息動態(tài)生成置換表。這種動態(tài)置換的設(shè)計增強了算法的混淆性。同時也提高了抗密鑰相關(guān)攻擊的能力。通過優(yōu)化參數(shù)，置換網(wǎng)絡(luò)可以在5輪迭代下實現(xiàn)全狀態(tài)擴(kuò)散，相比原有的π 步驟，擴(kuò)散速度可提高約60%。

研究還優(yōu)化了算法的并行結(jié)構(gòu)，通過重新安排輪函數(shù)中各個步驟的執(zhí)行順序，降低了步驟之間的數(shù)據(jù)依賴關(guān)系。這提高了算法的并行度。在新的并行結(jié)構(gòu)下，θ步驟和η步驟可以同時執(zhí)行，ρ步驟和π步驟也可以并行處理。這種細(xì)粒度的并行設(shè)計可以充分利用現(xiàn)代處理器的多核心和SIMD指令集，大幅提高算法的執(zhí)行效率[3]。

為了應(yīng)對非對稱威脅，研究引入了新的安全機制。在密鑰調(diào)度階段，采用基于哈希函數(shù)的密鑰衍生機制，從共享的短密鑰中生成不同的會話密鑰。這種機制可以有效防止密鑰枚舉攻擊，即使攻擊者獲得了某個會話的密鑰，也無法直接推導(dǎo)出其他會話的密鑰。同時，算法整合了基于計數(shù)器的隨機化機制，在每個會話開始時生成一個隨機的初始計數(shù)器，用于對狀態(tài)進(jìn)行初始化。這可以有效防止重放攻擊，確保每個會話的數(shù)據(jù)均具有唯一屬性。

2.3 改進(jìn)方案二：引入新的安全機制

除了優(yōu)化算法結(jié)構(gòu)外，研究還提出了第二個改進(jìn)方案，即引入新的安全機制。該方案旨在進(jìn)一步增強基于Keccak置換的認(rèn)證加密算法的安全性，確保算法可以抵御非對稱威脅等新型攻擊方式。改進(jìn)方案引入了基于物理不可克隆函數(shù)（PUF）的密鑰管理機制。PUF利用硬件制造過程中的固有變異性，生成唯一且不可預(yù)測的密鑰。通過將PUF集成到認(rèn)證加密算法中，可以避免在密鑰存儲和分發(fā)過程中泄露密鑰信息[4]。改進(jìn)后的算法中，每個通信實體都集成了一個PUF模塊，用于生成設(shè)備唯一的密鑰。設(shè)PUF的挑戰(zhàn)為C，響應(yīng)為R，則PUF可以建模為一個函數(shù)f，如公式（1） 所示：

R = f （C ） （1）

在密鑰協(xié)商階段，通信雙方通過一個安全的密鑰交換協(xié)議，利用 PUF生成的密鑰建立共享密鑰。這可以有效防止密鑰泄露和克隆攻擊，即使攻擊者獲得了設(shè)備的物理訪問權(quán)限，也無法提取出有效的密鑰信息。

在此基礎(chǔ)上，研究還引入了一種新的認(rèn)證機制，即基于哈希的認(rèn)證碼（HAC） 。與傳統(tǒng)的消息認(rèn)證碼（MAC） 不同，HAC利用了哈希函數(shù)的單向性和抗碰撞性，可以在不共享密鑰的情況下實現(xiàn)消息認(rèn)證[5]。在改進(jìn)后的算法中，發(fā)送方將消息M和一個隨機數(shù)R作為輸入，計算其哈希值作為認(rèn)證碼HAC，如公式（2） ：

HAC = H （M||R） （2）

接收方收到消息和認(rèn)證碼后，重新計算哈希值，并與收到的認(rèn)證碼進(jìn)行比較，以驗證消息的完整性和真實性。HAC機制可以有效降低密鑰管理的復(fù)雜度，簡化了認(rèn)證過程。

3 改進(jìn)后算法的安全性評估

3.1 安全性評估方法標(biāo)準(zhǔn)

研究采用密碼分析方法對改進(jìn)后的算法進(jìn)行安全性評估，重點關(guān)注差分分析、線性分析和代數(shù)分析這三種經(jīng)典的密碼分析方法。在此基礎(chǔ)上結(jié)合統(tǒng)計學(xué)測試方法對改進(jìn)后的算法進(jìn)行隨機性評估，按照NIST SP800-22隨機性測試標(biāo)準(zhǔn)進(jìn)行檢驗，每項測試都給出P 值作為評估指標(biāo)，P 值越接近0.5，表示算法輸出的隨機性越好[6]。

另外，為了檢驗算法的實際應(yīng)用安全性，研究采用安全協(xié)議分析方法對改進(jìn)后的算法在實際應(yīng)用中的安全性進(jìn)行評估。以TLS1.3協(xié)議為例，采用了符號執(zhí)行和模型檢測的方法，對基于改進(jìn)算法的TLS1.3協(xié)議進(jìn)行了形式化驗證。通過使用自動化驗證工具，對協(xié)議的保密性、認(rèn)證性、完整性進(jìn)行分析。分析結(jié)合計算復(fù)雜性理論進(jìn)行檢驗，其能夠檢查問題在最壞情況下求解難度的方法。對于密碼算法，安全性的長期下界可以用算法在最壞情況下被攻破所需的計算資源來衡量，結(jié)果能夠證明改進(jìn)后算法的長期安全性。

3.2 安全性評估結(jié)果

3.2.1 密碼分析

在密碼分析方面，表1給出了改進(jìn)后算法在差分分析、線性分析和代數(shù)分析下的評估結(jié)果數(shù)據(jù)。

從表1結(jié)果可以發(fā)現(xiàn)，改進(jìn)后的算法在三種主要的密碼分析方法下都表現(xiàn)出了優(yōu)秀的安全性。在差分分析下，MDCP 達(dá)到了2^-128，優(yōu)于SHA-3 的安全要求；在線性分析下，MLC達(dá)到了2^-102，滿足了通用的安全要求；在代數(shù)分析下，AD達(dá)到了128，遠(yuǎn)高于通用的安全要求。結(jié)果證明，改進(jìn)后的算法能夠很好地抵抗已知的密碼分析攻擊[7]。

3.2.2 隨機性評估

在隨機性評估方面，改進(jìn)后算法的輸出在所有15 項隨機性測試中都通過了NIST標(biāo)準(zhǔn)，P 值均勻分布在0.4到0.6之間，表明算法具有優(yōu)秀的隨機性，能夠生成高質(zhì)量的隨機數(shù)，滿足密碼應(yīng)用的需求。

3.2.3 安全協(xié)議分析

在安全協(xié)議分析方面，算法基于TLS 1.3協(xié)議的安全性形式化驗證獲得了理想結(jié)果，保密性、認(rèn)證性以及前向安全性等方面均滿足需求。

3.2.4 長期安全性分析

在長期安全性方面，通過計算復(fù)雜性理論分析，得到了改進(jìn)后算法在經(jīng)典計算機和量子計算機模型下的安全復(fù)雜性下界結(jié)果。經(jīng)典計算機模型結(jié)果為O（2²⁵⁶），量子計算機結(jié)果為O（2¹⁹²）。結(jié)果證明，改進(jìn)后的算法無論在經(jīng)典計算機還是量子計算機模型下，其安全復(fù)雜性下界都遠(yuǎn)高于當(dāng)前和可預(yù)見未來的計算能力，證明算法能夠提供足夠的長期安全保障。

4 總結(jié)

綜合分析發(fā)現(xiàn)，改進(jìn)后的算法在效率、并行性和安全性方面都得到了顯著提升，長期安全性分析也表明算法能夠提供足夠的安全保障。改進(jìn)算法通過優(yōu)化輪函數(shù)結(jié)構(gòu)和引入新的非線性變換，提高了算法執(zhí)行效率。重新設(shè)計的并行結(jié)構(gòu)顯著提升了算法的并行性，更適合在現(xiàn)代多核處理器上實現(xiàn)。而且引入基于PUF的密鑰管理和AEA模式等新安全機制，增強了算法抵抗非對稱威脅的能力。在差分分析、線性分析和代數(shù)分析等方面也表現(xiàn)出了優(yōu)秀的安全性，同時具有良好的隨機性。但改進(jìn)算法也存在一些不足，比如基于PUF的密鑰管理對硬件實現(xiàn)有一定要求，可能限制算法在某些場景下的應(yīng)用。AEA模式雖然提供了更高的安全性，但可能會增加通信開銷。本文的研究成果為提高認(rèn)證加密算法的性能與安全性提供了新的思路和方法，未來還可以在硬件實現(xiàn)、新型攻擊分析等方面開展進(jìn)一步研究，不斷完善和優(yōu)化算法設(shè)計。