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

第3章信息加密技術(shù)本章內(nèi)容3.1加密技術(shù)的相關(guān)概念和術(shù)語.3.2加密的基本思想3.3加密技術(shù)的分類3.4對稱加密算法—DES算法3.5非對稱加密算法--RSA算法3.6Diffie-Hellman密碼體制3.7背包密碼3.1加密的相關(guān)概念明文(plaintext)：也叫純文本,明碼密文(ciphertext)：也叫密碼文本算法(algorithm):加密和解密過程基于的某種數(shù)學程序,數(shù)學

變換.密鑰(Key):加解密過程中,某些只被通信雙方所掌握的專門的、關(guān)鍵的信息加密(encryption)解密(decryption)利用加密技術(shù)存儲、傳輸信息，可提供安全保護功能機密性完整性不可否認性密碼學的發(fā)展階段第1階段：1949年以前——古典密碼學密碼學還不是科學，而是藝術(shù)；出現(xiàn)一些簡單的密碼算法,加密設(shè)備,簡單的密碼分析手段；主要特點：數(shù)據(jù)的安全基于算法的保密第2階段：1949~1975年——現(xiàn)代密碼學密碼學成為科學計算機使得基于復(fù)雜計算的密碼成為可能主要特點:數(shù)據(jù)的安全基于密鑰而不是算法的保密第3階段：1975年以后——公鑰密碼學密碼學的新方向——公鑰密碼學公鑰密碼使得發(fā)送端和接收端無密鑰傳輸?shù)谋Ｃ芡ㄐ懦蔀榭赡?。Kerchoffs假設(shè)：如果密碼系統(tǒng)的強度依賴于攻擊者不知道算法的內(nèi)部機理，則該密碼系統(tǒng)注定會失敗。密碼系統(tǒng)的安全性應(yīng)該完全依賴于密鑰的安全性.密碼算法的安全性如果不論截取者獲得了多少密文，但在密文中都沒有足夠的信息來惟一地確定出對應(yīng)的明文，則這一密碼體制稱為無條件安全的，或稱為理論上是不可破的。在無任何限制的條件下，目前幾乎所有實用的密碼體制均是可破的。因此，人們關(guān)心的是要研制出在計算上(而不是在理論上)是不可破的密碼體制。如果一個密碼體制中的密碼不能被可以使用的計算資源破譯，則這一密碼體制稱為在計算上是安全的。破譯的代價超出信息本身的價值破譯的時間超出了信息的有效期.3.2基本加密思想-替換替換：按照一定的規(guī)則,將明文中每一個字符用不同的密文字符代替。(1)移位替換

缺點:很容易通過窮舉密鑰方式破解,密鑰的空間小.(2)單表替換:不規(guī)則將明文字母映射到密文字母空間.單表替換密鑰空間為26！使用密鑰窮舉很難破解其密碼隨著統(tǒng)計學和概率的發(fā)展，破解單一字母替代編碼非常容易。英文字母出現(xiàn)相對頻率密文語言統(tǒng)計規(guī)律2023/2/6(3)多表替代密碼:一個字母在不同位置上被替換成不同的密文字母。多表替換隱藏了字母的統(tǒng)計規(guī)律，比前兩者具有更好的安全性。Vigenere密碼:t個密文本，加密為：

ci=fi(mi)=(mi+ki)mod26,其中ki為密鑰,

i=0,1,…,t-1舉例說明：k=(6,14,15,7,4,17),t=6m=meetmeintheallyaftermidnightm=meetmeintheallyaftermidnightc=sstaqvobioirrznhjkkfbpheouwaabcdefghijklmnopqrstuvwxyz0123456789101112131415161718192021222324253.2基本加密思想—易位易位:把明文中的字符重新排列，本身不變，但位置變了。柵欄密碼，就是把要加密的明文分成N個一組，然后把每組的第i個字連起來，形成一段無規(guī)律的話。舉例1明文：THEREISACIPHER

去掉空格后變?yōu)椋篢HEREISACIPHER

兩個一組，得到：THEREISACIPHER

先取出第一個字母：TEESCPE

再取出第二個字母：HRIAIHR

連在一起就是：TEESCPEHRIAIHR舉例2:明文:

STRIKEWHILETHEIRONISHOT密鑰:PREDIC

密文:ETNE

ILRORIIH

KEOT

SWHIHTESSTRIKEWHILETHEIRONISHOTEPREDIC5632413.2基本加密思想--一次一密一次一密體制要求：密鑰是真正的隨機序列密鑰長度至少等于明文長度一個密鑰只用一次

