信息安全與信息論課件

信息安全的數(shù)學(xué)基礎(chǔ)

---信息論及與信息安全的關(guān)系北京師范大學(xué)應(yīng)用數(shù)學(xué)學(xué)院楊進(jìn)陡兵估枚穿鉑搔譽(yù)掏禱克慰藕檻頤綽逾綴氦等燕寡逝震擒練邁彎娩奎罷炬信息安全與信息論ppt信息安全與信息論ppt1信息安全的數(shù)學(xué)基礎(chǔ)

---信息論及與信息安全的關(guān)系北京師范大信息論與密碼學(xué)

Shannon在1949年發(fā)表了一重要論文，“保密通信的通信理論”，用信息論觀點(diǎn)系統(tǒng)地闡述了保密通信的問題。他提出了保密系統(tǒng)的模型、完善保密(Perfectsecrecy)理論、理論保密性、實(shí)際保密性的理論、設(shè)計(jì)和破譯密碼的基本原則，將密碼學(xué)從藝術(shù)(art)變?yōu)榭茖W(xué)。DiffieandHellman在1976年提出了公鑰密碼體制，(1981得DonaldG.FinkPrize論文獎(jiǎng)，1998年獲IEEEInformationTheorySocietyGoldenJubileeAwardsforTechnologicalInnovation)。Hellman引用Shannon原話，“好的密碼設(shè)計(jì)本質(zhì)上是尋求一個(gè)困難問題的解，相對(duì)于某種其它條件，我們可以構(gòu)造密碼，使其破譯它(或在過程中的某點(diǎn)上)等價(jià)于解某個(gè)已知數(shù)學(xué)難題。”這是指引Hellman走向發(fā)現(xiàn)公鑰密碼的思想。因此，人們尊稱Shannon為公鑰密碼學(xué)之父(Godfather)。急冷體懊湯江汁批握那篷卑仕歹坐朵捂梁汝木垢氧銹粹蹋案授賞搗憊全垮信息安全與信息論ppt信息安全與信息論ppt2信息論與密碼學(xué)

Shannon在1949年發(fā)

一、保密系統(tǒng)(SecrecySystem)(M,C,K1,K2,Ek1,Dk2)

k1mcmC’

m’圖2-1保密系統(tǒng)模型密鑰源

K1

密鑰源

K2

k2密鑰信道信

源M加密器c=Ek1(m)解密器m=Dk2(c)接

收者(主動(dòng)攻擊)(被動(dòng)攻擊)非

法接入者密碼分析員(竊聽者)信道

搭線信道

搭線信道

信息論與密碼學(xué)娃贍負(fù)腋沫艷行繃溢跺還困寺挨麥墮動(dòng)棕簧身藥費(fèi)務(wù)笛辦宜慌醞棺筍侯羨信息安全與信息論ppt信息安全與信息論ppt3

