如何基于置換算法來設計對稱加密算法一、置換算法的定義在密碼學中“置換”通常有兩層含義。狹義定義位置置換。給定一個有限符號序列置換算法按照固定規(guī)則重新排列符號的位置但不改變符號本身。例如把 64 個比特重新排成另一個順序。數(shù)學上可寫成雙射π:01…n-1→01…n-1輸出第i位等于輸入第πi位或反過來。因為π是雙射所以每個位置恰好被映射一次逆置換存在信息無損。廣義定義有限集合上的雙射。若集合為01n則置換是n比特串到自身的雙射P:01n→01n每個輸入對應唯一輸出每個輸出也恰好有一個原像。分組密碼的加密函數(shù)Ek在固定密鑰k下本質(zhì)上就是01n上的一個置換解密則是其逆置換。因此置換與“代換”不同代換改變符號的值例如把字節(jié)0x3A換成0xC5置換改變符號的位置例如把第 1 位放到第 17 位。純位置置換保持漢明重量、符號頻率和整體統(tǒng)計分布但改變局部相關(guān)性。二、置換算法在對稱加密算法中的地位1. Shannon的混淆與擴散Shannon提出強密碼需要“混淆”和“擴散”。混淆使密鑰與密文之間的關(guān)系復雜通常由非線性代換完成如 S 盒。擴散使明文或密鑰的每一位影響密文的許多位通常由置換和線性混合完成。置換算法主要承擔擴散功能。沒有擴散S 盒逐字節(jié)獨立工作局部變化無法傳播到整個分組容易受到差分分析、線性分析和截斷差分分析。2.分組密碼中的核心組件現(xiàn)代分組密碼常見結(jié)構(gòu)是 SPN即“代換-置換網(wǎng)絡”。代換層S 盒提供非線性置換層或線性擴散層重新排列或混合比特/字節(jié)使一個 S 盒的輸出擴散到下一輪多個 S 盒。密鑰加層引入密鑰。典型例子DES 中有初始置換 IP、擴展置換 E、P 盒、壓縮置換 PC-1/PC-2。AES 中沒有傳統(tǒng)比特 P 盒但有 ShiftRows 和 MixColumns它們共同完成字節(jié)級擴散。PRESENT、GIFT 等輕量級密碼使用規(guī)則比特置換層如 PRESENT 的 pLayer 將比特i映射為16imod63使每個 S 盒輸出擴散到下一輪不同 S 盒。3.分組密碼本身是偽隨機置換從理論上看一個安全分組密碼的理想模型是偽隨機置換即固定密鑰后加密函數(shù)看起來像一個隨機選擇的置換。安全性定義通常要求攻擊者不能區(qū)分Ek與隨機置換也不能區(qū)分其逆Ek-1與隨機逆置換。因此置換不僅是組件也是分組密碼的理論抽象。Luby-Rackoff 還證明用偽隨機函數(shù)通過 Feistel 結(jié)構(gòu)多輪迭代可以構(gòu)造偽隨機置換。4.流密碼、哈希與海綿結(jié)構(gòu)在流密碼、哈希函數(shù)和認證加密中置換也常作為核心。例如 Keccak/SHA-3 使用 Keccak-f[1600] 置換海綿結(jié)構(gòu)通過反復應用置換吸收和擠出數(shù)據(jù)。這里置換必須是高效、可逆、擴散良好的雙射。5.密鑰編排與白化置換還用于密鑰編排如 DES 的 PC-1、PC-2把密鑰比特重新排列和選取使輪密鑰之間相關(guān)性降低。白化操作中也常通過置換或線性混合增強密鑰影響?？傊脫Q在對稱加密中不是單獨的安全來源而是擴散和結(jié)構(gòu)的基礎(chǔ)。單獨使用純置換不安全因為它保持頻率和漢明重量但缺少置換現(xiàn)代分組密碼的擴散和雪崩效應會嚴重不足。三、密碼學性質(zhì)良好的置換算法應怎樣設計設計良好的置換算法需要區(qū)分目標是設計純位置置換/P 盒還是設計線性擴散層還是設計偽隨機置換/分組密碼整體。下面給出通用原則和具體方法。1.基本安全目標一個好的置換算法通常應滿足雙射與可逆性構(gòu)造上保證每個輸入有唯一輸出逆置換存在且高效。強擴散性輸入一位變化應影響輸出多位多輪后接近雪崩效應。雪崩準則翻轉(zhuǎn)輸入任意一位輸出每一位翻轉(zhuǎn)概率約為1/2。比特獨立準則輸出位之間盡量獨立不泄露輸入位關(guān)系。低差分與線性相關(guān)性若置換是非線性 S 盒或偽隨機置換應具有低差分均勻性和低線性偏差。大周期、無短循環(huán)作為置換其循環(huán)結(jié)構(gòu)不能有大量短環(huán)或固定點避免迭代攻擊和弱結(jié)構(gòu)。實現(xiàn)友好低門數(shù)、低延遲、常數(shù)時間、硬件面積小、抗側(cè)信道。2.純位置置換/P 盒的設計純位置置換是線性操作只重排比特或字節(jié)。設計重點在擴散。常用指標分支數(shù)BPminx≠0wtxwtPx分支數(shù)越大一個非零輸入經(jīng)過置換后非零位越多擴散越強。對線性擴散層MDS 矩陣可達到最優(yōu)分支數(shù)n1。擴散距離任意輸入位到輸出位的影響路徑長度。SAC/BIC檢查輸入翻轉(zhuǎn)一位時輸出位翻轉(zhuǎn)概率是否接近1/2。設計方法規(guī)則置換如循環(huán)移位、比特矩陣、PRESENT pLayer便于硬件布線幾乎零門成本。不規(guī)則置換通過搜索算法、SAT/SMT、MILP、遺傳算法尋找擴散更好的位置映射。與 S 盒配合置換層應使每個 S 盒輸出進入下一輪不同 S 盒最大化活躍 S 盒數(shù)量。寬軌跡策略擴散層分支數(shù)越高多輪后活躍 S 盒下界越大抗差分和線性分析能力越強。AES 的 ShiftRows MixColumns 是典型代表。注意純比特置換保持漢明重量本身線性不能單獨作為密碼。它必須與非線性代換和密鑰加交替迭代。3.線性擴散層的設計現(xiàn)代分組密碼常把置換推廣為線性擴散層如 GF(2) 或 GF(2^8) 上的矩陣乘法。設計要點使用MDS矩陣在n個符號上達到分支數(shù)n1如 AES MixColumns 在 4 字節(jié)上分支數(shù)為 5?？捎?Reed-Solomon 碼、Cauchy 矩陣、循環(huán)矩陣構(gòu)造。循環(huán)矩陣便于硬件實現(xiàn)但需檢查差分/線性分支數(shù)。二進制矩陣適合輕量級實現(xiàn)但分支數(shù)通常低于 MDS需要更多輪數(shù)補償。擴散層應與 S 盒層對齊使每輪活躍 S 盒數(shù)最大。4.密鑰控制置換與偽隨機置換若目標是設計一個由密鑰控制的置換族Pk或直接設計分組密碼常用結(jié)構(gòu)Feistel結(jié)構(gòu)輪函數(shù)不必可逆整體可逆。Luby-Rackoff 證明 3 輪可構(gòu)造 PRP4 輪可構(gòu)造強 PRP。SPN結(jié)構(gòu)S 盒 線性擴散 輪密鑰加多輪迭代。AES 是典型。ARX結(jié)構(gòu)模加、循環(huán)移位、異或。軟件友好但安全分析較復雜。Benes網(wǎng)絡/開關(guān)網(wǎng)絡用密鑰控制交換開關(guān)可實現(xiàn)任意置換適合設計密鑰控制置換但需防止相關(guān)密鑰攻擊。海綿結(jié)構(gòu)中的置換如 Keccak-f強調(diào)擴散、非線性、常數(shù)時間。設計時輪數(shù)必須足夠使差分、線性、積分、代數(shù)、滑動、不變子空間、回旋等攻擊的復雜度高于窮舉。密鑰編排應避免弱密鑰和輪密鑰簡單關(guān)系。5. S盒作為置換的設計S盒本身是01n→01n的雙射因此也是一種置換。AES S 盒設計是經(jīng)典先取有限域GF28上的乘法逆x?x-10?0再作仿射變換。結(jié)果是差分均勻性為 4線性偏差低代數(shù)次數(shù)為 7能抵抗已知差分和線性攻擊。設計 S 盒時應關(guān)注差分均勻性盡量小線性譜盡量平坦代數(shù)次數(shù)高無固定點、無反演點無隱藏陷門實現(xiàn)可常數(shù)時間。6.評估與驗證設計完成后需從多個維度評估數(shù)學指標分支數(shù)、SAC、BIC、差分均勻性、線性偏差、代數(shù)次數(shù)、置換周期。密碼分析差分、線性、截斷差分、積分、代數(shù)、滑動、不變子空間、回旋、相關(guān)密鑰。實現(xiàn)指標門數(shù)、面積、延遲、吞吐、功耗、常數(shù)時間性?？勺C明安全活躍 S 盒下界、寬軌跡策略、PRP/PRF 歸約?？偨Y(jié)置換算法是有限集合上的雙射在對稱加密中主要承擔擴散功能。現(xiàn)代分組密碼中它既是 SPN 的線性擴散層也是分組密碼整體的理論模型——偽隨機置換。好的置換設計不能孤立追求“排列復雜”而應與非線性 S 盒、密鑰加和多輪迭代配合純位置置換要優(yōu)化分支數(shù)、雪崩和活躍 S 盒線性擴散層要用 MDS 或高分支數(shù)矩陣偽隨機置換要用足夠輪數(shù)和抗分析結(jié)構(gòu)S 盒型置換要追求低差分、低線性、高代數(shù)次數(shù)。最終目標是在安全性、可證明性、實現(xiàn)效率和抗側(cè)信道之間取得平衡。