滿足上述三個條件的密碼系統(tǒng)是絕對安全的，不會被破譯(香農(nóng)在1949年已證明)缺陷:

密鑰的安全傳送,安全存放網(wǎng)絡(luò)狀態(tài)下同步密鑰2023/2/63.2基本加密思想–實例貼吧-神秘的摩斯密碼最近和一個心儀的女生告白，誰知道她給了一個摩斯密碼給我，說解出來了才答應(yīng)和我約會?？墒俏矣帽M了所有方法都解不開這個密碼。。好郁悶阿。只能求教你們了。

****-/*----/----*/****-/****-/*----/---**/*----/****-/*----/-****/***--/****-/*----/----*/**---/-****/**---/**---/***--/--***/****-/

她唯一給我的提示就是這個是5層加密的密碼.

也就是說要破解5層密碼才是答案.摩斯密碼有兩種“符號”用來表示字元：劃（—）和點（·），或分別叫嗒（Dah）和滴（Dit）或長和短。點的長度決定了發(fā)報的速度，并且被當作發(fā)報時間參考。劃一般是三個點的長度；點劃之間的間隔是一個點的長度；字元之間的間隔是三個點的長度；單詞之間的間隔是七個點的長度。Morsecode：——

/———/·—·/···/·

//—·—·/———/—··/·第一步摩爾斯解碼：****-/*----/----*/****-/****-/*----/---**/*----/****-/*----/-****/***--/****-/*----/----*/**---/-****/**---/**---/***--/--***/****-/數(shù)字：4194418141634192622374

：

第二步：手機按鍵碼表

4194418141634192622374得到：GZGTGOGXNCS第三步：QWE鍵盤碼表

QWERTYUIOPASDFGHJKLZXCVBNM

ABCDEFGHIJKLMNOPQRSTUVWXYZ得到：OTOEOIOUYVL第四步：柵欄密碼：（兩排柵欄）

OTOEO

I

OUYVL得到：OOTUOYEVOLI第五步：倒序排列：得到：ILOVEYOUTOO（最終結(jié)果）3.3加密算法的分類對稱加密算法加密密鑰與解密密鑰相同，又叫私有密鑰算法。著名密碼算法：DES/3DES數(shù)據(jù)加密標準IDEA國際數(shù)據(jù)加密算法RC系列(RC2,

RC4,

RC5)AES高級數(shù)據(jù)加密標準等非對稱加密算法加密密鑰與解密密鑰不同，而且解密密鑰不能根據(jù)加密密鑰計算出來,又叫公有密鑰算法著名密碼算法：RSA加密算法Diffie-Hellman加密算法背包密碼橢圓曲線加密算法對稱加密算法Strongcryptographymakestheworldasaferplace!@$#^%$&*$#￥@！#￥%*！@#￥%&!@$#^%$&*$#￥@！#￥%*！@#￥%&Strongcryptographymakestheworldasaferplace優(yōu)點:加解密速度快缺點:密鑰傳送非常重要密鑰管理很復(fù)雜非對稱加密算法原理Strongcryptographymakestheworldasaferplace!@$#^%$&*$#￥@！#￥%*！@#￥%&!@$#^%$&*$#￥@！#￥%*！@#￥%&Strongcryptographymakestheworldasaferplace又叫公鑰密碼算法。優(yōu)點安全性高,不需要安全信道來傳送密鑰缺點算法復(fù)雜，加解密速度慢。非對稱與對稱加密算法相結(jié)合的加密方式根據(jù)每次操作的數(shù)據(jù)單元是否分塊劃分分組密碼(blockcipher):用一個固定的變換對等長分組進行處理序列密碼(streamcipher):用一個時變變換對明文進行逐個比特處理密鑰源密鑰序列k0k1k2…公開信道秘密信道密鑰流產(chǎn)生器密鑰流產(chǎn)生器KK密鑰序列k0k1k2…明文序列m0m1m2…明文序列m0m1m2…密文序列c0c1c2…K為種子密鑰，一般較短；密鑰流發(fā)生器在K的控制下產(chǎn)生較長的密鑰流序列密碼的優(yōu)點：1）處理速度快，實時性好；2）錯誤傳播??；3）適用于軍事、外交等保密信道。序列密碼的缺點：1）明文擴散性差；2）需要密鑰同步。序列密碼的核心就是研究如何產(chǎn)生偽隨機序列真正的隨機序列是很難得到的偽隨機序列的性質(zhì)：看起來是隨機的不可預(yù)測的不能重復(fù)產(chǎn)生

