楊波現(xiàn)代密碼學第2版032PPT課件

1、第第3章章 分組密碼體制分組密碼體制 分組密碼概述分組密碼概述 數(shù)據(jù)加密標準數(shù)據(jù)加密標準 差分密碼分析與線性密碼分析差分密碼分析與線性密碼分析 分組密碼的運行模式分組密碼的運行模式 idea aes算法算法rijndael3.5 idea 來學嘉（來學嘉（x. j. lai）和）和j. l. massey提出的第提出的第1版版idea（international data encryption algorithm，國際數(shù)據(jù)加密算法）于國際數(shù)據(jù)加密算法）于1990年公布，當時稱為年公布，當時稱為pes（proposed encryption standard，建議加密標準）。，建議加密標準）。

2、1991年，在年，在biham和和shamir提出差分密碼分析之后，提出差分密碼分析之后，設計者推出了改進算法設計者推出了改進算法ipes，即改進型建議加密標，即改進型建議加密標準。準。1992年，設計者又將年，設計者又將ipes改名為改名為idea。這是。這是近年來提出的各種分組密碼中一個很成功的方案，近年來提出的各種分組密碼中一個很成功的方案，已在已在pgp中采用。中采用。3.5.1 設計原理設計原理 算法中明文和密文分組長度都是算法中明文和密文分組長度都是64比特，密鑰長比特，密鑰長128比特。其設計原理可從強度和實現(xiàn)比特。其設計原理可從強度和實現(xiàn)兩方面考慮兩方面考慮。 1. 密碼強度密

3、碼強度 算法的強度主要是通過有效的算法的強度主要是通過有效的混淆混淆和和擴散擴散特性而得特性而得以保證。以保證。 混淆混淆是通過使用以下是通過使用以下3種運算而獲得，種運算而獲得，3種運算都有種運算都有兩個兩個16比特的輸入和一個比特的輸入和一個16比特的輸出：比特的輸出： 逐比特異或，表示為逐比特異或，表示為。 模模216（即（即65536）整數(shù)加法，表示為）整數(shù)加法，表示為+ ，其輸入，其輸入和輸出作為和輸出作為16位無符號整數(shù)處理。位無符號整數(shù)處理。 模模216+1（即（即65537）整數(shù)乘法，表示為）整數(shù)乘法，表示為 ，其輸，其輸入、輸出中除入、輸出中除16位全為位全為0作為作為216

4、處理外，其余都作處理外，其余都作為為16位無符號整數(shù)處理。例如位無符號整數(shù)處理。例如0000000000000000 1000000000000000=1000000000000001這是因為這是因為216215 mod (216+1)=215+1。 表表3.6給出了操作數(shù)為給出了操作數(shù)為2比特長時比特長時3種運算的運算表。種運算的運算表。在以下意義下，在以下意義下，3種運算是不兼容的：種運算是不兼容的： 3種運算中任意兩種都不滿足分配律，例如種運算中任意兩種都不滿足分配律，例如a + （b c）(a + b ) (a + c ) 3種運算中任意兩種都不滿足結合律，例如種運算中任意兩種都不滿足

5、結合律，例如a +（b + c） (a + b ) + c 三種運算結合起來使用可對算法的輸入提供復雜的三種運算結合起來使用可對算法的輸入提供復雜的變換，從而使得對變換，從而使得對idea的密碼分析比對僅使用異或的密碼分析比對僅使用異或運算的運算的des更為困難。更為困難。 算法中擴散是由稱為算法中擴散是由稱為乘加乘加（multiplication/addition, ma）結構的基本單元）結構的基本單元實現(xiàn)的。實現(xiàn)的。 該結構的輸入是兩個該結構的輸入是兩個16比特的子段和兩個比特的子段和兩個16比特比特的子密鑰，輸出也為兩個的子密鑰，輸出也為兩個16比特的子段。比特的子段。 這一結構在算法中