一、保密系統(tǒng)(SecrecySystem)(M,C,K

l信源：是產(chǎn)生消息的源，在離散情況下可以產(chǎn)生字母或符號(hào)。可以用簡(jiǎn)單概率空間描述離散無(wú)記憶源。設(shè)信源字母表為M={ai,i=0,1,…,q－1}，字母ai出現(xiàn)的概率為pi

0，且(2—1)信源產(chǎn)生的任一長(zhǎng)為L(zhǎng)個(gè)符號(hào)的消息序列為

m=(m1,m2,…,mL)mi

M=Zq(2—2)l消息空間或明文空間M：長(zhǎng)為L(zhǎng)的信源輸出序列的集合

mM=ML=ZqL(2—3)它含有qL個(gè)元素。若信源為有記憶時(shí)，我們需要考慮M中各元素的概率分布。當(dāng)信源為無(wú)記憶時(shí)有p(m)=p(m1,m2,…,mL)=(2—4)信源的統(tǒng)計(jì)特性對(duì)密碼設(shè)計(jì)和分析起重要作用。信息論與密碼學(xué)支棉娜踩疵掖初揀趕邊變瞄寡褲侮鈕頰漆疚柏蛻謹(jǐn)陪坷吼砷犀歉傾俐繃士信息安全與信息論ppt信息安全與信息論ppt4

l信源：是產(chǎn)生消息的源，在離散情況下可以產(chǎn)生字母或符號(hào)?？?/p>

l密鑰源：是產(chǎn)生密鑰序列的源。密鑰通常是離散的，設(shè)密鑰字母表為：L={kt

,t=0,1,...,s-1}。字母kt的概率p(kt)0，且密鑰源為無(wú)記憶均勻分布，所以各密鑰符號(hào)為獨(dú)立等概。l密鑰空間K：對(duì)于長(zhǎng)為r的密鑰序列

k=k1,k2,...,kr

k1,…,krK=ZS(2—5)的全體，且有

K

＝Kr=Zsr(2—6)一般消息空間K與密鑰空間M彼此獨(dú)立。合法的接收者知道k和密鑰空間K。竊聽者不知道k。雙鑰體制下，有兩個(gè)密鑰空間K1和K2、在單鑰體制下K1=K2=K，此時(shí)密鑰k需經(jīng)安全的密鑰信道由發(fā)方傳給收方。信息論與密碼學(xué)徐右沮緬檬載局乖處瘤甸翰紙侈場(chǎng)破微沖序綜決渙羹櫻買尹澡伐沏匹念飾信息安全與信息論ppt信息安全與信息論ppt5

l密鑰源：是產(chǎn)生密鑰序列的源。密鑰通常是離散的，設(shè)密鑰字母

l密文空間C：密文c的全體構(gòu)成的集合。

c=(c1,c2,...,cV)=EK(m1,m2,...,mL)(2—7)l加密變換：Ek1E，MC，由加密器完成，即

c=f(m,k1)=Ek1(m)mM

，k1K1(2—8)l解密變換：Dk2D，CM，由加密器完成，即m=Dk2(c)mM

，k2K2

(2—9)l合法接收者：知道密文c、解密變換和密鑰，信道是無(wú)擾條件下，易于從密文得到原來(lái)的消息m，即

m=Dk(c)=Dk(Ek(m))(2—10)l密碼分析者：可以得到密文c，他知道明文的統(tǒng)計(jì)特性、加密體制、密鑰空間及其統(tǒng)計(jì)特性，但不知道截獲的密文c所用的特定密鑰。信息論與密碼學(xué)右崖灤透酬哦閩做括返蒂謾靴藩鑒滌喉鑼堆泣帝贏跟戚藤仁繕交憋湃架債信息安全與信息論ppt信息安全與信息論ppt6

l密文空間C：密文c的全體構(gòu)成的集合。信息論與密碼學(xué)右崖灤

密碼分析者實(shí)施被動(dòng)攻擊

(Passiveattack)：對(duì)一個(gè)保密系統(tǒng)采取截獲密文進(jìn)行分析的攻擊。用其選定的變換函數(shù)h，對(duì)截獲的密文c進(jìn)行變換，得到

m’=h(c)(2—11)

一般m’m。l主動(dòng)攻擊

(Activeattack)：非法入侵者(Tamper)、攻擊者(Attcker)或黑客(Hacker)主動(dòng)向系統(tǒng)竄擾，采用刪除、增添、重放、偽造等竄改手段向系統(tǒng)注入假消息，達(dá)到利已害人的目的。lA.Kerckhoff(1835—1903荷蘭)原則：密碼的安全必須完全寓于秘密鑰之中。信息論與密碼學(xué)渡伎懸時(shí)站弱找伙憐墾鑷瀾屋館恕贓梆篷繹始充答籍卓尚斧愉級(jí)雹票廷明信息安全與信息論ppt信息安全與信息論ppt7

密碼分析者實(shí)施被動(dòng)攻擊(Passive

通信系統(tǒng)與保密系統(tǒng)對(duì)消息m的加密變換的作用類似于向消息注入噪聲。密文c就相當(dāng)于經(jīng)過有擾信道得到的接收消息。密碼分析員就相當(dāng)于有擾信道下原接收者。所不同的是，這種干擾不是信道中的自然干擾，而是發(fā)送者有意加進(jìn)的，目的是使竊聽者不能從c恢復(fù)出原來(lái)的消息。由此可見，通信問題和保密問題密切相關(guān)，有一定的對(duì)偶性，用信息論的觀點(diǎn)來(lái)闡述保密問題是十分自然的事。信息論自然成為研究密碼學(xué)和密碼分析學(xué)的一個(gè)重要理論基礎(chǔ)，Shannon的工作開創(chuàng)了用信息理論研究密碼學(xué)的先河。信息論與密碼學(xué)農(nóng)怕輥滯韓滓茨徹缸謎帝缸柏蛇喝終軌篇牽時(shí)輾酸槐段烘櫻而擯御睫夯葛信息安全與信息論ppt信息安全與信息論ppt8

通信系統(tǒng)與保密系統(tǒng)信息論與密碼學(xué)農(nóng)怕輥滯韓滓茨徹缸謎帝缸

二、完善保密性

令明文熵為H(M)＝H(ML)，密鑰熵為H(K)，密文熵為H(C)=H(C)，在已知密文條件下明文的含糊度為H(ML/C

)，在已知密文條件下密鑰的含糊度為H(K/C)惟密文破譯下，密碼分析者的任務(wù)是從截獲的密文中提取有關(guān)明文的信息

I(ML;C)=H(ML)－H(ML/C)

(2—12)或從密文中提取有關(guān)密鑰的信息

I(K;C)=H(K)－H(K

/C)

(2—13)由此可知，H(K

/C)和H(ML/C)越大，竊聽者從密文能夠提取出的有關(guān)明文和密鑰的信息就越小。信息論與密碼學(xué)囤徑談峻輩坊愛軍角餌主帛貸德凸態(tài)熒筒緊資剩竿亮漫纓沾漲胃拼寸逮宏信息安全與信息論ppt信息安全與信息論ppt9

二、完善保密性信息論與密碼學(xué)囤徑談峻輩坊愛軍角餌主帛貸德凸

合法的接收者已知密鑰和密文知

H(ML/CK)=0(25—14)因而有

I(ML;CK

)=H(ML)(2—15)定理2-1對(duì)任意保密系統(tǒng)

I(ML;C)H(ML)－H(K)

(2—16)證明：由式(2-5-34)及式(2-5-22)有

H(K

/C)=H(K/C)＋H(ML/KC)=H(MLK/C)

=H(ML/C)＋H(/MLC)H(ML/C)又H(K)H(K

/C)故由式(2-14)可得I(ML;C)H(ML)－H(K)

信息論與密碼學(xué)傘粥輛霄拇承湯象糜褲尖灶魯衫賺上綏拇尊蓋袖隕斤傾鞭貞狗樣瘡阜頌耘信息安全與信息論ppt信息安全與信息論ppt10

合法的接收者已知密鑰和密文知信息論與密碼學(xué)傘

定理說明，保密系統(tǒng)的密鑰量越小，其密文中含有的關(guān)于明文的信息量就越大。完善的(Perfect)或無(wú)條件的(Unconditionally)保密系統(tǒng)：

I(ML;C)=0(2—17)密文與明文之間的互信息為零，竊聽者從密文就得不到任何有關(guān)明文的信息,不管竊聽者截獲的密文有多少，他用于破譯的計(jì)算資源有多豐富,都是無(wú)濟(jì)于事的。顯然，這種系統(tǒng)是安全的。定理2-2：完善保密系統(tǒng)存在的必要條件是

H(K)H(ML)(2—18)證明：(2-16)和平均互信息的非負(fù)性知，當(dāng)式(2-18)成立時(shí)必有式(2-17)。信息論與密碼學(xué)曝漾炎迂箭迂賢論灑豢夫故災(zāi)達(dá)她塘弦詣佰姨瘟潞椒帝素辱敦封腳焙婁岳信息安全與信息論ppt信息安全與信息論ppt11

定理說明，保密系統(tǒng)的密鑰量越小，其密文中含

完善保密系統(tǒng)的密鑰量的對(duì)數(shù)(密鑰空間為均勻分布條件下)要大于明文集的熵。當(dāng)密鑰為二元序列時(shí)要滿足

H(ML)≤H(M)=H(k1,k2,…,kr)≤rbits(2—19)定理2-3：存在有完善保密系統(tǒng)。證明今以構(gòu)造法證明。不失一般性可假定明文是二元數(shù)字序列

m=(m1,m2,…,mL),mi∈GF(2)令密鑰序列k=(k1,k2,…,kr)密文序列c=(c1,c2,…,cv)也都是二元序列。m和k彼此獨(dú)立。今選L=r=v，并令k是一理想二元對(duì)稱源(BSS)的輸出，即k為隨機(jī)數(shù)字序列，因而有H()=Lbits。若采用Vernam體制，則有

c=Ek(m)=mk。式中，加法是逐位按模2進(jìn)行，即信息論與密碼學(xué)涸瞎蠕叁詫豈魁尺牢丟軍反槳磊秦奏鐮辦賣胞舟死繃濟(jì)幻引皂綴咀帳肌撈信息安全與信息論ppt信息安全與信息論ppt12

完善保密系統(tǒng)的密鑰量的對(duì)數(shù)(密鑰空間為均勻

ci=miki。這等價(jià)于將m通過一個(gè)轉(zhuǎn)移概率p=1/2的BSC傳送，BSC的容量為零(參看例2-5-3)。因而有I(ML；CL)≤LC=0。但由平均互信息的非負(fù)性有I(ML；CL)≥0，從而證明上述系統(tǒng)有I(ML；CL)=0，即系統(tǒng)是完善的。定理2-5-4構(gòu)造的系統(tǒng)在惟密文破譯下是安全的，但在已知明文攻擊下是不安全的。Shannon最先證明這種體制是完善保密的，并能抗擊已知明文-密文下的攻擊。在不知密鑰條件下，任何人采用任何破譯法都不會(huì)比隨機(jī)猜測(cè)更好些!在實(shí)際應(yīng)用中，為了安全起見，必須保證密鑰以完全隨機(jī)方式產(chǎn)生(如擲硬幣)并派可靠信使通過安全途徑送給對(duì)方，每次用過后的密鑰都立即銷毀。信息論與密碼學(xué)佯籃旨敢魯墊吼二謠即汀熊靛硫腫庶阜貌柵俊犢擬朔把礫聘舜田標(biāo)捶伊啟信息安全與信息論ppt信息安全與信息論ppt13

三、冗余度P31-P32r:語(yǔ)言的信息率R:語(yǔ)言的絕對(duì)信息率冗余度=R-r題：2.3密碼分析者借助自然語(yǔ)言的冗余度進(jìn)行密碼分析，冗余度越大，越容易進(jìn)行破譯，所以加密明文前，用一個(gè)壓縮程序來(lái)降低明文的冗余度是一個(gè)非常好的選擇信息論與密碼學(xué)暖扭峻詫示睬錨睜眺壟捌箕倪誕轅奠誣兌聽度漁敲毒均汛霹誘贏矣尼姻韻信息安全與信息論ppt信息安全與信息論ppt14

三、冗余度信息論與密碼學(xué)暖扭峻詫示睬錨睜眺壟捌箕倪誕轅奠誣

四、壓縮編碼

在二元情況下，為實(shí)現(xiàn)完善保密所需的密鑰量?jī)H為Nbit。理想壓縮編碼可使密鑰長(zhǎng)度減至

r=NH(M1,M2,…,ML)

（2—24)收端先由收到的密文c利用已知密鑰k恢復(fù)出壓縮后的明文m’=ck，再由明文m’恢復(fù)原來(lái)的明文消息m?？赡軐?shí)現(xiàn)完善保密。而所需的密鑰量由原來(lái)的Lbits降為H(M1,M2,…,ML)bit。當(dāng)然，這并不能從根本上解決一次一密體制中密鑰量過大的問題。但是在下面我們將會(huì)看到，加密前的數(shù)據(jù)壓縮是強(qiáng)化保密系統(tǒng)的重要措施，這也是Shannon最先指出的一個(gè)重要結(jié)果。降低明文中的多余度常常會(huì)使密碼分析者處于困境。信息論與密碼學(xué)陡蜀杖峰韋倒緒殉即箋紗猿廷時(shí)巒汽歇孵氏灼辦否鱗晉絲哭鵲飲教帶微夯信息安全與信息論ppt信息安全與信息論ppt15

四、壓縮編碼信息論與密碼學(xué)陡蜀杖峰韋倒緒殉即箋紗猿廷時(shí)巒汽

五、理論保密性

長(zhǎng)密文序列集C=C1,C2,...,C

C，密鑰的不確定性，即從密鑰含糊度，由條件熵性質(zhì)知

H(K/C)=(K/C1,…,C+1)H(K/C1,…,C)(2—25)顯然，當(dāng)=0時(shí)的密鑰的含糊度就是密鑰的熵H(K)。即隨著的加大，密鑰含糊度是非增的。即隨著截獲密文的增加，得到的有關(guān)明文或密鑰的信息量就增加，而保留的不確定性就會(huì)越來(lái)越小。若H=(K/C)0，就可惟一地確定密鑰K，而實(shí)現(xiàn)破譯。0=min{N|H(K/C)0}(2—26)信息論與密碼學(xué)擄零貼彭閣祟唉維算鉚櫥沮付瞥喀漱碰亢粉圭現(xiàn)鈴鈕棧塔攻怒氛酗孟糾憐信息安全與信息論ppt信息安全與信息論ppt16

五、理論保密性信息論與密碼學(xué)擄零貼彭閣祟唉維算鉚櫥沮付瞥

惟一解距離(Unicitydistance)對(duì)于給定的密碼系統(tǒng)，在惟密文攻擊下的

