第二章信息加密技術(shù)

1、第二章 信息保密技術(shù)2.1 古典密碼古典密碼2.2 分組加密技術(shù)分組加密技術(shù)2.3 公約加密技術(shù)公約加密技術(shù)2.4 流密碼技術(shù)流密碼技術(shù)2.5 電子信封技術(shù)電子信封技術(shù)2.6 信息隱藏技術(shù)信息隱藏技術(shù)密碼學(xué) 密碼學(xué)從應(yīng)用角度可分為密碼編碼、密碼分析兩個(gè)分支，分別研究密碼的編制和破譯問(wèn)題。 密碼學(xué)：密碼編碼學(xué)密碼分析學(xué)密碼系統(tǒng)應(yīng)用參考模型在對(duì)稱密碼系統(tǒng)中，密鑰的管理扮演著非常重要的角色。發(fā)送者接收者攻擊者安全信道不安全信道消息M消息M密鑰K密鑰K密文C消息M消息M消息M發(fā)送者消息M發(fā)送者消息M密鑰K發(fā)送者消息M密鑰K發(fā)送者消息M安全信道密鑰K發(fā)送者消息M密文C安全信道密鑰K發(fā)送者消息M不安全信道

2、密文C安全信道密鑰K發(fā)送者消息M不安全信道密文C安全信道密鑰K發(fā)送者消息M密文C安全信道密鑰K發(fā)送者消息M不安全信道密文C安全信道密鑰K發(fā)送者消息M攻擊者不安全信道密文C安全信道密鑰K發(fā)送者消息M攻擊者不安全信道密文C安全信道密鑰K發(fā)送者消息M接收者攻擊者不安全信道密文C安全信道密鑰K發(fā)送者消息M接收者攻擊者不安全信道密文C安全信道密鑰K發(fā)送者消息M密鑰K接收者攻擊者不安全信道密文C安全信道密鑰K發(fā)送者消息M消息M密鑰K接收者攻擊者不安全信道密文C安全信道密鑰K發(fā)送者消息M2.1 古典密碼古典密碼 公元6年前的古希臘人使用的是一根叫scytale的棍子。送信人先繞棍子卷一張紙條，然后把要寫的信

3、息縱寫在上面，接著打開紙送給送信人。如果不知道棍子的寬度（這里作為密鑰），不可能解密里面的內(nèi)容。后來(lái)，羅馬的軍隊(duì)用凱撒密碼進(jìn)行通信。 古典密碼是密碼學(xué)的淵源，可用手工和機(jī)械操作來(lái)實(shí)現(xiàn)加解密，現(xiàn)在已很少采用了。2.1 古典密碼古典密碼1、代換密碼通常，明文和密文由統(tǒng)一字母表構(gòu)成。加密時(shí)，通常將明文消息劃分成長(zhǎng)為L(zhǎng)的消息單元，稱為明文組。L=1 單字母代換（流密碼） 將明文空間的元素（如字母、二元數(shù)據(jù)等）逐個(gè)進(jìn)行加密， 這種對(duì)明文消息加密的方式稱為流密碼。L1 多碼代換（分組密碼） 將明文分成固定長(zhǎng)度的組，如64bit一組，用同一密鑰 和算法對(duì)每一組加密，輸出也是固定長(zhǎng)度的密文。根據(jù)加密過(guò)程中使用

4、代換表數(shù)目的多少單表代換：對(duì)所有明文字母都用一種固定代換 進(jìn)行加密多表代換：用一個(gè)以上的代換表進(jìn)行加密多字母代換單表代換密碼單表代換密碼（1）移位密碼最著名的移位密碼是凱撒密碼。例：取k=3，明文字母和密文字母的對(duì)應(yīng)關(guān)系為明文：abcdefghijklmnopqrstuvwxyz密文：DEFGHIJKLMNOPQRSTUVWXYZABC明文m=“caser cipher is a shift substitution”所對(duì)應(yīng)的密文為c=“FDVHU FLSHU LV D VKLIW VXEVWLWXWLRO”單表代換密碼單表代換密碼補(bǔ)充：ROT13密碼建立在UNIX系統(tǒng)上的簡(jiǎn)單的加密程序在這種

