1、網絡與信息安全網絡與信息安全密碼學基礎密碼學基礎(一一)潘愛民，北京大學計算機研究所潘愛民，北京大學計算機研究所http:/ e: (x,k) y, y = e(x,k)xykeyxkdu解密解密: d: (y,k) x, x = d(y,k)對稱加密算法研究對稱加密算法研究u對稱加密算法的特點對稱加密算法的特點算法強度足夠算法強度足夠安全性依賴于密鑰，不是算法安全性依賴于密鑰，不是算法速度快速度快u兩門學科兩門學科密碼學密碼學密碼分析密碼分析用對稱加密算法建立起來的安全通訊用對稱加密算法建立起來的安全通訊密碼學密碼學u三種考慮角度三種考慮角度（1）從明文到密文的變換）從明文到密文的變換替換替

2、換(substitution)置換置換(transposition)（2）鑰匙的數目）鑰匙的數目對稱、單鑰加密法對稱、單鑰加密法雙鑰、公鑰加密雙鑰、公鑰加密（3）明文的處理方式）明文的處理方式分組加密（塊加密算法）分組加密（塊加密算法）流方式加密流方式加密密碼分析密碼分析u發現發現x和和k的過程被稱為密碼分析的過程被稱為密碼分析分析的策略取決于加密的技術以及可利用的分析的策略取決于加密的技術以及可利用的信息，在加密算法設計和攻擊時都需要用到信息，在加密算法設計和攻擊時都需要用到的技術的技術u根據可利用信息的不同，可分為根據可利用信息的不同，可分為5類：類：（1）只有密文）只有密文（2）已知部分

3、明文）已知部分明文-密文對密文對（3）選擇明文）選擇明文（4）選擇密文）選擇密文* （1）（）（2）（）（3）常見、（）常見、（4）不常見）不常見加密算法的有效性加密算法的有效性uunconditionally secure，絕對安全？，絕對安全？永不可破，是理想情況，理論上不可破，密永不可破，是理想情況，理論上不可破，密鑰空間無限，在已知密文條件下，方程無解鑰空間無限，在已知密文條件下，方程無解。但是我們可以考慮：。但是我們可以考慮：破解的代價超過了加密信息本身的價值破解的代價超過了加密信息本身的價值破解的時間超過了加密信息本身的有效期破解的時間超過了加密信息本身的有效期ucomputati

4、onally secure，滿足上述兩個條件滿足上述兩個條件直覺：什么是一個好的加密算法直覺：什么是一個好的加密算法u假設密碼假設密碼(password)k是固定的是固定的u明文和密文是一個映射關系：單射，即明文和密文是一個映射關系：單射，即 ek(x1) != ek(x2) if x1 != x2u通常情況是：明文非常有序通常情況是：明文非常有序u好的密碼條件下，我們期望得到什么樣的好的密碼條件下，我們期望得到什么樣的密文密文隨機性隨機性u如何理解隨機性如何理解隨機性靜態：特殊的點靜態：特殊的點動態：小的擾動帶來的變化不可知動態：小的擾動帶來的變化不可知考慮設計一個加密算法考慮設計一個加密算

5、法u打破明文本身的規律性打破明文本身的規律性隨機性隨機性(可望不可及可望不可及)非線性非線性(一定要一定要)統計意義上的規律統計意義上的規律u多次迭代多次迭代迭代是否會增加變換的復雜性迭代是否會增加變換的復雜性是否存在通用的框架，用于迭代是否存在通用的框架，用于迭代u復雜性帶來密碼分析的困難和不可知性復雜性帶來密碼分析的困難和不可知性實踐的檢驗和考驗實踐的檢驗和考驗已有密碼算法的討論已有密碼算法的討論u經典密碼算法經典密碼算法替換技術替換技術置換技術置換技術u現代密碼算法現代密碼算法des其他密碼算法其他密碼算法uaes密碼算法密碼算法rijndael經典密碼算法經典密碼算法u替換技術替換技術

6、caesar加密制加密制單表替換加密制單表替換加密制playfair加密制加密制hill加密制加密制多表加密制多表加密制u置換技術置換技術改變字母的排列順序，比如改變字母的排列順序，比如用對角線方式寫明文，然后按行重新排序用對角線方式寫明文，然后按行重新排序寫成一個矩陣，然后按照新的列序重新排列寫成一個矩陣，然后按照新的列序重新排列u轉輪加密體制轉輪加密體制u多步結合多步結合經典密碼算法特點經典密碼算法特點u要求的計算強度小要求的計算強度小udes之前之前u以字母表為主要加密對象以字母表為主要加密對象u替換和置換技術替換和置換技術u數據安全基于算法的保密數據安全基于算法的保密u密碼分析方法基于

