Shannon理論——筆記1

目錄

• Shannon理論——筆記1
• • 引言
  • 概略
  • 完善保密性
  • 熵
  • • 熵的性質(zhì)
  • 偽密鑰和唯一解距離
  • • 預(yù)備知識
    • 偽密鑰
    • 唯一解距離
  • 乘積密碼體制

引言

• 我們知道有這樣幾個(gè)評價(jià)密碼體制安全性的常用的準(zhǔn)則：
  • 計(jì)算安全性
  • 可證明安全性
  • 無條件安全性
• 其中無條件安全性允許無限的計(jì)算資源、無限的計(jì)算時(shí)間，所以不能用計(jì)算復(fù)雜性的觀點(diǎn)來研究。
• 研究無條件安全性的合適框架是概率論，我們將在后文進(jìn)行討論

概略

• Shannon的思想對密碼學(xué)的研究產(chǎn)生了巨大影響，那么這些究竟意味什么呢
• 本文主要打算介紹如下概念、思想
  • 完善保密性
  • 熵
  • 偽密鑰和唯一解距離
  • 乘積密碼體制

完善保密性

• 通俗地講，完善保密性就是說攻擊者Oscar不能通過觀察密文獲得明文的任何信息
  • 推測明文為某種情況的概率不會因?yàn)橹烂芪亩淖?/li>

定義：
一個(gè)密碼體制具有完善保密性，如果對于任意的$x\in \mathcal{P}$和$y\in \mathcal{C}$，都有$Pr[x|y]=Pr[x]$。也就是說，給定密文$y$,明文$x$的后驗(yàn)概率等于明文$x$的先驗(yàn)概率

• 一般的完整保密性
  • 對于任意固定的$x\in \mathcal{P}$。由Bayes定理，有：對每個(gè)$y\in \mathcal{C}$，我們有$Pr[y|x]=Pr[y]>0$（概率為零的情況可以直接從定義域中去掉）。
    • 也就是說，在完善保密密碼體制下，對于某固定明文，密文有限集中的任意元素都存在是由此明文被加密后的結(jié)果的可能
  • 因此，對于每個(gè)$y\in \mathcal{C}$，一定至少存在一個(gè)密鑰$K$，滿足$e_k(x)=y$。這樣就有$|\mathcal{K}|\ge |\mathcal{C}|$。
  • 又因?yàn)樵谌我庖粋€(gè)密碼體制中，加密函數(shù)是單射的，所以一定有$|\mathcal{C}|\ge |\mathcal{P}|$。
  • 于是我們得到
    • 在一個(gè)完善保密密碼體制中，$|\mathcal{K}|\ge |\mathcal{C}|\ge |\mathcal{P}|$
• 需要注意的是，上一步討論的是完善保密密碼體制所具備的必要條件，并不能作為判定依據(jù)
• 關(guān)于判定依據(jù)，當(dāng)$|\mathcal{K}|=|\mathcal{C}|=|\mathcal{P}|$時(shí)，Shannon最早提出了一個(gè)性質(zhì)：

定理
假設(shè)密碼體制$(\mathcal{P},\mathcal{C},\mathcal{K},\mathcal{E},\mathcal{D})$滿足$|\mathcal{K}|=|\mathcal{C}|=|\mathcal{P}|$。該密碼體制是完善保密的$?$每個(gè)密鑰被使用的概率都是$\frac{1}{|\mathcal{K}|}$，并且$?x\in \mathcal{P}andy\in \mathcal{C},?!K,s.t.e_K(x)=y$

熵

• 度量信息不確定性
  • 值越大，表示的不確定性越大
• 對于隨機(jī)變量X，其熵表示為H(X)

定義
假設(shè)隨機(jī)變量$\mathbf{X}$在有限集合X上取值，則隨機(jī)變量$\mathbf{X}$的熵定義為$$H(\mathbf{X})=?\sum _{x\in X}\mathrm{P}\mathrm{r}[\mathrm{x}]\mathrm{l}\mathrm{b}\mathrm{P}\mathrm{r}[\mathrm{x}]$$

