絕對(duì)安全和香農(nóng)密碼系統(tǒng)

絕對(duì)安全和香農(nóng)密碼系統(tǒng)小組成員：

04013002廖孜04013107鄧春燕

04013130陳金煒2015-12-28Part1密碼系統(tǒng)的基本概念Concealmentsystems

Privacysystems“True”secrecysystems

：信息被“隱藏”在密碼里，而不是僅僅被藏起來(lái)。即使“敵方”截獲也無(wú)法獲得信息。從一個(gè)簡(jiǎn)單的密碼系統(tǒng)講起：替換密碼加密方式/密鑰明文密文幾個(gè)基本概念：冗余度：一段文字在不丟失任何信息的情況下在長(zhǎng)度上最多能夠省略多少字符比方說(shuō)，假設(shè)英語(yǔ)的冗余度為75%，不是說(shuō)任意從英語(yǔ)文本中去掉四分之三的字母，還是可以閱讀，只是說(shuō)，對(duì)一個(gè)充分大的N，可以找到一種編碼方式將英文壓縮為原來(lái)的四分之一。幾個(gè)基本概念：先驗(yàn)概率：敵方在截獲密文前破解密匙的可能性。先驗(yàn)概率由整個(gè)隨機(jī)過程決定，由密碼分析者對(duì)于情況的先驗(yàn)分析決定后驗(yàn)概率：敵方在截獲密文后破解密文的可能性。敵方截獲足夠長(zhǎng)的密文后，可能使得某一消息的概率趨于1而其他消息個(gè)概率總和趨于0。英文中26個(gè)字母出現(xiàn)文本中的頻率統(tǒng)計(jì)：兩種安全標(biāo)準(zhǔn)：理論保密性：密碼分析者在具有無(wú)限時(shí)間和計(jì)算資源的條件下，密碼系統(tǒng)的抗破譯能力。實(shí)際保密性：密碼分析者在有限的計(jì)算資源以及其他限制條件下，密碼系統(tǒng)的抗破譯能力。絕對(duì)安全（定義）：后驗(yàn)概率等于先驗(yàn)概率，即密文不泄露明文的任何信息

熵：一種對(duì)信息的不確定性的信息度量條件熵：設(shè)

X和Y是兩個(gè)隨機(jī)變量。對(duì)于

Y的任何固定值y

，得到一個(gè)(條件)概率分布P(X|y)。顯然，

定義條件熵

為熵

取遍所有的

的加權(quán)平均值：

條件熵度量了由

Y揭示的

X的平均信息量。密鑰和密文唯一決定明文，即其中K為密鑰，C為密文，P為明文絕對(duì)安全系統(tǒng)：條件熵（條件信息量總平均值）在N無(wú)窮大的情況下仍不趨近于零。當(dāng)H(N)趨于0的時(shí)候使它倒退到任意大的N。Part2保密系統(tǒng)的數(shù)學(xué)模型圖像的分析：?譯碼器：功能形同函數(shù)。?接收端：。（必須存在唯一逆矩陣）?保密系統(tǒng)：是一個(gè)由一定概率且唯一可逆的變換矩陣組成的集合。若組成集合的相同，則此兩個(gè)保密系統(tǒng)相同。?為簡(jiǎn)化處理，假設(shè)截取者知道正在使用的系統(tǒng)，即。簡(jiǎn)單系統(tǒng)的表示（線圖）閉系統(tǒng)：對(duì)于每個(gè)信息（M），若和每個(gè)密文（E）之間都有標(biāo)注密鑰（K）的連線，則系統(tǒng)是閉系統(tǒng)。反之則為開系統(tǒng)。E1E2E3E41、維吉尼亞碼

密鑰：由周期為d的一串字母重復(fù)構(gòu)成。規(guī)則：(密鑰+信息)(mod26)舉例：信息NOWSTHE

密鑰GAHAHGA

密文TODSANE