7、明文的可讀性以及字母密碼分析方法基于明文的可讀性以及字母和字母組合的頻率特性和字母組合的頻率特性現代密碼算法現代密碼算法udes(data encryption standard)uideaublowfishurc5ucast-128u分組密碼算法設計指導原則分組密碼算法設計指導原則udiffusion(發散發散)小擾動的影響波及到全局小擾動的影響波及到全局密文沒有統計特征，明文一位影響密文的多密文沒有統計特征，明文一位影響密文的多位，增加密文與明文之間關系的復雜性位，增加密文與明文之間關系的復雜性uconfusion(混淆混淆)強調密鑰的作用強調密鑰的作用增加密鑰與密文之間關系的復雜性增加密

8、鑰與密文之間關系的復雜性u結構簡單、易于分析結構簡單、易于分析feistel分組加密算法結構之動機分組加密算法結構之動機u分組加密算法，一一映射分組加密算法，一一映射u當當n較小時，等價于替換變換較小時，等價于替換變換u當當n較大時，比如較大時，比如n=64，無法表達這樣的，無法表達這樣的任意變換。任意變換。ufeistel結構很好地解決了二者之間的矛盾結構很好地解決了二者之間的矛盾feistel分組加密算法結構之思想分組加密算法結構之思想u基本思想：用簡單算法的乘積來近似表達基本思想：用簡單算法的乘積來近似表達大尺寸的替換變換大尺寸的替換變換u多個簡單算法的結合得到的加密算法比任多個簡單算法

9、的結合得到的加密算法比任何一個部分算法都要強何一個部分算法都要強u交替使用替換變換和排列交替使用替換變換和排列(permutation)u混淆混淆(confusion)和發散和發散(diffusion)概念的概念的應用應用feistel結構圖結構圖feistel結構定義結構定義u加密加密: li = ri-1; ri = li-1 f(ri-1,ki)u解密解密: ri-1 = li li-1 = ri f(ri-1,ki) = ri f(li,ki)feistel分組加密算法特點分組加密算法特點u分組大小。越大安全性越高，但速度下降，分組大小。越大安全性越高，但速度下降，64比較合理比較合理

10、u密鑰位數。越大安全性越高，但速度下降，密鑰位數。越大安全性越高，但速度下降，64廣泛使用，但現在已經不夠用廣泛使用，但現在已經不夠用128u步數，典型步數，典型16步步u子鑰產生算法。算法越復雜，就增加密碼分析子鑰產生算法。算法越復雜，就增加密碼分析的難度的難度u每一步的子函數。函數越復雜，就增加密碼分每一步的子函數。函數越復雜，就增加密碼分析的難度析的難度u快速軟件實現，包括加密和解密算法快速軟件實現，包括加密和解密算法u易于分析。便于掌握算法的保密強度以及擴展易于分析。便于掌握算法的保密強度以及擴展辦法。辦法。feistel分組分組加密算法加密算法之解密算法之解密算法feistel分組加

11、密算法之解密算法推導分組加密算法之解密算法推導des算法算法u1977年由美國的標準化局年由美國的標準化局(nbs，現為，現為nist)采納采納u64位分組、位分組、56位密鑰位密鑰u歷史：歷史：ibm在在60年代啟動了年代啟動了lucifer項目，當時的項目，當時的算法采用算法采用128位密鑰位密鑰改進算法，降低為改進算法，降低為56位密鑰，位密鑰，ibm提交給提交給nbs(nist)，于是產生，于是產生desdes算法基本結構算法基本結構des: 每一輪每一輪li = ri-1 ri = li-1 f(ri-1,ki)des: function fexpansion: 32 48s-box

12、: 6 4 permutationdes: 32位到位到48位的擴展表位的擴展表32 | 01 02 03 04 | 0504 | 05 06 07 08 | 0908 | 09 10 11 12 | 1312 | 13 14 15 16 | 1716 | 17 18 19 20 | 2120 | 21 22 23 24 | 2524 | 25 26 27 28 | 2928 | 29 30 31 32 | 01des: s-boxs(1):14 04 13 01 02 15 11 08 03 10 06 12 05 09 00 0700 15 07 04 14 02 13 01 10 06

13、12 11 09 05 03 0804 01 14 08 13 06 02 11 15 12 09 07 03 10 05 0015 12 08 02 04 09 01 07 05 11 03 14 10 00 06 13des: permutation16 07 20 21 29 12 28 1701 15 23 26 05 18 31 1002 08 24 14 32 27 03 0919 13 30 06 22 11 04 25des之每步密鑰產生過程之每步密鑰產生過程upc-1在第一步之前在第一步之前upc2u左移位數目表左移位數目表1或者或者2位位des的強度的強度u56位密鑰的使用