• 比如當(dāng)X只有一種可能取值時(shí)（即取該值的概率為1），其熵為0

熵的性質(zhì)

• $0\le H(\mathbf{X})\le \mathrm{l}\mathrm{b}n,其中n=|X|$
  • 可由Jenson不等式證得
• $H(\mathbf{X},\mathbf{Y})\le H(\mathbf{X})+H(\mathbf{Y})$，當(dāng)且僅當(dāng)$\mathbf{X},\mathbf{Y}$統(tǒng)計(jì)獨(dú)立時(shí)等號成立

定義
假設(shè)$\mathbf{X},\mathbf{Y}$是兩個(gè)隨機(jī)變量。對于$\mathrm{Y}$的任何固定值y,得到一個(gè)$\mathrm{X}$上的條件概率分布；記相應(yīng)的隨機(jī)變量為$\mathbf{X}|y$，顯然$$H(\mathbf{X}|y)=?\sum _x\mathrm{P}\mathrm{r}[\mathrm{x}|\mathrm{y}]\mathrm{l}\mathrm{b}\mathrm{P}\mathrm{r}[\mathrm{x}|\mathrm{y}]$$定義條件熵$H(\mathbf{X}|\mathbf{Y})$為熵$H(\mathbf{X}|y)$取遍所有y的加權(quán)平均值。計(jì)算公式為$$H(\mathbf{X}|\mathbf{Y})=?\sum _y\sum _x\mathrm{P}\mathrm{r}[\mathrm{y}]\mathrm{P}\mathrm{r}[\mathrm{x}|\mathrm{y}]\mathrm{l}\mathrm{b}\mathrm{P}\mathrm{r}[\mathrm{x}|\mathrm{y}]$$條件熵度量了$\mathbf{Y}$揭示的$\mathbf{X}$的平均信息量

• $H(\mathbf{X},\mathbf{Y})=H(\mathbf{Y})+H(\mathbf{X}|\mathbf{Y})\le H(\mathbf{Y})+H(\mathbf{X})$等式成立當(dāng)且僅當(dāng)$\mathbf{X},\mathbf{Y}$統(tǒng)計(jì)獨(dú)立

偽密鑰和唯一解距離

預(yù)備知識

密鑰含糊度

$H(\mathbf{K}|\mathbf{C})$：度量了給定密文下密鑰的不確定性

• $\mathbf{H}(\mathbf{C}|\mathbf{K},\mathbf{P})=0$
  • 因?yàn)槊荑€和明文唯一決定密文
• $\mathbf{H}(\mathbf{P}|\mathbf{K},\mathbf{C})=0$
  • 因?yàn)槊荑€和密文唯一決定明文
• $\mathbf{K},\mathbf{P}$是統(tǒng)計(jì)獨(dú)立的$?H(\mathbf{K},\mathbf{P})=H(\mathbf{K})+H(\mathbf{P})$
  • 因?yàn)槊荑€是在Alice知道明文之前選取的，所以可以合理地假設(shè)密鑰、明文是統(tǒng)計(jì)獨(dú)立的隨機(jī)變量
• 值得注意的是，盡管密鑰和密文唯一決定明文，但我們并不能像上一步那樣認(rèn)為$\mathbf{K},\mathbf{C}$是統(tǒng)計(jì)獨(dú)立的

定理
設(shè)$(\mathcal{P},\mathcal{C},\mathcal{K},\mathcal{E},\mathcal{D})$是一個(gè)密碼體制，那么$$H(\mathbf{K}|\mathbf{C})=H(\mathbf{K})+H(\mathbf{P})?H(\mathbf{C})$$

偽密鑰

• 密碼分析的基本目的是確定密鑰
• 考慮唯密文攻擊，對于Oscar而言，它可以得到多個(gè)密鑰
  • 通過這些密鑰對某些明文加密得到Oscar所唯一知道的密文，這一過程在計(jì)算上是可行的
  • 但這樣的明文不一定都有意義，很多可能只是雜亂的字母的組合而已，這部分對應(yīng)的密鑰可直接被Oscar排除
  • 但仍可能會有多個(gè)密鑰，其對應(yīng)明文在一個(gè)語言體系下都是有意義的，并非雜亂的字母組合
