傳統(tǒng)加密技術(shù).ppt

1、Chapter 2 傳統(tǒng)加密技術(shù),信息安全概論,密碼學(xué)(cryptology),將密碼當(dāng)成一種科學(xué)來研究，就產(chǎn)生了密碼學(xué)。 密碼學(xué)(cryptology)源于希臘語krypts，意為“隱藏的”和 grphein意為 “書寫”。 密碼學(xué)是一門古老而年輕的科學(xué)。,2020年6月23日9時(shí)31分,3,密碼學(xué)的發(fā)展歷史,第1階段：1949年以前 第2階段：從1949年到1975年 標(biāo)志：1949年Shannon發(fā)表的保密系統(tǒng)的信息理論一文。 第3階段：1976年至今。 標(biāo)志：1976年Diffie和Hellman發(fā)表了密碼學(xué)新方向一文。,第一階段古典密碼,密碼學(xué)還不是科學(xué),而是藝術(shù) 出現(xiàn)一些密碼算法和

2、加密設(shè)備 簡(jiǎn)單的密碼分析手段出現(xiàn) 主要特點(diǎn)：數(shù)據(jù)的安全基于算法的保密,古典密碼,古典密碼的加密方法一般是代換與置換，使用手工或機(jī)械變換的方式實(shí)現(xiàn)。 古典密碼的代表密碼體制主要有：?jiǎn)伪泶婷艽a、多表代替密碼及轉(zhuǎn)輪密碼 Caesar密碼就是一種典型的單表加密體制； 多表代替密碼有Playfair密碼、Hill密碼、Vigenere密碼； 著名的Enigma密碼就是第二次世界大戰(zhàn)中使用的轉(zhuǎn)輪密碼。,第二階段 19491975,計(jì)算機(jī)使得基于復(fù)雜計(jì)算的密碼成為可能 相關(guān)技術(shù)的發(fā)展 1949年,香農(nóng)發(fā)表了(The Communication Theory of Secrecy Systems), 它證明

3、了密碼編碼學(xué)是如何置于堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)之上的，從此密碼學(xué)發(fā)展成為一個(gè)專門學(xué)科。標(biāo)志性事件 1967年David Kahn的The Codebreakers 1971-73年IBM Watson實(shí)驗(yàn)室的Horst Feistel等幾篇技術(shù)報(bào)告 主要特點(diǎn)：數(shù)據(jù)的安全基于密鑰而不是算法的保密,第三階段：1976,公鑰密碼學(xué)成為主要研究方向 主要特點(diǎn):公鑰密碼使得發(fā)送端和接收端無密鑰傳輸?shù)谋Ｃ芡ㄐ懦蔀榭赡堋?代表性事件： 1976年, Diffie和Hellman發(fā)表的革命性論文密碼學(xué)新方向(New deryctions in cryptography), 突破了傳統(tǒng)密碼體制使用秘密密鑰所帶來的密鑰管理

4、難題, 使密碼的發(fā)展進(jìn)入了一個(gè)全新的發(fā)展時(shí)期。 1977年，Rivest，Shamir和Adleman提出了RSA公鑰算法。 DES算法出現(xiàn)。 80年代，出現(xiàn)IDEA和CAST等算法。 90年代，對(duì)稱密鑰密碼算法進(jìn)一步成熟，Rijndael，RC6等出現(xiàn)，逐步出現(xiàn)橢圓曲線等其他公鑰算法。 2001年，Rijndael成為DES算法的替代者。,2020年6月23日9時(shí)31分,8,2.1 對(duì)稱密碼的模型,傳統(tǒng)密碼/常規(guī)密碼/私鑰密碼/單鑰密碼conventional / private-key / single-key 發(fā)送方和接收方共享一個(gè)共同的密鑰 sender and recipient s

