無線網絡安全技術2011-2密碼學概述

無線網絡安全技術秦中元

東南大學信息科學與工程學院

信息安全研究中心

zyqin@2024/7/92上節(jié)課內容課程相關信息第一章概述1.1信息安全1.2網絡安全1.3無線網絡安全2024/7/93本次課內容第二章經典加密技術2.1密碼學概述2.2古典密碼代替密碼置換密碼2024/7/942.1密碼學概述密碼學(Cryptology):是研究信息系統(tǒng)安全保密的科學.密碼編碼學(Cryptography):主要研究對信息進行編碼,實現(xiàn)對信息的隱蔽.密碼分析學(Cryptanalytics):主要研究加密消息的破譯或消息的偽造.2024/7/952.1.1基本術語消息被稱為明文(Plaintext)。用某種方法偽裝消息以隱藏它的內容的過程稱為加密(Encryption)，被加密的消息稱為密文(Ciphertext)，而把密文轉變?yōu)槊魑牡倪^程稱為解密(Decryption)。對明文進行加密操作的人員稱作加密員或密碼員(Cryptographer).所傳送消息的預定對象稱為接收者(Receiver).密碼算法(CryptographyAlgorithm):是用于加密和解密的數(shù)學函數(shù)。密碼員對明文進行加密操作時所采用的一組規(guī)則稱作加密算法(EncryptionAlgorithm).接收者對密文解密所采用的一組規(guī)則稱為解密算法(DecryptionAlgorithm).2024/7/96加解密過程示意圖加密和解密算法的操作通常都是在一組密鑰的控制下進行的,分別稱為加密密鑰(EncryptionKey)和解密密鑰(DecryptionKey).2024/7/97加密通信的模型密碼學的目的：Alice和Bob兩個人在不安全的信道上進行通信，而破譯者Oscar不能理解他們通信的內容。2024/7/982.1.2密碼學的起源和發(fā)展三個階段：1949年之前密碼學是一門藝術1949～1975年密碼學成為科學1976年以后密碼學的新方向——公鑰密碼學2024/7/99密碼學的起源隱寫術(steganography):通過隱藏消息的存在來保護消息.隱形墨水圖像信息藏頭詩2024/7/9102024/7/9112024/7/912密碼學的起源和發(fā)展(1949年之前)古典密碼（classicalcryptography)密碼學還不是科學,而是藝術出現(xiàn)一些密碼算法和加密設備密碼算法的基本手段(substitution&permutation)出現(xiàn)，針對的是字符簡單的密碼分析手段出現(xiàn)主要特點：數(shù)據(jù)的安全依賴于算法是否保密；2024/7/913密碼學的起源和發(fā)展(1949～1975)

計算機使得基于復雜計算的密碼成為可能1949年Shannon的“TheCommunicationTheoryofSecretSystems”1967年DavidKahn的《TheCodebreakers》1971-73年IBMWatson實驗室的HorstFeistel等的幾篇技術報告Smith,J.L.,TheDesignofLucifer,ACryptographicDeviceforDataCommunication,1971Smith,J.L.,…,AnExprementalApplicationofCryptogrphytoaremotelyAccessedDataSystem,Aug.1972Feistel,H.,CryptographyandComputerPrivacy,May1973數(shù)據(jù)的安全基于密鑰而不是算法的保密2024/7/914密碼學的起源和發(fā)展(1976年以后)1976年Diffie&Hellman的“NewDirectionsinCryptography”提出了不對稱密鑰密碼1977年Rivest,Shamir&Adleman提出了RSA公鑰算法90年代逐步出現(xiàn)橢圓曲線等其他公鑰算法公鑰密碼使得發(fā)送端和接收端無密鑰傳輸?shù)谋Ｃ芡ㄐ懦蔀榭赡埽?024/7/9152.1.3密碼算法分類1.按照保密的內容分類:受限制的（restricted)算法:算法的保密性基于保持算法的秘密?；诿荑€（key-based)的算法:算法的保密性基于對密鑰的保密。2024/7/916密碼算法分類2.基于密鑰的算法，按照密鑰的特點分類：對稱密碼算法（symmetriccipher)：又稱傳統(tǒng)密碼算法（conventionalcipher)，就是加密密鑰和解密密鑰相同，或實質上等同，即從一個易于推出另一個。又稱秘密密鑰算法或單密鑰算法。非對稱密鑰算法（asymmetriccipher)，又稱公開密鑰算法（public-keycipher)：加密密鑰和解密密鑰不相同，從一個很難推出另一個。 公開密鑰算法用一個密鑰進行加密,而用另一個進行解密.其中的加密密鑰可以公開,又稱公開密鑰（publickey)，簡稱公鑰。解密密鑰必須保密,又稱私人密鑰（privatekey)私鑰，簡稱私鑰。2024/7/917密碼算法分類3.按照明文的處理方法：分組密碼（blockcipher):將明文分成固定長度的組，用同一密鑰和算法對每一塊加密，輸出也是固定長度的密文。流密碼（streamcipher):又稱序列密碼.序列密碼每次加密一位或一字節(jié)的明文，也可以稱為流密碼。 流密碼是手工和機械密碼時代的主流。2024/7/9182.1.4密碼分析假設破譯者Oscar是在已知密碼體制的前提下來破譯Bob使用的密鑰。這個假設稱為Kerckhoff原則。最常見的破解類型如下：1.唯密文攻擊：Oscar具有密文串y.2.已知明文攻擊:Oscar具有明文串x和相應的密文y.3.選擇明文攻擊：Oscar可獲得對加密機的暫時訪問，因此他能選擇明文串x并構造出相應的密文串y。4.選擇密文攻擊:Oscar可暫時接近密碼機,可選擇密文串y，并構造出相應的明文x.這一切的目的在于破譯出密鑰或密文2024/7/919密碼算法的安全性無條件安全（Unconditionallysecure）無論破譯者有多少密文,他也無法解出對應的明文,即使他解出了,他也無法驗證結果的正確性.Onetimepad計算上安全（Computationallysecure）破譯的代價超出信息本身的價值破譯的時間超出了信息的有效期.2024/7/920窮盡密鑰搜索所需的平均時間熱力學的角度問題：多長的密鑰是計算上安全的？方法：利用熱力學第二定律進行求解。解：信息的表達需要一定的能量。通過改變系統(tǒng)的狀態(tài)，記錄單獨的1位所需要的能量不少于kT（T表示系統(tǒng)的絕對溫度，k=1.38*10-16erg/K為Boltzman常數(shù))