3.4對稱加密算法--DES算法20世紀70年代,由IBM公司發(fā)展出來1976年，DES被授權(quán)在美國政府非密級政府通信中使用1977年，DES作為美國聯(lián)邦信息處理標準正式生效，是世界上一項最早被公認的實用的密碼標準2000年10月2日，NIST公布了新的AES，DES作為標準正式結(jié)束密鑰固定長度,只有56位以塊模式對64bits的明文塊進行操作DES算法的原理DES算法的入口參數(shù)有三個：Key、Data、ModeKey為8個字節(jié)共64位，是DES算法的工作密鑰Data也為8個字節(jié)64位，是要被加密或被解密的數(shù)據(jù)Mode為DES的工作方式,有兩種：加密或解密。DES算法是這樣工作的：如Mode為加密，則用Key去把數(shù)據(jù)Data進行加密，生成Data的密碼形式（64位）作為DES的輸出結(jié)果如Mode為解密，則用Key去把密碼形式的數(shù)據(jù)Data解密，還原為Data的明碼形式（64位）作為DES的輸出結(jié)果。DES算法的實現(xiàn)步驟加密過程如圖所示。四個關(guān)鍵點：1、IP置換表和IP逆置換表。2、函數(shù)f。3、子密鑰Ki。4、S盒的工作原理。(1)

IP置換表和IP逆置換表5850123426181026052443628201246254463830221466456484032241685749413325179159514335271911361534537292113563554739312315740848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725（2）函數(shù)f函數(shù)f有兩個輸入：32位的Ri-1和48位Ki。3212345456789891011121312131415161716171819202120212223242524252627282928293031321（3）子密鑰ki。（4）S盒的工作原理首先回顧一下S盒變換在函數(shù)f中的位置：（4）S盒的工作原理S盒以6位作為輸入，而以4位作為輸出，現(xiàn)在以S1為例說明其過程。假設(shè)輸入為A=a1a2a3a4a5a6，則a2a3a4a5所代表的數(shù)是0到15之間的一個數(shù)，記為：k=a2a3a4a5；由a1a6所代表的數(shù)是0到3間的一個數(shù)，記為h=a1a6。在S1的h行（范圍0～3），k列（范圍0～15）找到一個數(shù)B，B在0到15之間，用4位二進制表示，為B=b1b2b3b4，這就是S1的輸出。練習：已知A＝101110求B012345678910111213141501441312151183106125907101574142131106121195382411481362111512973105031512824917511314100613kh一次關(guān)于DES的攻擊測試:

1997年1月，美國RSA公司公布了一個“秘密密鑰挑戰(zhàn)”競賽項目：懸賞一萬美元破解密鑰長度為56比特的DES密碼算法，以測試因特網(wǎng)上的分布式計算能力，并測試DES算法的相對安全程度。競賽規(guī)則：明文開頭是：“Theunknowmessageis:”

密鑰是隨機選取的；明文和密鑰都嚴加保密；挑戰(zhàn)者解出密鑰后，用E-mail迅速向RSA公司報告，第一個解出者為勝利者。密鑰窮舉攻擊程序：由參賽者RockeVerser設(shè)計，用于窮舉所有可能的DES密鑰。供其它參與者下載和使用。

56位DES的全部密鑰窮舉量是：72,057,584,037,927,936≈72*1015競賽結(jié)果：在RSA公布后的第140天，窮舉攻擊程序?qū)嵤┑牡?6天解出密鑰和密文。1997年6月17日晚10點39分，美國鹽湖城iNet公司的職員Michael

Sanders在其奔騰90Hz、16M內(nèi)存的PC機上成功地解出了競賽的密文。密文：“Theunknowmessageis:StrongCryptographymakestheworldasaferplace.”密鑰：855889lab0c85166測試表明：①依靠因特網(wǎng)分布式計算能力，用密鑰窮舉法破譯DES成為可能。②隨著計算能力的增長，必須增加密鑰長度，才能更安全。密鑰長度密鑰空間窮舉時間401,099,511,627,77678秒485小時5672,057,594,037,927,93959天6418,446,744,073,709,551,61641年7210,696年802,738,199年88700,978,948年96179,450,610,898年11211,760,475,235,863,837年128340,282,366,920,938,463,374,607,431,768,211,456770,734,505,057,572,442,069年3.5非對稱加密算法--RSA算法由MIT的Rivest,Shamir&Adleman在1978提出.分組加密算法RSA的安全性依賴于大數(shù)因子分解問題:

