信息安全-三-信息安全密碼學(xué)課件

信息安全數(shù)學(xué)基礎(chǔ)信息安全基礎(chǔ)密碼學(xué)基礎(chǔ)與應(yīng)用信息安全數(shù)學(xué)基礎(chǔ)信息安全基礎(chǔ)信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件密碼學(xué)的基本概念是經(jīng)過偽裝后的明文c。全體可能出現(xiàn)的密文集合稱為密文空間C密文未經(jīng)過加密的原始信息稱為明文m，明文的全體稱為明文空間M明文由明文空間、密文空間、密碼方案和密鑰空間組成密碼系統(tǒng)密碼學(xué)的基本概念是經(jīng)過偽裝后的明文c。全體可能出現(xiàn)的密文集合密碼學(xué)的基本概念(2)加密和解密算法的操作在稱為密鑰（k）的元素控制下進行。密鑰的全體稱為密鑰空間（K）密鑰確切地描述了加密變換和解密變換的具體規(guī)則密碼方案加密算法對明文進行加密時所使用的規(guī)則的描述Ｅ(m)解密算法對密文進行還原時所使用的規(guī)則D(c)密碼學(xué)的基本概念(2)加密和解密算法的操作在稱為密鑰（k）的2022/11/2514密碼學(xué)的發(fā)展歷程密碼學(xué)是一門古老而深奧的學(xué)科，是結(jié)合數(shù)學(xué)、計算機科學(xué)、電子與通信等諸多學(xué)科于一體的交叉學(xué)科，是研究信息系統(tǒng)安全保密的一門科學(xué)。密碼學(xué)主要包括密碼編碼學(xué)和密碼分析學(xué)兩個分支，其中密碼編碼學(xué)的主要目的是尋求保證信息保密性或仁整形的方法，密碼分析學(xué)的主要目的是研究加密消息的破譯或消息的偽造。密碼學(xué)經(jīng)歷了從古代密碼學(xué)到現(xiàn)代密碼學(xué)的演變。2022/11/2114密碼學(xué)的發(fā)展歷程密碼學(xué)是一門古老而深2022/11/2515最早將現(xiàn)代密碼學(xué)概念運用于實際的是Caesar大帝，他是古羅馬帝國末期著名的統(tǒng)帥和政治家。Caesar發(fā)明了一種簡單的加密算法把他的信息加密用于軍隊傳遞，后來被稱為Caesar密碼。它是將字母按字母表的順序排列，并且最后一個字母與第一個字母相連。加密方法是將明文中的每個字母用其后邊的第三個字母代替，就變成了密文。替代密碼的基本思想，是將明文中的每個字母用此字符在字母表中后面第k個字母替代，加密過程可以表示為函數(shù)E(m)=(m+k)modn。其中：m為明文字母在字母表中的位置數(shù)，n為字母表中的字母個數(shù)，k為密鑰，E(m)為密文字母在字母表中對應(yīng)的位置數(shù)。其解密過程可以表示為函數(shù)E(m)=(m-k)modn。置換密碼的基本思想，不改變明文字符，只是將字符在明文中的排列順序改變，從而實現(xiàn)明文信息的加密，又稱為換位密碼。矩陣換位法是實現(xiàn)置換密碼的一種常用方法，它將明文中的字母按照給的順序安排在一個矩陣中，然后根據(jù)密鑰提供的順序重新組合矩陣中字母，從而形成密文。明文abcdefghijklm密文DEFGHIJKLMNOP明文nopqrstuvwxyz密文QRSTUVWXYZABC2022/11/2115最早將現(xiàn)代密碼學(xué)概念運用于實際的是C2022/11/2516第一階段：古代―1949年這階段的密碼技術(shù)可以說是一種藝術(shù)，而不是一種科學(xué)，密碼學(xué)專家常常是憑知覺和信念來進行密碼設(shè)計和分析，而不是推理和證明，沒有形成密碼學(xué)的系統(tǒng)理論。這一階段設(shè)計的密碼稱為經(jīng)典密碼或古典密碼，并且密碼算法在現(xiàn)代計算機技術(shù)條件下都是不安全的。第二階段：1949―1975年1949年C.E.Shannon（香農(nóng)）發(fā)表在《貝爾實驗室技術(shù)雜志》上的《保密系統(tǒng)的信息理論（CommunicationTheoryofSecrecySystem）》為私鑰密碼體系（對稱加密）建立了理論基礎(chǔ)，從此密碼學(xué)成為一門科學(xué)。圖3-3為Shannon提出的保密通信模型。密碼學(xué)直到今天仍具有藝術(shù)性，是具有藝術(shù)性的一門科學(xué)。這段時期密碼學(xué)理論的研究工作進展不大。1967年DavidKahn發(fā)表了《TheCodeBreakers(破譯者)》一書，詳盡地闡述了密碼學(xué)的發(fā)展和歷史，使人們開始了解和接觸密碼。1976年，Pfister（菲斯特）和美國國家安全局NSA（NationalSecurityAgency）一起制定了數(shù)據(jù)加密標準（DataEncryptionStandard，DES），這是一個具有深遠影響的分組密碼算法。2022/11/2116第一階段：古代―1949年2022/11/2517第三階段：1976年到~1976年Diffie和Hellman發(fā)表的文章“密碼學(xué)發(fā)展的新方向”導(dǎo)致了密碼學(xué)上的一場革命，他們首先證明了在發(fā)送端和接收端無密鑰傳輸?shù)谋Ｃ芡ㄐ攀强赡艿?，從而開創(chuàng)了公鑰密碼學(xué)的新紀元。從此，密碼開始充分發(fā)揮它的商用價值和社會價值。1978年，在ACM通信中，Rivest、Shamir和Adleman公布了RSA密碼體系，這是第一個真正實用的公鑰密碼體系，可以用于公鑰加密和數(shù)字簽名。由于RSA算法對計算機安全和通信的巨大貢獻，該算法的3個發(fā)明人因此獲得計算機界的諾貝爾獎—圖靈獎（A.M.TuringAward）。在EuroCrypt’91年會上，中國旅居瑞士學(xué)者來學(xué)嘉（X.J.Lai）和JamesL.Massey提出了IDEA，成為分組密碼發(fā)展史上的又一個里程碑。2022/11/2117第三階段：1976年到~保密通信系統(tǒng)的基本模型加密算法解密算法密碼分析者加密密鑰Ke解密密鑰Kd竊聽干擾明文m明文m密文c有了密鑰的概念后，加密的過程：c=EKe(m)，解密的過程:m=DKd(c)，其中m∈M，c∈C保密通信系統(tǒng)的基本模型加密算法解密算法密碼分析者加密密鑰Ke信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件密碼體制的分類1.按照密碼的發(fā)展歷史分類

密碼可分為古典密碼和近現(xiàn)代密碼

2.按照需要保密的內(nèi)容分類

