分組演化密碼體制的安全性研究

分組演化密碼體制的安全性研究密碼技術(shù)是保障信息安全的關(guān)鍵技術(shù),信息的保密性,完整性,可控性和不可否認(rèn)性等安全要求,都離不開密碼技術(shù)的運(yùn)用.設(shè)計(jì)出高效安全的密碼系統(tǒng)是密碼學(xué)者們長(zhǎng)期追求的目標(biāo).對(duì)于一個(gè)密碼系統(tǒng),直觀上講,頻繁地更換密鑰帶來的不確定性能夠提高整個(gè)系統(tǒng)的安全強(qiáng)度.更一般地,若每次使用的密鑰都是隨機(jī)且相互獨(dú)立的,此密碼系統(tǒng)就是“一次一密”密碼系統(tǒng).眾所周知,“一次一密”密碼系統(tǒng)提供完善保密性,是絕對(duì)安全的密碼,攻擊者從密文得不到任何明文的信息,不管攻擊者截獲了多少密文,擁有多么豐富的計(jì)算資源,都無(wú)濟(jì)于事.不過“一次一密”密碼系統(tǒng)只在唯密文攻擊下是絕對(duì)安全的,而且它給密鑰的產(chǎn)生和管理都帶來嚴(yán)重的問題,故這種密碼系統(tǒng)并不實(shí)用.在過去的十五年里,演化計(jì)算,模擬退火,爬山算法等智能算法被廣泛用于設(shè)計(jì)密碼學(xué)性質(zhì)優(yōu)良的單/多輸出布爾函數(shù).受“一次一密”更換密鑰能夠增強(qiáng)密碼安全性以及日趨成熟的智能計(jì)算的啟發(fā),導(dǎo)師張煥國(guó)教授將密碼學(xué)與演化計(jì)算結(jié)合起來,借鑒生物進(jìn)化的思想,提出了演化密碼概念,并對(duì)DES分組密碼的核心部件S盒組進(jìn)行了實(shí)際演化,得到一種用演化方法設(shè)計(jì)S盒組的方法,并獲得了一批在抗差分分析和線性分析能力上均優(yōu)異的S盒組.此后,Clark給出了利用模擬退火生成高非線性度,低自相關(guān)的S盒的方法,Laskari等利用粒子群優(yōu)化算法對(duì)S盒的演化設(shè)計(jì)進(jìn)行了研究,馮登國(guó)教授給出了利用演化算法增加對(duì)合S盒的非線性度的方法,童言博士在其博士論文里詳細(xì)介紹了利用啟發(fā)式搜索設(shè)計(jì)非線性整形置換的方法.考慮到設(shè)計(jì)的復(fù)雜度水平,國(guó)內(nèi)外已有的關(guān)于演化密碼的研究大都集中在演化設(shè)計(jì)密碼算法中關(guān)鍵運(yùn)算部件.在演化密碼設(shè)計(jì)中,這些部件的密碼學(xué)性質(zhì)是以當(dāng)時(shí)已有攻擊的密碼學(xué)指標(biāo)作為適應(yīng)值函數(shù)進(jìn)行演化篩選的,從單個(gè)設(shè)計(jì)出的運(yùn)算部件上分析,這些部件的安全性水平較演化前有明顯提高或保持在一個(gè)相當(dāng)高的水平,足以滿足密碼學(xué)應(yīng)用的要求.作為演化密碼研究的重要補(bǔ)充,演化密碼體制的安全性研究既是考察演化密碼安全強(qiáng)度有力的評(píng)估標(biāo)準(zhǔn),也為密碼部件的演化設(shè)計(jì)提供了理論依據(jù).不過,關(guān)于演化密碼體制的安全性研究有兩個(gè)問題始終沒有得到徹底解決：理論考察演化密碼的安全性和定量分析核心部件的演化對(duì)整個(gè)密碼體制的安全性貢獻(xiàn).作為攻擊迭代型分組密碼最有效的兩種方法,差分密碼分析和線性密碼分析成功運(yùn)用于多種分組密碼體制,分組密碼體制抵抗這兩種攻擊的能力評(píng)估已成為評(píng)價(jià)其安全強(qiáng)度最基本,最重要的衡量標(biāo)準(zhǔn).鑒于上述研究背景,本文對(duì)分組演化密碼體制抵抗線性密碼分析和差分密碼分析的安全性水平進(jìn)行了深入的研究.重點(diǎn)考察了演化策略和演化次數(shù)對(duì)線性攻擊和差分攻擊分組演化密碼的數(shù)據(jù)復(fù)雜度,時(shí)間復(fù)雜度以及攻擊成功率的影響.線性密碼分析,差分密碼分析以及相關(guān)密碼分析等方法屬于統(tǒng)計(jì)密碼分析范疇.本文首先簡(jiǎn)要地介紹了統(tǒng)計(jì)密碼分析的基本框架,系統(tǒng)闡述了統(tǒng)計(jì)密碼分析的理論基礎(chǔ),重點(diǎn)介紹了獲取密鑰信息的理論基礎(chǔ)：基于對(duì)數(shù)似然比(LLR)和λ2統(tǒng)計(jì)方法的假設(shè)檢驗(yàn)理論以及次序統(tǒng)計(jì)量理論.隨后,本文對(duì)分組演化密碼對(duì)抗線性密碼分析的安全性水平進(jìn)行了分析.在這一部分,本文首先考察了一維線性密碼分析(算法2)的數(shù)據(jù)復(fù)雜度,時(shí)間復(fù)雜度,線性偏差和攻擊成功率的關(guān)系,比較了算法2攻擊演化密碼體制和固定算法密碼體制的數(shù)據(jù)復(fù)雜度和時(shí)間復(fù)雜度；然后從向量布爾函數(shù)的角度,利用對(duì)數(shù)似然比(LLR)的統(tǒng)計(jì)方法對(duì)Matsui最初提出的算法1和算法2進(jìn)行了擴(kuò)展,給出了利用多個(gè)線性逼近式進(jìn)行攻擊的多維線性密碼分析方法：算法1和算法2的LLR擴(kuò)展算法,并進(jìn)一步研究了影響這兩個(gè)擴(kuò)展算法攻擊成功率的相關(guān)因素,考察了攻擊過程中數(shù)據(jù)復(fù)雜度,時(shí)間復(fù)雜度,線性逼近式對(duì)應(yīng)的概率分布容量以及攻擊成功率的關(guān)系,并以此為基礎(chǔ)比較了這兩個(gè)擴(kuò)展算法攻擊演化密碼體制和固定算法密碼體制的數(shù)據(jù)復(fù)雜度和時(shí)間復(fù)雜度,論證了分組演化密碼對(duì)抗線性密碼分析的安全性水平高于固定算法密碼.接下來本文考察了分組演化密碼對(duì)抗差分密碼分析的安全性水平.這一部分內(nèi)容首先研究了差分攻擊過程中數(shù)據(jù)復(fù)雜度,時(shí)間復(fù)雜度,最佳差分特征概率和攻擊成功率的關(guān)系,比較了差分攻擊演化密碼體制和固定算法密碼體制的數(shù)據(jù)復(fù)雜度和時(shí)間復(fù)雜度；隨后利用χ2統(tǒng)計(jì)方法對(duì)一維差分密碼分析進(jìn)行了擴(kuò)展,給出了可以利用多個(gè)差分特征進(jìn)行攻擊的多重差分密碼分析方法,并給出了多重差分密碼分析的數(shù)據(jù)復(fù)雜度,時(shí)間復(fù)雜度,差分特征對(duì)應(yīng)的概率分布容量以及攻擊成功率之間的關(guān)系式,進(jìn)而比較了利用多重差分密碼分析攻擊分組演化密碼和固定算法密碼的數(shù)據(jù)復(fù)雜度和時(shí)間復(fù)雜度差異.這一部分的研究結(jié)果表明分組演化密碼對(duì)抗差分密碼分析的安全性水平高于固定算法密碼.作為對(duì)理論研究的補(bǔ)充和論證,本文最后以輕量分組密碼PRESENT為例,給出了演化PRESENT密碼,并全面考察了在使用線性密碼分析算法2,算法1和算法2的LLR擴(kuò)展,一維差分密碼