5、密碼中，A被N代替，B被O代替，每一個(gè)字母是環(huán)移13所對(duì)應(yīng)的字母。用ROT13加密文件兩遍便恢復(fù)出原始文件： P=ROT13(ROT13(P)ROT13并非為保密設(shè)計(jì)，它經(jīng)常用在英特網(wǎng)電子郵件中隱藏特定的內(nèi)容，以避免泄露一個(gè)難題的解答等。單表代換密碼 wfeazw為密鑰 排列后有26*25*24*1種選擇， 所以密鑰有26！種，太復(fù)雜，不容易記憶。 因此實(shí)際中密鑰句子常被使用，密鑰句子中的字母被依次填入密文字母表（重復(fù)的字母只用一次），沒(méi)用的字母按自然順序排列舉例在后一頁(yè)a b cx y zw f ea z w有26種選擇有25種選擇有24種選擇(2)替換密碼=a b cx y zw f ea

6、 z w=有26種選擇a b cx y zw f ea z w=有25種選擇有26種選擇a b cx y zw f ea z w=有24種選擇有25種選擇有26種選擇a b cx y zw f ea z w=單表代換密碼替換密碼 P24例：密鑰句子為studentteacherabcdefghijklmnopqrstuvwxyzstudenachrklmnopqrstuvwxyz 密鑰 明文 I love you密文 h love you單表代換密碼(3)仿射密碼 y=ax+b(mod 26) a,bZ26 當(dāng)a=1時(shí)，仿射密碼移位密碼 如果解密是可能的，必須要求仿射函數(shù)是雙射的：對(duì)任何y Z

7、26,方程ax+by(mod 26)有唯一解。由數(shù)論可知，當(dāng)且僅當(dāng)gcd(a,26)=1,對(duì)每個(gè)y有唯一解。對(duì)于aZ26， gcd(a,26)=1的a只有12種選擇，對(duì)于參數(shù)b沒(méi)有要求，所以仿射密碼有12*26種可能的密鑰。因?yàn)椋?。多表代換密碼多表代換：以一系列（兩個(gè)以上）代換表依次 對(duì)明文消息的字母進(jìn)行代換的加密方法。一次一密：對(duì)每個(gè)明文字母都采用不同的代換表 或密鑰進(jìn)行加密，稱為一次一密密碼 （理論上唯一不可破的密碼）周期多表代換：代換表個(gè)數(shù)有限，重復(fù)使用。 實(shí)際應(yīng)用中采用，例如維吉尼亞密碼維吉尼亞密碼（Vigenere密碼）利用Vigenere表格進(jìn)行加密，加密方法如下：給定一個(gè)單鑰字母

8、x和一個(gè)明文字母y，密文字母則在表格中x行y列的交叉點(diǎn)；例如，明文為：we are discovered save yourself,若取單密鑰為v，則加密時(shí)從密鑰v開始，對(duì)應(yīng)每個(gè)明文字母順序向下取密鑰，結(jié)果如下： 明文：wearediscoveredsaveyourself密鑰：vxyzabcdefghijklmnopqrstuv 密文：RAAPDDJUFSAKYMMCLHRMEKIKXFA也可選取一個(gè)關(guān)鍵詞重復(fù)成與明文同樣長(zhǎng)度作為密鑰進(jìn)行加密。若取關(guān)鍵詞為deceptive，加密結(jié)果如下： 明文：wearediscoveredsaveyourself密鑰：deceptivedeceptiv