• 在這些密鑰中，只有一個(gè)密鑰是正確的
• 那些可能的但不正確的密鑰稱為 偽密鑰

唯一解距離

定義
一個(gè)密碼體制的唯一解距離定義為使得偽密鑰的期望數(shù)等于零的$n$的值，記為$n_0$，即在給定的足夠的計(jì)算時(shí)間下分析者能唯一計(jì)算出密鑰所需密文的平均值

• 可以看出，偽密鑰的存在對密文的破譯造成了障礙

• 偽密鑰數(shù)越小，破譯自然越方便

• 所以我們的目的就是推導(dǎo)偽密鑰的期望數(shù)的下界

  • 為什么是期望數(shù)？
    • 因?yàn)樗鶕碛忻芪牡牟煌瑫斐蓚蚊荑€數(shù)的不同
    • 所以對所有這些值的期望的描述才能更好地描述背后的密碼體制

• 偽密鑰的期望數(shù)如何表示？

  • 給定$y\in {\mathcal{C}}^n$，定義$$K(y)=\{K\in \mathcal{K}:?x\in {\mathcal{P}}^n,s.t.\mathrm{P}\mathrm{r}[\mathrm{x}]>0,e_k(x)=y\}$$
    • 即$K(y)$是密文為$y$的可能密鑰的集合
      • 這里可能的含義需要格外注意
        • 在這些密鑰下$y$對應(yīng)的明文有意義
        • 否則對應(yīng)密鑰可以直接被排除，便無所謂可能了
  • 于是$y$對應(yīng)的偽密鑰數(shù)目為 $$|K(y)|?1$$
  • 偽密鑰的平均數(shù)目(期望)為$$\begin{array}{rl}\overline{s_n}& =\sum _{y\in {\mathcal{C}}^n}\mathrm{P}\mathrm{r}[\mathrm{y}](|K(y)|?1)\\ & =\sum _{y\in {\mathcal{C}}^n}\mathrm{P}\mathrm{r}[\mathrm{y}]|K(y)|?\sum _{y\in {\mathcal{C}}^n}\mathrm{P}\mathrm{r}[\mathrm{y}]\\ & =\sum _{y\in {\mathcal{C}}^n}\mathrm{P}\mathrm{r}[\mathrm{y}]|K(y)|?1\end{array}$$

• 如前所述，唯一解距離為使得$\overline{s_n}=0$的$n$的值

• 想要找到這個(gè)$n_0$，就要考慮$\overline{s_n}$與$n$之間的關(guān)系

• 如何建立與$n$的聯(lián)系？

  • 回顧$\overline{s_n}$的關(guān)系式
    • 其與每個(gè)密文y的概率以及y下可能密鑰集的大小有關(guān)
    • 而由前述知識，密鑰集大小$|K(y)|$的對數(shù)是熵$H(\mathbf{K}|y)$的上限
      • 這為我們提供了一條向外建立聯(lián)系的思路
    • 聯(lián)立：$$\begin{array}{rl}\overline{s_n}+1=& \sum _{y\in {\mathcal{C}}^n}\mathrm{P}\mathrm{r}[\mathrm{y}]|K(y)|\\ & \sum _{y\in {\mathcal{C}}^n}\mathrm{P}\mathrm{r}[\mathrm{y}]H(\mathbf{K}|y)=H({\mathbf{K}|\mathbf{C}}^n)\end{array}$$
  • 于是$$\begin{array}{rl}H({\mathbf{K}|\mathbf{C}}^n)& =\sum _{y\in {\mathcal{C}}^n}\mathrm{P}\mathrm{r}[\mathrm{y}]H(\mathbf{K}|y)\\ & \le \sum _{y\in {\mathcal{C}}^n}\mathrm{P}\mathrm{r}[\mathrm{y}]\mathrm{l}\mathrm{b}|K(y)|\\ & \le \mathrm{l}\mathrm{b}\sum _{y\in {\mathcal{C}}^n}\mathrm{P}\mathrm{r}[\mathrm{y}]|K(y)|\\ & \le \mathrm{l}\mathrm{b}(\overline{s_n}+1)\end{array}$$