根據(jù)密碼體制的密碼算法是否需要保密，可分為受限制的算法（算法的保密基于保持算法的秘密）和基于密鑰的算法（算法的保密性僅僅基于對密鑰的保密）1883年Kerchoffs第一次明確提出了編碼的原則，即加密算法應(yīng)建立在算法的公開不影響明文和密鑰的安全的基礎(chǔ)上密碼體制的分類1.按照密碼的發(fā)展歷史分類

密碼可分為古典密碼體制的分類3.根據(jù)加密算法和解密算法所使用的密鑰是否相同分類

對稱密碼體制

公鑰密碼體制：也稱為非對稱密碼體制4.根據(jù)對明文的處理方式

分組密碼算法和流密碼算法5.根據(jù)是否能進行可逆的加密變換

分為單向函數(shù)密碼體制和雙向變換密碼體制密碼體制的分類3.根據(jù)加密算法和解密算法所使用的密鑰是否相對稱密碼體制

對稱密碼體制SymmetricKeyCryptosystem

加密密鑰=解密密鑰

密鑰必須保密

對稱密碼體制對稱密碼體制加密密鑰=解密密鑰密鑰必公鑰密碼體制公鑰密碼體制PublicKeyCryptosystem

加密密鑰≠解密密鑰

加密密鑰為公鑰（PublicKey），公鑰無需保密解密密鑰為私鑰（PrivateKey）公鑰密碼體制公鑰密碼體制加密密鑰≠解密密鑰加密密鑰為公信息安全-三-信息安全密碼學(xué)課件密碼分析與密碼系統(tǒng)的安全性密碼系統(tǒng)的安全性取決于(1)所使用的密碼算法的保密強度(2)密碼算法以外不安全的因素因此必須同時完善技術(shù)與管理上的要求，才能保證整個密碼系統(tǒng)的安全密碼分析研究如何分析和破解密碼密碼分析與密碼系統(tǒng)的安全性密碼系統(tǒng)的安全性取決于(1)所使信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件密碼分析-窮舉攔截了密文UVACLYFZLJBYLK=1明文=tuzbkxeykiaxkK=2明文=styajwdxjhzwjK=3明文=rsxzivcwigyviK=4明文=qrwyhubvhfxuhK=5明文=pqvxgtaugewtgK=6明文=opuwfsztfdvsfK=7明文=notverysecure則密鑰為7密碼分析-窮舉攔截了密文UVACLYFZLJBYL密碼分析-統(tǒng)計密文XLILSYWIMWRSAJSVWEPIJSVJSYVQMPPMSRHSPPEVWMXMWASVX-LQSVLY-VVCFIJSVIXLIWIPPIVVIGIMZIWQSVISJJIVW頻率分析：I14V13S12,推測i為英文中統(tǒng)計頻率最高的e,則k=4,解密后明文：Thehouseisnowforsaleformilliondollarsitisworthmorehurrybeforethesellerreceivesmoreoffers密碼分析-統(tǒng)計密文XLILSYWIMWRSAJSVWEPI模運算A=q*n+rn正數(shù),r非負，則amodn=r求模：27mod536mod12-18mod14-7mod10模運算A=q*n+rn正數(shù),r非負，則amodn信息安全-三-信息安全密碼學(xué)課件逆元A+bΞ0(modn)a,b為加法逆A*b

Ξ1(modn)a,b為乘法逆A,b為0-n之間的整數(shù)逆元A+bΞ0(modn)a,b為加法逆信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件求解過程Gcd(a,b)R1=a,r2=b;s1=1,s2=0;t1=0;t2=1;While(r2>0){Q=r1/r2;R=r1-q*r2;r1=r2;r2=r;S=s1-q*s2;s1=s2;s2=s;T=t1-q*t2;t1=t2;t2=t;}gcd(a,b)=r1;s=s1;t=t1s*a+t*b=r1;求解過程Gcd(a,b)表格幫助理解算法QR1R2RS1S2ST1T2T5161282110101-512821701-11-56321701-14-562370-14623表格幫助理解算法QR1R2RS1S2ST1T2T516128線性丟番圖方程Ax+by=c設(shè)d=gcd(a,b),c%d!=0則無解，c%d==0則無窮個解有解，求出s,t1特解x0=(c/d)*s,y0=(c/d)*t2通解x=x0+k(b/d)y=y0-k(a/d)k為整數(shù)解決問題：100元換成20元和5元的組合，用本方法求解線性丟番圖方程Ax+by=c設(shè)d=gcd(a,b)信息安全-三-信息安全密碼學(xué)課件擴展歐幾里得算法求逆元Gcd(n,a)=1，則存在逆元N=26a=11則存在逆元。找尋11對26中的乘法逆元：N=100a=23求解過程12對26的乘法逆qr1r2rt1t2T22611401-2211431-251431-25-733105-72610726擴展歐幾里得算法求逆元Gcd(n,a)=1，則存在逆元qr133單變量線性方程ax

Ξb(modn)設(shè)d=gcd(a,n)如果dmodb==0有d個解，dmodb!=0無解1方程兩邊同除以d簡化方程2簡化后的方程兩邊同乘以a的乘法逆，求得特解x03x=x0+k(n/d)k=0,1,…(d-1)

練習(xí)：10xΞ2(mod15)

14xΞ12(mod18)單變量線性方程axΞb(modn)信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件仿射密碼示例例：Alice欲將明文m=“affine”用仿射密碼加密，傳訊給Bob，Bob來解讀。

密鑰：Alice與Bob事先協(xié)定一把密鑰K=(3,8)其中g(shù)cd(3,26)=1

加密：解密：仿射密碼示例例：Alice欲將明文m=“affine”用仿射信息安全-三-信息安全密碼學(xué)課件仿射密碼的選擇明文攻擊截獲密文：PWUFFOGWCHFDWIWEJOUUNJORSMDWRHVCMWJUPVCCG1明文et->WC2明文et->WF對于4->2219->2帶入方程，4*k1+k222(mod26)19*k1+k22(mod26)求得k1=16k2=10k1=16乘法不可逆，因此不是合理答案對于04->2219->5帶入4*k1+k222(mod26)19*k1+k22(mod26)k1對26乘法可逆，進行解密得到Besttimeoftheyearisspringwhenflowersbloom仿射密碼的選擇明文攻擊截獲密文：PWUFFOGWCHFDWI信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件對單表加密算法的統(tǒng)計分析字母百分比字母百分比a8.2n6.8b1.5o7.5c2.8p1.9d4.2q0.1e12.7r6.0f2.2s6.3g2.0t9.0h6.1u2.8i7.0v1.0j0.1w2.4k0.8x2.0l4.0y0.1m2.4z0.1另外最常出現(xiàn)的雙字母組合為：th(3.15%)，he(2.51%)，an(1.72)，in(1.69%)，er(1.54%)，re(1.48%)，es(1.45%)，on(1.45%)，ea(1.31%)，ti(1.28)，at(1.24%)，st(a.21%)，en(1.20%)，nd(1.18%)等。最常出現(xiàn)的三字母組合（Trigram）為：the，ing，and，her，ere，ent，tha，…。對單表加密算法的統(tǒng)計分析字母百分比字母百分比a8.2n6.8信息安全-三-信息安全密碼學(xué)課件維吉尼亞（Vigenere）密碼維吉尼亞密碼：一種典型的多表替代密碼，該密碼體制有一個參數(shù)n，表示采用n位長度的字符串（例如一個英文單詞）作為密鑰。設(shè)密鑰k=k1k2…kn，明文M=m1m2…mn，則加密變換為：Ek(m1,m2,…,mn)=(m1+k1mod26,m2+k2mod26,…,mn+knmod26)