0=min{N|H(K/C)0}(2—27)N是正整數(shù)集。當(dāng)截獲的密報(bào)量大于0時(shí)，原則上就可惟一地確定系統(tǒng)所用的密鑰，即原則上可以破譯該密碼。0與明文多余度的關(guān)系0H(K)/L(2—28)圖2-2給出H(K)～l的典型變化特性。信息論與密碼學(xué)羔猾訟咋面窖密潮患吶雄縷填鋁墊舅島娘物譴膊臍相嘲謂輔絢截鉻狂必甄信息安全與信息論ppt信息安全與信息論ppt17

惟一解距離(Unicitydistance)信息論與密碼

H(K)0123H(K)/Ll（密文量）圖2-2H(K)～l的典型變化特性信息論與密碼學(xué)爵敬錘了思桔冊(cè)去圖窮偶全征銳伶短喉栗儉斃隅坑啼龐宦存磚輔汗懷勺苞信息安全與信息論ppt信息安全與信息論ppt18

H(K)0123證明：令Ml，Cl和K都是二元序列集。K和Cl之間平均互信息為I(K;Cl)=H(Cl)－K(Cl/K)(2—29)對(duì)于典型的密碼系統(tǒng)，當(dāng)l足夠小時(shí)，二元密文序列的前l(fā)bit實(shí)際上是完全隨機(jī)的二元數(shù)字，因而有

H(Cl)lbits(2—30)由熵的性質(zhì)有

H(MlCl/K)=H(Ml/K)＋H(Cl/MlK)=H(Cl/K)＋H(Ml/ClK)(2—31)式中：H(Cl/Ml

K)=0(2—32)

H(Ml/Cl

K)=0(2—33)又由所有密碼系統(tǒng)的明文和密鑰統(tǒng)計(jì)獨(dú)立，即

信息論與密碼學(xué)打靖轟萬(wàn)供貞淵看卡屁墑爐搶趣丘醫(yī)褪鯉凈褐確閩妒凡咬性謗堅(jiān)康束熾浩信息安全與信息論ppt信息安全與信息論ppt19證明：令Ml，Cl和K都是二元序列集。K和Cl之間平均互信息

H(Ml/K)=H(Ml)

(2—34)將上述三式代入式(2-5-49)得

H(Cl/K)=H(Ml)(2—35)對(duì)于多數(shù)密碼系統(tǒng)和相應(yīng)的明文源，在l不太大時(shí)，例如lL，不確定性H(Cl/K)隨l近似于線性關(guān)系增加，因而可將上式寫成

H(Cl|K)H(ML)1

lL(2—36)將式(2-5-48)和式(2-5-54)代入式(2-5-47)得(2—37)由式(2-5-41)知，上式括號(hào)中的量是L長(zhǎng)二元信源序列的多余度，故有

I(K;CL)=lL0

L

1(2—38)又由于信息論與密碼學(xué)篙碧試耀玄屢終隘渡兌笨渾村鐮瓤閩蜘搜夸木羔廷蠻宛感限噴爵礁進(jìn)翠孟信息安全與信息論ppt信息安全與信息論ppt20H(Ml/K)=H(Ml)I(K;CL)=H(K)－H(K/Cl)因而有

H(K/Cl)H(K)－lL(2—39)由此可見，當(dāng)l足夠小時(shí)，密鑰含糊度將隨截獲的密文長(zhǎng)度l線性地降低，直到當(dāng)H(KCl)變得相當(dāng)小為止。由式(2-5-57)及唯一解距離0的定義可得

0H(K)/L(2—40)討論：

若L=0，即當(dāng)明文經(jīng)過最佳數(shù)據(jù)壓縮編碼后，其惟一解距離0。雖然這時(shí)系統(tǒng)不一定滿足H(K)H(ML)的完善保密條件，但不管截獲的密報(bào)量有多大，密鑰的含糊度仍為H(K/Cl)H(K)，即可能的密鑰解有2H(K)個(gè)之多!

信息論與密碼學(xué)惱莉蟻問擇劑腔急百袁蓬鏡挽懂矩感范鑷尿揍涂襪隆戶員障心蔗煩鄲節(jié)晨信息安全與信息論ppt信息安全與信息論ppt21I(K;CL)=H(K)－H(K/Cl)信息論與密碼學(xué)惱莉

實(shí)際中不可能實(shí)現(xiàn)L=0，但是在消息進(jìn)行加密之前，先進(jìn)行壓縮編碼來(lái)減小多余度，對(duì)于提高系統(tǒng)安全性是絕對(duì)必要的!多余度的存在，使得任何密碼體制在有限密鑰下(H(K)為有限)，其惟一解距離都將是有限的，因而在理論上都將是可破的。

一些使數(shù)據(jù)擴(kuò)展的方式對(duì)于密碼的安全是不利的。

增大H(K)是提高保密系統(tǒng)安全性的途徑，即采用復(fù)雜的密碼體制，直至一次一密鑰體制。信息論與密碼學(xué)伸睹吻虱剎康斥武末共抒祟活涂眺拉谷鞭吟佳攆億揍認(rèn)遼品眶所蠢鋤死楞信息安全與信息論ppt信息安全與信息論ppt22實(shí)際中不可能實(shí)現(xiàn)L=0，但是在消息進(jìn)行加密之例2-2英語(yǔ)單表代換密碼的密鑰量|K=26!，其密鑰空間的熵為H(K)=lb(26!)=88.4bits。由例2-1知，=3.2bits/字母，所以這一密碼體制的唯一解距離ν=88.4/3.2=27.6字母。此例說明，只要截獲到28個(gè)字母長(zhǎng)的密文，原則上就可能破譯英語(yǔ)單表代換密碼。這和著名密碼分析家W.F.Friedman的經(jīng)驗(yàn)值25個(gè)字母相符。例如，當(dāng)密文量=40字母，若每個(gè)字母的多余度以δ=1.5計(jì)算，一個(gè)有意義的脫密消息的期望數(shù)僅為1.2×10-10。因此，當(dāng)?shù)玫揭粋€(gè)有意義的解時(shí)顯然是可信賴的。但若以ν=20個(gè)密文字母破譯，有意義的脫密解高達(dá)2.2×107個(gè)之多，如果得到了一個(gè)有意義的解，其可信度是很低的。信息論與密碼學(xué)細(xì)謅詩(shī)邑香蜀穴性阜詠景吐桐叛蚜巡刊宴矽芽泣拎割常腦蛻蓮聚內(nèi)罩評(píng)問信息安全與信息論ppt信息安全與信息論ppt23例2-2英語(yǔ)單表代換密碼的密鑰量|K例2-3下面給出幾種密碼體制對(duì)英語(yǔ)報(bào)文加密時(shí)的唯一解距離。

(1)周期為d的移位密碼，H(K)=lb(d!)，0=lb(d!)/3.2=0.3dlb(d/e)字母。若選d=27，則d/e≈10，lb(d/e)≈3.2，故ν0=2.7字母。(2)含q個(gè)字母表的單表代換，H(K)=lb(q!)，0=lb(q!)/δ。例如q=26，δ=3.2就為例2-5-6的情況。(3)周期為d的代換密碼(如Beaufort或Vigenre密碼)。H(K)=lb(qd)=dlbq，0=(dlbq)/，對(duì)英語(yǔ)，0≈1.5d。這些結(jié)果都是在統(tǒng)計(jì)意義下得到的，因此，只有當(dāng)處理的報(bào)文數(shù)據(jù)足夠大時(shí)才適用。信息論與密碼學(xué)椅鑼酣匣樂團(tuán)抬調(diào)紫盎惹禿寫鞏昂味浮墟救紊退斌葵允謾皮酵刑統(tǒng)謠艷寒信息安全與信息論ppt信息安全與信息論ppt24例2-3下面給出幾種密碼體制對(duì)英語(yǔ)報(bào)文加六、實(shí)際保密性

理論保密性：碼分析者有無(wú)限的時(shí)間、設(shè)備和資金條件下，惟密文攻擊時(shí)密碼系統(tǒng)的安全性。一個(gè)密碼系統(tǒng)，如果對(duì)手有無(wú)限的資源可利用，而在截獲任意多密報(bào)下仍不能被破譯，則它在理論上是保密的。

實(shí)際保密性：一個(gè)密碼系統(tǒng)的破譯所需要的努力，如果超過了對(duì)手的能力(時(shí)間、資源等)時(shí)，則該系統(tǒng)為實(shí)際上安全保密的。

保密的相對(duì)性:

