chap7.3密碼與解密模型-

7.3密碼和解密模型密碼的歷史密碼的作用密碼模型西元前404年斯巴達(dá)國(今希臘)北路軍司令萊山得在征服雅典之后,信使趕到,獻(xiàn)上了一條皮帶,上面有文字,通報(bào)敵軍欲斷其歸路的企圖.4世紀(jì)希臘出現(xiàn)了隱蔽書信內(nèi)容的初級密碼.8世紀(jì)古羅馬教徒為傳播新教,創(chuàng)造了「圣經(jīng)密碼」.中世紀(jì)末葉，西班牙的平民百姓與貴族階級的青年男女,為了沖破封建制度對自由戀愛的束縛,不得不采取種種秘密通信的形式,從而導(dǎo)致了各種原始密碼的產(chǎn)生.密碼的歷史2023/2/4

1200年羅馬教皇政府和意大利世俗政府開始有系統(tǒng)地使用密碼.19世紀(jì)隨著資本主義的發(fā)展和資產(chǎn)階級相互斗爭的需要,出現(xiàn)了無線電密碼通信.密碼的作用1917年，英國破譯了德國外長齊默爾曼的電報(bào)，促成了美國對德宣戰(zhàn)。1942年，美國從破譯日本海軍密報(bào)中，獲悉日軍對中途島地區(qū)的作戰(zhàn)意圖和兵力部署，從而能以劣勢兵力擊破日本海軍的主力，扭轉(zhuǎn)了太平洋地區(qū)的戰(zhàn)局。2023/2/4密碼學(xué)名詞明文需要采用某種方法對其進(jìn)行變換來隱蔽它所載荷的信息或字符串加密過程將明文變換成另一種不能被非授權(quán)者所理解的隱蔽信息的消息或字符串的過程明文經(jīng)過加密過程的變換所得的消息或密文字符串將明文變?yōu)槊芪牡淖儞Q加密變換解密變換將密文變?yōu)槊魑牡淖儞Q密鑰加（解）密變換所使用的參數(shù)2023/2/4置換密碼是一個最容易實(shí)現(xiàn)而且最為人們熟悉的密碼。只需要把每個字母由其它的字母來替換而形成密文。而替換的規(guī)則是隨機(jī)的或者是系統(tǒng)的。凱撒密碼是首先將訊息(明碼)中的字母,用不同的字母代替。他的做法是系統(tǒng)地將字母向后推三個位置。a-Db-Ec-Fd-Ge-Hf-Ig-Jh-Ki-Lj-Mk-Nl-Om-Pn-Qo-Rp-Sq-Tr-Us-Vt-Wu-Xv-Yw-Zx-Ay-Bz-C置換密碼2023/2/4關(guān)于模運(yùn)算（mod26）模m

等價設(shè)

a,b為兩個整數(shù),若稱

a模m等價于b，記作剩余集稱為模m的剩余集運(yùn)算律設(shè)a,b

為兩個整數(shù)，則模m

倒數(shù)設(shè)，若存在使得則稱a模m可逆（有模m

倒數(shù)），記作命題模26倒數(shù)表25175112371931521912523211917151197531a–1(mod26)a整數(shù)a模m

可逆a

與m

無公共質(zhì)數(shù)因子2023/2/4thismessageistopsecretWKLVPHVVDJHLVWRSVHFUHWwearethechampionZHDUHWKHFKDPSLRQ如果26個字母被從1到26編號，用p表示明文中某個字母的編號，用c表示相應(yīng)的密文中字母的編號，則凱撒密碼就可以由如下的模型給出

