第11講--IDEA算法.ppt

IDEA分組密碼算法 王濱2005年3月23 IDEA分組密碼算法概述 XuejiaLai和JamesMassey于1990年提出了PES ProposedEncryptionStandard 推薦加密標(biāo)準(zhǔn) 分組密碼算法 為了抗擊差分密碼分析 設(shè)計者于1991年對PES作了改進(jìn) 并將改進(jìn)后的算法稱為IPES ImprovedProposedEncryptionStandard 改進(jìn)型推薦加密標(biāo)準(zhǔn) IPES于1992年改名為IDEA InternationalDataEncryptionAlgorithm 國際數(shù)據(jù)加密標(biāo)準(zhǔn) 算法的描述 分組長度 64比特密鑰長度 128比特迭代圈數(shù) 8圈 每圈6個子密鑰 附加一個輸出變換 4個子密鑰 子密鑰長度 16比特 52個子密鑰由128比特初始密鑰通過密鑰生成算法生成 使用的三種基本運(yùn)算 按位模2加 模216加法 模216 1乘法 整個運(yùn)算過程全部在16位子分組上進(jìn)行 因此該算法對16位處理器尤其有效 將待加密的64比特明文數(shù)據(jù)X分成4個16位子塊 作為算法第一圈的輸入 每圈有6個16比特圈子密鑰參與變換 經(jīng)過8圈迭代后得4個16比特子塊 再通過一個輸出變換得算法的輸出 級連起來即為密文Y 一 加密算法 所用符號的含義 xi i 1 2 3 4 是16比特明文子分組 yi i 1 2 3 4 是16比特密文子分組 zi i 1 52 16比特圈子密鑰 wi j i 1 2 8 j 1 2 3 4 是16比特中間結(jié)果 表示16比特的逐位異或運(yùn)算 表示16比特整數(shù)的模216加法運(yùn)算 表示16比特整數(shù)的模216 1乘法運(yùn)算 其中全零子塊用216代替 IDEA加密總體方案流程圖 IDEA第一圈的細(xì)節(jié) Fz5 z6 IDEA的輸出變換 二 子密鑰生成算法 首先將128比特初始密鑰從左到右分成8個16比特子塊 并將所得的8個子塊直接作為加密算法中最前面的8個子密鑰 然后將上述128比特密鑰循環(huán)左移25位 將其從左到右分成8個16比特子塊 得到隨后的8個子密鑰 重復(fù)這個過程 直到產(chǎn)生52個16比特子密鑰為止 三 脫密算法 這里z 1表示z的模216 1乘法逆 z表示z的模216加法逆 脫密密鑰與加密密鑰的對應(yīng)關(guān)系為 脫密算法與加密算法是相同的 只是在脫密過程中使用脫密密鑰 IDEA加 脫密子密鑰的關(guān)系 64bit明文X 子加密過程 輸出變換 循環(huán)8 循環(huán)1 循環(huán)1 子加密過程 變換 子加密過程 變換 輸出變換 64bit密文Y 循環(huán)1 子加密過程 變換 64bit密文Y 循環(huán)8 四 IDEA加 脫密變換的相似性 圖示的變換是IDEA的圈變換中的一部分 稱為共處理變換 設(shè)該變換的輸入為 輸出為 要證明IDEA加 脫密算法的相似性 只需證明共處理變換的4個輸入子塊經(jīng)過兩次共處理變換后的輸出仍然是它本身即可 若記乘加結(jié)構(gòu)輸出的左16比特為LMA 右16比特為RMA 則有下面4個式子 由于 則 這說明當(dāng)共處理變換以作為輸入 而子密鑰不變時 其輸出為 至此證明了IDEA分組密碼加 脫密變換的相似性 二 IDEA算法的設(shè)計原理 IDEA是一種使用128比特密鑰以64比特分組為單位加密數(shù)據(jù)的分組密碼 其設(shè)計目標(biāo)可以歸結(jié)為兩方面 一方面與密碼強(qiáng)度有關(guān) 另一方面與使用的方便性有關(guān) 一 密碼強(qiáng)度 IDEA的下列特性與其密碼強(qiáng)度有關(guān) 分組長度 分組長度應(yīng)足夠大 以抵抗統(tǒng)計分析 使用64比特的分組大小通常認(rèn)為已經(jīng)足夠強(qiáng) 另外使用密碼反饋操作方式可以進(jìn)一步加強(qiáng)算法這方面的強(qiáng)度 密鑰長度 密鑰長度應(yīng)足夠長 以抵抗密鑰窮盡攻擊 通過使用128比特的長度 在將來的很長時間里IDEA似乎在這方面都是安全的 關(guān)于混亂 密文應(yīng)以一種復(fù)雜的方式依賴于明文和密鑰 這樣做的目的是使確定密文的統(tǒng)計特性和明文的統(tǒng)計特性的依賴關(guān)系非常復(fù)雜 IDEA通過使用三種不同的操作達(dá)到該目的 而DES主要靠異或運(yùn)算及小的非線性S盒代替來實現(xiàn) 關(guān)于擴(kuò)散 每個明文比特都應(yīng)該影響每個密文比特 并且 每個密鑰比特都應(yīng)該影響每個密文比特 單個明文比特應(yīng)擴(kuò)散到許多密文比特才能隱藏明文的統(tǒng)計特性 在IDEA中 擴(kuò)散是由乘加結(jié)構(gòu) MA 實現(xiàn)的 MA的輸入有兩部分 一部分是由明文導(dǎo)出的兩個16比特數(shù)值 另一部分是兩個16比特子密鑰 計算機(jī)進(jìn)行的徹底檢查證明 第一圈輸出的每一比特依賴于輸入 明文部分和密鑰部分 的每一比特 經(jīng)8圈循環(huán)之后 可提供非常有效的擴(kuò)散 二 實現(xiàn)方面的考慮 IDEA的設(shè)計考慮到了方便硬件和軟件實現(xiàn) 通常由超大規(guī)模集成電路進(jìn)行的硬件實現(xiàn)的設(shè)計目標(biāo)是取得高速度 而軟件實現(xiàn)則有靈活和低價的優(yōu)點 使用子分組 密碼操作應(yīng)該在對于軟件來說很自然的子分組上進(jìn)行 具有這種特性的子分組包括8 16或32比特 IDEA使用16比特子分組 使用簡單操作 密碼操作應(yīng)該容易使用加法 移位等基本操作編程實現(xiàn) IDEA的三種操作符合該要求 其中最困難的模乘法也可以容易地用簡單的基本操作構(gòu)成 1 便于軟件實現(xiàn)的原則 模216 1乘法的具體運(yùn)算過程如下 1 如果a 0 則 2 若a b為兩個非零整數(shù) 則有 其中表示ab除以216所得的商 我們不妨用 ab h表示32比特數(shù)ab的高16位 ab l表示32比特數(shù)ab的低16位 則有 則 其中 加密和解密過程類似 加密和解密應(yīng)該只在使用密鑰的方式上有所不同 以便于同一個設(shè)備既可用于加密又可用于解密 和DES一樣 IDEA具有滿足該要求的結(jié)構(gòu) 規(guī)則的結(jié)構(gòu) 為