假設在宇宙中運行，宇宙的環(huán)境溫度為3.2K，則計算機操作1位需消耗4.4*10-16erg

太陽每年輻射的能量約為1.21*1041erg,可處理187位。假設連續(xù)提供32年，可處理192位。256位：1020年。結論：對256位的密鑰進行窮舉攻擊是絕對行不通的。2024/7/922本次課內容第二章經典加密技術2.1密碼學概述2.2古典密碼代替密碼置換密碼2024/7/9232.2古典密碼古典密碼總的來說是基于字符的密碼代替密碼（substitutioncipher)：就是明文中的每一個字符被替換成密文中的另一個字符。接收者對密文做反向替換就可以恢復出明文。置換密碼(permutationcipher)，又稱換位密碼（transpositioncipher)：明文的字母保持相同，但順序被打亂了。2024/7/9242.2.1代替密碼簡單代替密碼（simplesubstitutioncipher),又稱單字母密碼（monoalphabeticcipher):明文的一個字符用相應的一個密文字符代替。多字母密碼（polyalphabeticcipher)：明文中的字符映射到密文空間的字符還依賴于它在上下文中的位置。2024/7/925簡單代替密碼單表代換密碼移位（shift）密碼、乘數(shù)（multiplicative)密碼仿射（affine)密碼、多項式（Polynomial)密碼密鑰短語（KeyWord)密碼多表代換密碼維吉尼亞（Vigenere)密碼博福特（Beaufort）密碼滾動密鑰(running-key)密碼弗納姆(Vernam)密碼轉輪機(rotormachine)2024/7/926多字母代換密碼可以用矩陣變換方便地描述多字母代換密碼，有時又稱其為矩陣變換密碼。PlayfaircipherHillcipher2024/7/9272.2.2數(shù)學基礎同余的概念：給定任意整數(shù)a和q，以q除a，余數(shù)是r，則可以表示為a=sq+r,0≤r<q，其中商s=[a/q],表示小于a/q的最大整數(shù)。定義r為amodq的剩余，記為r≡amodq.若整數(shù)a和b有(amodq)=(bmodq)，則稱a與b在modq下同余。對于滿足{r}={a|a=sq+r,s∈Z}的整數(shù)集稱為同余類。模運算有下述性質：若q|(a-b)，則a≡bmodq(amodq)=(bmodq)意味a≡bmodqa≡bmodq等價于b≡amodq若a≡bmodq且b≡cmodq，則a≡cmodq2024/7/928模算術（ModularArithmatic)在modq的q個剩余類集{0，1，2，…，q-1}上可以定義加法和乘法運算如下:加法:((amodq)+(bmodq))modq=(a+b)modq乘法:((amodq)×(bmodq))modq=(a×b)modq2024/7/9292.2.3移位密碼算法數(shù)學描述：設P=C=K=Z，對k∈K，定義ek(x)=x+k(mod26)=y∈C同時dk(y)=y-k(mod26)1：26個英文字母與模26剩余類集合{0,….,25}建立一一對應；2.當k=3時，為Caesar密碼，即abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABC例子:cipher=>FLSKHU實際算法為：同時有，d3(y)=y-3(mod26)2024/7/930移位密碼算法分析移位密碼很容易受到唯密文攻擊。因為：加解密算法已知可能嘗試的密鑰只有26個例如：給定加密的消息: PHHWPHDIWHUWKHWRJDSDUWB通過強力攻擊得到明文：