c=p+3(Mod26)其中的數(shù)3就是凱撒密碼的秘鑰，更一般的形式由下面的公式給出c=p+k(Mod26)其中1≤k≤25.稱這種密碼為移位置換密碼，k稱為移位因子.2023/2/4仿射變換密碼上面移位置換密碼的一個簡單變種就是仿射變換密碼，其數(shù)學(xué)表示為在上面例子移位置換密碼下，明文中相鄰的字母對應(yīng)的密文字母也是相鄰的，如A和B對應(yīng)的密文字母分別為D和E,但在仿射變換下，對應(yīng)的密文字母分別為H和K，它們有3個字母的間隔(a=3)其中自然數(shù)a必須與模m互素2023/2/42023/2/4例假設(shè)下面是仿射變換加密的，試破譯此文FSFPREDLFSHRLERKFXRSKTDMMPRRKFSFUXAFSDHKFSPVMRDSKARLVUURRIFEFKKANEHOFZFUKRESVVS假設(shè)此問題由26個英文字母組成，取m=26.由于與26互素，a有12種不同的取法，b有26種不同的取法，所以仿射變換有12*26=312種?？梢杂妙l率法，即密文中出現(xiàn)次數(shù)最多的字母與英文中最常見的字母對應(yīng)。在密文中在平常統(tǒng)計(jì)中F：出現(xiàn)12次E：出現(xiàn)頻率13.04%R：出現(xiàn)12次T：出現(xiàn)頻率13.04%S：出現(xiàn)9次Z：出現(xiàn)頻率0.08%K：出現(xiàn)8次2023/2/42023/2/42023/2/4GTGAERCSGTKESRE……RKLGUGXDERTMMT利用上述解密公式對密文進(jìn)行解密得到：這是一串沒有意義的字符串，解密失敗2023/2/4最后破譯文為ANAMERICANSECRETAGENTWILLMEETANAFGHANISTANMOLEINTHECOFFEEBARATTHURSDAYAFTERNOON即ANAMERICANSECRETAGENTWILLMEETANAFGHANISTANMOLEINTHECOFFEEBARATTHURSDAYAFTERNOON破譯成功(3)如令R(17)對應(yīng)E(4)，K(10)對應(yīng)T(19)，得同余式17=4a+b(mod26)10=19a+b(mod26),我們可以得到加密公式：c=3p+5(mod26),解密公式：p=3-1(c-5)(mod26)=9(c-5)(mod26)=9c+7(mod26)2023/2/4多重圖系統(tǒng)Hill密碼中所用的數(shù)學(xué)手段是矩陣運(yùn)算。

加密過程：1）將英文的26個字母、空格和必要的標(biāo)點(diǎn)符號與1到29之間的整數(shù)建立一一對應(yīng)關(guān)系，稱為字符的表值，然后根據(jù)明文字符的表值，將明文信息用數(shù)字表示。設(shè)通訊雙方給出這29個字符的表值如下：ABCDEFGHIGKLMNO123456789101112131415PQRSTUVWXYZ空格？！16171819202122232425262728292023/2/42）選擇一個n階可逆整數(shù)方陣A，稱為Hilln密碼的加密矩陣，它是加密體制的“密鑰”，是加密的關(guān)鍵，僅通訊雙方掌握。3）將明文字母分組。Hill2

使用的是二階矩陣，所以將明文字母每2個一組（可以推廣至Hilln密碼），若最后僅有一個字母，則補(bǔ)充一個沒有實(shí)際意義的啞字母。這樣使得每組都有2個字母，查出每個字母的表值，構(gòu)成一個二維列向量。4）令，由的兩個分量反查字符表值得到的兩個字母即為密文字母。2023/2/4

解密過程：加密過程的逆過程。字符（明文）表值一組數(shù)分組向量A左乘向量反查表值密文ＨILL密碼的數(shù)學(xué)模型2023/2/4例：設(shè)明文為“MEET求這段明文的Hill2密文。將明文分為：

MEET對應(yīng)密文WYPM2023/2/42023/2/4設(shè)方陣滿足命題2的條件,容易驗(yàn)證2023/2/4對上面例子,det(A)=5,它與29互素，所以滿足2的條件，故A關(guān)于模29的逆為2023/2/4對密文WYPM進(jìn)行解密得到即明文MEET2023/2/4一個簡單實(shí)例明文：Ourmarshalwasshot分組：ourmarshalwasshott補(bǔ)充啞元對應(yīng)向量加密：左乘加密矩陣直接結(jié)果2023/2/4密文向量密文ekrmkbixyjyceelshh解密求得解密矩陣左乘密文向量再取模即可求得明文向量，

從而得出明文結(jié)論使用Hill密碼時的加解密矩陣應(yīng)該模26

可逆2023/2/4HILLn密碼的破譯

關(guān)鍵在于求出解密矩陣（解密密鑰）

只要破譯出n組線性無關(guān)的密文向量

若有2023/2/4一個破譯例子甲方截獲了一段密文：OJWPISWAZUXAUUISEABAUCRSIPLBHAAMMLPJJOTENH經(jīng)分析這段密文是用HILL2密碼編譯的，且這段密文的字母UCRS依次代表了字母TACO，若明文字母的表值如前，試破譯這密文的內(nèi)容？關(guān)系根據(jù)解密原理2023/2/4計(jì)算解密密鑰A－12023/2/4破譯密文向量明文向量明文：ClintonisgoingtovisitacountryinMiddleEast2023/2/4