9、edeceptive 密文：ZICVTWQNGRZGVTWAVZHCQYGLMGJVigenere密碼的強(qiáng)度在于對(duì)每個(gè)明文字母有多個(gè)密文字密碼的強(qiáng)度在于對(duì)每個(gè)明文字母有多個(gè)密文字母對(duì)應(yīng)，因此該字母的頻率信息是模糊的。母對(duì)應(yīng)，因此該字母的頻率信息是模糊的。Vigenere密碼表格ABCDEFGHIJKLMNOPQRSTUVWXYZBCDEFGHIJKLMNOPQRSTUVWXYZACDEFGHIJKLMNOPQRSTUVWXYZABDEFGHIJKLMNOPQRSTUVWXYZABCEFGHIJKLMNOPQRSTUVWXYZABCDFGHIJKLMNOPQRSTUVWXYZABCDEGHIJK

10、LMNOPQRSTUVWXYZABCDEFHIJKLMNOPQRSTUVWXYZABCDEFGIJKLMNOPQRSTUVWXYZABCDEFGHJKLMNOPQRSTUVWXYZABCDEFGHIKLMNOPQRSTUVWXYZABCDEFGHIJLMNOPQRSTUVWXYZABCDEFGHIJKMNOPQRSTUVWXYZABCDEFGHIJKLNOPQRSTUVWXYZABCDEFGHIJKLMOPQRSTUVWXYZABCDEFGHIJKLMNPQRSTUVWXYZABCDEFGHIJKLMNOQRSTUVWXYZABCDEFGHIJKLMNOPRSTUVWXYZABCDEFGHIJ

11、KLMNOPQSTUVWXYZABCDEFGHIJKLMNOPQRTUVWXYZABCDEFGHIJKLMNOPQRSUVWXYZABCDEFGHIJKLMNOPQRSTVWXYZABCDEFGHIJKLMNOPQRSTUWXYZABCDEFGHIJKLMNOPQRSTUVXYZABCDEFGHIJKLMNOPQRSTUVWYZABCDEFGHIJKLMNOPQRSTUVWXZABCDEFGHIJKLMNOPQRSTUVWXY設(shè)密鑰為 K ，用多字母代換 （L=2）對(duì)“l(fā)ove”進(jìn)行加密。 Xzda 每次對(duì)L1個(gè)字母進(jìn)行代換。容易隱蔽和均勻化字母的自然頻率，從而有利于抗統(tǒng)計(jì)分析明文x=(x1,

12、x2),密文y=(y1,y2)Y1=11x1+3x2Y2=8x1+7x211 83 7k=簡(jiǎn)記為y=xK，K為密鑰線性代數(shù)：可用K-1來(lái)解密，x=yk-111 83 712 16=24X 26Z7 1823 11=11 83 7-111 83 722 5=4 d 1a11 83 7X1 x2=y1 y2練習(xí)設(shè)密鑰為 ，用多字母代換 （L=2）對(duì)“l(fā)ove”進(jìn)行加密11 83 7k=設(shè)密鑰為 ，用多字母代換 （L=2）對(duì)“l(fā)ove”進(jìn)行加密。 xzwcLo12 16 x z11 83 712 16=24 26ve22 5 w c11 83 722 5=23 3多字母代換密碼當(dāng)m=1時(shí)，退化成單字

13、母仿射代換函數(shù) y=ax當(dāng)m=2時(shí)，如前例當(dāng)m=3時(shí)，例如Hill密碼 希爾密碼當(dāng)m3時(shí)，計(jì)算K-1沒(méi)有有效的方法， 所以大大限制了多字母代換密碼 的廣泛應(yīng)用。Hill密碼Hill密碼Hill密碼也是一種多字母替代密碼，它由數(shù)學(xué)家Lester Hill于1929年研制成功。加密方法用向量或矩陣表示為C1C2C3K11 K12 K13K21 K22 K23K31 K32 K33P1P2P3=C1C2C3=K11 K12 K13K21 K22 K23K31 K32 K33C1C2C3=P1P2P3K11 K12 K13K21 K22 K23K31 K32 K33C1C2C3=或 C=KP 其中，C