計算n=pq，公鑰{e，n}，私鑰{d，n}RSA算法密鑰生成過程選取兩個不同的素數(shù)p和q公鑰{7,187}，私鑰{23,187}已知公鑰e和n，能夠破解出私鑰d嗎？分組對應(yīng)數(shù)字值設(shè)為m,加密將明文內(nèi)容進行分組,分組長度k滿足RSA算法加解密過程解密將密文內(nèi)容進行分組,分組長度為k加密過程解密過程明文明文密文加密過程解密過程公鑰私鑰相等嗎？分組長度k為什么要小于RSA安全性討論RSA算法總結(jié)密鑰生成過程加密過程:

c=memodn解密過程:

m=cdmodn程序演示計算n=pq，公鑰{e，n}，私鑰{d，n}選取兩個不同的素數(shù)p和q2023/2/6413.6

Diffie-Hellman密碼體制Diffie-Hellman

公鑰密碼系統(tǒng)出現(xiàn)在RSA之前，它實際是仍在使用的最古老的公鑰系統(tǒng)。由于該算法本身限于密鑰交換的用途，被許多商用產(chǎn)品用作密鑰交換技術(shù)，因此又稱之為Diffie-Hellman密鑰交換。這種密鑰交換技術(shù)的目的在于使得兩個用戶安全地交換一個秘密密鑰以便用于以后的報文加密。DH密鑰交換的安全性依賴于計算有限域中的離散對數(shù)問題。離散對數(shù)問題本原元(primitiveelement)：給定素數(shù)p，如果a是素數(shù)p的一個本原元，那么數(shù)值

amodp,a2modp,...,ap-1modp是各不相同的整數(shù)，并且以某種排列方式組成了從1到p-1的所有整數(shù)。離散對數(shù)：對于一個整數(shù)β和素數(shù)p的一個本原元a，可以找到惟一的指數(shù)d，使得

β=admodp，其中0≤d≤(p-1)，指數(shù)d稱為β的以a為基數(shù)的模p的離散對數(shù)或者指數(shù)。2023/2/6451.基本原理Diffie-Hellman密鑰交換XAXBYAYBKA計算KB計算用戶A用戶B

公開公開秘密秘密會話秘密會話秘密

密鑰交換過程

舉例例：為了計算簡單，使用很小數(shù)字。設(shè)P=47,以及47的一個本原元a=3，A選擇秘密密鑰XA=8，B選擇秘密密鑰XB=10。（1）雙方各自計算其公開密鑰用戶A計算：YA=38mod47=6561mod47=28mod47用戶B計算：YB=310mod47=59049mod47=17mod47（2）交換YA和YB；（3）交換密鑰后，A、B分別計算共享的秘密會話密鑰KA、KB：用戶A計算：KA=YBXAmod47=178mod47=4

mod47用戶B計算：KB=YAXBmod47=2810mod47=4

mod47A和B雙方獨立地決定采用4作為會話密鑰。2023/2/647Diffie-Hellman密鑰交換Diffie-Hellman算法具有兩個吸引力的特征：對共享密鑰提供的保護，能夠抵抗來自于被動敵手（竊聽者）的攻擊僅當需要時才生成密鑰，減小了將密鑰存儲很長一段時間而致使遭受攻擊的機會。除對全局參數(shù)的約定外，密鑰交換不需要事先存在的基礎(chǔ)結(jié)構(gòu)。存在不足：沒有提供雙方身份的任何信息。它是計算密集性的，因此容易遭受阻塞性攻擊，即對手請求大量的密鑰。受攻擊者花費了相對多的計算資源來求解無用的冪系數(shù)而不是在做真正的工作。沒辦法防止重放攻擊。容易遭受中間人的攻擊。2023/2/648中間人攻擊BobAliceEve3.7背包(Knapsack)密碼給定一組n個重量W0,W1,...,Wn-1和一個總重量S,能否找到一組系數(shù)ai

{0,1}滿足

S=a0W0+a1W1+...+an-1Wn-1實例

重量(62,93,26,52,166,48,91,141)問題：找到系數(shù)滿足S=302答案:62+26+166+48=302此處系數(shù)為（10101100）已證明一般knapsack問題是NP-完全問題(非常難解)公鑰密碼49背包(Knapsack)問題一般背包問題(GK)很難解決但超遞增背包問題(super-increasingknapsack)

(SIK)很容易解決SIK要求重量遞增排列且每個重量比前面所有重量和還大實例重量(2,3,7,14,30,57,120,251)

問題:找出子集滿足和=186從大到小逐步推算…