6、重復使用了這一結構在算法中重復使用了8次，獲得了非常有次，獲得了非常有效的擴散效果。效的擴散效果。圖圖3.14 ma結構結構2. 實現(xiàn)實現(xiàn) idea可方便地通過軟件和硬件實現(xiàn)?？煞奖愕赝ㄟ^軟件和硬件實現(xiàn)。 軟件實現(xiàn)采用軟件實現(xiàn)采用16比特子段處理，可通過使用容易比特子段處理，可通過使用容易編程的加法、移位等運算實現(xiàn)算法的編程的加法、移位等運算實現(xiàn)算法的3種運算。種運算。 硬件由于加、解密相似，差別僅為使用密鑰的方硬件由于加、解密相似，差別僅為使用密鑰的方式，因此可用同一器件實現(xiàn)。再者，算法中規(guī)則的式，因此可用同一器件實現(xiàn)。再者，算法中規(guī)則的模塊結構，可方便模塊結構，可方便vlsi的實現(xiàn)。的實現(xiàn)

7、。3.5.2 加密過程加密過程 如圖如圖3.15所示，加密過程由連續(xù)的所示，加密過程由連續(xù)的8輪迭代和一個輸輪迭代和一個輸出變換組成；出變換組成； 算法將算法將64比特的明文分組分成比特的明文分組分成4個個16比特的子段，每比特的子段，每輪迭代以輪迭代以4個個16比特的子段作為輸入，輸出也為比特的子段作為輸入，輸出也為4個個16比特的子段；比特的子段； 最后的輸出變換也產(chǎn)生最后的輸出變換也產(chǎn)生4個個16比特的子段，鏈接起來比特的子段，鏈接起來后形成后形成64比特的密文分組。比特的密文分組。 每輪迭代還需使用每輪迭代還需使用6個個16比特的子密鑰，最后的輸出比特的子密鑰，最后的輸出變換需使用變換

8、需使用4個個16比特的子密鑰，所以子密鑰總數(shù)為比特的子密鑰，所以子密鑰總數(shù)為52。 圖圖3.15的右半部分表示由初始的的右半部分表示由初始的128比特密鑰產(chǎn)生比特密鑰產(chǎn)生52個子密鑰的子密鑰產(chǎn)生器。個子密鑰的子密鑰產(chǎn)生器。圖圖3.15 idea的加密框圖的加密框圖 1. 輪結構輪結構 圖圖3.16是是idea第第1輪的結構示意圖，以后各輪也都輪的結構示意圖，以后各輪也都是這種結構，但所用的子密鑰和輪輸入不同。從結是這種結構，但所用的子密鑰和輪輸入不同。從結構圖可見，構圖可見，idea不是傳統(tǒng)的不是傳統(tǒng)的feistel密碼結構密碼結構。每輪。每輪開始時有一個變換，該變換的輸入是開始時有一個變換，

9、該變換的輸入是4個子段和個子段和4個個子密鑰，變換中的運算是兩個乘法和兩個加法，輸子密鑰，變換中的運算是兩個乘法和兩個加法，輸出的出的4個子段經(jīng)過異或運算形成了兩個個子段經(jīng)過異或運算形成了兩個16比特的子比特的子段作為段作為ma結構的輸入。結構的輸入。ma結構也有兩個輸入的結構也有兩個輸入的子密鑰，輸出是兩個子密鑰，輸出是兩個16比特的子段。比特的子段。圖圖3.16 idea第第1輪的輪結構輪的輪結構圖圖3.17 idea的輸出變換的輸出變換2. 子密鑰的產(chǎn)生子密鑰的產(chǎn)生 加密過程中加密過程中52個個16比特的子密鑰是由比特的子密鑰是由128比特的加比特的加密密鑰按如下方式產(chǎn)生的：密密鑰按如下

10、方式產(chǎn)生的： 前前8個子密鑰個子密鑰z1，z2，z8直接從加密密鑰中取，即直接從加密密鑰中取，即z1取前取前16比特比特（最高有效位），（最高有效位），z2取下面的取下面的16比特，依次類推。比特，依次類推。 然后加密密鑰循環(huán)左移然后加密密鑰循環(huán)左移25位，再取下面位，再取下面8個子密鑰個子密鑰z9，z10，z16，取法與，取法與z1，z2，z8的取法相的取法相同。這一過程重復下去，直到同。這一過程重復下去，直到52子密鑰都被產(chǎn)生為子密鑰都被產(chǎn)生為止。止。3. 解密過程解密過程 解密過程和加密過程基本相同，但子密鑰的選取不解密過程和加密過程基本相同，但子密鑰的選取不同。解密子密鑰同。解密子密鑰