14、和P是長(zhǎng)度為3的列向量，分別表示密文和明文，K是3*3矩陣，表示加密密鑰，加密操作要執(zhí)行模26運(yùn)算。11 83 7X1 x2=y1 y2例如，如果使用的加密密鑰是K=17 17 521 18 21 2 2 19欲對(duì)明文pay more money進(jìn)行加密，則現(xiàn)將明文按三個(gè)字母一組分組（不足三個(gè)時(shí)補(bǔ)字母x），然后每組字母求密文。該明文的前三個(gè)字母表示為pay=(15 0 24) ，計(jì)算密文的過(guò)程如下 (15 0 24) K=(375 819 486) mod 26=(11 13 18) =LNS以此類推，可得密文為。?解密時(shí)使用逆矩陣K-1=對(duì)密文(11 13 18)T做運(yùn)算K-1 (11 13

15、 18)T mod 26=(431 494 570) T=(15 0 24) T=pay Hill密碼的強(qiáng)度在于完全隱藏了單字母的頻率。LNS HDL EWM TRW2.1 古典密碼古典密碼 2、置換密碼（換位密碼） 不改變明文字母，但通過(guò)重排而更改它們的位置。 例如：矩陣變換密碼、縱行換位密碼矩陣變換加密:將明文中的字母按給定順序安排在1個(gè)矩陣中，然后用另一種順序選中矩陣的字母來(lái)產(chǎn)生密文，一般為列變換次序。如原列次序?yàn)?234，先列次序?yàn)?413矩陣變換加密給定一個(gè)置換：f = ，根據(jù)給定的次序，按526413的列序重新排列，得到所以密文是 oerwntc ueks i yrt.解密過(guò)程正好

16、相反，按序排列密文后，通過(guò)列置換，再按行讀取數(shù)據(jù)即可。123456526413如將明文network security按行排列在3*6矩陣中，如下所示：1 2 3 4 5 6n e t w o r k s e c u r i t y 5 2 6 4 1 3o e r w n tc u e k s i y r t縱行換位密碼明文以固定的寬度水平地寫在一張圖表紙上，密文按垂直方向讀出。解密就是將密文按相同的寬度垂直地寫在圖表紙上，然后水平地讀出明文。Plaintext：COMPUTERGRAPHICSMAYBESLOWBUTATLEASTITSEXPENSIVE COMPUTERGR (10個(gè)為一

17、組) APHICSMAYB ESLOWBUTAT LEASTITSEX PENSIVECiphertext: CAELPOPSEEMHLANPIOSSUCWTITSBIVEMUTERATSGYAERBTX換位密碼對(duì)存儲(chǔ)的要求很大，有時(shí)還要求特定的長(zhǎng)度，因而比較麻煩，換位密碼對(duì)存儲(chǔ)的要求很大，有時(shí)還要求特定的長(zhǎng)度，因而比較麻煩，因此代替密碼（代換密碼）較為常用。因此代替密碼（代換密碼）較為常用。破譯Kerckhoff假設(shè)：攻擊方知道所用的密碼系統(tǒng)目標(biāo)：設(shè)計(jì)一個(gè)在Kerckhoff假設(shè)下達(dá)到的安全系統(tǒng)移位密碼極易破解，僅統(tǒng)計(jì)出最高頻度字母再與明文字母表對(duì)應(yīng)決定出位移量，就差不多得到正確解了。安全密

18、碼系統(tǒng)的一個(gè)必要條件必要條件是密鑰的空間必須足夠大，使得窮舉密鑰搜索破譯是不可能的。（非充分條件）2.2 分組加密技術(shù)2.2.1基本概念分組加密技術(shù)屬于對(duì)稱密碼體制的范疇；分組密碼的工作方式是將明文分成固定長(zhǎng)度的組，如64bit為一組，用同一密鑰和算法對(duì)每一組加密，輸出也是固定長(zhǎng)度的密文。例如DES密碼算法的輸入為64bit，密鑰長(zhǎng)度為56bit，密文長(zhǎng)度為64bit。設(shè)計(jì)分組密碼算法的核心技術(shù)是：在相信復(fù)雜函數(shù)可以通過(guò)簡(jiǎn)單函數(shù)迭代若干次得到的原則下，利用簡(jiǎn)單圈函數(shù)等運(yùn)算，充分利用非線性運(yùn)算。以DES算法為例，它采用美國(guó)國(guó)家安全的局設(shè)計(jì)的8個(gè)S-Box和P-置換，經(jīng)過(guò)16圈迭代，最終產(chǎn)生64b