維吉尼亞（Vigenere）密碼維吉尼亞密碼：一種典型的多表信息安全-三-信息安全密碼學(xué)課件維吉尼亞密碼舉例例

設(shè)明文為“killthem”密鑰為“gun”，試用維吉尼亞密碼對明文進行加密。加密密鑰：k=gun=(6,20,13)明文對應(yīng)的數(shù)字為1081111197412密鑰對應(yīng)的數(shù)字6201362013620相加取余變換后：16224171320106對應(yīng)的密文是：qcyrnvkg因

密文為：qcyrvkg維吉尼亞密碼舉例例設(shè)明文為“killthem”密鑰為“g信息安全-三-信息安全密碼學(xué)課件維吉尼亞密碼分析不保存頻率，需要先求出密鑰長度，再求出密鑰/wiki/%E7%BB%B4%E5%90%89%E5%B0%BC%E4%BA%9A%E5%AF%86%E7%A0%811求密鑰長度,密文：LIONWGFGEGGDVWGHHCQUCRHRWAGWIOWQLKZETKKMEVLWPCZVGTHVTSGXQOVGCSVETQLTJSUMVWVEUVLXEWSLGFZMVVWLGYHCUSWXQHKVGSHEEVFLCFDGVSUMPHKIRZDMPHHBVWVWJWIXGFWLTSHGJOUEEHHVUCFVGOWICQLTJSUXGLW維吉尼亞密碼分析不保存頻率，需要先求出密鑰長度，再求出密鑰找到串索引位置，求出差：JSU68168差100SUM69117差48VWV7213260MPH1191278差的最大公約數(shù)為4，密鑰為4的倍數(shù)，首先嘗試一下4，獲得幾個子串，c1由1,5,9…組成,c2由2,6,10,…組成，每個片段分別用統(tǒng)計攻擊,以便得到明文片段。如果明文還不清楚，嘗試8,12…找到串索引位置，求出差：HILL希爾密碼密鑰為一個矩陣解密密鑰為矩陣的逆矩陣HILL希爾密碼密鑰為一個矩陣希爾密碼希爾密碼：利用矩陣變換來對信息實現(xiàn)加密。數(shù)學(xué)定義：設(shè)m是一個正整數(shù)，令M=E=(Z26)m，密鑰Km×m={定義在Z26上的m×m矩陣}，其中K的行列式值必須和26互素，否則不存在K的逆矩陣K-1。對任意的密鑰Km×m，定義加密/解密變換為Ek(x)=Km×m·xmod26

Dk(y)=K-1m×m·ymod26希爾密碼希爾密碼：利用矩陣變換來對信息實現(xiàn)加密。希爾（Hill）密碼舉例密鑰產(chǎn)生：首先決定所用矩陣的大小，譬如是2×2

其中E的行列式值detE必須與26互質(zhì)，否則不存在E的反矩陣。明文：m=‘Hill’

矩陣形態(tài)加密過程：密文c=‘pbwz’

希爾（Hill）密碼舉例密鑰產(chǎn)生：首先決定所用矩陣的大小，譬Hill密碼解密過程解密矩陣計算加密矩陣的反矩陣，再進行模運算（mod26），得解密矩陣

解密過程Hill密碼解密過程解密矩陣計算加密矩陣的反矩陣，再進行模運信息安全-三-信息安全密碼學(xué)課件希爾密碼分析假定知道m(xù)，并且有m個分組的明文密文對，就可以對密碼進行已知明文攻擊創(chuàng)建兩個mXm的矩陣明文P和密文C，C=PKK=CP-1.如果不知道m(xù)，m不大，也可以進行嘗試.假設(shè)m=3，已知三個明文密文對[050710]-----------[030600][131707]-----------[141609][000504]-----------[031711]希爾密碼分析假定知道m(xù)，并且有m個分組的明文密文對，就可以對K=p-1C先求得P的逆矩陣，然后乘積得到K211401030600020307000825X141609=050709130308031711010211K=p-1C先求得P的逆矩陣，然后乘積得到K信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件通俗解釋：離散對數(shù)歐拉定理指出如果gcd(a,n)=1，則aφ(n)≡1modn?，F(xiàn)在考慮如下的一般形式：am≡1modn如果a與n互素，則至少會有一整數(shù)m（比如m=φ(n)）滿足這一方程。稱滿足方程的最小正整數(shù)m為模n下a的階。例如：a=7，n=19，則易求出71≡7mod19，72≡11mod19，73≡1mod19，即7在模19下的階為3。

通俗解釋：離散對數(shù)歐拉定理指出如果gcd(a,n)=1，本原根定理

設(shè)a的階為m，則ak≡1modn的充要條件是k為m的倍數(shù)。推論：a的階m整除φ(n)。如果a的階m等于φ(n)，則稱a為n的本原根。如果a是n的本原根，則a,a2,…,aφ(n)在modn下互不相同且都與n互素。特別地，如果a是素數(shù)p的本原根，則a,a2,…,ap-1在

modp下都不相同。

本原根定理設(shè)a的階為m，則ak≡1modn的充要條件是N=8求階a\ix123456711111111331313135515151577171717i=Ψ（8）=4，aimod8的結(jié)果表。Ord(1)=1,ord(3)=ord(5)=ord(7)=2N=8求階a\i123456711111111331313本原根n=7a\ix123456111111122412413326451442142155462316616161本原根為3，5推論：存在本原根，則本源根的數(shù)目為φ(φ(n))本原根n=7a\i12345611111112241241本原根舉例例如：n=9，則φ(n)=6，考慮2在mod9下的冪21mod9≡2，22mod9≡4，23mod9≡8，24mod9≡7，25mod9≡5，26mod9≡1。即2的階為6，正好等于φ(9)，所以2為9的本原根。

本原根舉例例如：n=9，則φ(n)=6，考慮2在mod9下離散對數(shù)計算b≡akmodp

p=19本原根前提下，對于任意b∈{1,…,p-1}，都有且僅有唯一的正整數(shù)k與b對應(yīng)，使得b≡akmodp，也就是說b和k之間是一一對應(yīng)的關(guān)系。稱k為模p下以a為底b的離散對數(shù)，記為k≡logab(modp)