保密系統(tǒng)的例子A:0B:1C:2D:3E:4F:5G:6H:7I:8J:9K:10L:11M:12N:13O:14P:15Q:16R:17E:18T:19U:20V:21W:22X:23Y:24Z:25延伸：使用頻率分析法可以破解。最終被稱為計(jì)算機(jī)之父的巴貝奇破解，其設(shè)計(jì)出世界上第一臺(tái)計(jì)算機(jī)。2、矩陣系統(tǒng)（普雷費(fèi)爾碼）密鑰：由25個(gè)英文字母組成的5×5字母矩陣（J由于很少使用，故省略，若出現(xiàn)用I代替）步驟：編密鑰表--整理明文--編寫密文舉例：

密鑰：【信息：wherethereislife,thereishope.】

整理明文：wherethereislifethereishopex密文：tkgy

owokgynlhjofcmyggkmlmbwf

保密系統(tǒng)的例子延伸：使用方便而且可以讓頻度分析法失效，但在一戰(zhàn)中破解。?若兩個(gè)保密系統(tǒng)T和R有相同的信息空間，構(gòu)造加權(quán)和，得到新系統(tǒng)：S=pT+qR(p+q=1)更一般地，構(gòu)造S=p1T+p2R+…+pmU(Σpi=1)?另一種方法是乘積運(yùn)算：S=RT。S的密鑰由T和R的一部分密鑰組成。若：T的m個(gè)密鑰的概率分別為：

S的n個(gè)密鑰的概率分別為：則S的mn個(gè)密鑰的概率分別為：

注意：很多情況下，變化是等效的，因此可以把他們的概率直接加起來(lái)。

保密系統(tǒng)的代數(shù)學(xué)純密碼&混合密碼變換集。其中，相當(dāng)于正在使用的特定密鑰。如果所有的密鑰都是相當(dāng)（即：等可能）的，并且對(duì)于任意三個(gè)，都存在一個(gè)，使得，那么是“純”密碼。下面可能用到的公式：

Theorem

1.在純密碼中，將消息空間映射成其自身的操作Ti-1Ti組成一個(gè)順序?yàn)閙的組。其中，m為不同密鑰的個(gè)數(shù)。證明：假設(shè)：存在，使得。故：

因此，得到：

兩邊取逆：

整理下標(biāo)，得：Theorem

2.兩個(gè)純密碼的乘積，交換順序后是純密碼。證明：

假設(shè)：對(duì)于每個(gè)，都有對(duì)應(yīng)的，使得。

*只有單一的純密鑰的系統(tǒng)，是純系統(tǒng)。因?yàn)椋??！鞯淖C明：（逆變換）（純密碼性質(zhì)）△Theorem

3.在一個(gè)純系統(tǒng)中，信息可以被分為剩余類的集合，密文相應(yīng)地為。有如下性質(zhì)：①消息剩余類是m重包含的，總共含有所有可能的信息。對(duì)于密文的剩余類也一樣。②用任一密鑰將中的任一信息譯碼，產(chǎn)生中密文。反過來(lái)也成立。③中的信息數(shù)，稱為，等于中的密文數(shù)，也是密鑰個(gè)數(shù)k地一個(gè)除數(shù)。④中的每一信息可以通過個(gè)不同的密鑰譯碼到內(nèi)的每一密文。?概念的重要性在于，在一個(gè)純密碼中，所有密鑰本質(zhì)上是一樣的。對(duì)于一個(gè)特定的信息，無(wú)論用哪個(gè)密鑰，所有信息的后驗(yàn)概率是一樣的。（信息剩余類）（密文剩余類）

由左圖可以看出：?4、2、1均為k=4

的除數(shù)。（滿足性質(zhì)③）?M和E的變換是純系統(tǒng)。（滿足性質(zhì)②）Theorem