11、u1，u2，u52是由加密子密鑰是由加密子密鑰按如下方式得到（將加密過程最后一步的輸出變換按如下方式得到（將加密過程最后一步的輸出變換當作第當作第9輪）：輪）： 第第i(i=1,9)輪解密的前輪解密的前4個子密鑰由加密過程第個子密鑰由加密過程第(10-i)輪的前輪的前4個子密鑰得出：個子密鑰得出：其中第其中第1和第和第4個解密子密鑰取為相應的第個解密子密鑰取為相應的第1和第和第4個加密子密鑰的模個加密子密鑰的模216+1乘法逆元，第乘法逆元，第2和第和第3個子密鑰個子密鑰的取法為：當輪數(shù)的取法為：當輪數(shù)i=2,8時，取為相應的第時，取為相應的第3個和第個和第2個加密子密鑰的模個加密子密鑰的模2

12、16加法逆元。加法逆元。i=1和和9時，取為相時，取為相應的第應的第2個和第個和第3個加密子密鑰的模個加密子密鑰的模216加法逆元。加法逆元。 第第i(i=1,8)輪解密的后兩個子密鑰等于加密過程輪解密的后兩個子密鑰等于加密過程第第(9-i)輪的后兩個子密鑰。輪的后兩個子密鑰。 表表3.7是對以上關系的總結。其中是對以上關系的總結。其中zj的模的模216+1乘法乘法逆元為逆元為z-1j，滿足，滿足（見表（見表3.7）zj z-1j=1mod(216+1) 因因216+1是一素數(shù)，所以每一個不大于是一素數(shù)，所以每一個不大于216的非的非0整數(shù)整數(shù)都有一個惟一的模都有一個惟一的模216+1乘法逆元

13、。乘法逆元。zj的模的模216加法逆加法逆元為元為-zj，滿足：，滿足： -zj + zj=0 mod (216) 下面驗證解密過程的確可以得到正確的結果。圖下面驗證解密過程的確可以得到正確的結果。圖3.18中左邊為加密過程，由上至下，右邊為解密過中左邊為加密過程，由上至下，右邊為解密過程，由下至上。將每一輪進一步分為兩步，第程，由下至上。將每一輪進一步分為兩步，第1步步是變換，其余部分作為第是變換，其余部分作為第2步，稱為子加密。步，稱為子加密。圖圖3.18 idea加密和解密框圖加密和解密框圖現(xiàn)在從下往上考慮。對加密過程的最后一個輸出變現(xiàn)在從下往上考慮。對加密過程的最后一個輸出變換，以下關

14、系成立：換，以下關系成立： y1=w81 z49 y2=w83 + z50y3=w82 + z51 y4=w84 z52解密過程中第解密過程中第1輪的第輪的第1步產(chǎn)生以下關系：步產(chǎn)生以下關系： j11=y1 u1 j12=y2 + u2j13=y3 + u3 j14=y4 u4將解密子密鑰由加密子密鑰表達并將將解密子密鑰由加密子密鑰表達并將y1，y2，y3,，y4代入以下關系，有代入以下關系，有j11=y1 z-149= w81 z49 z-149= w81j12=y2 + -z50=w83 + z50 + -z50=w83j13=y3 + -z51=w82 + z51 + -z51=w82j

15、14=y4 z-152= w84 z52 z-152= w84可見解密過程第可見解密過程第1輪第輪第1步的輸出等于加密過程最后步的輸出等于加密過程最后一步輸入中第一步輸入中第2個子段和第個子段和第3個子段交換后的值。從個子段交換后的值。從圖圖3.16，可得以下關系：，可得以下關系：w81=i81mar(i81i83，i82i84)w82=i83mar(i81i83，i82i84)w83=i82mal(i81i83，i82i84)w84=i84mal(i81i83，i82i84)其中其中mar(x,y)是是ma結構輸入為結構輸入為x和和y時的右邊輸時的右邊輸出，出，mal(x,y)是左邊輸出。則是左邊輸出。則v11=j11mar(j11j13,j12j14) =w81mar(w81w82,w83w84) =i81mar(i81i83,i82i84) mar i81mar(i81i83,i82i84)i83 mar(i81 i83,i82i84), i82 mal(i81i83,i82i84) i84 mal(i81i83,i82i84) =i81mar(i81i83,i82i84) mar(i81i83,i82i84) =i81類似地，可有類似地，可有v12=i83 v13=i82 v14=i84所以解密過程第所以解