第11講--IDEA算法.ppt

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