Multi2算法的線性分析.pdf

1、由日立公司開發(fā)的MULTI2(Multi-MediaEncryptionAlgorithm2)算法是一個主要用于多媒體加密的分組密碼。該算法于1994年在ISO/IEC（國際標準化組織/國際電工技術(shù)委員會）9979注冊，并在美國和日本申請了專利保護。該算法采用Feistel結(jié)構(gòu)，其分組長度64比特，數(shù)據(jù)密鑰長度64比特，系統(tǒng)密鑰長度256比特。在ISO標準中建議加解密輪數(shù)至少為32輪，在ISDB標準中使用的也是這個輪數(shù)。密鑰擴展算法將數(shù)

2、據(jù)密鑰和系統(tǒng)密鑰擴展為長度為256比特的加密密鑰。加密時加密密鑰分成8個32比特的子密鑰在各輪函數(shù)中使用，8輪以后密鑰重復使用。加密流程中使用了4個輪函數(shù)π1、π2、π3、π4，并依此順序循環(huán)重復使用。
　　本文學習了《CryptanalysisoftheISDBScramblingAlgorithm(MULTI2)》和《ImprovedLinearAnalysisonBlockCipherMULTI2》兩篇文章中關于MULTI2

3、算法的線性分析。兩篇文章中給出了輪函數(shù)的一些高相關度的線性路線，但沒有給出具體的尋找方式。其中最高的兩條四輪路線相關度分別是2-5.7和2-2，在《ImprovedLinearAnalysisonBlockCipherMULTI2》中，四輪區(qū)分器所需的數(shù)據(jù)復雜度為25，攻擊的最高輪數(shù)為28輪，所用的時間復雜度為2123.2，數(shù)據(jù)復雜度為237。
　　本文用概率方法分別討論了π2、π4函數(shù)的弱密鑰條件下的線性特性。對于π2函數(shù)，在弱

4、密鑰空間K2k=｛k=(k31，k30，…，k0)|k30=k29=k28=k27=k25=k25=k24=0｝下，若輸入掩碼為α=0x9c000001，輸出掩碼為β=0x00000001，相關度|Corπ2(α，β）|較大。經(jīng)過大量的實驗測試得到相關度|Corπ2(α，β）|＞2-1。并且在實驗中我們還發(fā)現(xiàn)，當輸入掩碼為α'=0x90000001，0x96000001，0x9a000001，輸出掩碼為β=0x00000時，同樣有高概率

5、相關度|Corπ2(α'，β)]＞2-1.5。對于π4函數(shù)，在弱密鑰空間K4k=｛k=(k31，k30，…，k0)|k29=k28｝下，若輸入掩碼為α=0x40000001，輸出掩碼為β=0x00000001，則相關度|Corπ4(α'，β）|≥2-1。
　　本文還借用了頻譜理論中的Walsh譜理論，特別是廣義Walsh譜，將其與線性分析相結(jié)合，更一般性的對類π4函數(shù)的線性性質(zhì)進行了譜分析。給出了函數(shù)模型y=fk(r)的定義:x=

6、r+k，y=（x＜＜＜m）+x+l。得到了密鑰與相關度的量化關系。由此結(jié)論可以根據(jù)相關度的統(tǒng)計結(jié)果直接計算對應的密鑰值。
　　本文最后用活動函數(shù)的概念去分析四輪線性路徑可能的模式。然后結(jié)合上面得到的弱密鑰條件下的高概率相關度對應的掩碼，得到了一個高概率的四輪線性路線。其中輸入掩碼為(α=0x9c000000，β=0x9c000001)，輸出掩碼為(y=0x00000000，δ=0x40000001），相關度|Corπ1,π2,π3