Hill密碼的加密與解密過程類似于在n維向量空間中進(jìn)行線性變換及其逆變換。每個明文向量是一個Zm上的n維向量，乘以加密矩陣并對m取余，仍為Zm上的一個n維向量。由于加密矩陣A為模m的可逆矩陣，所以如果知道了n個線性無關(guān)的n維明文向量及其對應(yīng)的密文向量，就可以求出它的加密矩陣A及其模m的逆矩陣A-1(modm)2023/2/4公開密鑰系統(tǒng)Hill密碼的加密和解密都只需要加密矩陣這個密鑰就可以了。這種系統(tǒng)稱為單密鑰系統(tǒng)。如果加密和解密使用兩個不同的密鑰，則稱為雙密鑰系統(tǒng)，也稱為公開密鑰系統(tǒng)。密鑰的擁有者將其中一個密鑰公開，另一個保密。雙密鑰系統(tǒng)（1）W.Diffie和M.Hellman最早提出（2）R.L.Rivest,A.Shamir和L.Adleman

提出第一個方法雙密鑰系統(tǒng)的程序是這樣的收方先告訴發(fā)方如何把情報(bào)制成密碼（敵人也聽到）發(fā)方依法發(fā)出情報(bào)的密文（敵人也可能收到密文）收方將密碼還原成原文（敵人卻解不開密文）2023/2/4公鑰密碼系統(tǒng)的加密原理每個通信實(shí)體有一對密鑰（公鑰，私鑰）。公鑰公開，用于加密，私鑰保密，用作解密A向B發(fā)送消息，用B的公鑰加密B收到密文后，用自己的私鑰解密PlainText加密算法解密算法ABcipherPlainTextB的私鑰C的公鑰B的公鑰任何人向B發(fā)送信息都可以使用同一個密鑰(B的公鑰)加密沒有其他人可以得到B的私鑰，所以只有B可以解密2023/2/4公鑰密碼系統(tǒng)的簽名原理A向B發(fā)送消息，用A的私鑰加密（簽名）B收到密文后，用A的公鑰解密（驗(yàn)證）PlainText加密算法解密算法cipherPlainTextABA的私鑰A的公鑰2023/2/4RSA算法簡介RonRivest,AdiShamir,LeonardAdlemanRSA的安全性基于大數(shù)分解的難度RSA在美國申請了專利（已經(jīng)過期），在其他國家沒有RSA已經(jīng)成了事實(shí)上的工業(yè)標(biāo)準(zhǔn)，在美國除外2023/2/4數(shù)論基礎(chǔ)a與b的最大公因數(shù)：gcd(a,b)gcd(20,24)=4,gcd(15,16)=1如果gcd(a,b)=1，稱a與b互素模運(yùn)算moda=qn+r0≤r<n;q=[a/n];

[x]表示小于或等于x的最大整數(shù)a=[a/n]n+(amodn),r=mmodn如果(amodn)=(bmodn)，則稱a與b模n同余，記為

a≡bmodn

例如，23≡8mod5,8≡1mod72023/2/4數(shù)論基礎(chǔ)（續(xù)）歐拉函數(shù)ф(n)n是正整數(shù)，ф(n)是比n小且與n

互素的正整數(shù)的個數(shù)ф(3)=|{1,2}|=2

ф(4)=|{1,3}|=2

ф(5)=|{1,2,3,4}|=4

ф(6)=|{1,5}|=2

ф(7)=|{1,2,3,4,5,6}|=6ф(10)=|{1,3,7,9}|=4

ф(11)=|{1,2,3,4,5,6,7,8,9,10}|=10

如果p是素?cái)?shù)，則ф(p)=p-1,比如ф(2),ф(5)，ф(11)如果p,q是素?cái)?shù)，則ф(pq)=ф(p)ф(q)＝(p-1)(q-1)。比如，ф(10)=ф（2*5）=ф（2）ф（5）=1*4=42023/2/4數(shù)論基礎(chǔ)（續(xù)）例如：

m=3,n=10;ф(10)=4mф(n)=34=81;81mod10=1

即

81≡1mod1034+1=243≡3mod10歐拉定理若整數(shù)m

和n

互素，則等價形式2023/2/4數(shù)論基礎(chǔ)（續(xù)）推論：給定兩個素?cái)?shù)p,q,兩個正整數(shù)n,m

，使得n=pq,0<m<n

；則對于任意正整數(shù)k

，下列關(guān)系成立：

mkф(n)+1≡mmodn2023/2/4RSA算法操作過程密鑰產(chǎn)生1.取兩個大素?cái)?shù)p,q,保密;2.計(jì)算n=pq，公開n;3.計(jì)算歐拉函數(shù)ф(n)=（p-1）(q-1)；4.任意取一個與ф(n)互素的小整數(shù)e,即

gcd(e,ф(n))=1;1<e<ф(n)

e作為公鑰公開;5.尋找d,使得

de≡1modф(n),ed=k

ф(n)+1

d作為私鑰保密。p=7,q=17n=119Ф(n)=96選擇e=55d=k×96＋1令k=4,得到求得d=772023/2/4RSA算法加密/解密過程密鑰對（KU,KR