5、hare a common key 所有的傳統(tǒng)密碼算法都是私鑰密碼 20世紀(jì)70年代以前私鑰密碼是唯一類型 至今仍廣泛應(yīng)用,密碼學(xué)基本概念,密碼學(xué)(cryptology) ：研究信息的保密和復(fù)原保密信息以獲取其真實(shí)內(nèi)容的學(xué)科稱為密碼學(xué)。它包括密碼編碼學(xué)和密碼分析學(xué)。 密碼編碼學(xué)(cryptography)：研究對(duì)信息進(jìn)行編碼實(shí)現(xiàn)隱蔽信息的一門學(xué)科。 密碼分析學(xué)(cryptanalytics)：不知道任何加密細(xì)節(jié)的條件下解密消息的技術(shù)，即“破譯”。,密碼學(xué)基本概念,明文（plaintext)：信息的原始形式，一般是信息的基本單元（字母、數(shù)字或符號(hào)等）的有限排列； 密文（cipher)：明文經(jīng)過加

6、密以后的結(jié)果形式 加密變換(encryption) ：從明文到密文的變換過程 解密變換(decryption) ：從密文還原成明文的過程 加密算法：對(duì)明文進(jìn)行加密時(shí)采用的一組規(guī)則。 解密算法：對(duì)密文進(jìn)行解密時(shí)采用的一組規(guī)則。 密鑰（key)：用于加解密變換的關(guān)鍵信息，視其用于加解密而分別稱為加密密鑰與解密密鑰；,2020年6月23日9時(shí)31分,11,對(duì)稱密碼模型 （Symmetric Cipher Model）,2020年6月23日9時(shí)31分,12,對(duì)稱密碼安全的兩個(gè)必備條件: 加密算法必須是足夠強(qiáng)的 a strong encryption algorithm 即使對(duì)手擁有一定數(shù)量的密文和產(chǎn)生

7、每個(gè)密文的明文，他也不能破譯密文或發(fā)現(xiàn)密碼 惟有發(fā)送者和接收者知道的秘密密鑰 a secret key known only to sender / receiver,2020年6月23日9時(shí)31分,13,2020年6月23日9時(shí)31分,14,19世紀(jì)，Kerckhoff原則： 系統(tǒng)的保密性不依賴于對(duì)加密體制或算法的保密，而依賴于對(duì)密鑰的保密。,密碼體制的分類,按轉(zhuǎn)換明文為密文的運(yùn)算類型分 代換: 明文中的每個(gè)元素映射為另一元素 置換: 明文中的元素重新排列,密碼體制的分類,按所用的密鑰數(shù)分 單密鑰密碼（也稱對(duì)稱/秘密鑰/傳統(tǒng)密碼） 優(yōu)點(diǎn)：運(yùn)行速度快，具有可靠的保密強(qiáng)度； 不足：不便密鑰交換和

8、管理。 雙鑰密碼（也稱非對(duì)稱/公鑰密碼） 優(yōu)點(diǎn)：便于密鑰交換和管理，還可用于消息認(rèn)證（數(shù)字簽名）； 不足：運(yùn)行速度緩慢，其安全性所依賴的數(shù)學(xué)難題的復(fù)雜性一般都未能證明。,一般說來，單鑰密碼體制（包括分組、序列密 碼）都是基于計(jì)算安全性的 而雙鑰密碼體制是基于可證明安全性的。 這兩種安全性都是從計(jì)算量來考慮，但不盡相同。 計(jì)算安全要算出或估計(jì)出破譯它的計(jì)算量下限 可證明安全則要從理論上證明破譯它的計(jì)算量不低于解已知數(shù)學(xué)難題的計(jì)算量。,密碼體制的分類,按處理明文的方法分： 分組（塊）密碼：按組處理 - 特點(diǎn)：適合數(shù)據(jù)庫加密，組內(nèi)有錯(cuò)誤擴(kuò)散；一般用于公開的理論研究。 序列（流）密碼：連續(xù)處理輸入元素