31≡332≡933≡834≡535≡1536≡737≡238≡639≡18310≡16311≡10312≡11313≡14314≡4315≡12316≡17317≡13318≡1離散對數(shù)的這一特點保證了任意一個明文（密文）字符都有且僅有唯一的密文（明文）字符與之對應(yīng)離散對數(shù)計算b≡akmodpp=1931≡332離散對數(shù)舉例如p=7,存在本原根3，5取3，則存在b，k對：3-12-26-34-45-51-6離散對數(shù)舉例如p=7,存在本原根3，5離散對數(shù)難題當(dāng)a、k、p已知時，可有快速算法比較容易地求出b的值；但如果已知b、a和p時，要求k的值，對于小心選擇的p將至少需要p1/2次以上的運算，如果p足夠大，求解離散對數(shù)問題是相當(dāng)困難的，這就是著名的離散對數(shù)難題。由于離散對數(shù)問題具有較好的單向性，所以離散對數(shù)問題在公鑰密碼學(xué)中得到廣泛應(yīng)用。像EIGamal、Diffie-Hellman、DSA等密碼算法都是建立在離散對數(shù)問題之上的離散對數(shù)難題當(dāng)a、k、p已知時，可有快速算法比較容易地求出b信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件中國電建昆明院中國電建昆明院RSA算法的過程：密鑰產(chǎn)生找素數(shù)選取兩個大的隨機的素數(shù)p，q計算模n和Euler函數(shù)φ(n)n＝pqφ(n)=(p-1)(q-1)找ed≡1modφ(n)隨機取一個數(shù)e(與φ(n)互素)，用擴展Euclid算法求d即可發(fā)布d保密，(d,n)是私鑰Ks發(fā)布(e,n)，這是公鑰Kp銷毀p、qRSA算法的過程：密鑰產(chǎn)生找素數(shù)RSA的簡單例子任選兩個素數(shù)p＝7，q＝17n＝pq＝φ(n)＝請練習(xí)任務(wù)：對明文M=19加密

n＝pq＝119φ(n)＝(p-1)(q-1)＝6×16＝96選取整數(shù)1<e<φ(n)與φ(n)互素：e＝5求e的逆元d：ed≡1modφ(n)請練習(xí)計算C=Me(modn)=?其中M=19請練習(xí)計算M=Cd(modn)=?請練習(xí)d=77c=66RSA的簡單例子任選兩個素數(shù)p＝7，q＝17n＝pq＝練習(xí)p=3，q=11對bnuz進行加密2142126練習(xí)p=3，q=11信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件

如果Alice和Bob想在不安全的信道上交換密鑰，他們可以采用如下步驟：

(1)?Alice和Bob協(xié)商一個大素數(shù)p及p的本原根a，a和p可以公開；

(2)?Alice秘密產(chǎn)生一個隨機數(shù)x，計算X=axmodp，然后把X發(fā)送給Bob；

(3)?Bob秘密產(chǎn)生一個隨機數(shù)y，計算Y=aymodp，然后把Y發(fā)送給Alice；如果Alice和Bob想在不安全的信道上交(4)?Alice計算k=Yxmodp；

(5)?Bob計算k'=Xymodp。

k和k'是恒等的，因為k=Yxmodp=(ay)xmodp=(ax)ymodp=Xymodp=k'

線路上的搭線竊聽者只能得到a、p、X和Y的值，除非能計算離散對數(shù)，恢復(fù)出x和y，否則就無法得到k，因此，k為Alice和Bob獨立計算的秘密密鑰。(4)?Alice計算k=Yxmodp；

下面用一個例子來說明上述過程。Alice和Bob需進行密鑰交換，則：●兩人協(xié)商后決定采用素數(shù)p=353及其本原根a=3?！?Alice選擇隨機數(shù)x=97，計算X=397mod353＝40，并發(fā)送給Bob?！?Bob選擇隨機數(shù)y=233，計算Y=3233mod353＝248，并發(fā)送給Alice。●?Alice計算k=Yxmodp＝24897mod353=160?！?Bob計算k'=Xymodp＝40233mod353=160。k和k‘(160)?即為秘密密鑰。下面用一個例子來說明上述過程。Alice和Diffie-Hellman密鑰交換Bob和Alice都不關(guān)心最終的密鑰到底是什么Bob和Alice相互之間都不分享他們各自的保密數(shù)攻擊者能夠得到g、p以及值gamodp和gbmodp，而得到k的唯一辦法是計算出a和b，這等價于求解離散對數(shù)問題Dh密鑰交換Diffie-Hellman密鑰交換Bob和Alice都不關(guān)Diffie-Hellman的參數(shù)選擇(1)素數(shù)p必須要非常大(多于300個十進制數(shù)位)。(2)素數(shù)p的選擇必須要使得p－1具有至少一個大的素因子(多于60個十進制數(shù)位)。(3)生成元必須要從群<Zp*,×>中選擇。(4)Alice和Bob算出對稱密鑰后，必須立即銷毀x和y。x和y的值只能使用一次Diffie-Hellman的參數(shù)選擇(1)素數(shù)p必須要非2中間人攻擊

Diffie-Hellman密鑰交換容易遭受中間人攻擊：

(1)?Alice發(fā)送公開值(a和p)給Bob，攻擊者Carol截獲這些值并把自己產(chǎn)生的公開值發(fā)送給Bob。

(2)?Bob發(fā)送公開值給Alice，Carol截獲它然后把自己的公開值發(fā)送給Alice。

(3)?Alice和Carol計算出二人之間的共享密鑰k1。2中間人攻擊(4)?Bob和Carol計算出另外一對共享密鑰k2。造成中間人攻擊的原因是Diffie-Hellman密鑰交換不認證對方，沒有對公鑰的合法性進行驗證，利用數(shù)字簽名可以挫敗中間人攻擊。(4)?Bob和Carol計算出另外一對信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件公鑰密碼算法解決的問題為什么需要公鑰密碼算法呢，它可解決以下問題密鑰分配密碼系統(tǒng)密鑰管理問題

