概率論基礎(chǔ)

假定x和y是分別定義在有限集合X和Y上的隨機(jī)變量。聯(lián)合概率 (P(x_i,y_i)) 是 (x=x_i, y=y_i) 的概率。條件概率 (P(x_i vert y_i )) 是 (y=y_i) 時(shí)， (x=x_i) 的概率。如果對(duì)于任意(x in X , y in Y) 都有 (P(x, y) = P(x)P(y)) 則隨機(jī)變量X和Y是統(tǒng)計(jì)獨(dú)立的。

貝葉斯定理：

[P(X|Y) = frac{P(X)P(Y|X)}{P(Y)}
]

在密碼體制中，就可以如下定義：

[P(p|c) = frac{P(p)P(c|p)}{P(c)} = frac{P(p)sum_{{k:p=d_k(c)}}P(k)}{sum_{{k:c in C(k)}}P(k)P(p=d_k(c))} \ P(c) = sum_{{k:c in C(k)}}P(k)P(p=d_k(c)) \ P(c|p) = sum_{{k:p=d_k(c)}}P(k)
]

熵的含義

消息的信息量描述了消息的不確定性
香農(nóng)從概率測(cè)量的角度來描述消息M的信息量，并用信息熵來進(jìn)行度量：$$H(M) = - sum^n_{i=1}P(x_i)log_2P(x_i)$$

其中n為事件總數(shù)，(x_i) 表示隨機(jī)事件，(log_2P(x_i)) 表示自信息量。

熵的性質(zhì)

[H(X,Y) = H(Y) + H(X|Y) = H(Y) + H(Y|X)
]

密碼體制組成部分熵的基本關(guān)系

假設(shè)(P,C,K,E,D)是一個(gè)密碼體制。P代表明文空間、C表示密文空間，K表示密鑰空間，E表示加密算法，D表示解密算法。
那么有 H(K|C) = H(K) + H(P) - H(C)
證明如下：

H(K,P,C) = H(C|K, P) + H(K, P)。 由于密鑰和明文唯一決定密文，因此H(C|K, P) = 0， 而K和P是統(tǒng)計(jì)獨(dú)立的，因此 H(K, P) = H(K) + H(P)
同樣地，密鑰和密文唯一決定明文，因此H(P|K,C) = 0。 于是H(K,P,C) = H(K, C)
H(K|C) = H(K, C) - H(C) = H(K, P, C) - H(C) = H(K) + H(P) - H(C)

相關(guān)性

自然語言的字符之間不是毫無關(guān)聯(lián)的。為了衡量自然語言信源符號(hào)之間的依賴程度，引入了相關(guān)性和冗余度的概念。

信源符號(hào)之間的依賴程度稱為信源的相關(guān)性。
假設(shè)信源有m個(gè)符號(hào)，那么對(duì)于不同情況可以分別計(jì)算信源的熵：

[egin{align}&H_0 = log_2m \ &H_1=H(X_1)\&H_2=H(X_2|X_1)\&cdots \&H_n=H(X_n|X_1X_2 cdots X_{n-1})\&H_{infty}=H((lim_{n o infty}X_n|X_1X_2 cdots X_{n-1}))end{align}
]

可以證明 (H_0 ge H_1 ge H_2 ge cdots ge H_{infty})

也就是說，符號(hào)相關(guān)程度越大，熵值越小，反之亦然。

冗余度

為了描述信源的相關(guān)性，引入信源效率(eta)和冗余度(gamma)

可得，信源效率 (eta = frac{H_{infty}}{H_0}) 信源冗余度為 (gamma = 1 - eta)

可見，(H_0) 是信源符號(hào)獨(dú)立等概率分布時(shí)信源的熵，是每個(gè)符號(hào)所能攜帶的最大信息量。但實(shí)際上每個(gè)符號(hào)僅能攜帶 (H_{infty}) 的信息。 因此 (gamma) 就是信源中多余成分的比例。

唯一解距離

對(duì)于長(zhǎng)度為S的密文序列 (C^S = (C_1, C_2, cdots , C_S)) , 其密鑰含糊度為 (H(K|C^S)) 有下界： (H(K) - gamma SH_0)

當(dāng)(S = frac{H(K)}{H_0 gamma}) 時(shí)， 稱S為唯一解距離。當(dāng)唯一解距離為無窮大時(shí)，系統(tǒng)稱為理想保密系統(tǒng)。

唯一解距離只給出了存在性結(jié)論，而沒有給出具體的破譯方法。唯一解距離指出了當(dāng)進(jìn)行破譯攻擊時(shí)，可能解密出唯一有意義的明文所需要的最少密文量。唯一解距離越長(zhǎng)，密碼系統(tǒng)越好。 但是，這是假定分析者能利用明文語言的全部統(tǒng)計(jì)知識(shí)的條件下得到的。實(shí)際上由于自然語言的復(fù)雜性，目前沒有任何一種分析方法能夠做到這一點(diǎn)。所以 一般破譯所需的密文量要遠(yuǎn)遠(yuǎn)大于理論值。

密碼攻擊類型

唯密文攻擊 分析者除了擁有截獲的密文以外沒有其它可以利用的信息。（僅僅竊聽）
已知明文攻擊 不僅掌握了相當(dāng)數(shù)量的密文，還有一些已知的明-密文對(duì)可供使用。（有內(nèi)奸）
選擇明文攻擊 不僅能夠獲得一定數(shù)量的明-密文對(duì)，還可以選擇任何明文并在使用同一未知密鑰的情況下得到相應(yīng)的密文（暫時(shí)控制加密機(jī)）
選擇密文攻擊 能夠選擇不同的加密密文，還能得到對(duì)應(yīng)的明文。其任務(wù)是推算出密鑰及密文對(duì)應(yīng)的明文（暫時(shí)控制解密機(jī)）
選擇文本攻擊 （暫時(shí)控制加密機(jī)與解密機(jī)）
這五種攻擊類型依次增強(qiáng)。能夠抵御這五種類型的攻擊是密碼算法的基本要求。

密碼體制的安全性

無條件安全

不論提供的密文有多少，密文中包含得的信息都不足以惟一地確定其對(duì)應(yīng)的明文

具有無線計(jì)算資源的密碼分析者也無法破譯某個(gè)密碼系統(tǒng)。

計(jì)算安全性

涉及攻破密碼體制所需的計(jì)算工作量。

計(jì)算出或估算出破譯它的計(jì)算量下限，利用已有的最好方法破譯該密碼系統(tǒng)所需要的努力超出了破譯者的破譯能力。

可證明安全性

通過有效的轉(zhuǎn)化，將密碼體制的任何有效攻擊歸約為一類已知難處理的問題。即使用多項(xiàng)式歸約技術(shù)形式化證明一種密碼體制的安全性。

這種方法只是說明了安全性和另一個(gè)問題相關(guān)的，并沒有完全證明它是安全的。

總結(jié)

以上是生活随笔為你收集整理的香农理论在密码学中的应用的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。