9、，每次輸出一個(gè) - 特點(diǎn)：加解密速度快，無錯(cuò)誤擴(kuò)散；一般用于實(shí)際的安全產(chǎn)品。,2020年6月23日9時(shí)31分,19,流密碼模型,2020年6月23日9時(shí)31分,20,密碼分析學(xué) Cryptanalysis,典型目標(biāo)：得到密鑰，而不是僅僅得到單個(gè)密文對(duì)應(yīng)的明文。 攻擊傳統(tǒng)密碼體制的一般方法 密碼分析：利用算法的性質(zhì)和明文的特征或某些明密文對(duì)。 窮舉攻擊： 對(duì)一條密文嘗試所有可能的密鑰。平均而言，成功至少需要嘗試所有可能密鑰的一半。,基于密碼分析的攻擊,2020年6月23日9時(shí)31分,22,兩個(gè)概念,絕對(duì)安全，unconditional security 無論花多少時(shí)間，攻擊者都無法將密文解密 原

10、因：攻擊者所需要的信息不在密文里。 除一次一密外，所有的加密算法都不是絕對(duì)安全的 計(jì)算安全，computational security 破譯密碼的代價(jià)超過密文信息的價(jià)值； 破譯密碼的時(shí)間超出了密文信息的有效生命期。,2020年6月23日9時(shí)31分,23,窮舉攻擊：,2020年6月23日9時(shí)31分,24,非技術(shù)因素的攻擊,社會(huì)工程 偷竊 收買 逼問 ,2020年6月23日9時(shí)31分,25,2.2 代換技術(shù),代換法： 將明文字母替換成其他字母、數(shù)字或符號(hào)的方法; 如果把明文看成是0或1的序列，那么密文就是0或1比特序列的另一種表達(dá)。,2020年6月23日9時(shí)31分,26,2.2.1 愷撒密碼 C

11、aesar Cipher,由古羅馬人Julius Caesar發(fā)明的一種密碼體制，它是使用最早的密碼體制之一。 首先用在軍事通信中 替代原理 用字母后的第三個(gè)字母代替 字母表看作是循環(huán)的，即z后面的字母是a,愷撒密碼的一般形式,將英文字母表左環(huán)移k（0k26）位得到替換表，則得一般的Caesar算法。 共有26種可能的密碼算法（25種可用） 將每個(gè)字母分配一個(gè)數(shù)值，如a0，b=1等，則算法可表示為： 加密算法：c = E(p) = (p + k) mod (26) 解密算法：p = D(c) = (ck) mod (26),2020年6月23日9時(shí)31分,28,愷撒密碼 - 加密,方式一：公式

12、計(jì)算 明文編碼： 如a=0，b=1，z=25，則 明文P p1p2pn （加密）運(yùn)算：Ci pi + k （mod 26）, i 1,2,n 方式二：查表,2020年6月23日9時(shí)31分,29,愷撒密碼 - 解密,方式一：公式計(jì)算 密文C c1c2cn （解密）運(yùn)算：Pi ci - k （mod 26）, i1,2,n 方式二：查表（例k=3）,2020年6月23日9時(shí)31分,30,對(duì)愷撒密碼的密碼分析,愷撒密碼的三個(gè)特征 加密和解密算法已知 需嘗試的密鑰只有25個(gè) 所破譯的明文語言已知，其意義易于識(shí)別 這三個(gè)特征使窮舉攻擊很容易實(shí)現(xiàn) 抗攻擊分析： 加大密鑰空間：如允許字母的任意替代 使明文的

13、語言未知：如將明文壓縮,2020年6月23日9時(shí)31分,31,2.2.2 單表代替密碼,不是簡(jiǎn)單有序地字母移位 每個(gè)明文字母映射到一個(gè)不同的隨機(jī)密文字母 密鑰數(shù)目： 26！,2020年6月23日9時(shí)31分,32,單表代換密碼分析,密鑰空間： 26! 4 x 1026 大于56位DES的密鑰空間。 貌似安全，實(shí)則不然 ： 基于語言統(tǒng)計(jì)規(guī)律仍可破譯,2020年6月23日9時(shí)31分,33,語言的冗余與密碼分析,人類的語言是有冗余的 字母的使用頻率是不同的 在英語中E使用的頻率最高 有些字母使用較少 單字母、雙字母、三字母組合統(tǒng)計(jì),2020年6月23日9時(shí)31分,34,英語字母使用頻率,2020年6月