14、位密鑰的使用理論上的強度，理論上的強度，97年年$100000的機器可以在的機器可以在6小時內用窮舉法攻破小時內用窮舉法攻破des實際攻破的例子，實際攻破的例子，97年年1月提出挑戰，有人利月提出挑戰，有人利用用internet的分布式計算能力，組織志愿軍連的分布式計算能力，組織志愿軍連接了接了70000多個系統在多個系統在96天后攻破天后攻破udes算法的本質算法的本質關鍵在于關鍵在于8個個s-boxu針對針對des的密碼分析的密碼分析差分分析法差分分析法線性分析法線性分析法差分分析法差分分析法u屬于選擇明文攻擊屬于選擇明文攻擊u基本思想：通過分析特定明文差對結果密基本思想：通過分析特定明文

15、差對結果密文差的影響來獲得可能性最大的密鑰文差的影響來獲得可能性最大的密鑰u差分在差分在des的的16步加密過程中的傳遞，每步加密過程中的傳遞，每一個一個s-box對于差分傳遞的概率特性對于差分傳遞的概率特性u子密鑰不影響每一步的輸入差分，但是影子密鑰不影響每一步的輸入差分，但是影響輸出的差分響輸出的差分u針對每一個針對每一個des步驟，用差分法可以推導步驟，用差分法可以推導出該步的密鑰出該步的密鑰每一步的差分分析法每一步的差分分析法針對針對des的密碼分析的密碼分析u差分分析法差分分析法247對選擇明文，經過對選擇明文，經過247量級的計算可攻破量級的計算可攻破u線性分析法線性分析法思想：用