數(shù)字簽名問題公鑰密碼算法解決的問題為什么需要公鑰密碼算法呢，它可解決以下不可逆加密體制不可逆加密體制又稱為單向密碼體制，它是一種從明文到密文的不可逆變換，通常在明文到密文的轉(zhuǎn)換中存在信息的損失，因此密文無法恢復(fù)成明文，實現(xiàn)不可逆密碼體制的方法是通過單向散列函數(shù)。單向散列函數(shù)用于某些只需要加密、不需要解密的特殊場合，例如:文件完整性保證口令存儲不可逆加密體制不可逆加密體制又稱為單向密碼體制，它是一種從明單向散列函數(shù)的性質(zhì)①函數(shù)的輸入（明文）可以是任意長度；②函數(shù)的輸出（密文）是固定長度的；③已知明文m，求H(m)較為容易，可用硬件或軟件實現(xiàn)；④已知散列值h，求使得H(m)=h的明文m在計算上是不可行的，這一性質(zhì)稱為函數(shù)的單向性，稱H(m)為單向散列函數(shù)；⑤散列函數(shù)具有防偽造性（又稱弱抗沖突性），即已知m，找出m’(m’≠m)使得H(m’)=H(m)在計算上是不可行的；⑥散列函數(shù)具有很好的抵抗攻擊的能力（又稱強抗沖突性），即找出任意兩個不同的輸入x、y，使得H(y)=H(x)在計算上是不可行的。單向散列函數(shù)的性質(zhì)①函數(shù)的輸入（明文）可以是任意長度；單向散列函數(shù)的性質(zhì)和種類提示：強抗沖突性自然包含弱抗沖突性。第⑤和第⑥個條件給出了散列函數(shù)無碰撞性的概念，如果散列函數(shù)對不同的輸入可產(chǎn)生相同的輸出，則稱該函數(shù)具有碰撞性collision。常見的單向散列函數(shù)有MD5和SHA-1，散列函數(shù)的安全性主要來源于它的單向性。單向散列函數(shù)的性質(zhì)和種類提示：強抗沖突性自然包含弱抗沖突性。散列函數(shù)算法被破解的含義MD5的散列碼長度是128比特，而SHA-1的散列碼長度是160比特。近年來有報道稱已可以在24小時內(nèi)找到MD5的一個沖突，使得MD5對于不同的輸入有相同的輸出結(jié)果，因此說MD5算法已經(jīng)被破解。注意：說MD5算法被破解，只是說可以通過密文找到與明文有相同散列值的一個碰撞，而絕不是說可以將MD5算法加密的密文還原成明文。散列函數(shù)算法被破解的含義MD5的散列碼長度是128比特，而S2對散列函數(shù)的攻擊由于單向散列函數(shù)接受的輸入長度是任意的，而它的輸出長度是固定值，因此單向散列函數(shù)將帶來數(shù)據(jù)的壓縮，單向散列函數(shù)肯定會存在碰撞的可能。如果用單向散列函數(shù)對消息求散列值，是不希望發(fā)生碰撞的，否則攻擊者可以把消息修改成特定的模式，使其和原始消息具有相同的散列值，而用戶卻無法通過計算散列值發(fā)現(xiàn)數(shù)據(jù)已經(jīng)被修改因此散列函數(shù)又被稱為數(shù)字指紋，就是說一般每個不同的消息都有其獨特的散列值。2對散列函數(shù)的攻擊由于單向散列函數(shù)接受的輸入長度是任意的兩類生日攻擊對單向散列函數(shù)的攻擊是指找到散列函數(shù)對不同輸入的碰撞，這稱為生日攻擊，它包括兩類，分別對應(yīng)攻擊散列函數(shù)的弱抗沖突性和強抗沖突性1.第Ⅰ類生日攻擊2.第Ⅱ類生日攻擊（基于生日悖論）兩類生日攻擊對單向散列函數(shù)的攻擊是指找到散列函數(shù)對不同輸入的第Ⅰ類生日攻擊已知一散列函數(shù)H有n個可能的輸出，H(x)是一個特定的輸出，如果對H隨機取k個輸入，則至少有一個輸入y使得H(y)=H(x)的概率為0.5時，k有多大？由(1+x)k≈1+kx，其中|x|<<1，可得1-[1-1/n]k≈1-[1-k/n]=k/n

若使上述概率等于0.5，則k=n/2。特別地，如果H的輸出為m比特長，即可能的輸出個數(shù)n=2m，則k=2m-1

第Ⅰ類生日攻擊已知一散列函數(shù)H有n個可能的輸出，H(x)是第Ⅱ類生日攻擊（基于生日悖論）生日悖論是指：任意找23個人，則他們中有兩個人生日相同的概率會大于50%，如果有30人，則此概率大約為70%，這比我們憑感覺認為的概率要大得多，因此稱為生日悖論。設(shè)散列函數(shù)H有2m個可能的輸出（即輸出長為m比特），如果H的k個隨機輸入中至少有兩個產(chǎn)生相同輸出的概率大于0.5，則k=2m/2。稱尋找函數(shù)H的具有相同輸出的兩個任意輸入的攻擊方式為第Ⅱ類生日攻擊。

第Ⅱ類生日攻擊（基于生日悖論）生日悖論是指：任意找23個人，兩類生日攻擊的難度比較可看出第Ⅱ類生日攻擊比第Ⅰ類生日攻擊容易，因為它只需要尋找2m/2個輸入。因此抵抗第Ⅱ類生日攻擊（對應(yīng)強抗沖突性）比抵抗第Ⅰ類生日攻擊（對應(yīng)弱抗沖突性）要難。例子：針對散列函數(shù)的第Ⅱ類生日攻擊的方法

兩類生日攻擊的難度比較可看出第Ⅱ類生日攻擊比第Ⅰ類生日攻擊容散列函數(shù)的設(shè)計及MD5算法一個好的散列函數(shù)的設(shè)計有一些基本原則：1）對不同的輸入，要盡量不產(chǎn)生相同的散列值（抗沖突性）。2）兩個明文即使只有微小的差別（如只有一位不同），它們的散列值也會有很多位都發(fā)生變化（擴散性），這樣根本不能從散列值看出兩個明文的相似性。3）將明文的長度信息記錄在散列值中，這樣可以更好的防止沖突散列函數(shù)的設(shè)計及MD5算法一個好的散列函數(shù)的設(shè)計有一些基本原MD5散列算法MD5散列算法散列函數(shù)的分類1）帶秘密密鑰的Hash函數(shù)：消息的散列值由只有通信雙方知道的秘密密鑰K來控制。此時，散列碼稱作MAC（MessageAuthenticationCode，消息認證碼）原文消息摘要MACHash函數(shù)密鑰k散列函數(shù)的分類1）帶秘密密鑰的Hash函數(shù)：消息的散列值由消息認證碼的實現(xiàn)MAC的實現(xiàn)的一個簡單方法是先對消息求散列值，再用一個對稱密鑰加密該散列值，這樣，接收方必須知道該對稱密鑰才能夠提取這個散列值，并將該散列值與對消息求出的散列值進行比較。由于散列函數(shù)并不是專為MAC而設(shè)計的，它不使用密鑰，并不能直接構(gòu)造MAC。于是人們想出了將密鑰直接加到原文中再求hash值方法構(gòu)造MAC，傳輸前把密鑰K移去。這種方案的一種實現(xiàn)叫做HMAC消息認證碼的實現(xiàn)MAC的實現(xiàn)的一個簡單方法是先對消息求散列值HMACHash密鑰K原文MAC原文MAC原文密鑰KHashMAC比較HMACHash密鑰K原文MAC原文MAC原文密鑰KHashMDC2）不帶秘密密鑰的散列函數(shù)：消息散列值的產(chǎn)生無需使用密鑰，任何人都可以使用公開的散列函數(shù)算法對散列值進行驗證，這就是普通的散列函數(shù)。此時，散列值稱作MDC（Manipulationdetectioncode，篡改檢驗碼）。MDC通常用來檢測文件或報文的完整性。MDC2）不帶秘密密鑰的散列函數(shù)：消息散列值的產(chǎn)生無需使用密根據(jù)散列函數(shù)使用的算法根據(jù)散列函數(shù)使用的算法，目前的散列函數(shù)主要分為兩類，MD5128位散列值SHA-1 160位散列值根據(jù)散列函數(shù)使用的算法根據(jù)散列函數(shù)使用的算法，目前的散列函數(shù)問題散列函數(shù)的要求是什么？什么是HMAC，MDC問題散列函數(shù)的要求是什么？密碼學(xué)應(yīng)用密碼學(xué)應(yīng)用對稱加密法使用方式ECB電子密碼本CBC密碼分組鏈接模式CFB密碼反饋模式OFC輸出反饋模式CTR計數(shù)器模式分組密碼和流密碼對稱加密法使用方式ECB電子密碼本密碼學(xué)應(yīng)用數(shù)字信封數(shù)字簽名數(shù)字證書。。。要求掌握RSA算法過程，給定n,p,q,能夠算出e,nd,n,加密和解密EIGAMAL算法，給定n,a,選定x，能夠計算y，并能夠加密和解密給定n,a,雙方選定x,y，能夠交換秘鑰DH密碼學(xué)應(yīng)用數(shù)字信封數(shù)字信封技術(shù)：1AB各自產(chǎn)生自己的公私鑰對2公布自己的公鑰，保密自己的私鑰3A待加密信息M，產(chǎn)生對稱加密法的秘鑰k，對稱加密法加密M得到C4A使用B的公鑰，加密k,傳送到B5A將密文C傳送給BB1使用自己的私鑰解密，得到k對應(yīng)42使用k，解密C得到M對應(yīng)5,3數(shù)字信封技術(shù)：1AB各自產(chǎn)生自己的公私鑰對任務(wù)Java加密庫函數(shù)http:///lib/view/open1397274257325.html任務(wù)Java加密庫函數(shù)運用歐拉定律，求結(jié)果12-1mod7777=7X1116-1mod323323=17X1920-1mod403403=31X1344-1mod667667=23X29運用歐拉定律，求結(jié)果12-1mod7777求φ值Φ(29)φ(32)φ(80)φ(100)φ（101）φ(pe)=pe-pe-1p為素數(shù)求φ值Φ(29)φ(32)φ(80)φ(100)φ（練習(xí)1在RSA中，給出n=221,e=5,求d給出n=3937,e=17,求d給出p=19,q=23,e=3,求n,