4.在一個(gè)純系統(tǒng)中，不同信息的后驗(yàn)概率和所選的密鑰是獨(dú)立的。密鑰的后驗(yàn)概率在數(shù)值上是相同的，但存在不同密鑰排列選擇的過程。?任意密鑰的選擇導(dǎo)致了在純密碼中的相同的問題---密碼分析的問題。（上一頁(yè)圖）由于不同的密鑰可以產(chǎn)生相同剩余類中的密文，意味著：相同剩余類中的密文在分析上是等效的。?從維吉尼亞碼舉例：密文被寫在長(zhǎng)度為d的連續(xù)塊中，當(dāng)d=5時(shí)：

?5欄被分別切開，且重組構(gòu)成有意義的信息。

?當(dāng)列被切開，唯一的剩余信息是密文的剩余類Theorem5.如果是純系統(tǒng)，那么。其中，是的任意兩個(gè)變換。反過來(lái)，如果上述等式在系統(tǒng)中成立，那么是純系統(tǒng)。證明：①前半部分的證明由純系統(tǒng)的定義易證。②后半部分：

左邊：右邊：同理，可以得到：Ti、Tj等效，成立。

（②得證）△△Part3密碼系統(tǒng)的理論安全性密碼體制的組成通常情況下，一個(gè)密碼體制由五元組{SL，Cn，Br，Ek，Dk}五個(gè)部分組成：·明文信息空間SL，它是全體明文s的集合；·密文信息空間Cn，它是全體密文c的集合；·密鑰空間Br，它是全體密鑰b的集合；·加密算法Ek:它是一族由SL到Cn的加密變換，即SL→Cn;·解密空間Dk，它是一族由Cn到SL的解密變換，即Cn→SL密碼分析的類型唯密文破譯：僅能對(duì)截獲的密文進(jìn)行分析，得出明文或密鑰；已知明文破譯：分析破譯部分已知的明文－密文對(duì)；選擇明文破譯：可以選擇任何明文-密文對(duì)；選擇密文破譯：可以選擇任何密文-明文對(duì)。顯然，唯密文破譯是對(duì)系統(tǒng)的密碼破解威脅最弱的一類攻擊。利用信息論的語(yǔ)言來(lái)表述保密系統(tǒng)：明文熵：H(SL)=H(S1S2‥SL)密鑰熵：H(Br)=H(B1B2‥Br)密文熵：H(Cn)=H(C1C2‥Cn)已知密文，關(guān)于明文的疑義度為H(SL/Cn)明文和密文之間的互信息：I(SL;Cn)=H(SL)－H(SL/Cn)①?gòu)拿芪闹刑崛∮嘘P(guān)密鑰的信息：I(Br;Cn)＝H(Br)－H(Br/Cn)②完全保密性對(duì)合法接收者：H(SL/CnBr)＝0所以：I(SL;CnBr)＝H(SL)－H(SL/CnBr)

＝H(SL)顯然，I(SL;Cn)＝0時(shí)，為完全保密系統(tǒng)，或無(wú)條件保密系統(tǒng)，破譯者無(wú)法破譯。完全保密性保密系統(tǒng)的三個(gè)基本結(jié)論定理1：

I(SL;Cn)≥H(SL)－H(Br)說(shuō)明：必須使密鑰量盡可能大，才能使互信息為0。定理2：完全保密系統(tǒng)的必要條件：

H(Br)≥H(SL)也就是說(shuō)密鑰熵大于明文熵。一般明文存在剩余度，所以密鑰量可以下降。定理3：存在完全的保密系統(tǒng)。對(duì)合法接收者：H(SL/CnBr)＝0所以：I(SL;CnBr)＝H(SL)－H(SL/CnBr)

＝H(SL)顯然，I(SL;Cn)＝0時(shí)，為完全保密系統(tǒng)，或無(wú)條件保密系統(tǒng)，破譯者無(wú)法破譯。完全保密性問題：在唯密條件下，破譯時(shí)需要處理至少多少密文量？2015-12-28已知：H(Br/Cn)＝H(Br/C1C2‥Cn）

≤H(Br/C1C2‥