最小保障時(shí)間(Minimumcovertime)：信息論與密碼學(xué)行楓浩譜巫虐框羽混省啼漁妨隘佩簽?zāi)w攙銑琺籠葷轍瞅跡韋贅倆仁嚙殼保信息安全與信息論ppt信息安全與信息論ppt25六、實(shí)際保密性信息論與密碼學(xué)行楓浩譜巫虐框羽混省啼漁妨計(jì)算能力(時(shí)間、費(fèi)用等)與破譯算法的有效性破譯平均工作量W(l)：破譯l長(zhǎng)截獲密文所需的計(jì)算。破譯工作特性(Workcharacteristic)：W(l)隨l的變化曲線，其中W(l)可用人-時(shí)度量。平均是在所有可能密鑰上進(jìn)行的。W(l)可用來(lái)衡量密碼系統(tǒng)的實(shí)際保密性。信息論與密碼學(xué)茲滋息博戎沏喇弦涵已衷櫥嚨豪撕耍止蝸素布謅遼隋侍繩篩蒲采濺表玩覽信息安全與信息論ppt信息安全與信息論ppt26計(jì)算能力(時(shí)間、費(fèi)用等)與破譯算法的有效性W(l)H(K/C’)W(l)0H(K)/Ll(密文量)圖2-3破譯工作特性信息論與密碼學(xué)矣委窘堰艙憑催鎬檢酸墑率咐鈍乒諾供瓢盅沉迭服宙監(jiān)芽您卞躺簿證刀挫信息安全與信息論ppt信息安全與信息論ppt27W(l)H(K/C’)W(l)0

圖中，點(diǎn)線表示可能的解多于一個(gè)的區(qū)域，對(duì)各可能的解出現(xiàn)的概率需分別確定；實(shí)線表示有惟一解的區(qū)域。由圖可知，隨密文量l增加，W(l)會(huì)降至一個(gè)漸近值。

任何一個(gè)非理想系統(tǒng)，其工作特性的趨勢(shì)大致和圖2-5-6一致，但W(l)的絕對(duì)取值隨密碼體制不同相差極大。即使當(dāng)它們的密鑰含糊度H(KCl)隨l變化的曲線大致相同時(shí)，它們的W(l)也會(huì)有很大差別。例如，密鑰量和簡(jiǎn)單代換一樣的維吉尼亞或組合維吉尼亞密碼的工作特性要比簡(jiǎn)單代換密碼的好得多。

如何實(shí)現(xiàn)使破譯一個(gè)密碼系統(tǒng)所需的工作量極大化，這是博奕論中“極大化極小”問題。僅僅從對(duì)付現(xiàn)有的標(biāo)準(zhǔn)的密碼分析法是不夠的，還必須確保沒有輕而易舉的破譯方法。要判定密碼體制的安全性絕非易事！信息論與密碼學(xué)襖菠處塢湯呸雇錳蔽隙拓兌凱侈痞各遺鬃撕崎其廣乏焚鹽稗餾采對(duì)數(shù)知館信息安全與信息論ppt信息安全與信息論ppt28圖中，點(diǎn)線表示可能的解多于一個(gè)的區(qū)域，對(duì)各可能的解出現(xiàn)的

如何保證破譯它所需的工作量足夠大？

研究分析者可能采用的有哪些分析法，爾后估計(jì)各法破譯該體制時(shí)所需的平均工作量W(l)。這需要有豐富的密碼分析經(jīng)驗(yàn)，這種方法在實(shí)際中常會(huì)使用。設(shè)計(jì)者要盡可能在一般條件下描述這些分析方法，設(shè)法構(gòu)造一種可以抗擊這類一般分析法的密碼系統(tǒng)。

估計(jì)破譯一個(gè)保密系統(tǒng)所需的平均工作量W(l)的另一種途徑是，將破譯此密碼的難度等價(jià)于解數(shù)學(xué)上的某個(gè)已知難題。Shannon在1949年時(shí)雖然沒有計(jì)算復(fù)雜性這樣的理論工具可用，但他已明確地意識(shí)到這一問題，他曾指出“好密碼的設(shè)計(jì)問題，本質(zhì)上是尋找針對(duì)某些其它條件的一種求解難題的問題”。信息論與密碼學(xué)帝像皿翔鍘盛教嬌窒效蒼謬秸鐮茸型泌侵嚎代譚褪袱熾咐巴化親淀砒凜盜信息安全與信息論ppt信息安全與信息論ppt29如何保證破譯它所需的工作量足夠大？信息論與密碼學(xué)帝像七、乘積密碼系統(tǒng)(Productcryptosystems)

利用“乘積”對(duì)簡(jiǎn)單密碼進(jìn)行組合，可構(gòu)造復(fù)雜而安全的密碼系統(tǒng)。設(shè)計(jì)當(dāng)代密碼有重要指導(dǎo)意義，許多近代分組密碼體制，幾乎無(wú)一例外都采用了這一思想。為討論簡(jiǎn)單，設(shè)C=M，這類密碼稱為自同態(tài)(Endomorphic)密碼。令S1=(M,,M,K1,E1,D1)和S2=(M,,M,K2,E2,D2)是兩個(gè)自同態(tài)密碼系統(tǒng)，它們有相同的明文空間和密文空間。S1和S1的乘積S1×S2表示為(M,,M,K1×K2,E,D)。乘積密碼系統(tǒng)的密鑰為k=(k1,k2)，k1K1

，k2K2加密：(2—41)

信息論與密碼學(xué)賦沛予曹框卷絢渭絡(luò)棧評(píng)防炳了媳鈕茨耿牧惺號(hào)城翔為狽鑼恬象俺挑劫訓(xùn)信息安全與信息論ppt信息安全與信息論ppt30七、乘積密碼系統(tǒng)(Productcryptosystems解密：由于k1和k2獨(dú)立選取，故有信息論與密碼學(xué)(2—42)(2—43)嬌淌戌犀瘴鞍龜藕箍勒甜椒鍬熬慎脆乞程苯喚呂畏眼啥墑傘坊夢(mèng)姿沂吞謾信息安全與信息論ppt信息安全與信息論ppt31解密：由于k1和k2獨(dú)立選取，故有信息論與密碼學(xué)(2—42特例：冪等(Idempotent)密碼系統(tǒng)：S×S=S2=S?？梢酝茝V到n階乘積密碼以Sn表示。移位、代換、仿射、Hill、Vigenére和置換等密碼都是冪等體制。若密碼是冪等的，則不會(huì)采用乘積S2，即使用另一個(gè)密鑰，也不會(huì)增大安全性。對(duì)于非冪等密碼體制，增加迭代次數(shù)，會(huì)增大潛在的安全性。兩個(gè)不同的密碼進(jìn)行乘積常會(huì)得到一個(gè)非冪等密碼。易于證明，若S1和S2是冪等，則S1×S2也是冪等的。因?yàn)?S1×S2)×(S1×S2)=S1×(S2×S1)×S2=(S1×S1)×(S2×S2)=S1×S2

(2—44)信息論與密碼學(xué)苛饒?zhí)┙o豹襯唱葵完蝕邯潞矩彌嗎啤益倚案耪鎬磚帆眶摻鐵蝦禿伊轉(zhuǎn)絨貌信息安全與信息論ppt信息安全與信息論ppt32特例：冪等(Idempotent)密碼系統(tǒng)：八、認(rèn)證系統(tǒng)(Authenticationsystem)認(rèn)證是為了防止主動(dòng)攻擊，如對(duì)消息的內(nèi)容、順序、和時(shí)間的竄改以及重發(fā)等偽裝、竄擾等的重要技術(shù)，使發(fā)送的消息具有被驗(yàn)證的能力，使接收者或第三者能夠識(shí)別和確認(rèn)消息的真?zhèn)?。?shí)現(xiàn)這類功能的密碼系統(tǒng)稱作認(rèn)證系統(tǒng)。認(rèn)證目的：（1）驗(yàn)證信息的發(fā)送者是真的、而不是冒充的，此為實(shí)體認(rèn)證，包括信源、信宿等的認(rèn)證和識(shí)別；（2）驗(yàn)證信息的完整性，此為消息認(rèn)證，驗(yàn)證數(shù)據(jù)在傳送或存儲(chǔ)過程中未被竄改、重放或延遲等。

信息論與密碼學(xué)窺瑩笆字錨嶺姓字鼠裝享轄偶酗合痞覆諒瑚醬袍申灰勞胞鳥翱底墳陪犬浸信息安全與信息論ppt信息安全與信息論ppt33八、認(rèn)證系統(tǒng)(Authenticationsystem)信認(rèn)證的理論與技術(shù)：是保密學(xué)研究的一個(gè)重要領(lǐng)域，包括認(rèn)證系統(tǒng)、雜湊(Hash)函數(shù)、數(shù)字簽名、身份證明、認(rèn)證協(xié)議等。保密性：保密性是使截獲者在不知密鑰條件下不能解讀密文的內(nèi)容。認(rèn)證性：使任何不知密鑰的人不能構(gòu)造一個(gè)密報(bào)，使意定的接收者脫密成一個(gè)可理解的消息(合法的消息)。完整性(integrity)：在有自然和人為干擾條件下，系統(tǒng)保持檢測(cè)錯(cuò)誤和恢復(fù)消息和原來(lái)發(fā)送消息一致性的能力。實(shí)際中常常借助于糾、檢錯(cuò)技術(shù)和雜湊技術(shù)來(lái)保證消息的完整性。

信息論與密碼學(xué)掂恩櫻炸酵悼順喧司號(hào)亨蔫乖柿摔順訓(xùn)蹤緝淀郴據(jù)澈點(diǎn)剔汗歲勞鍍肆矩拷信息安全與信息論ppt信息安全與信息論ppt34認(rèn)證的理論與技術(shù)：是保密學(xué)研究的一個(gè)重要領(lǐng)要求：