19、it密文，每圈迭代使用的48bit子密鑰是由原始的56bit產(chǎn)生的。2.2 分組加密技術(shù)2.2.1標(biāo)準(zhǔn)算法的介紹DES算法國(guó)際數(shù)據(jù)加密算法IDEAASE算法2.2 分組加密技術(shù)2.2.3分組密碼的分析方法完全可破譯密碼破譯者可以確定該密碼正在使用的密鑰，則他可以象合法用戶一樣閱讀所有的消息。（對(duì)于非對(duì)稱密碼，知道私鑰）部分可破譯密碼破譯者僅能從所竊取的密文中恢復(fù)明文，卻發(fā)現(xiàn)不了密鑰。2.2 分組加密技術(shù)2.2.3分組密碼的分析方法分組密碼的攻擊可分以下幾類：唯密文攻擊已知明文攻擊選擇明文攻擊選擇密文攻擊2.3 公鑰加密技術(shù)2.3.1 基本概念 一個(gè)加密系統(tǒng)的加密密鑰和解密密鑰是不一樣的，不能又

20、一個(gè)推出另一個(gè)。公鑰用于加密（公開的），私鑰用于解密（保密的）。B的公鑰用戶A密文C非對(duì)稱密碼算法信息MB的私鑰用戶B信息M密文C非對(duì)稱密碼算法公開信道用戶A信息M用戶A信息M用戶A非對(duì)稱密碼算法信息M用戶A非對(duì)稱密碼算法信息M用戶AB的公鑰非對(duì)稱密碼算法信息M用戶AB的公鑰非對(duì)稱密碼算法信息M用戶A密文CB的公鑰非對(duì)稱密碼算法信息M用戶A密文CB的公鑰非對(duì)稱密碼算法信息M用戶A公開信道密文CB的公鑰非對(duì)稱密碼算法信息M用戶A公開信道密文CB的公鑰非對(duì)稱密碼算法信息M用戶A密文C公開信道密文CB的公鑰非對(duì)稱密碼算法信息M用戶A密文C公開信道密文CB的公鑰非對(duì)稱密碼算法信息M用戶A非對(duì)稱密碼算法

21、密文C公開信道密文CB的公鑰非對(duì)稱密碼算法信息M用戶A解決了對(duì)稱密碼體制中的密鑰管理難題，滿足了開放系統(tǒng)的要求。解決了對(duì)稱密碼體制中的密鑰管理難題，滿足了開放系統(tǒng)的要求。2.3 公鑰加密技術(shù)公鑰加密技術(shù)的核心：運(yùn)用了一種特殊的數(shù)學(xué)函數(shù)-單向陷門函數(shù)。 Y=f(x) x=f-1(y)單向陷門函數(shù): 從一個(gè)方向求值是容易的，但其逆向計(jì)算卻很困難。2.3 公鑰加密技術(shù)定義1 設(shè)f是一個(gè)函數(shù)，如果對(duì)于任意給定的x，計(jì)算y，使得y=f(x)是容易計(jì)算的，但對(duì)于任意給定的y，計(jì)算x，使得x=f-1(y)是難解的。即求f的逆函數(shù)是難解的。稱f是一個(gè)單向函數(shù)。定義2 設(shè)f是一個(gè)函數(shù)，t是與f有關(guān)的一個(gè)參數(shù)。對(duì)