φ(n)，d。加密信息thisislaugh，編碼值為字母順序練習(xí)1在RSA中，練習(xí)2在eigamal中，給出素數(shù)p=31,選擇適當(dāng)?shù)谋驹鵤,私鑰x,計算g。a,g,p為公鑰，x為私鑰運用字母表順序編碼hello，加密并解密他們練習(xí)2在eigamal中，給出素數(shù)p=31,選擇適當(dāng)?shù)谋驹毩?xí)3DH密鑰分配：

本原根g=7,p=23A選擇x=3B選擇y=6描述它們交換密鑰的過程練習(xí)3DH密鑰分配：信息安全數(shù)學(xué)基礎(chǔ)信息安全基礎(chǔ)密碼學(xué)基礎(chǔ)與應(yīng)用信息安全數(shù)學(xué)基礎(chǔ)信息安全基礎(chǔ)信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件密碼學(xué)的基本概念是經(jīng)過偽裝后的明文c。全體可能出現(xiàn)的密文集合稱為密文空間C密文未經(jīng)過加密的原始信息稱為明文m，明文的全體稱為明文空間M明文由明文空間、密文空間、密碼方案和密鑰空間組成密碼系統(tǒng)密碼學(xué)的基本概念是經(jīng)過偽裝后的明文c。全體可能出現(xiàn)的密文集合密碼學(xué)的基本概念(2)加密和解密算法的操作在稱為密鑰（k）的元素控制下進行。密鑰的全體稱為密鑰空間（K）密鑰確切地描述了加密變換和解密變換的具體規(guī)則密碼方案加密算法對明文進行加密時所使用的規(guī)則的描述Ｅ(m)解密算法對密文進行還原時所使用的規(guī)則D(c)密碼學(xué)的基本概念(2)加密和解密算法的操作在稱為密鑰（k）的2022/11/25237密碼學(xué)的發(fā)展歷程密碼學(xué)是一門古老而深奧的學(xué)科，是結(jié)合數(shù)學(xué)、計算機科學(xué)、電子與通信等諸多學(xué)科于一體的交叉學(xué)科，是研究信息系統(tǒng)安全保密的一門科學(xué)。密碼學(xué)主要包括密碼編碼學(xué)和密碼分析學(xué)兩個分支，其中密碼編碼學(xué)的主要目的是尋求保證信息保密性或仁整形的方法，密碼分析學(xué)的主要目的是研究加密消息的破譯或消息的偽造。密碼學(xué)經(jīng)歷了從古代密碼學(xué)到現(xiàn)代密碼學(xué)的演變。2022/11/2114密碼學(xué)的發(fā)展歷程密碼學(xué)是一門古老而深2022/11/25238最早將現(xiàn)代密碼學(xué)概念運用于實際的是Caesar大帝，他是古羅馬帝國末期著名的統(tǒng)帥和政治家。Caesar發(fā)明了一種簡單的加密算法把他的信息加密用于軍隊傳遞，后來被稱為Caesar密碼。它是將字母按字母表的順序排列，并且最后一個字母與第一個字母相連。加密方法是將明文中的每個字母用其后邊的第三個字母代替，就變成了密文。替代密碼的基本思想，是將明文中的每個字母用此字符在字母表中后面第k個字母替代，加密過程可以表示為函數(shù)E(m)=(m+k)modn。其中：m為明文字母在字母表中的位置數(shù)，n為字母表中的字母個數(shù)，k為密鑰，E(m)為密文字母在字母表中對應(yīng)的位置數(shù)。其解密過程可以表示為函數(shù)E(m)=(m-k)modn。置換密碼的基本思想，不改變明文字符，只是將字符在明文中的排列順序改變，從而實現(xiàn)明文信息的加密，又稱為換位密碼。矩陣換位法是實現(xiàn)置換密碼的一種常用方法，它將明文中的字母按照給的順序安排在一個矩陣中，然后根據(jù)密鑰提供的順序重新組合矩陣中字母，從而形成密文。明文abcdefghijklm密文DEFGHIJKLMNOP明文nopqrstuvwxyz密文QRSTUVWXYZABC2022/11/2115最早將現(xiàn)代密碼學(xué)概念運用于實際的是C2022/11/25239第一階段：古代―1949年這階段的密碼技術(shù)可以說是一種藝術(shù)，而不是一種科學(xué)，密碼學(xué)專家常常是憑知覺和信念來進行密碼設(shè)計和分析，而不是推理和證明，沒有形成密碼學(xué)的系統(tǒng)理論。這一階段設(shè)計的密碼稱為經(jīng)典密碼或古典密碼，并且密碼算法在現(xiàn)代計算機技術(shù)條件下都是不安全的。第二階段：1949―1975年1949年C.E.Shannon（香農(nóng)）發(fā)表在《貝爾實驗室技術(shù)雜志》上的《保密系統(tǒng)的信息理論（CommunicationTheoryofSecrecySystem）》為私鑰密碼體系（對稱加密）建立了理論基礎(chǔ)，從此密碼學(xué)成為一門科學(xué)。圖3-3為Shannon提出的保密通信模型。密碼學(xué)直到今天仍具有藝術(shù)性，是具有藝術(shù)性的一門科學(xué)。這段時期密碼學(xué)理論的研究工作進展不大。1967年DavidKahn發(fā)表了《TheCodeBreakers(破譯者)》一書，詳盡地闡述了密碼學(xué)的發(fā)展和歷史，使人們開始了解和接觸密碼。1976年，Pfister（菲斯特）和美國國家安全局NSA（NationalSecurityAgency）一起制定了數(shù)據(jù)加密標準（DataEncryptionStandard，DES），這是一個具有深遠影響的分組密碼算法。2022/11/2116第一階段：古代―1949年2022/11/25240第三階段：1976年到~1976年Diffie和Hellman發(fā)表的文章“密碼學(xué)發(fā)展的新方向”導(dǎo)致了密碼學(xué)上的一場革命，他們首先證明了在發(fā)送端和接收端無密鑰傳輸?shù)谋Ｃ芡ㄐ攀强赡艿模瑥亩_創(chuàng)了公鑰密碼學(xué)的新紀元。從此，密碼開始充分發(fā)揮它的商用價值和社會價值。1978年，在ACM通信中，Rivest、Shamir和Adleman公布了RSA密碼體系，這是第一個真正實用的公鑰密碼體系，可以用于公鑰加密和數(shù)字簽名。由于RSA算法對計算機安全和通信的巨大貢獻，該算法的3個發(fā)明人因此獲得計算機界的諾貝爾獎—圖靈獎（A.M.TuringAward）。在EuroCrypt’91年會上，中國旅居瑞士學(xué)者來學(xué)嘉（X.J.Lai）和JamesL.Massey提出了IDEA，成為分組密碼發(fā)展史上的又一個里程碑。2022/11/2117第三階段：1976年到~保密通信系統(tǒng)的基本模型加密算法解密算法密碼分析者加密密鑰Ke解密密鑰Kd竊聽干擾明文m明文m密文c有了密鑰的概念后，加密的過程：c=EKe(m)，解密的過程:m=DKd(c)，其中m∈M，c∈C保密通信系統(tǒng)的基本模型加密算法解密算法密碼分析者加密密鑰Ke信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件密碼體制的分類1.按照密碼的發(fā)展歷史分類