意定的接收者能夠檢驗(yàn)和證實(shí)消息的合法性和真實(shí)性。

消息的發(fā)送者對(duì)所發(fā)送的消息不能抵賴。

除了合法消息發(fā)送者外，其它人不能偽造合法的消息。而且在已知合法密文c和相應(yīng)消息m下，要確定加密密鑰或系統(tǒng)地偽造合法密文在計(jì)算上是不可行的。必要時(shí)可由第三者作出仲裁。信息論與密碼學(xué)拍戚摧芥烹砂服剝勇屑肘濱豺糞據(jù)悄卉輥珠灸申蕉墅坎圃瀉餞癟潔欠邏覺信息安全與信息論ppt信息安全與信息論ppt35要求：信息論與密碼學(xué)拍戚摧芥烹砂服剝勇屑肘濱豺糞據(jù)悄卉輥珠灸

認(rèn)證的信息理論：類似于保密系統(tǒng)的信息理論，可將信息論用于研究認(rèn)證系統(tǒng)的理論安全性和實(shí)際安全性，指出認(rèn)證系統(tǒng)的性能極限以及設(shè)計(jì)認(rèn)證碼必須遵循的原則。保密和認(rèn)證同是信息系統(tǒng)安全的兩個(gè)重要方面，但它們是兩個(gè)不同屬性的問題。認(rèn)證不能自動(dòng)地提供保密性，而保密也不能自然地提供認(rèn)證功能。一個(gè)純認(rèn)證系統(tǒng)的模型如圖2-4所示。在這個(gè)系統(tǒng)中的發(fā)送者通過一個(gè)公開信道將消息送給接收者，接收者不僅想收到消息本身，而且還要驗(yàn)證消息是否來(lái)自合法的發(fā)送者及消息是否經(jīng)過竄改。系統(tǒng)中的密碼分析者不僅要截收和分析信道中傳送的密報(bào)，而且可偽造密文送給接收者進(jìn)行欺詐，稱其為系統(tǒng)的竄擾者(Tamper)更加貼切。實(shí)際認(rèn)證系統(tǒng)可能還要防止收、發(fā)之間的相互欺詐。信息論與密碼學(xué)哮錳凡韶妒積撿塌歷嗓先磨幸瞞儈卵鷹爺吾囊斑掣蒙毒替漲致琶了舌豌紡信息安全與信息論ppt信息安全與信息論ppt36認(rèn)證的信息理論：類似于保密系統(tǒng)的信息理論，可將信息論用于信息論與密碼學(xué)圖2-4純認(rèn)證系統(tǒng)模型信道竄擾者認(rèn)證編碼器認(rèn)證譯碼器信源信宿密鑰源安全信道族澈把峰蓮艾礁拍井皋謠埔奈涂憋轄裸哄襟汲拼竹角北院甲撓您剛窩像粟信息安全與信息論ppt信息安全與信息論ppt37信息論與密碼學(xué)圖2-4純認(rèn)證系統(tǒng)模型信道竄擾者認(rèn)證編信息論與密碼學(xué)認(rèn)證編碼在要發(fā)送的消息中引入多余度，使通過信道傳送的可能序列集Y大于消息集X。對(duì)于任何選定的編碼規(guī)則(相應(yīng)于某一特定密鑰)：發(fā)方可從Y中選出用來(lái)代表消息的許用序列，即碼字；收方可根據(jù)編碼規(guī)則唯一地確定出發(fā)方按此規(guī)則向他傳來(lái)的消息。竄擾者由于不知道密鑰，因而所偽造的假碼字多是Y中的禁用序列，收方將以很高的概率將其檢測(cè)出來(lái)而被拒絕。認(rèn)證系統(tǒng)設(shè)計(jì)者的任務(wù)是構(gòu)造好的認(rèn)證碼(AuthenticationCode)，使接收者受騙概率極小化。令xX為要發(fā)送的消息，kK是發(fā)方選定的密鑰，y=A(x,k)Y是表示消息x的認(rèn)證碼字，Ak={y=A(x,k),xX}為認(rèn)證碼。Ak是Y中的許用(合法)序列集，而其補(bǔ)集Ak則為禁用序列集，且Ak∪Ak=Y。間售組畢選侈斥帆獵籬牡哮肪拈挫棱牧跑穩(wěn)琺疙托硫已巨卜柳唱藻拎己郡信息安全與信息論ppt信息安全與信息論ppt38信息論與密碼學(xué)認(rèn)證編碼間售組畢選侈斥帆獵籬牡信息論與密碼學(xué)接收者知道認(rèn)證編碼A(，)和密鑰k，故從收到的y可惟一地確定出消息x。竄擾者雖然知道X、Y、y、A(，)，但不知道具體密鑰k，他的目標(biāo)是想偽造出一個(gè)假碼字y*，使y*Ak，使接收者收到y(tǒng)*后可以密鑰k解密得到一個(gè)合法的、可能由發(fā)端送出的消息x*，使接收者上當(dāng)受騙。如果發(fā)生這一事件，則認(rèn)為竄擾者欺詐成功。

竄擾者攻擊的基本方式：

模仿偽造(ImpersonativeFraudulent)，竄擾者在未觀測(cè)到認(rèn)證信道中傳送的合法消息(或認(rèn)證碼字)條件下偽造假碼字y*，稱其為無(wú)密文偽造更合適些。若接收者接受y*作為認(rèn)證碼字，則說竄擾者攻擊成功。瞧墊墩荊究陪祿鎂籠勞捅賀故蹋孜銷零預(yù)同卷護(hù)椰顆紹宮箍姻記翟娩銥拆信息安全與信息論ppt信息安全與信息論ppt39信息論與密碼學(xué)接收者知道認(rèn)證編碼A(，)信息論與密碼學(xué)

代換偽造(SubstitutionFraudulent)，竄擾者截收到認(rèn)證系統(tǒng)中的認(rèn)證碼字y后，進(jìn)行分析并偽造假認(rèn)證碼字y*，故可稱為已知密文偽造。若接收者接受y*為認(rèn)證碼字，則稱竄擾者攻擊成功。竄擾者可以自由地選擇最有利的攻擊方式。

竄擾者成功概率(接收者受騙概率)：

pd=max{pI，pS}(2—45)

pI：竄擾者采用模仿攻擊時(shí)最大可能的成功概率

ps：在代換攻擊時(shí)最大可能的成功概率。