22、于任意給定的x，計(jì)算y，使得y=f(x)是容易計(jì)算的。如果當(dāng)不知道參數(shù)t時(shí)，求f的逆函數(shù)是難解的，但當(dāng)知道參數(shù)t時(shí)，求f的逆函數(shù)是容易的。稱f是一個(gè)單向陷門函數(shù)。參數(shù)t稱為陷門。在公鑰加密算法中，加密變換就是一個(gè)單向陷門函數(shù)，知道陷門的人很容易進(jìn)行解密變換，而不知道陷門的人則無(wú)法有效地進(jìn)行解密變換2.3 公鑰加密技術(shù)數(shù)學(xué)難題-不存在一個(gè)計(jì)算該問(wèn)題的有效方法；目前、以后足夠時(shí)間內(nèi)，求逆函數(shù)在計(jì)算上不可行時(shí)間長(zhǎng)度難以忍受。絕對(duì)安全的密碼經(jīng)常給密鑰管理帶來(lái)非常大的壓力?，F(xiàn)在主流的編碼思想是尋找密鑰管理簡(jiǎn)單，且破譯者利用現(xiàn)有資源無(wú)法在預(yù)定時(shí)間內(nèi)破譯的密碼編碼方法，這就是計(jì)算上安全的密碼。根據(jù)單向陷門函

23、數(shù)的思想，學(xué)者們提出許多公鑰加密的方法，都是基于復(fù)雜數(shù)學(xué)難題的。根據(jù)基于的數(shù)學(xué)難題，至少有以下三類系統(tǒng)目前被認(rèn)為是安全和有效的：大整數(shù)因子分解系統(tǒng)（代表性的有RSA）橢圓曲線離散對(duì)數(shù)系統(tǒng)（ECC）離散對(duì)數(shù)系統(tǒng)（代表性的有DSA）2.3 公鑰加密技術(shù)2.3.2 RSA公鑰密碼算法RSA的安全性建立在兩大數(shù)論難題上大數(shù)分解素性檢測(cè)即：將兩個(gè)大數(shù)相乘在計(jì)算上很容易實(shí)現(xiàn)，但將該乘積分解成兩個(gè)大素?cái)?shù)因子的計(jì)算量是相當(dāng)巨大的，以至于在實(shí)際計(jì)算中是不能實(shí)現(xiàn)的。算法見教材 P45RSA公鑰密碼算法1、gcd函數(shù)：求最大公因數(shù) 例如 gcd(7,17)=1 gcd(16,12)=4 gcd(e, (n)=1表示

24、e和(n)互素，即最大公因數(shù)為12、歐拉函數(shù)(n)(n)表示不超過(guò)n且與n互素的整數(shù)個(gè)數(shù);易證明當(dāng)n=pq，p和q為不同的素?cái)?shù)時(shí)，(pq)=(p-1)(q-1)例：求(15) 小于15，且與15互素的整數(shù)個(gè)數(shù) 1,2,4,7,8,11,13,14 共有8個(gè) (15) =8練習(xí) 求(35) 提示：35=5*7，且5和7是素?cái)?shù) RSA公鑰密碼算法例 構(gòu)造一個(gè)RSA算法如下：(1)選擇兩個(gè)素?cái)?shù) p=7 q=17(2)計(jì)算n=p*q=7*17=119(3)計(jì)算(n) =(7-1)(17-1)=96(4)選擇一個(gè)e，它與(n) 互素 5與96互素，e=5 e的選取很容易，所有大于的選取很容易，所有大于p和和q的質(zhì)數(shù)都可用的質(zhì)數(shù)都可用(5)求出d，它小于(n)，且(d*e)mod 96=1 77*5=4*96+1 d=77 (6)公鑰 Kp=5，119，私鑰Ks=77，119RSA公鑰密碼算法公鑰 Kp=5，119，私鑰Ks=77，119假設(shè)明文m=19加密時(shí)，195(mod119)=66 得到密文C=66 解密時(shí) 6677(mod1