14、23日9時(shí)31分,35,2.2.3 Playfair密碼,單表代換缺陷是：密文帶有原始字母使用頻率的一些統(tǒng)計(jì)學(xué)特征。 對(duì)策：每個(gè)字母提供多種代換。 最著名的多表代替密碼 Playfair密碼: Charles Wheatstone 于1854年發(fā)明, 用其朋友Baron Playfair 命名 把明文中的雙字母音節(jié)作為一個(gè)單元并將其轉(zhuǎn)換成密文的“雙字母音節(jié)”,2020年6月23日9時(shí)31分,36,Playfair密鑰矩陣,5 x 5 字母矩陣 從左到右，從上到下： 填寫密鑰單詞 用其他字母填寫剩下的空缺 I = J,2020年6月23日9時(shí)31分,37,加密 明文分組（填充）：2個(gè)字母組 同行

15、字母對(duì)加密：循環(huán)向右，eiFK 同列字母對(duì)加密：循環(huán)向下，cuEM，xiAS 其它字母對(duì)加密：矩形對(duì)角線字母，且按行排序，hsBP，esIL（或JL） 解密 加密的逆向操作,Playfair密碼的加/解密步驟,2020年6月23日9時(shí)31分,38,Playfair密碼安全性分析,安全性優(yōu)于簡(jiǎn)單的單表代換密碼 共有26x26個(gè)字母對(duì)，判斷單個(gè)字母對(duì)困難 字母對(duì)的相對(duì)頻率的統(tǒng)計(jì)規(guī)律低于單個(gè)字母的 利用頻率分析字母對(duì)較困難 在WW中使用多年 雖然明文中字母的統(tǒng)計(jì)規(guī)律在密文中得到了降低，但密文中仍含有明文的部分結(jié)構(gòu)信息 給定幾百個(gè)字母，即可被攻破,2020年6月23日9時(shí)31分,39,字母出現(xiàn)的相對(duì)頻

16、率,2020年6月23日9時(shí)31分,40,2.2.4 希爾(Hill)密碼,另一個(gè)有趣的多表代換密碼 1929年由數(shù)學(xué)家Lester Hill發(fā)明 加密方法是由m個(gè)線性方程決定的，方程中每個(gè)字母被指定為一個(gè)數(shù)值（a=0,b=1,z=25),2020年6月23日9時(shí)31分,41,Hill密碼的加/解密過程,明文分組并編碼 CKP mod 26，其中，K為密鑰矩陣，P、C分別為明、密文分組,加密:,解密:,密文分組并編碼 PK-1C mod 26,對(duì)密鑰矩陣K的要求：在mod 26下可逆.,2020年6月23日9時(shí)31分,42,密鑰矩陣K,明文分組P“mor”,明文編碼 P,加密 C,mod 26

17、,C,，即C“HDL”,Hill密碼的例子,加密：,K1,2020年6月23日9時(shí)31分,43,密鑰矩陣K,明文P“mor”,明文 P,解密 P,mod 26,C,C“HDL”,Hill密碼的例子,解密：,K1,2020年6月23日9時(shí)31分,44,Hill密碼的特點(diǎn),完全隱藏了單字母的頻率特性。 連續(xù)m個(gè)明文替換成m個(gè)密文 所用矩陣越大所隱藏的頻率信息越多。 足以抵抗唯密文攻擊 較易被已知明文攻擊破解,2020年6月23日9時(shí)31分,45,2.2.5 多表代換密碼 Polyalphabetic Ciphers,代換規(guī)則： 使用一系列相關(guān)的單表替代規(guī)則 一個(gè)密鑰決定對(duì)一個(gè)給定的變換選擇特定的規(guī)

