1.9 Khufu和Khafre快速軟件加密算法

Khufu和Khafre快速軟件加密算法是由R. C. Merkle在1990年美洲密碼年會上提出的，類似于DES的多層迭代分組密碼，迭代層數(shù)規(guī)定為8的整數(shù)倍，輸入和輸出分組均為64比特，加密速度在SUN 4/260上可達4～8 Mb/s。因為是軟件加密算法，所以與硬件加密算法相比有更大的靈活性，其加密層數(shù)和密鑰長度均沒有具體規(guī)定，可根據(jù)被加密數(shù)據(jù)的價值，以及對安全性和加密速度的要求來確定。迭代層數(shù)可以是8～64之間的任意8的整數(shù)倍，一般用16層、24層或32層。密鑰長度一般為64比特的整數(shù)倍。

Khufu和Khafre設計的基本思想是：面向軟件、快速實現(xiàn)。當時R.C. Merkle認為還沒有一種被大家普遍接受的軟件加密算法，大部分商業(yè)加密軟件都用軟件仿效硬件實現(xiàn)DES加密算法。由于DES加密算法是面向硬件設計的，每層要并行進行8次查表（S盒代替），然后進行一次置換。而對于軟件來說，8次查表也只能逐個進行，所以速度慢。R. C. Merkle估計，用軟件實現(xiàn)DES加密算法的速度為安全性相當?shù)摹⒚嫦蜍浖用芩惴ǖ?/10～1/5。

Khufu加密算法和Khafre加密算法基本相同，略有差別。在加密時，前者的S盒由密鑰決定，后者的S盒固定不變；在使用時，前者用于大量成批數(shù)據(jù)的加密，后者用于少量數(shù)據(jù)的加密。

我們先介紹Khufu加密算法。把數(shù)據(jù)（明文）分為左、右兩半，各32比特，分別記為L和R，加密的第一步是把明文與64比特的輔助密鑰（Auxiliary Key, AK）進行模2加，然后進行n層變換，最后與另外64比特的輔助密鑰進行模2加，最后得到輸出密文。每層變換由一次查表和一次循環(huán)移位組成，把L最右邊一個字節(jié)作為S盒的輸入，輸出32比特并與R進行模2加，然后L循環(huán)右移1個或多個字節(jié)，再變換左、右兩部分，從而實現(xiàn)一層變換。Khufu加密算法如圖1.9.1所示。

S盒是一個由256個32比特組成的RAM表，若把它看成4個長度為256字節(jié)的序列，則每列是0～255的一個排列。S盒的輸入是1字節(jié)，把它作為地址碼，從RAM表中取出相應的32比特作為輸出。每經過8層變換，S盒就要更換一次，所以S盒的個數(shù)是由層數(shù)決定的。左部分1～8層的循環(huán)右移的字節(jié)數(shù)分別為2、2、1、1、2、2、3、3，經過8層循環(huán)右移后，數(shù)據(jù)回到原來位置，然后進行9～16層、17～24層…，不斷重復上述循環(huán)右移的字節(jié)數(shù)。經過8層變化后，每個字節(jié)恰好作為一次S盒的輸入。

R. C. Merkle在1990年美洲密碼年會上發(fā)表的文章中對Khufu加密算法的密鑰量沒做規(guī)定，只是談到從初始密鑰算出128比特的輔助密鑰和每8層變化一次的S盒，并沒有介紹怎樣從初始密鑰計算輔助密鑰。各層的S盒是從一個初始S盒出發(fā)，在初始密鑰參與的情況下，按一定的算法生成的。初始S盒也是一個256×32比特的RAM表，每個字節(jié)列都是0～255的一個排列，生成S盒的過程可分為兩步。

（1）生成一個足夠長的偽隨機字節(jié)序列。先從初始密鑰得到64字節(jié)的初始值，采用Khufu加密算法，以分組連接的方式對這64字節(jié)進行加密，得到64個偽隨機字節(jié)，再次加密后又可又得到64個偽隨機字節(jié)…，直到偽隨機字節(jié)序列足夠長，在下面第（2）步中用它來決定第R[i]個字節(jié)的值。

（2）由偽隨機字節(jié)序列來產生初始S盒。從初始S盒的每個字節(jié)列的第0個字節(jié)開始到第255個字節(jié)，對每個字節(jié)進行一次對換，第i個字節(jié)與該列的第R[i]個字節(jié)對換，其中R[i]是由第（1）步生成的相應偽隨機字節(jié)決定的。經過這樣變化后的S盒仍然保持每列是0～255的一個排列，用上述方法可以生成足夠多的S盒。

Khufu加密算法的每層變化使用了一個較大的非線性S盒，S盒的輸出與右半部分R進行模2加，經多層非線性變化后，達到了混亂的目的。又因為每層進行一次字節(jié)移位，經8層變化后，明文輸入的每個字節(jié)都恰好用來查一次表，使變化后的每個密文的比特依賴于整個明文輸入和密鑰，達到了擴散的目的。

DES加密算法每層要查8個S盒，進行一次64比特的置換。Khufu加密算法針對軟件實現(xiàn)的特點，把S盒的規(guī)模擴大，每層只查一次，并用循環(huán)移位來代替置換，這樣同樣達到了混亂和擴散的目的，但速度比DES加密算法快得多。

Khafre加密算法與Khufu加密算法類似，不同的是Khafre加密算法用一組固定的S盒，稱其為標準S盒。在加密少量數(shù)據(jù)或只加密一個64比特分組時，由于不必計算S盒，所以速度快。另外，因為Khafre加密算法的S盒與密鑰無關，所以除了在算法的開頭和結束數(shù)據(jù)要和64比特的密鑰進行模2加，每經過8層變換，都要用64比特的密鑰與數(shù)據(jù)進行一次模2加。此外，由于S盒是固定的，因此Khafre加密算法要用更多層的變化才能得到與Khufu加密算法相同的安全性。