16、線性近似描述思想：用線性近似描述des變換變換根據根據247已知明文，可以找到已知明文，可以找到des的密鑰的密鑰二重二重des c = ek2(ek1(p) p = dk1(dk2(c)針對兩重分組加密算法的針對兩重分組加密算法的三重三重desc=ek3(dk2(ek1(p) p=dk1(ek2( dk3(c)分組密碼的用法分組密碼的用法u電子簿模式電子簿模式(electronic codebook mode)ecbu密碼塊鏈接密碼塊鏈接(cipher block chaining)cbcu密碼反饋方式密碼反饋方式(cipher feedback)cfbu輸出反饋方式輸出反饋方式(outpu

17、t feedback)ofb電子簿模式電子簿模式ecbu相同明文相同明文相同密文相同密文u同樣信息多次出現造同樣信息多次出現造成泄漏成泄漏u信息塊可被替換信息塊可被替換u信息塊可被重排信息塊可被重排u密文塊損壞密文塊損壞僅僅對應對應明文塊損壞明文塊損壞u適合于傳輸短信息適合于傳輸短信息密碼塊鏈接密碼塊鏈接cbcu需要共同的初始化需要共同的初始化向量向量ivu相同明文相同明文不同密不同密文文u初始化向量初始化向量iv可以可以用來改變第一塊用來改變第一塊u密文塊損壞密文塊損壞兩兩明明文文塊塊損壞損壞u安全性好于安全性好于ecb密碼反饋方式密碼反饋方式cfbucfb:分組密碼分組密碼流密碼流密碼u需

18、要共同的移位寄存器初始值需要共同的移位寄存器初始值ivu對于不同的消息，對于不同的消息，iv必須唯一必須唯一u一個單元損壞影響多個單元一個單元損壞影響多個單元: (w+j-1)/j w為分組加密塊大小，為分組加密塊大小，j為流單元位數為流單元位數輸出反饋方式輸出反饋方式ofbuofb:分組密碼分組密碼流密碼流密碼u需要共同的移位寄存器初始值需要共同的移位寄存器初始值ivu一個單元損壞只影響對應單元一個單元損壞只影響對應單元分組密碼與序列分組密碼與序列(流流)密碼密碼u定義：定義：分組密碼分組密碼(block cipher)是對一個大的明文塊是對一個大的明文塊(block)進行固定變換的操作進行

19、固定變換的操作序列密碼序列密碼(stream cipher)也叫流密碼，是對也叫流密碼，是對單個明文位單個明文位(組組)的隨時間變換的操作的隨時間變換的操作u相互轉換相互轉換u序列密碼序列密碼異或異或one-time pad其他的密碼算法其他的密碼算法uideaublowfishurc5ucast-128urc2urc4idea算法算法u90年首次出現，年首次出現，91年修訂，年修訂，92公布細節公布細節u有望取代有望取代desu128位密鑰，位密鑰，64位分組位分組u設計目標可從兩個方面考慮設計目標可從兩個方面考慮加密強度加密強度易實現性易實現性idea設計思想設計思想u得到得到confus

20、ion的途徑的途徑按位異或按位異或以以216(65536)為模的加法為模的加法以以216+1 (65537)為模的乘法為模的乘法互不滿足分配律、結合律互不滿足分配律、結合律u得到得到diffusion的途徑的途徑乘加乘加(ma)結構結構u實現上的考慮實現上的考慮軟件和硬件實現上的考慮軟件和硬件實現上的考慮idea加密算法加密算法idea每一輪每一輪blowfish算法算法u作者為作者為bruce schneier93ublowfish算法特點算法特點采用了采用了feistel結構，結構，16輪輪快速：快速：18時鐘周期一個字節時鐘周期一個字節緊湊：消耗不到緊湊：消耗不到5k內存內存簡單：結構簡

21、單，易于實現和判定算法強度簡單：結構簡單，易于實現和判定算法強度安全性可變：通過選擇不同的密鑰長度選擇安全性可變：通過選擇不同的密鑰長度選擇不同的安全級別。從不同的安全級別。從32位到位到32*14=448位不位不等等子密鑰產生過程復雜，一次性子密鑰產生過程復雜，一次性blowfish算法討論算法討論ublowfish算法可能是最難攻破的傳統加算法可能是最難攻破的傳統加密算法，因為密算法，因為s-box密鑰相關密鑰相關u算法本身的特點算法本身的特點由于子密鑰和由于子密鑰和s-box產生需要執行產生需要執行521個個blowfish加密算法，所以不適合于加密算法，所以不適合于密鑰頻繁變化的應用場

22、合密鑰頻繁變化的應用場合子密鑰和子密鑰和s-box產生可以保存起來產生可以保存起來u與與feistel分組密鑰算法不同，每一步的兩分組密鑰算法不同，每一步的兩個部分都參與運算，不是簡單的傳遞個部分都參與運算，不是簡單的傳遞u密鑰變長帶來靈活性密鑰變長帶來靈活性u速度快，在同類算法中相比較是最快的速度快，在同類算法中相比較是最快的rc5加密算法加密算法u作者為作者為ron rivestu算法特點算法特點三個參數三個參數參數參數w：表示字長，：表示字長，rc5加密兩字長分組，可用加密兩字長分組，可用值為值為16、32、64參數參數r：表示輪數，可用值：表示輪數，可用值0,1,255參數參數b：表示

23、密鑰：表示密鑰k的字節數，可用值的字節數，可用值0,1,255rc5版本：版本：rc5-w/r/b算法作者建議標定版本為算法作者建議標定版本為rc5-32/12/16rc5加密算法加密算法u三個基本運算三個基本運算字的加法，模字的加法，模2w +按位異或按位異或 左循環移位左循環移位 u算法：算法：le0 = a + s0re0 = b + s1for i = 1 to r dolei = (lei-1 rei-1) rei-1 + s2*irei = (rei-1 lei) lei + s2*i+1rc5加、解密算法結構加、解密算法結構cast-128加密算法加密算法urfc 214497定

24、義定義u密鑰密鑰48-128位，位，8位增量位增量u16輪輪feistel分組結構分組結構u64位分組位分組u特殊處：特殊處：每一步兩個子密鑰每一步兩個子密鑰每一步的每一步的f不同不同cast-128每步細節圖每步細節圖cast-128算法之討論算法之討論us-box是固定的，但設計時盡量保證了非是固定的，但設計時盡量保證了非線性。設計者認為，選擇一個好的非線性線性。設計者認為，選擇一個好的非線性s-box比隨機的比隨機的s-box更可取更可取u子密鑰的產生過程采用了與其他算法不同子密鑰的產生過程采用了與其他算法不同的產生法來加強其強度。目標是對抗已知的產生法來加強其強度。目標是對抗已知明文攻

25、擊。明文攻擊。blowfish和和rc5算法使用了不算法使用了不同的技術來保證這一點。同的技術來保證這一點。uf函數具有好的函數具有好的confusion、diffusion等特等特性。子密鑰相關、輪數相關增加了強度。性。子密鑰相關、輪數相關增加了強度。rc2加密算法加密算法u設計者設計者ron rivestu分組長度分組長度64位，密鑰長度位，密鑰長度8到到1024位位u適合于在適合于在16位微處理器上實現位微處理器上實現urc2在在s/mime中用到的密鑰為中用到的密鑰為40、64、128位不等位不等rc4流加密算法流加密算法u設計者設計者ron rivestu工作方式工作方式ofbu算法

26、特點：算法特點：簡單、快速簡單、快速隨機序列的產生，用到隨機序列的產生，用到8*8的的s盒盒aes介紹介紹u1997年年nist宣布征集宣布征集aes算法算法要求要求: 與三重與三重des比，要快且至少一樣安全比，要快且至少一樣安全,分組分組128位位,密鑰密鑰128/192/256位位u1998年確定第一輪年確定第一輪15個候選者個候選者u1999年確定第二輪五個候選者年確定第二輪五個候選者: mars, rc6, rijndael, serpent, twofishu2000年底年底rijndael勝出勝出rijndael簡介簡介u不屬于不屬于feistel結構結構u加密、解密相似但不對稱

27、加密、解密相似但不對稱u支持支持128/192/256(/32=nb)數據塊大小數據塊大小u支持支持128/192/256(/32=nk)密鑰長度密鑰長度u有較好的數學理論作為基礎有較好的數學理論作為基礎u結構簡單、速度快結構簡單、速度快rijndael簡介簡介(續續)u數據數據/密鑰的矩陣表示密鑰的矩陣表示a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35k00k01k02k03k10k11k12k13k20k21k22k23k30k31k32k33nrnb=4nb=6nb=8nk=4 10 12

28、14nk=6 12 12 14nk=8 14 14 14u輪數輪數rijndael算法結構算法結構u假設：假設：state表示數據，以及每一輪的中間結果表示數據，以及每一輪的中間結果roundkey表示每一輪對應的子密鑰表示每一輪對應的子密鑰u算法如下：算法如下：第一輪之前執行第一輪之前執行addroundkey(state,roundkey)round(state,roundkey) bytesub(state);shiftrow(state);mixcolumn(state);addroundkey(state,roundkey); finalround(state,roundkey) b

29、ytesub(state);shiftrow(state);addroundkey(state,roundkey); rijndael: addroundkey操作操作u按字節在按字節在gf(28)上相加上相加(xor)a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35k00k01k02k03k04k05k10k11k12k13k14k15k20k21k22k23k24k25k30k31k32k33k34k35 =b00b01b02b03b04b05b10b11b12b13b14b15b20b21b2

30、2b23b24b25b30b31b32b33b34b35rijndael: bytesub操作操作ubytesub(s-box)非線性、可逆非線性、可逆u獨立作用在每個字節上獨立作用在每個字節上u先取先取gf(28)上乘法的逆上乘法的逆,再經過再經過gf(2)上一個仿射變換上一個仿射變換a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35b00b01b02b03b04b05b10b11b12b13b14b15b20b21b22b23b24b25b30b31b32b33b34b35s-boxaijbijr

31、ijndael: shiftrow操作操作u第一行保持不變第一行保持不變,其他行內的字節循環移位其他行內的字節循環移位rijndael: mixcolumn操作操作u列作為列作為gf(28)上多項式乘以多項式上多項式乘以多項式c(x)多項式多項式c(x) = 03x3+ 01x2+ 01x+ 02 c-1(x) = 0bx3+ 0dx2+ 09x+ 0eu模模m(x) = x4+1每一輪操作每一輪操作round(state,roundkey) bytesub(state);shiftrow(state);mixcolumn(state);addroundkey(state,roundkey);

32、 a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35rijndael: key schedule(1)u主密鑰生成子密鑰數組主密鑰生成子密鑰數組, (nr+1)*nb個字個字unk=6keyexpansion(byte key4*nk, word wnb*(nr+1) for(i=0;ink;i+) wi=(key4*i, key4*i|+1, key4*i+2, key4*i+3); for(i=nk;inb*(nr+1);i+) temp=wi-1; if(i%nk = 0) temp=bytes

33、ub(temp6keyexpansion(byte key4*nk, word wnb*(nr+1) for(i=0;ink;i+) wi=(key4*i, key4*i|+1, key4*i+2, key4*i+3); for(i=nk;inb*(nr+1);i+) temp=wi-1; if(i%nk = 0) temp=bytesub(temp8)rconi/nk; else if(i%nk = 4) temp=bytesub(temp8); wi=wi-nktemp; ; ;rijndael: 加密結構加密結構rijndael(state,cipherkey) keyexpansion(cipherkey, expandedkey); addroundkey(state, expandedkey) for(i=1;inr;+i) bytesub(state);shiftrow(state);mixcolumn(state);addroundkey(state,expandedkey+nb*i); byt