18、則 例： Vigenre密碼（1858） Beaufort 密碼 Vernam密碼,Vigenre密碼的歷史,Blaise de Vigenre 發(fā)明了多字母替換密碼（polyalphabetic substitution cipher） 隨著破譯單表密碼的技術(shù)提高，使得vigenre cipher 逐漸被各國使用 1854年，首次被 Charles Babbage 攻破，但沒有公開 Friedrich Kasiski于1863年攻破并發(fā)表了此密碼的各種變形，被沿用到20世紀(jì),2020年6月23日9時(shí)31分,47,Vigenre密碼,方式一：數(shù)學(xué)公式計(jì)算 設(shè)明文 P = p1p2pn，密鑰 k

19、 = k1k2kn，密文C = c1c2cn 加密： ci= pi+ki (mod 26)，=1，2，n； 說明：若明文長(zhǎng)度大于n，則k重復(fù)使用。,加密:,2020年6月23日9時(shí)31分,48,方式二：查表法 （密鑰k，明文P）密文C,Vigenre密碼,2020年6月23日9時(shí)31分,49,Vigenre密碼,方法一：數(shù)學(xué)公式計(jì)算 pi = ciki (mod 26)，=1，2，n； 方法二：查表 密鑰k行里密文C所在列的頂部字母明文P,解密：,2020年6月23日9時(shí)31分,50,Vigenre密碼例子,加密過程： P“encode and decode”，k“mykey”,2020年6月

20、23日9時(shí)31分,51,Vigenre密碼例子,解密過程： C“QLMSBQYXHBQAYHC”，k“mykey”,2020年6月23日9時(shí)31分,52,Vigenre密碼的安全性,強(qiáng)度在于：每個(gè)明文字母對(duì)應(yīng)著多個(gè)密文字母，明、密文字母不是一一對(duì)應(yīng)關(guān)系 字母的統(tǒng)計(jì)規(guī)律進(jìn)一步降低 Vigenre本人建議：密鑰與明文一樣長(zhǎng) Vigenre代換表中的每一行就是一Caesar密碼,Vigenre密碼分析,攻擊： 首先作單表代換假設(shè)，用頻率分析方法 然后猜測(cè)Vigenre密鑰關(guān)鍵字長(zhǎng)度 密鑰： deceptivedeceptivedeceptive 明文： wearediscoveredsaveyour

21、self 密文： Z I CVTWQNGRZGVTWAVZHCQYGLMGJ 反攻擊：用與消息一樣長(zhǎng)的非周期性的密鑰。 相應(yīng)的攻擊：密鑰和明文有相同的字母頻率分布 對(duì)抗技術(shù)：選擇與明文一樣長(zhǎng)而且沒有統(tǒng)計(jì)關(guān)系的密鑰。 技術(shù)的關(guān)鍵：密鑰構(gòu)造方法。 Vernam密碼：用循環(huán)的帶子構(gòu)造密鑰。(最終密鑰還是重復(fù)) 一次一密：產(chǎn)生隨機(jī)密鑰，不重復(fù)。不可破 一次一密實(shí)際很少使用。,2020年6月23日9時(shí)31分,54,2.2.6 一次一密,隨機(jī)密鑰 安全強(qiáng)度取決于密鑰的隨機(jī)性 理論上不可破 實(shí)際上不可行 產(chǎn)生大量的隨機(jī)密鑰難 密鑰分配與保護(hù)更難,2.3 置換密碼 Transposition Ciphers,置換：對(duì)明文字母的某種置換 柵欄技術(shù)：按對(duì)角線的順序?qū)懗雒魑?，以行的順序讀出作為密文 易破譯 矩陣排列法 純置換密碼易識(shí)別 多次置換：多階段加密，安全性更高,2020年6月23日9時(shí)31分,56,例：柵欄技術(shù),明文：meet me after the toga party 寫為: m e m a t r h t g p r y e t e f e t e