密碼可分為古典密碼和近現(xiàn)代密碼

2.按照需要保密的內(nèi)容分類

根據(jù)密碼體制的密碼算法是否需要保密，可分為受限制的算法（算法的保密基于保持算法的秘密）和基于密鑰的算法（算法的保密性僅僅基于對密鑰的保密）1883年Kerchoffs第一次明確提出了編碼的原則，即加密算法應(yīng)建立在算法的公開不影響明文和密鑰的安全的基礎(chǔ)上密碼體制的分類1.按照密碼的發(fā)展歷史分類

密碼可分為古典密碼體制的分類3.根據(jù)加密算法和解密算法所使用的密鑰是否相同分類

對稱密碼體制

公鑰密碼體制：也稱為非對稱密碼體制4.根據(jù)對明文的處理方式

分組密碼算法和流密碼算法5.根據(jù)是否能進行可逆的加密變換

分為單向函數(shù)密碼體制和雙向變換密碼體制密碼體制的分類3.根據(jù)加密算法和解密算法所使用的密鑰是否相對稱密碼體制

對稱密碼體制SymmetricKeyCryptosystem

加密密鑰=解密密鑰

密鑰必須保密

對稱密碼體制對稱密碼體制加密密鑰=解密密鑰密鑰必公鑰密碼體制公鑰密碼體制PublicKeyCryptosystem

加密密鑰≠解密密鑰

加密密鑰為公鑰（PublicKey），公鑰無需保密解密密鑰為私鑰（PrivateKey）公鑰密碼體制公鑰密碼體制加密密鑰≠解密密鑰加密密鑰為公信息安全-三-信息安全密碼學(xué)課件密碼分析與密碼系統(tǒng)的安全性密碼系統(tǒng)的安全性取決于(1)所使用的密碼算法的保密強度(2)密碼算法以外不安全的因素因此必須同時完善技術(shù)與管理上的要求，才能保證整個密碼系統(tǒng)的安全密碼分析研究如何分析和破解密碼密碼分析與密碼系統(tǒng)的安全性密碼系統(tǒng)的安全性取決于(1)所使信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件密碼分析-窮舉攔截了密文UVACLYFZLJBYLK=1明文=tuzbkxeykiaxkK=2明文=styajwdxjhzwjK=3明文=rsxzivcwigyviK=4明文=qrwyhubvhfxuhK=5明文=pqvxgtaugewtgK=6明文=opuwfsztfdvsfK=7明文=notverysecure則密鑰為7密碼分析-窮舉攔截了密文UVACLYFZLJBYL密碼分析-統(tǒng)計密文XLILSYWIMWRSAJSVWEPIJSVJSYVQMPPMSRHSPPEVWMXMWASVX-LQSVLY-VVCFIJSVIXLIWIPPIVVIGIMZIWQSVISJJIVW頻率分析：I14V13S12,推測i為英文中統(tǒng)計頻率最高的e,則k=4,解密后明文：Thehouseisnowforsaleformilliondollarsitisworthmorehurrybeforethesellerreceivesmoreoffers密碼分析-統(tǒng)計密文XLILSYWIMWRSAJSVWEPI模運算A=q*n+rn正數(shù),r非負，則amodn=r求模：27mod536mod12-18mod14-7mod10模運算A=q*n+rn正數(shù),r非負，則amodn信息安全-三-信息安全密碼學(xué)課件逆元A+bΞ0(modn)a,b為加法逆A*b

Ξ1(modn)a,b為乘法逆A,b為0-n之間的整數(shù)逆元A+bΞ0(modn)a,b為加法逆信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件求解過程Gcd(a,b)R1=a,r2=b;s1=1,s2=0;t1=0;t2=1;While(r2>0){Q=r1/r2;R=r1-q*r2;r1=r2;r2=r;S=s1-q*s2;s1=s2;s2=s;T=t1-q*t2;t1=t2;t2=t;}gcd(a,b)=r1;s=s1;t=t1s*a+t*b=r1;求解過程Gcd(a,b)表格幫助理解算法QR1R2RS1S2ST1T2T5161282110101-512821701-11-56321701-14-562370-14623表格幫助理解算法QR1R2RS1S2ST1T2T516128線性丟番圖方程Ax+by=c設(shè)d=gcd(a,b),c%d!=0則無解，c%d==0則無窮個解有解，求出s,t1特解x0=(c/d)*s,y0=(c/d)*t2通解x=x0+k(b/d)y=y0-k(a/d)k為整數(shù)解決問題：100元換成20元和5元的組合，用本方法求解線性丟番圖方程Ax+by=c設(shè)d=gcd(a,b)信息安全-三-信息安全密碼學(xué)課件擴展歐幾里得算法求逆元Gcd(n,a)=1，則存在逆元N=26a=11則存在逆元。找尋11對26中的乘法逆元：N=100a=23求解過程12對26的乘法逆qr1r2rt1t2T22611401-2211431-251431-25-733105-72610726擴展歐幾里得算法求逆元Gcd(n,a)=1，則存在逆元qr133單變量線性方程ax

