chap7.3密碼與解密模型-

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

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

等價(jià)設(shè)

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

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

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

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

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

可逆a

與m

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

c=p+3(Mod26)其中的數(shù)3就是凱撒密碼的秘鑰，更一般的形式由下面的公式給出c=p+k(Mod26)其中1≤k≤25.稱這種密碼為移位置換密碼，k稱為移位因子.2023/2/4仿射變換密碼上面移位置換密碼的一個(gè)簡(jiǎn)單變種就是仿射變換密碼，其數(shù)學(xué)表示為在上面例子移位置換密碼下，明文中相鄰的字母對(duì)應(yīng)的密文字母也是相鄰的，如A和B對(duì)應(yīng)的密文字母分別為D和E,但在仿射變換下，對(duì)應(yīng)的密文字母分別為H和K，它們有3個(gè)字母的間隔(a=3)其中自然數(shù)a必須與模m互素2023/2/42023/2/4例假設(shè)下面是仿射變換加密的，試破譯此文FSFPREDLFSHRLERKFXRSKTDMMPRRKFSFUXAFSDHKFSPVMRDSKARLVUURRIFEFKKANEHOFZFUKRESVVS假設(shè)此問(wèn)題由26個(gè)英文字母組成，取m=26.由于與26互素，a有12種不同的取法，b有26種不同的取法，所以仿射變換有12*26=312種。可以用頻率法，即密文中出現(xiàn)次數(shù)最多的字母與英文中最常見的字母對(duì)應(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利用上述解密公式對(duì)密文進(jìn)行解密得到：這是一串沒(méi)有意義的字符串，解密失敗2023/2/4最后破譯文為ANAMERICANSECRETAGENTWILLMEETANAFGHANISTANMOLEINTHECOFFEEBARATTHURSDAYAFTERNOON即ANAMERICANSECRETAGENTWILLMEETANAFGHANISTANMOLEINTHECOFFEEBARATTHURSDAYAFTERNOON破譯成功(3)如令R(17)對(duì)應(yīng)E(4)，K(10)對(duì)應(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)算。

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

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

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

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

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

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

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

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

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

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

提出第一個(gè)方法雙密鑰系統(tǒng)的程序是這樣的收方先告訴發(fā)方如何把情報(bào)制成密碼（敵人也聽到）發(fā)方依法發(fā)出情報(bào)的密文（敵人也可能收到密文）收方將密碼還原成原文（敵人卻解不開密文）2023/2/4公鑰密碼系統(tǒng)的加密原理每個(gè)通信實(shí)體有一對(duì)密鑰（公鑰，私鑰）。公鑰公開，用于加密，私鑰保密，用作解密A向B發(fā)送消息，用B的公鑰加密B收到密文后，用自己的私鑰解密PlainText加密算法解密算法ABcipherPlainTextB的私鑰C的公鑰B的公鑰任何人向B發(fā)送信息都可以使用同一個(gè)密鑰(B的公鑰)加密沒(méi)有其他人可以得到B的私鑰，所以只有B可以解密2023/2/4公鑰密碼系統(tǒng)的簽名原理A向B發(fā)送消息，用A的私鑰加密（簽名）B收到密文后，用A的公鑰解密（驗(yàn)證）PlainText加密算法解密算法cipherPlainTextABA的私鑰A的公鑰2023/2/4RSA算法簡(jiǎn)介RonRivest,AdiShamir,LeonardAdlemanRSA的安全性基于大數(shù)分解的難度RSA在美國(guó)申請(qǐng)了專利（已經(jīng)過(guò)期），在其他國(guó)家沒(méi)有RSA已經(jīng)成了事實(shí)上的工業(yè)標(biāo)準(zhǔn)，在美國(guó)除外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ù)的個(gè)數(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

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

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

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

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

mkф(n)+1≡mmodn2023/2/4RSA算法操作過(guò)程密鑰產(chǎn)生1.取兩個(gè)大素?cái)?shù)p,q,保密;2.計(jì)算n=pq，公開n;3.計(jì)算歐拉函數(shù)ф(n)=（p-1）(q-1)；4.任意取一個(gè)與ф(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算法加密/解密過(guò)程密鑰對(duì)（KU,KR