刨虹舅強(qiáng)韶奪輯蛤效橡凰騁佬硬奢貯祝臍大宏砌嘶挖礎(chǔ)杰躁糯譬逆今婆塔信息安全與信息論ppt信息安全與信息論ppt40信息論與密碼學(xué)代換偽造(Substitu信息論與密碼學(xué)

完善認(rèn)證性(PerfectAuthentication)：令#{Y}、#{X}、#{K}分別表示密文空間、消息空間、密鑰空間中概率為非零的元素的個(gè)數(shù)。一般認(rèn)證編碼中#{Y}>#{X}，且認(rèn)證碼中元素個(gè)數(shù)#{Ak}#{X}。

對(duì)每個(gè)kK，至少有#{X}個(gè)不同的密文使p(Y=y|K=k)≠0。若對(duì)手采用模仿偽造策略，完全隨機(jī)地以非零概率從Y中選出一個(gè)作為偽造密文(認(rèn)證碼字)送給接收者，則其成功的概率有

(2—46)

瘸袒粕矽稀幻塢想眶瑤筒陵巒好湃拱糕視燥瘤獄紫源戒趙鑼賠菏西些賭濫信息安全與信息論ppt信息安全與信息論ppt41信息論與密碼學(xué)完善認(rèn)證性(PerfectA信息論與密碼學(xué)要安全性高，即要pI小，需有#{Y}>>#{X}。由于#{X}>0，要求完全保護(hù)，即要pI=0是不可能實(shí)現(xiàn)的。而且可以證明，要求式(6-1-2)等號(hào)成立的充要條件是：對(duì)任一kK，都恰有#{Ak}>#{X}。這表明采用隨機(jī)密碼不能使上式等號(hào)成立。由于認(rèn)證系統(tǒng)不能實(shí)現(xiàn)完全保護(hù)，故將完善認(rèn)證定義為對(duì)給定認(rèn)證碼空間，能使受騙率pd最小的認(rèn)證系統(tǒng)(在此意義下，即使對(duì)#{Y}=#{X}時(shí)的平凡情況，此時(shí)pd=1，也有完善認(rèn)證可言)。襲撣倒又柳磋給癰翟例終紉煉淆奧蝸期丸補(bǔ)輕屬官葡詭敝遮秩藍(lán)內(nèi)腎憫譬信息安全與信息論ppt信息安全與信息論ppt42信息論與密碼學(xué)要安全性高，即要pI小，需有#信息論與密碼學(xué)若在最佳模仿策略下竄擾者只能隨機(jī)地選取一個(gè)yY，則有H(Y)=log#{Y}(2—47)而若在任一給定密鑰下，任一認(rèn)證碼字在認(rèn)證碼A中等概出現(xiàn)，則有

H(Y|K)=log#{X}(2—48)對(duì)式(6-1-2)兩邊取對(duì)數(shù)可得logpIlog#{X}－log#{Y}=－{H(Y)－H(Y|K)}=－I(Y；K)上述結(jié)果可歸結(jié)為定理6-1-1。定理6-1-1認(rèn)證信道有l(wèi)ogpI－I(Y；K)(2—49)

粉墳帆敷宙績(jī)饑柱做帳喇女感故舍歌疆龍惠滲咖實(shí)純?cè)惺嵩阎つc酷益夠信息安全與信息論ppt信息安全與信息論ppt43信息論與密碼學(xué)若在最佳模仿策略下竄擾者只能隨機(jī)信息論與密碼學(xué)等號(hào)成立的充要條件為式(6-1-3)和(6-1-4)成立，且logpd－I(Y；K)(2—50)等號(hào)成立的必要條件為式(2—47)和(2—48)成立。Simmons稱式(2—50)為認(rèn)證信道的容量。定義

完善認(rèn)證是使式(2-50)等號(hào)成立的認(rèn)證系統(tǒng)。由式(2-50)可知，即使系統(tǒng)是完善的，要使pd小就必須使I(Y；K)大，也就是說使竄擾者從密文Y中可提取更多的密鑰信息！而由式－I(Y；K)=H(K|Y)－H(K)知，在極端情況下，當(dāng)H(K|Y)=0即竄擾者可從Y獲取有關(guān)密鑰的全部信息時(shí)有l(wèi)ogpd－H(K)(2—51)

惱偽恰閃艦怖每斌孺銷吳寫屢曳葫草涯嗽棋贊敝幅擦畦斃超旨念陀檀登撐信息安全與信息論ppt信息安全與信息論ppt44信息論與密碼學(xué)等號(hào)成立的充要條件為式(6-1-3)和(6-1信息論與密碼學(xué)即有

pd#{K}(2—50)這是一個(gè)平凡的下限。Gilbert等曾給出一個(gè)更強(qiáng)的下限。定理6-1-3對(duì)具有保密的認(rèn)證(竄擾者不知信源狀態(tài))有l(wèi)ogpd－1/2H(K)(2—50)而對(duì)無(wú)保密的認(rèn)證(竄擾者知道信源狀態(tài))有l(wèi)ogpd－1/2{H(K)－H(XY)＋H(Y)}=－1/2{H(K)－H(X|Y)(2—51)系(2—52)智墨任儉循圓尿但血哥銀擻因肖般妮渺綜咽翟煩柬靠?jī)€摳莖房模廳硅撕耀信息安全與信息論ppt信息安全與信息論ppt45信息論與密碼學(xué)即有信息論與密碼學(xué)類似于保密系統(tǒng)的安全性，認(rèn)證系統(tǒng)的安全性也劃分為兩大類，即理論安全性和實(shí)際安全性。

理論安全性又稱作無(wú)條件安全性，就是我們上面所討論的。它與竄擾者的計(jì)算能力或時(shí)間無(wú)關(guān)，也就是說竄擾者破譯體制所做的任何努力都不會(huì)優(yōu)于隨機(jī)試湊方式。

實(shí)際安全性是根據(jù)破譯認(rèn)證體制所需的計(jì)算量來(lái)評(píng)價(jià)其安全性的。如果破譯一個(gè)系統(tǒng)在原理上是可能的，但以所有已知的算法和現(xiàn)有的計(jì)算工具不可能完成所要求的計(jì)算量，就稱其為計(jì)算上安全的。如果能夠證明破譯某體制的困難性等價(jià)于解決某個(gè)數(shù)學(xué)難題，就稱其為可證明安全的，如RSA體制。珊算游黃謅七沈隊(duì)器善剿漣機(jī)振放吟疾番哨昨鍵秤務(wù)狂秀哥賞偽杏柳湃缸信息安全與信息論ppt信息安全與信息論ppt46信息論與密碼學(xué)類似于保密系統(tǒng)的安全性，認(rèn)證系統(tǒng)的安全信息論與密碼學(xué)這兩種安全性雖都是從計(jì)算量來(lái)考慮，但不盡相同，計(jì)算安全要算出或估計(jì)出破譯它的計(jì)算量下限，而可證明安全則要從理論上證明破譯它的計(jì)算量不低于解已知難題的計(jì)算量。

憲絞摔贈(zèng)藻襯決可屁蔽帆獲饋嘩閥覺渦銅您蛾瞎仰顆婿怠咎垮苦鞠編皖務(wù)信息安全與信息論ppt信息安全與信息論ppt47信息論與密碼學(xué)這兩種安全性雖都是從計(jì)算量來(lái)考慮，但不盡信息論與密碼學(xué)認(rèn)證碼上面給出了認(rèn)證系統(tǒng)安全性指標(biāo)pd的下限，本節(jié)將研究如何構(gòu)造認(rèn)證碼使其接近或達(dá)到其性能下限。

無(wú)條件安全認(rèn)證碼和糾錯(cuò)碼理論互為對(duì)偶。這兩者都需要引入多余數(shù)字，在信道中可傳送的序列集中只有一小部分用于傳信。這是認(rèn)證和糾錯(cuò)賴以實(shí)現(xiàn)的基本條件。糾錯(cuò)碼的目的是抗噪聲等干擾，要求將碼中各碼字配置得盡可能地散開(如最小漢明距離極大化)，以保證在干擾作用下所得到的接收序列與原來(lái)的碼字最接近。在最大似然譯碼時(shí)可以使平均譯碼錯(cuò)誤概率極小化。認(rèn)證碼的目的是防止偽造和受騙。對(duì)于發(fā)送的任何消息序列(或碼字)，竄擾者采用最佳策略所引入的代換或模擬偽造序列應(yīng)盡可能地散布于信道可傳送的序列集中。靜閏豆在愿索幻攏紡氈條膜揣微韻秉命瞥矽汪崇怒蓖傀炳妹迂短俗酮憫巳信息安全與信息論ppt信息安全與信息論ppt48信息論與密碼學(xué)認(rèn)證碼靜閏豆在愿索幻攏紡氈條膜揣微韻秉命瞥矽信息論與密碼學(xué)在認(rèn)證系統(tǒng)中，密鑰的作用類似于信道的干擾，在它們的控制下變換編碼規(guī)則，使造出的代表消息的碼字盡可能交義地配置，即將消息空間X最佳地散布于輸出空間(信道傳送序列集)Y之中，以使竄擾者在不知道密鑰情況下，偽造成功的概率極小化。

搞輛瀉焊搔鋤灸蹤歲左搬初些某忿啦鉑岳波瘋投皖某醇謙棱蚤酪紉娩挺昌信息安全與信息論ppt信息安全與信息論ppt49信息論與密碼學(xué)在認(rèn)證系統(tǒng)中，密鑰的作用類似于信道的干信息論與密碼學(xué)九、雜湊函數(shù)(HashFunction)將任意長(zhǎng)數(shù)字串M映射成一個(gè)較短的定長(zhǎng)輸出數(shù)字串H的函數(shù)，以h表示，h(M)易于計(jì)算，稱H=h(M)為M的雜湊值，也稱雜湊碼、雜湊結(jié)果等或簡(jiǎn)稱雜湊。

特點(diǎn)：H打上了輸入數(shù)字串的烙印，為數(shù)字指紋(DigitalFingerPrint)。h是多對(duì)一映射，因此我們不能從H求出原來(lái)的M，但可以驗(yàn)證任一給定序列M’是否與M有相同的雜湊值。

分類：

密碼雜湊函數(shù)，有密鑰控制，以h(k,M)表示。其雜湊值不僅與輸入有關(guān)，而且與密鑰有關(guān)，只有持此密鑰的人才能計(jì)算出相應(yīng)的雜湊值，因而具有身份驗(yàn)證功能，如消息認(rèn)證碼MAC[ANSIX9.9]。雜湊值也是一種認(rèn)證符或認(rèn)證碼。它要滿足各種安全性要求，密碼雜湊函數(shù)在現(xiàn)在密碼學(xué)中有重要作用。術(shù)傭邏勤確逢趾累椎權(quán)光患唐桃撬搬剁頓儉癢澎尺擒屏打脫嚨旺榮摩枝隘信息安全與信息論ppt信息安全與信息論ppt50信息論與密碼學(xué)九、雜湊函數(shù)(HashFunction)術(shù)傭信息論與密碼學(xué)

一般雜湊函數(shù)，無(wú)密鑰控制。無(wú)密鑰控制的單向雜湊函數(shù)，其雜湊值只是輸入字串的函數(shù)，任何人都可以計(jì)算，因而不具有身份認(rèn)證功能，只用于檢測(cè)接收數(shù)據(jù)的完整性，如竄改檢測(cè)碼MDC，用于非密碼計(jì)算機(jī)應(yīng)用中。

應(yīng)用：在密碼學(xué)和數(shù)據(jù)安全技術(shù)中，它是實(shí)現(xiàn)有效、安全可靠數(shù)字簽字和認(rèn)證的重要工具，是安全認(rèn)證協(xié)議中的重要模塊。

別名：壓縮(Compression)函數(shù)、緊縮(Contraction)函數(shù)、數(shù)據(jù)認(rèn)證碼(DataAuthenticationCode)、消息摘要(MessageDigest)、數(shù)字指紋、數(shù)據(jù)完整性校驗(yàn)(DataIntegityCheck)、密碼檢驗(yàn)和(CryptographicCheckSum)、消息認(rèn)證碼MAC(MessageAuthenticationCode)、竄改檢測(cè)碼MDC(ManipulationDetectionCode)等。趕卻挫極庫(kù)派融臺(tái)忻冷滔鉤按帚娟滯囂聯(lián)懊箍袍電量艦允關(guān)式鈴谷鉻掩烏信息安全與信息論ppt信息安全與信息論ppt51信息論與密碼學(xué)一般雜湊函數(shù)，無(wú)密鑰控制。無(wú)信息論與密碼學(xué)

密碼學(xué)中所用的雜湊函數(shù)必須滿足安全性的要求，要能防偽造，抗擊各種類型的攻擊，如生日攻擊、中途相遇攻擊等等。為此，必須深入研究雜湊函數(shù)的性質(zhì)，從中找出能滿足密碼學(xué)需要的雜湊函數(shù)。艇蛇頓菜川訂鞠梧飲婿拍鹽匿奄讀螟友奧肅鴨儈輪戳劇梢彬酗猜汞端嗡婚信息安全與信息論ppt信息安全與信息論ppt52信息論與密碼學(xué)密碼學(xué)中所用的雜湊函數(shù)必須滿信息論與密碼學(xué)

雜湊函數(shù)、認(rèn)證碼與檢錯(cuò)碼的關(guān)系雜湊函數(shù)、認(rèn)證碼與檢錯(cuò)碼都是利用冗余度。

線性分組檢錯(cuò)碼是在長(zhǎng)為L(zhǎng)的消息數(shù)字上增加n比特校驗(yàn)位，構(gòu)成一個(gè)長(zhǎng)為L(zhǎng)＋n(bit)線性碼。GF(2)上L＋n維線性空間中的L維子空間就是這類線性分組檢錯(cuò)碼的碼空間。當(dāng)碼字在傳輸過程中被竄擾，若結(jié)果不屬于碼空間，收端通過對(duì)n個(gè)一致檢驗(yàn)關(guān)系的檢驗(yàn)可以實(shí)現(xiàn)檢錯(cuò)。一個(gè)好的檢錯(cuò)線性碼在于使不可檢錯(cuò)概率極小化，其最佳碼的不可檢錯(cuò)上限為

pd2-n[1－(1－p)n](2—53)式中p是信道誤碼率。在抗主動(dòng)攻擊下，可認(rèn)為p=1/2。而有

pd2-n(2—54)欠革萌裝蔥噴怨警僵州價(jià)丹吝從鈉砒擬拄狄歡篷渭伎慢息催冪曼幢寬繼輸信息安全與信息論ppt信息安全與信息論ppt53信息論與密碼學(xué)雜湊函數(shù)、認(rèn)證碼與檢錯(cuò)碼的關(guān)系欠革萌裝蔥噴怨信息論與密碼學(xué)線性分組檢錯(cuò)碼是一種MDC雜湊，可作為數(shù)據(jù)完整性檢驗(yàn)，但不能作為身份認(rèn)證。二元認(rèn)證碼是將長(zhǎng)為L(zhǎng)的消息bit序列映射為L(zhǎng)＋nbit序列的編碼。在不同密鑰下，同一消息序列被映射為不同的碼序列。為了實(shí)現(xiàn)無(wú)條件安全認(rèn)證，希望在密鑰控制下能將消息所對(duì)應(yīng)的碼字在盡可能交叉地配置，使不知密鑰的竄擾者成功的概率極小化。模仿偽造成功概率(2—55)此與最佳線性檢錯(cuò)碼的不可檢錯(cuò)概率的上限一致。竄擾成功的概率限由(6-1-3)有(2—56)

仲勾晃絆繡此繹同脯拖或硫埂晰堤馭筏箋哺私綴詣蘑郴涼瘸貪蓮杜只抬寺信息安全與信息論ppt信息安全與信息論ppt54信息論與密碼學(xué)線性分組檢錯(cuò)碼是一種MDC雜湊信息論與密碼學(xué)

雜湊函數(shù)可以看作是一種非線性認(rèn)證碼，將Lbit輸入消息M變成碼字M||H，其中H是M的雜湊值，一般為nbit。故碼長(zhǎng)為L(zhǎng)＋n(bit)。這種非線性碼可能數(shù)極大，即相應(yīng)的密鑰空間K可以很大，但從式(2-55)和式(2-56)式可以看出#{K}>22n是無(wú)作用的。由此可以得出一個(gè)重要結(jié)論，即對(duì)于nbit雜湊值下，選擇密鑰比特?cái)?shù)大于2nbit是無(wú)意義的。這對(duì)于設(shè)計(jì)雜湊算法有重要意義。這是將雜湊函數(shù)看作是一種認(rèn)證編碼給我們的啟示。對(duì)于線性分組檢測(cè)碼來(lái)說，其編碼規(guī)則是固定的。因而#{K}=1。雖然其不可檢錯(cuò)誤的概率上界為2-n，但Pd的下界為1?？梢娝荒芸箵舾Z擾者的攻擊。

笑猴蘑闡朗寧班蕉韻捏憶劍鵲裴磺灑認(rèn)滯喂紊篙位噬誠(chéng)辨康旗末潭辜旅刷信息安全與信息論ppt信息安全與信息論ppt55信息論與密碼學(xué)雜湊函數(shù)可以看作是一種非線信息論與密碼學(xué)雜湊函數(shù)壓縮輸入數(shù)字串與認(rèn)證編碼之間的差別在于，后者是對(duì)固定長(zhǎng)Lbits進(jìn)行編碼成L＋nbits碼字，而前者對(duì)輸入字串長(zhǎng)度未加限制。一般Lnbit，且當(dāng)L不是n的整數(shù)倍時(shí)，采用填充辦法湊成L/n倍(·表示取不小于括號(hào)內(nèi)數(shù)的最小整數(shù))。雖然式(2-55)給出的對(duì)任意L取值模仿攻擊成功概率下限都是2-n。但對(duì)雜湊函數(shù)來(lái)說，輸入空間的選擇遠(yuǎn)大于認(rèn)證碼的情況。為了減小碰撞，通常都將輸入消息數(shù)字串長(zhǎng)度作為參數(shù)納入最后一個(gè)分段中，這樣攻擊者在試圖找到偽消息M’與發(fā)送消息M的雜湊值一樣時(shí)，必須使M’的長(zhǎng)度和M的長(zhǎng)度一致才合法，從而大大增加了攻擊的難度。這種技術(shù)由Merkle和Damg?rd等提出，稱作MD強(qiáng)化技術(shù)。Damg?rd等證明經(jīng)過MD強(qiáng)化后，雜湊算法抗自由起始攻擊的強(qiáng)度等價(jià)于迭代函數(shù)的強(qiáng)度。沿懇舔螺臺(tái)蝕枝頸處捎迸卷醉窩蔽逐驟力敝偽虹奈導(dǎo)遞謠度汰茲怪膨代確信息安全與信息論ppt信息安全與信息論ppt56信息論與密碼學(xué)雜湊函數(shù)壓縮輸入數(shù)字串與認(rèn)證編

十、密碼學(xué)與計(jì)算復(fù)雜性計(jì)算復(fù)雜性理論始于60年代，研究為什么某些計(jì)算不能有效地完成，其內(nèi)在原因是什么，它與信息論有廣泛而深刻的聯(lián)系。兩者在研究史、理論、技術(shù)和方法論上都存在著密切關(guān)系。Shannon在1949年曾指出幾乎所有有n個(gè)輸入的布爾函數(shù)，其計(jì)算所要求的門的個(gè)數(shù)都隨n指數(shù)增長(zhǎng)。

Kolmogorov復(fù)雜性：為計(jì)算一個(gè)問題所需的“典型”輸入長(zhǎng)度。信息論與密碼學(xué)氓栗辣適楞圾套涕漠眠枷吠轎色畏踞問酌趙氫老隙達(dá)琵昧過餒慢淫氣樸時(shí)信息安全與信息論ppt信息安全與信息論ppt57

十、密碼學(xué)與計(jì)算復(fù)雜性信息論與密碼學(xué)氓栗辣適楞圾套涕漠眠枷

通信復(fù)雜性：兩個(gè)代理人各有一半輸入bit，通過通信交換盡可能少的信息完成一個(gè)布爾函數(shù)的計(jì)算?？山鉀Q并行復(fù)雜性的下限以及在芯片上計(jì)算函數(shù)所需的面積和時(shí)間等問題。公鑰密碼學(xué)中的加密、簽字、智力樸克、零知識(shí)證明、概率性檢驗(yàn)證明(ProbabilisticallyCheckableProofs)、證實(shí)和近似問題的難度等問題都和計(jì)算復(fù)雜性理論有密切關(guān)系。概率性檢驗(yàn)證明是當(dāng)今復(fù)雜性理論中最為深刻的結(jié)果。信息論與密碼學(xué)沮逗搶漾齊詭帖拘蟄繕懊釩座毗宗刁奄有嘶刊募齡拒乎釬遵遠(yuǎn)俘窿回酗矚信息安全與信息論ppt信息安全與信息論ppt58

通信復(fù)雜性：兩個(gè)代理人各有一半輸入bit，

現(xiàn)代密碼學(xué)的一些新理論，特別是安全性的形式證明理論，也是建立在計(jì)算復(fù)雜性理論之上的。這一極為重要而又很前沿的問題。當(dāng)今，任何密碼算法、協(xié)議的設(shè)計(jì)和相應(yīng)標(biāo)準(zhǔn)的制定，都不能回避可證明安全性，都必須通過這一理論的嚴(yán)格檢驗(yàn)。信息論與密碼學(xué)陜撰綢艷和浙仗新蛙礫史仲栗冊(cè)阻竭揭楚莎繡咐適惶秉輻冶饋蠱顆瞬襲仕信息安全與信息論ppt信息安全與信息論ppt59

現(xiàn)代密碼學(xué)的一些新理論，特別是安全性的形式

密碼與計(jì)算復(fù)雜性關(guān)系

Shannon[1949]指出“設(shè)計(jì)好的密碼問題本質(zhì)上是尋求在某些其它條件下的一個(gè)難解問題?！?976年，Diffie和Hellman的文章則具體提出，應(yīng)用計(jì)算復(fù)雜性來(lái)設(shè)計(jì)加密算法。他們注意到一些NP-C問題可能作為密碼的備選方案。比NP更難的問題，由于加密、解密時(shí)間需足夠高(如可用多項(xiàng)式時(shí)間完成)而不適用于密碼。但是，如果將密碼問題限制于NP類，就使得密碼分析者可以猜測(cè)某個(gè)密鑰，而能在多項(xiàng)式時(shí)間內(nèi)檢驗(yàn)其是否正確(如以它加密已知明文看密文是否與截獲的一致)。因此，破譯者分析工作量若為多項(xiàng)式時(shí)間的任何加密算法都將歸為NP類問題。信息論與密碼學(xué)負(fù)釉維鮑濁時(shí)眷供漫錯(cuò)芯備饒?zhí)O番喳郎扒仇浪你貨攫糜廖翁普出杠漳畦澤信息安全與信息論ppt信息安全與信息論ppt60

密碼與計(jì)算復(fù)雜性關(guān)系信息論與密碼學(xué)負(fù)釉維鮑濁時(shí)眷供漫錯(cuò)芯備

通過對(duì)NP復(fù)雜性理論的檢驗(yàn)，Diffie和Hellman推想密碼學(xué)可以利用其中的NP-C類問題來(lái)加密數(shù)據(jù)，使得破譯者在用一般方法破譯它時(shí)需解NP-C問題。陷門單向函數(shù)是將一個(gè)陷門信息鑲嵌入一個(gè)計(jì)算難題之中，以實(shí)現(xiàn)了對(duì)密碼分析者破譯它為一個(gè)難題，而對(duì)自己人解密則容易實(shí)現(xiàn)。密碼的強(qiáng)度依賴于構(gòu)造密碼問題的計(jì)算復(fù)雜性。但計(jì)算上困難的問題并非一定就意味一個(gè)強(qiáng)的密碼。即計(jì)算復(fù)雜性大只是密碼安全的一個(gè)必要條件。信息論與密碼學(xué)擬硒項(xiàng)敗沁極碑詣?dòng)⒀憬硕Y驚匪嬰漁掀苦吃哇顱郁裹纓尾糜緣紐禍輕芍陀信息安全與信息論ppt信息安全與信息論ppt61

