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

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

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

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

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

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

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

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

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

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

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

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

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

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

14、系成立：換，以下關(guān)系成立： y1=w81 z49 y2=w83 + z50y3=w82 + z51 y4=w84 z52解密過(guò)程中第解密過(guò)程中第1輪的第輪的第1步產(chǎn)生以下關(guān)系：步產(chǎn)生以下關(guān)系： j11=y1 u1 j12=y2 + u2j13=y3 + u3 j14=y4 u4將解密子密鑰由加密子密鑰表達(dá)并將將解密子密鑰由加密子密鑰表達(dá)并將y1，y2，y3,，y4代入以下關(guān)系，有代入以下關(guān)系，有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可見(jiàn)解密過(guò)程第可見(jiàn)解密過(guò)程第1輪第輪第1步的輸出等于加密過(guò)程最后步的輸出等于加密過(guò)程最后一步輸入中第一步輸入中第2個(gè)子段和第個(gè)子段和第3個(gè)子段交換后的值。從個(gè)子段交換后的值。從圖圖3.16，可得以下關(guān)系：，可得以下關(guān)系：w81=i81mar(i81i83，i82i84)w82=i83mar(i81i83，i82i84)w83=i82mal(i81i83，i82i84)w84=i84mal(i81i83，i82i84)其中其中mar(x,y)是是ma結(jié)構(gòu)輸入為結(jié)構(gòu)輸入為x和和y時(shí)的右邊輸時(shí)的右邊輸出，出，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所以解密過(guò)程第所以解