meetmeafterthetogaparty.2024/7/9312.2.4乘數(shù)密碼算法加密函數(shù)取形式為ek(x)=kx(mod26),k∈Z，要求唯一解的充要條件是gcd(k,26)=1該算法的數(shù)學描述為：設P=C=Z，K={k∈Z|gcd(k,26)=1},對k∈K，定義ek(x)=kx(mod26)和dk(y)=k-1(y)(mod26)，x,y∈Z例子:k=9,ABCDEFGHIJKLMNOPQRSTUVWXYZAJSBKTCLUDMVENWFOXGPYHQZIR加密操作：

cipher=>SUFLKX2024/7/932乘數(shù)密碼算法分析密鑰空間小。對于乘數(shù)密碼，當且僅當a與26互素時，加密變換才是一一映射的，因此a的選擇有11種：

a=3,5,7,9,11,15,17,19,21,23,25可能嘗試的密鑰只有11個2024/7/933仿射密碼加密函數(shù)取形式為ea,b(x)=ax+b(mod26),a,b∈Z，要求唯一解的充要條件是gcd(a,26)=1。q=26時，可能的密鑰是26*12-1=311個2024/7/9342.2.5任意的單表代替密碼算法設P=C=Z，K是由26個符號0,1,…,25的所有可能置換組成。任意π∈K，定義eπ(x)=π(x)=y且dπ(y)=π-1(y)=x,π-1是π的逆置換。注：1.置換π的表示：

π＝2.移位密碼、乘數(shù)密碼、仿射密碼算法都是替換密碼的特例3.密鑰空間K很大，|k|=26!≈4×1026，破譯者窮舉搜索是不行的，然而，可由統(tǒng)計的方式破譯它。2024/7/935單表替換密碼的破譯通過字母的使用頻率破譯2024/7/93602468101214ABCDEFGHIJKLMNOPQRSTUVWXYZ頻率密文字母頻率基于語言統(tǒng)計規(guī)律的破譯 1密文：UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ2統(tǒng)計字母的相對頻率；3猜測PZ可能是e和t；4統(tǒng)計字母的相對頻率-雙字母5猜測ZW可能是th，因此ZWP可能是the6經過反復猜測、分析和處理，明文：

itwasdisclosedyesterdaythatserveralinformalbutdirectcontactshavebeenmadewithpoliticalrepresentativesofthevietconginmoscow2024/7/9372.2.6對抗頻率分析的辦法多名代替密碼多表代替密碼多字母代替密碼2024/7/938多名和多表代替密碼與簡單代替密碼類似，只是映射是一對多的，每個明文字母可以加密成多個密文字母。需要較大的密文空間。 例如，A可能對應于5、13、25，B可能對應于7、9、31、42。當對字母的賦值個數(shù)與字母出現(xiàn)頻率成比例時。這是因為密文符號的相關分布會近似于水平線，可以挫敗頻率分析。多表代替密碼：是以一系列（兩個以上）代換表依此對明文消息的字母進行代換的方法。2024/7/939Vigenérecipher(1858)是一種多表移位代替密碼例子：q=26,x=polyalphabeticcipher,K=RADIO明文x=polyalphabeticcipher密鑰k=RADIORADIORADIORADIO密文y=GOOGOCPKTPNTLKQZPKMF2024/7/940Vigenérecipher的破譯依然保留了字符頻率某些統(tǒng)計信息重碼分析法：間距是密鑰長度整數(shù)倍的相同子串有相同密文，反過來，密文中兩個相同的子串對應的密文相同的可能性很大。一次一密Vigenere密碼的改進思路Vigenere密碼的弱點：周期性加長密鑰長度-〉用一個和明文長度一樣長的密鑰如果每次加密都用與明文一樣長的真隨機密鑰，將是最安全的。無法破解！缺點？？2024/7/9422.2.7多字母代替密碼-PlayfairPlayfair:將明文中的雙字母組合作為一個單元對待，并將這些單元轉換為密文的雙字母組合。5×5變換矩陣的構造:先密鑰，后字母順序。I與J視為同一字符加密規(guī)則:按成對字母加密

1)相同對中的字母加分隔符(如x) balloon→balxloon 2)同行取右邊:he→EC 3)同列取下邊:dm→MT 4)其他取交叉:kt→MQ，OD→TR2024/7/943Playfair舉例5×5變換矩陣2024/7/944Playfair密碼分析Playfair有26X26=676種字母對組合字符出現(xiàn)幾率一定程度上被均勻化基于字母頻率的攻擊比較困難依然保留了相當?shù)慕Y構信息2024/7/9452.2.8Hill密碼(1929)基于矩陣的線性變換:將明文與密文都視作m元的向量（x1,x2

，…,xm)；(y