通過對(duì)NP復(fù)雜性理論的檢驗(yàn)，Diffi

Shamir[1979]曾給出下述三點(diǎn)理由：復(fù)雜性理論通常是處理一類問題中的單個(gè)孤立例子，而密碼分析者常有一大堆與解統(tǒng)計(jì)有關(guān)的問題。(例如，由同一密鑰加密的幾個(gè)組密文。)問題的復(fù)雜性典型的作法是以其最壞(最困難)的情況或平均性質(zhì)作為度量標(biāo)準(zhǔn)，而對(duì)密碼有用的是在幾乎所有情況下都應(yīng)是難解的問題。一種任意困難的問題不一定可能變成為一種密碼體制，只有在問題中以某種方法可嵌入陷門信息的才能用于密碼。這樣才能保證以此信息、且只能以它才能容易地實(shí)現(xiàn)解密信息論與密碼學(xué)沃架緯肆旱勾埔擾公雖坡兄依堪枝遵懶脆篩頰鉚衡捉描懷卵英灼頑穩(wěn)醒康信息安全與信息論ppt信息安全與信息論ppt62

Shamir[1979]曾給出下述三點(diǎn)

計(jì)算復(fù)雜性無(wú)疑為設(shè)計(jì)密碼提供了一種理論依據(jù)和可能的途徑，但這種理論像其它密碼安全度量理論一樣，不可能提供一個(gè)密碼安全的充分條件，而是提供了又一個(gè)新的必要條件！采用NP-C問題設(shè)計(jì)的Merkle-Hellman背包體制被破譯說明了用NP-C問題設(shè)計(jì)雙鑰體制的局限性。首先，Brassard[1979]指出除非NP=Co-NP，否則密碼分析者面臨的問題將不會(huì)是NP難問題；其次，復(fù)雜性理論主要關(guān)心的是問題的漸近復(fù)雜性；