Ξb(modn)設(shè)d=gcd(a,n)如果dmodb==0有d個解，dmodb!=0無解1方程兩邊同除以d簡化方程2簡化后的方程兩邊同乘以a的乘法逆，求得特解x03x=x0+k(n/d)k=0,1,…(d-1)

練習(xí)：10xΞ2(mod15)

14xΞ12(mod18)單變量線性方程axΞb(modn)信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件仿射密碼示例例：Alice欲將明文m=“affine”用仿射密碼加密，傳訊給Bob，Bob來解讀。

密鑰：Alice與Bob事先協(xié)定一把密鑰K=(3,8)其中g(shù)cd(3,26)=1

加密：解密：仿射密碼示例例：Alice欲將明文m=“affine”用仿射信息安全-三-信息安全密碼學(xué)課件仿射密碼的選擇明文攻擊截獲密文：PWUFFOGWCHFDWIWEJOUUNJORSMDWRHVCMWJUPVCCG1明文et->WC2明文et->WF對于4->2219->2帶入方程，4*k1+k222(mod26)19*k1+k22(mod26)求得k1=16k2=10k1=16乘法不可逆，因此不是合理答案對于04->2219->5帶入4*k1+k222(mod26)19*k1+k22(mod26)k1對26乘法可逆，進行解密得到Besttimeoftheyearisspringwhenflowersbloom仿射密碼的選擇明文攻擊截獲密文：PWUFFOGWCHFDWI信息安全-三-信息安全密碼學(xué)課件信息安全-三-信息安全密碼學(xué)課件對單表加密算法的統(tǒng)計分析字母百分比字母百分比a8.2n6.8b1.5o7.5c2.8p1.9d4.2q0.1e12.7r6.0f2.2s6.3g2.0t9.0h6.1u2.8i7.0v1.0j0.1w2.4k0.8x2.0l4.0y0.1m2.4z0.1另外最常出現(xiàn)的雙字母組合為：th(3.15%)，he(2.51%)，an(1.72)，in(1.69%)，er(1.54%)，re(1.48%)，es(1.45%)，on(1.45%)，ea(1.31%)，ti(1.28)，at(1.24%)，st(a.21%)，en(1.20%)，nd(1.18%)等。最常出現(xiàn)的三字母組合（Trigram）為：the，ing，and，her，ere，ent，tha，…。對單表加密算法的統(tǒng)計分析字母百分比字母百分比a8.2n6.8信息安全-三-信息安全密碼學(xué)課件維吉尼亞（Vigenere）密碼維吉尼亞密碼：一種典型的多表替代密碼，該密碼體制有一個參數(shù)n，表示采用n位長度的字符串（例如一個英文單詞）作為密鑰。設(shè)密鑰k=k1k2…kn，明文M=m1m2…mn，則加密變換為：Ek(m1,m2,…,mn)=(m1+k1mod26,m2+k2mod26,…,mn+knmod26)

維吉尼亞（Vigenere）密碼維吉尼亞密碼：一種典型的多表信息安全-三-信息安全密碼學(xué)課件維吉尼亞密碼舉例例

設(shè)明文為“killthem”密鑰為“gun”，試用維吉尼亞密碼對明文進行加密。加密密鑰：k=gun=(6,20,13)明文對應(yīng)的數(shù)字為1081111197412密鑰對應(yīng)的數(shù)字6201362013620相加取余變換后：16224171320106對應(yīng)的密文是：qcyrnvkg因

密文為：qcyrvkg維吉尼亞密碼舉例例設(shè)明文為“killthem”密鑰為“g信息安全-三-信息安全密碼學(xué)課件維吉尼亞密碼分析不保存頻率，需要先求出密鑰長度，再求出密鑰/wiki/%E7%BB%B4%E5%90%89%E5%B0%BC%E4%BA%9A%E5%AF%86%E7%A0%811求密鑰長度,密文：LIONWGFGEGGDVWGHHCQUCRHRWAGWIOWQLKZETKKMEVLWPCZVGTHVTSGXQOVGCSVETQLTJSUMVWVEUVLXEWSLGFZMVVWLGYHCUSWXQHKVGSHEEVFLCFDGVSUMPHKIRZDMPHHBVWVWJWIXGFWLTSHGJOUEEHHVUCFVGOWICQLTJSUXGLW維吉尼亞密碼分析不保存頻率，需要先求出密鑰長度，再求出密鑰找到串索引位置，求出差：JSU68168差100SUM69117差48VWV7213260MPH1191278差的最大公約數(shù)為4，密鑰為4的倍數(shù)，首先嘗試一下4，獲得幾個子串，c1由1,5,9…組成,c2由2,6,10,…組成，每個片段分別用統(tǒng)計攻擊,以便得到明文片段。如果明文還不清楚，嘗試8,12…找到串索引位置，求出差：HILL希爾密碼密鑰為一個矩陣解密密鑰為矩陣的逆矩陣HILL希爾密碼密鑰為一個矩陣希爾密碼希爾密碼：利用矩陣變換來對信息實現(xiàn)加密。數(shù)學(xué)定義：設(shè)m是一個正整數(shù)，令M=E=(Z26)m，密鑰Km×m={定義在Z26上的m×m矩陣}，其中K的行列式值必須和26互素，否則不存在K的逆矩陣K-1。對任意的密鑰Km×m，定義加密/解密變換為Ek(x)=Km×m·xmod26

Dk(y)=K-1m×m·ymod26希爾密碼希爾密碼：利用矩陣變換來對信息實現(xiàn)加密。希爾（Hill）密碼舉例密鑰產(chǎn)生：首先決定所用矩陣的大小，譬如是2×2

其中E的行列式值detE必須與26互質(zhì)，否則不存在E的反矩陣。明文：m=‘Hill’

矩陣形態(tài)加密過程：密文c=‘pbwz’

希爾（Hill）密碼舉例密鑰產(chǎn)生：首先決定所用矩陣的大小，譬Hill密碼解密過程解密矩陣計算加密矩陣的反矩陣，再進行模運算（mod26），得解密矩陣

解密過程Hill密碼解密過程解密矩陣計算加密矩陣的反矩陣，再進行模運信息安全-三-信息安全密碼學(xué)課件希爾密碼分析假定知道m(xù)，并且有m個分組的明文密文對，就可以對密碼進行已知明文攻擊創(chuàng)建兩個mXm的矩陣明文P和密文C，C=PKK=CP-1.如果不知道m(xù)，m不大，也可以進行嘗試.假設(shè)m=3，已知三個明文密文對[050710]-----------[030600][131707]-----------[141609][000504]-----------[031711]希爾密碼分析假定知道