• 而由預(yù)備知識中定理$$H({\mathbf{K}|\mathbf{C}}^n)=H(\mathbf{K})+H({\mathbf{P}}^n)?H({\mathbf{C}}^n)$$

• 由于自然語言中各字符間并非毫無關(guān)聯(lián)，引入如下概念：

定義
自然語言$L$的的熵(每字母)$$H_L=\underset{n\to \infty }{\lim }\frac{H({\mathbf{P}}^n)}{n}$$
語言L的冗余度定義為$$R_L=1?\frac{H_L}{\mathrm{l}\mathrm{b}|\mathcal{P}|}$$

• 可知$H_L$是屬于一種自然語言$L$的固有性質(zhì)，它度量了這種語言的每個(gè)字母的平均熵，一個(gè)隨機(jī)語言具有熵$\mathrm{l}\mathrm{b}|\mathcal{P}|$
  • 同時(shí)，這也提供了一種對$H({\mathbf{P}}^n)$的估計(jì)
• 有$$\{\begin{array}{l}H({\mathbf{P}}^n)\approx n{H}_L=n(1?R_L)\mathrm{l}\mathrm{b}|\mathcal{P}|\\ H({\mathbf{C}}^n)\le n\mathrm{l}\mathrm{b}|\mathcal{C}|\end{array}$$
• 所以,如果$|\mathcal{C}|=|\mathcal{P}|$有 $$\mathrm{l}\mathrm{b}(\overline{s_n}+1)\ge H({\mathbf{K}|\mathbf{C}}^n)=H(\mathbf{K})+H({\mathbf{P}}^n)?H({\mathbf{C}}^n)\ge H(\mathbf{K})?n{R}_L\mathrm{l}\mathrm{b}|\mathcal{P}|$$
• 考慮等概率選取密鑰的情況，此時(shí)$H(\mathbf{K})=\mathrm{l}\mathrm{b}|\mathcal{K}|$，有

定理
假設(shè)$(\mathcal{P},\mathcal{C},\mathcal{K},\mathcal{E},\mathcal{D})$是一個(gè)密碼體制，$|\mathcal{C}|=|\mathcal{P}|$并且密鑰是等概率選取。設(shè)$R_L$表示明文的自然語言的冗余度，那么給定一個(gè)充分長（長為n）的密文串，偽密鑰的期望數(shù)滿足$$\overline{s_n}\ge \frac{|\mathcal{K}|}{|\mathcal{P}{|}^{n{R}_L}}?1$$

• 在這種情況下，我們可以得到$$n_0\approx \frac{\mathrm{l}\mathrm{b}|\mathcal{K}|}{R_L\mathrm{l}\mathrm{b}|\mathcal{P}|}$$
  • 這意味著，給定的密文串的長度至少為25時(shí)，通常解密才是唯一的
• 至此，關(guān)于唯一解距離的求解已經(jīng)討論結(jié)束
• 值得注意的是，所求結(jié)果并不一定準(zhǔn)確，而且運(yùn)算中的符號連接很多都是不等號，但這樣的求得的唯一解距離實(shí)際上也可以標(biāo)明一個(gè)密碼系統(tǒng)的好壞
  • 唯一解距離越長，密碼系統(tǒng)越好
  • 當(dāng)唯一解距離為無窮大時(shí)，系統(tǒng)稱為理想保密系統(tǒng)
    • 此時(shí)Oscar便無法從眾多“可能”的密鑰中得到真正正確的密鑰
    • 而實(shí)際上由于自然語言的復(fù)雜性，目前沒有任何一種分析方法可以做到

乘積密碼體制

• 即通過“乘積”組合密碼體制

總結(jié)

以上是生活随笔為你收集整理的Shannon理论——笔记1的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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