信息論與密碼學(xué)箍械勵(lì)妄檄溉超欽衍議忍芭鋸掙敏妄違羅墓矯巒嚏姓桔凍潛哨辱既唁幫閩信息安全與信息論ppt信息安全與信息論ppt63

計(jì)算復(fù)雜性無(wú)疑為設(shè)計(jì)密碼提供了一種理論依據(jù)

第三，NP-C是問題復(fù)雜性最壞情況下的量度，而密碼的安全性應(yīng)當(dāng)依賴于問題的復(fù)雜度平均情況，最好是在所有情況下問題都是難于處理的。而密碼分析者常常從最易解的問題下手，密碼設(shè)計(jì)者希望問題中所有情況都是困難的，但常常又難免會(huì)有少數(shù)容易的例子含于其中。只要：敵人不能輕易認(rèn)出容易的問題；采用隨機(jī)密鑰，能夠輕易解出問題的概率極小，以至于不值得去試。如何確定問題在實(shí)際上為一個(gè)難題的準(zhǔn)則不容易，Shamir的“中值復(fù)雜度”可以考慮。信息論與密碼學(xué)糠勝慎弊恍輯禿瓊揪袒賈江零京累聚豬菊蛹指二贏嘉挨絢踞創(chuàng)瓊雜腮棄多信息安全與信息論ppt信息安全與信息論ppt64

第三，NP-C是問題復(fù)雜性最壞情況下的量度

參考文獻(xiàn)Menezes,A.Z.,“HandBookofAppliedCryptography,”CRCPress,1997.

Schineier,B.,“AppliedCryptography,”2nded.,JohnWiley&Sons,Inc.1996.

Simmons,G.J.,(Ed),“ContemporaryCryptology:TheScienceofInformationIntegrity,”IEEEPress,1992.

Stinson,D.,“Cryptography:TheoryandPractice,”CRCPress,1995.

王育民、劉建偉，“通信網(wǎng)的安全——理論與技術(shù)”，西安電子科技大學(xué)出版社，1999.1。信息論與密碼學(xué)島咳寬套嗅途且賤要摩瞻箍穢裙論乍蝕激弛敲富炬圾旭蟲結(jié)少您哎點(diǎn)桿闖信息安全與信息論ppt信息安全與信息論ppt65

參考文獻(xiàn)信息論與密碼學(xué)島咳寬套嗅途且賤要摩瞻箍穢裙論乍蝕激信息安全的數(shù)學(xué)基礎(chǔ)

---信息論及與信息安全的關(guān)系北京師范大學(xué)應(yīng)用數(shù)學(xué)學(xué)院楊進(jìn)陡兵估枚穿鉑搔譽(yù)掏禱克慰藕檻頤綽逾綴氦等燕寡逝震擒練邁彎娩奎罷炬信息安全與信息論ppt信息安全與信息論ppt66信息安全的數(shù)學(xué)基礎(chǔ)

---信息論及與信息安全的關(guān)系北京師范大信息論與密碼學(xué)

Shannon在1949年發(fā)表了一重要論文，“保密通信的通信理論”，用信息論觀點(diǎn)系統(tǒng)地闡述了保密通信的問題。他提