寫在最前面

主要在 哈工大密碼學(xué)課程 張宇老師課件 的基礎(chǔ)上學(xué)習(xí)記錄筆記。

內(nèi)容補(bǔ)充：駱婷老師的PPT
《introduction to modern cryphtography》–Jonathan Katz, Yehuda Lindell（現(xiàn)代密碼學(xué)——原理與協(xié)議）中相關(guān)章節(jié)
密碼學(xué)復(fù)習(xí)筆記 這個博主好有意思
B站視頻 密碼學(xué)原理《Introduction to modern Cryptography》

初步筆記，如有錯誤請指正

快速補(bǔ)充一些密碼相關(guān)的背景知識

私鑰加密與偽隨機(jī)性 第一部分

在本節(jié)課程中，我們學(xué)習(xí)計(jì)算安全下的私鑰加密和偽隨機(jī)性的第一部分。我們會學(xué)習(xí)一個完整的現(xiàn)代密碼學(xué)研究過程，從定義到假設(shè)，再到一個密碼學(xué)方案，最后使用規(guī)約法來證明其安全性。

目錄：密碼學(xué)的計(jì)算方法論，計(jì)算安全加密的定義，偽隨機(jī)性，規(guī)約法，構(gòu)造安全的加密方案

密碼學(xué)的計(jì)算方法論

3. 計(jì)算安全思想

   • 完美保密局限性在于密鑰需要很長，而且如果密鑰不夠長，則不能達(dá)到完美保密。Kerchhoffs提出另一個原則：一個加密方案如果不是數(shù)學(xué)上，那必須是實(shí)踐上不可破解的。 不同于在完美保密部的信息論上的安全，計(jì)算安全放松了安全條件來追求實(shí)踐中的安全，使得密鑰相對于明文可以很短。
   • 計(jì)算安全：
     • 敵手在可行的時間內(nèi)運(yùn)行，破解密碼的時間是有限的
     • 敵手以非常小的概率成功，能成功但可能性很小

4. 放松條件的必要性

   為什么相對于完美保密，要放松對安全的需求?？紤]之前的不可區(qū)分實(shí)驗(yàn)，

   • 為了對抗蠻力攻擊，需要限定敵手的能力；因?yàn)橹灰o了充足的時間來遍歷$|\mathcal{K}|$，蠻力攻擊一定會成功；
   • 為了對抗隨機(jī)猜測，需要允許小到可忽略的（negligible）成功概率；因?yàn)橄共乱灿?span id="n5n3t3z" class="katex--inline">$1/|\mathcal{K}|$概率成功；

5. 具體法與漸進(jìn)法

   • 具體法：限定時間和成功的概率為具體值；一個加密方案是$(t,\epsilon )$-安全的，如果對任意敵手以時間 $t$ 運(yùn)行，成功破解方案的概率最多是 $\epsilon$。
   • 具體法的問題是缺乏規(guī)律性，無法描述密鑰長度、時間和成功概率之間的關(guān)系。
   • 漸進(jìn)法：計(jì)算復(fù)雜性理論使用是與輸入規(guī)模$n$有關(guān)的函數(shù)來表示時間或空間復(fù)雜性。例如，快速排序算法的時間復(fù)雜性是$O(n?\log n)$，其中$n$是問題的規(guī)模，這里是排序元素的個數(shù)。
   • 具體法和漸進(jìn)法的區(qū)別之一是，一個是點(diǎn)，一個是線。

6. P=NP？

   • 如何定義“可行的時間”和“非常小的概率”？答案來自計(jì)算復(fù)雜性理論，理論上認(rèn)為一個搜索問題（例如，獲得密鑰）是相對簡單的，如果解決該問題算法的時間復(fù)雜性為問題規(guī)模參數(shù)$n$的多項(xiàng)式；而需要非多項(xiàng)式（包括指數(shù)）時間復(fù)雜性來解決的問題是難以被實(shí)際解決的。
   • 在計(jì)算復(fù)雜性理論中，問題可分為兩類：
     • 一類可解的問題，稱為P（polynomial time）問題，是指能夠在問題規(guī)模的多項(xiàng)式時間內(nèi)由確定性圖靈機(jī)解決的問題；
     • 另一類包含P問題的更大范圍的NP（nondeterministic polynomial time）問題，不能確定是否在多項(xiàng)式時間內(nèi)可以解決，但能夠在多項(xiàng)式時間內(nèi)驗(yàn)證一個答案是否正確的問題；盡管理論上用非確定性圖靈機(jī)可在多項(xiàng)式時間解決，但非確定性圖靈機(jī)還無法實(shí)現(xiàn)；
     • 在NP問題中，包含一類相似的難題，尚未找到多項(xiàng)式時間算法，但這些問題中的一個若被解決了，則其它也能被解決，稱為NP完全問題（NP-Complete）；與NP完全問題一樣難或更難的問題，稱為NP難問題（NP-Hard）；
     • 科學(xué)家們相信NP問題集合不同于P問題集合，在NP問題中有一些難題無法在多項(xiàng)式時間內(nèi)解決，即P$\ne$NP；
       • 在一部穿越電視劇《天才基本法》中，一個情節(jié)是：P=NP被證明真成立。
     • 加密與計(jì)算復(fù)雜性：1955年，約翰·納什在其給NSA的信中說，他猜測破解一個復(fù)雜的代碼需要密鑰長度指數(shù)的時間。如果如此，則意味著P$\ne$NP，因?yàn)榻鉀Q問題所需時間不是多項(xiàng)式的，而驗(yàn)證答案是多項(xiàng)式的。
     • 因此，將多項(xiàng)式時間認(rèn)為是“可行的時間”，而非多項(xiàng)式的指數(shù)時間被認(rèn)為是“不可行的”；
     • 非常小的概率定義為，比任何多項(xiàng)式分之一都小。

7. 有效的計(jì)算

   • 一個算法是多項(xiàng)式時間的（polynomial time），如果存在一個多項(xiàng)式使得對于任意輸入，算法都在該多項(xiàng)式步驟內(nèi)結(jié)束。
   • 一個算法可以在多項(xiàng)式時間內(nèi)以任何多項(xiàng)式時間算法作為子例程來運(yùn)行；
   • 概率（probabilistic）算法有“擲硬幣”的能力。其中，隨機(jī)數(shù)生成器應(yīng)該是為密碼學(xué)用途來設(shè)計(jì)的，而不是C語言里的random()。相反地，沒有隨機(jī)性的算法就是確定性的；
   • 開放問題：概率性的敵手比確定性的敵手更強(qiáng)大嗎？$\mathcal{P}=\mathcal{B}\mathcal{PP}$ (限定錯誤的概率多項(xiàng)式)?

8. 可忽略的成功概率

   • 一個函數(shù)$f$是可忽略的，若對于任意多項(xiàng)式$p(?)$，存在一個$N$使得對于所有整數(shù)$n>N$，$f(n)<\frac{1}{p(n)}$。

9. 漸進(jìn)方法（Asymptotic）

   • 根據(jù)上面的基礎(chǔ)，采用漸進(jìn)方法來定義安全，所謂“漸進(jìn)”是指不研究一個參數(shù)固定的問題的復(fù)雜性，而是研究時間復(fù)雜性隨著問題參數(shù)$n$的變化而變化的規(guī)律；
   • 問題X（破解加密方案）是難的，若X不能由任何多項(xiàng)式時間算法以時間$t$解決，除非以可忽略的概率$\epsilon$；
   • $t$和$\epsilon$都描述為安全參數(shù)$n$（通常是密鑰長度）的函數(shù)；
   • 注意：安全是對足夠大的$n$值來說的；
   • 例如，例子中隨著$n$的增加，破解的復(fù)雜性隨密鑰空間指數(shù)增加，加密方案更難破解。

計(jì)算安全加密的定義：對稱加密算法

10. 定義私鑰加密方案

    • 回顧私鑰加密相關(guān)定義

11. 竊聽不可區(qū)分實(shí)驗(yàn)

    • 在竊聽不可區(qū)分實(shí)驗(yàn)中，敵手和挑戰(zhàn)者之間進(jìn)行一個思維實(shí)驗(yàn)。敵手根據(jù)安全參數(shù)產(chǎn)生兩個相同長度的不同消息，并發(fā)送給挑戰(zhàn)者；挑戰(zhàn)者根據(jù)安全參數(shù)生成密鑰，并對隨機(jī)選擇的一個消息進(jìn)行加密，將挑戰(zhàn)密文發(fā)送給敵手。敵手輸出一個比特，來表示對被加密消息的猜測，若猜對，則實(shí)驗(yàn)成功。
    • 一個敵手$\mathcal{A}$與一個挑戰(zhàn)者$\mathcal{C}$進(jìn)行3輪交互：
      1. $\mathcal{A}$選擇兩個長度相同、內(nèi)容不同明文$m_0,m_1$，并發(fā)送給$\mathcal{C}$；
      2. $\mathcal{C}$根據(jù)密鑰生成算法生成一個新密鑰$k$，隨機(jī)生成一個比特$b$并挑選一個明文$m_b$，加密${\mathsf{Enc}}_k(m_b)$后得到挑戰(zhàn)密文$c$，并發(fā)送給$\mathcal{A}$；
      3. $\mathcal{A}$輸出對所加密明文的猜測$b^{\prime }$，若$b=b^{\prime }$，則$\mathcal{A}$成功；否則，失敗；
    • 這與之前在完美保密中的不可區(qū)分實(shí)驗(yàn)類似的，區(qū)別在于本實(shí)驗(yàn)不是無條件的，而是輸入“安全參數(shù)”，該參數(shù)將作用于安全定義。竊聽不可區(qū)分實(shí)驗(yàn)既用在了信息論安全定義，也用在了計(jì)算安全定義，這就在兩者之間建立了聯(lián)系。

12. 私鑰加密安全定義

    • 一個加密方案在出現(xiàn)竊聽者時是不可區(qū)分加密，若對于任意概率多項(xiàng)式時間的敵手，存在一個可忽略函數(shù)，使得不可區(qū)分實(shí)驗(yàn)成功概率與1/2相比（兩者間的差異）是可忽略的。
    • 其中，多項(xiàng)式時間和可忽略都是對于“安全參數(shù)”的函數(shù)。

13. 理解不可區(qū)分性的定義

    • 一次一密方案在出現(xiàn)竊聽者時是否是不可區(qū)分的？
    • 若一個敵手一直在實(shí)驗(yàn)中失敗，該方案是安全的嗎？
    • 在兩個連續(xù)竊聽不可區(qū)分實(shí)驗(yàn)中，使用同一個密鑰的概率有多大？
    • 若從密文中猜測到消息中最低比特的概率是3/4，該方案是安全的嗎？
    • 若從密文中猜測到消息中最低3個比特的概率是3/8，該方案是安全的嗎？

• 相關(guān)性：$X$和$Z$的分布不可區(qū)分，$Y$和$Z$的分布不可區(qū)分，那么$X$和$Y$的分布是不可區(qū)分的嗎？

14. 語義安全（semantic security）

    • 之前在導(dǎo)論部分有一個問題：如何定義不泄漏“meaningful”的信息。下面引入語義安全的概念來解決這個問題。
    • 直覺：沒有關(guān)于明文的任何有意義的信息泄漏
    • 關(guān)于明文的信息用明文的函數(shù)來表示，$h(m)$表示敵手預(yù)先了解的關(guān)于明文的外部信息，$f(m)$表示敵手希望獲取的關(guān)于明文的有意義的信息
    • 定義：加密方案是竊聽者出現(xiàn)時語義安全的，如果對于任意敵手，任意明文分布，任意函數(shù)$f$和$h$，一個敵手根據(jù)密文和$h(m)$獲得$f(m)$，另一個敵手只根據(jù)$h(m)$獲得$f(m)$，這兩個敵手成功的概率之間的差異是可以忽略的
    • 定理：一個私鑰加密方案是竊聽者不可區(qū)分的，當(dāng)且僅當(dāng)該方案是語義安全的。
    • 證明略。直覺上，從右到左：若敵手能夠在不可區(qū)分實(shí)驗(yàn)中成功（不是不可區(qū)分的），則意味著根據(jù)密文獲得了關(guān)于區(qū)分明文的某些信息（不是語義安全）；反之，若敵手能夠獲得關(guān)于明文的某些信息（不是語義安全），那么可以利用這些信息來區(qū)分明文（不是不可區(qū)分的）。

偽隨機(jī)性

15. 偽隨機(jī)性概念（Pseudorandomness）

    • 回顧之前完美保密的局限性，密鑰長度需要和明文一樣長才安全；計(jì)算安全中放松了安全的定義，那密鑰能不能短一些，或者說能不能放松對隨機(jī)性的要求，產(chǎn)生足夠長但不完全隨機(jī)的密鑰？下面我們來學(xué)習(xí)偽隨機(jī)性概念。
    • 真隨機(jī)性不能由一個可描述的機(jī)制產(chǎn)生。這里的“可描述的機(jī)制”顯然是不包括“擲骰子”，而是指確定性的機(jī)制；
    • 偽隨機(jī)對于不知道其機(jī)制的觀察者來說，看起來是真的隨機(jī)；
    • 一個固定的字符串談不上是否隨機(jī)/偽隨機(jī)，隨機(jī)/偽隨機(jī)指的是產(chǎn)生字符串的過程；
    • 問題：能否絕對地證明隨機(jī)性？不能，因?yàn)槲覀兛赡苁遣恢榔錂C(jī)制的觀察者。

16. 區(qū)分器（Distinguisher）：統(tǒng)計(jì)測試

    • 一類判斷是否隨機(jī)的務(wù)實(shí)的方法是，從一個隨機(jī)生成器中得到多個隨機(jī)序列并進(jìn)行一套統(tǒng)計(jì)測試。
    • 例如，序列中0和1的數(shù)量之差不應(yīng)該太大，最大連續(xù)0的長度不應(yīng)該太長等等。
    • 偽隨機(jī)性意味著下一比特不可預(yù)測（next-bit unpredictable），通過所有下一比特測試等且僅當(dāng)通過所有統(tǒng)計(jì)測試。（這是姚期智的貢獻(xiàn)）
    • 問題是難以確定多少測試才足夠？

17. 定義偽隨機(jī)性的直覺

    • 直覺：從一個短的真隨機(jī)種子生成一個長的隨機(jī)串，這個偽隨機(jī)串與真隨機(jī)串是不可區(qū)分的。
    • 這是不是和圖靈測試類似？
    • 區(qū)分器輸入一個比特串，輸出1位比特。注意：該比特不一定表示輸入的串是否是隨機(jī)的。

偽隨機(jī)生成器（PRG）

18. 偽隨機(jī)生成器 （Pseudorandom Generator） 定義

    • 一個確定性的多項(xiàng)式時間算法 G : { 0 , 1 } n → { 0 , 1 } ? ( n ) G : \{0,1\}^n \to \{0,1\}^{\ell(n)} G:{0,1}n→{0,1}?(n)是一個偽隨機(jī)生成器（PRG），如果：
      • 延展：$?n,?(n)>n$。只有生成更長的串才有意義，否則可以直接從種子中復(fù)制一段輸出；
      • 偽隨機(jī)：對于任意PPT區(qū)分器$D$，$\left|\mathrm{Pr}[D(r)=1]?\mathrm{Pr}[D(G(s))=1]\right|\le \mathsf{negl}(n)$。其中，$r$是隨機(jī)的，種子$s$隨機(jī)的，$?(?)$是延展因子。這里的意思是輸出不同結(jié)果的概率差可以忽略，如果有一個區(qū)分器始終輸出1，則兩個概率都是1，差為0；另外，輸出1并不需要表示特定含義，改成輸出0也可以。
    • 存在性：若單向函數(shù)存在或$\mathcal{P}\ne \mathcal{NP}$，則PRG存在。后面我們會進(jìn)一步學(xué)習(xí)。

19. 真實(shí)案例

    • C語言的random()
    • Netscape早期版本的漏洞https://people.eecs.berkeley.edu/~daw/papers/ddj-netscape.html

• 從這兩個例子可以看出來，輸出都是可預(yù)測的。

20. 關(guān)于PRG的一些問題

    • 利用下一比特不可預(yù)測，還有PRG的不可區(qū)分實(shí)驗(yàn)定義可以解決這些問題。

21. 充分種子空間

    • 稀疏輸出：當(dāng)擴(kuò)展因子為$2n$時，在長度為$2n$的串中只會產(chǎn)生$2^{?n}$。
    • 蠻力攻擊：給定無窮的時間，通過枚舉所有種子來產(chǎn)生所有串，能以較高的概率區(qū)分出偽隨機(jī)串。
    • 充分種子空間：種子必須長來抵抗蠻力攻擊。

22. 不充分的隨機(jī)性

    • 2008年，為了避免一個編譯警告，Debian的一個發(fā)布版本中誤刪了一行代碼，引起OpenSSL中關(guān)于隨機(jī)生成器的漏洞。

規(guī)約法

23. 規(guī)約法（Reduction）

    • 規(guī)約法是將一個問題A變換為另一個問題B。變換的意思可以理解為，A可以通過解決B來解決。
    • 規(guī)約$A{\le }_{m}B$：$A$可規(guī)約為B，如果B的解存在并且給定該解時A可解，其中$m$表示映射規(guī)約；這里可以將規(guī)約理解為A對B的子函數(shù)調(diào)用，除了子函數(shù)B是一個黑盒，解決A的步驟都應(yīng)該是明確的。
    • 解決A不能比解決B更難，因?yàn)锳可以通過解決B來得到解決。
    • 例題，測量矩形面積可規(guī)約到測量矩形邊長；計(jì)算一個數(shù)的平方可規(guī)約到兩個數(shù)乘積，相反可以規(guī)約嗎？

規(guī)約證明

24. 規(guī)約證明

    • 我們現(xiàn)在站在敵手的角色來思考，希望解決“破解”加密方案這個問題，并且在此之前我們已經(jīng)知道有個一“假設(shè)”問題是不可解決的；
    • 為了證明一個加密方案$\Pi$在假設(shè)$X$下是安全的，就是證明“破解”問題不可解。
    • 將解決“假設(shè)”$X$問題的算法${\mathcal{A}}^{\prime }$規(guī)約到“破解”$\Pi$的算法$\mathcal{A}$。如果加密方案可以被破解，則假設(shè)問題也可以解決。然而，由于假設(shè)問題是難以解決的，這導(dǎo)致矛盾，說明加密方案不可以被破解。
    • 先令一個概率多項(xiàng)式時間的算法$\mathcal{A}$能夠以概率$\epsilon (n)$破解$\Pi$ ；
    • 假設(shè)：一個問題$X$是難以解決的，即不存在多項(xiàng)式時間算法來解決$X$；${\mathcal{A}}^{\prime }$是一個解決$X$的概率算法；
    • 規(guī)約：解決假設(shè)問題$X$可以通過破解加密方案$\Pi$，即將${\mathcal{A}}^{\prime }$規(guī)約到$\mathcal{A}$，${\mathcal{A}}^{\prime }$通過以$\mathcal{A}$作為子函數(shù)可以以概率$1/p(n)$有效地解決問題$X$；
    • 矛盾：若加密方案可以被有效破解，即$\epsilon (n)$是不可忽略的，則${\mathcal{A}}^{\prime }$可以以不可忽略的概率$\epsilon (n)/p(n)$解決問題$X$，這與假設(shè)矛盾，因而$\epsilon (n)$一定是可忽略的。

25. 一個規(guī)約法證明PRG的例子

    • 假設(shè)$F$是PRG，證明$G$也是PRG。
    • 問題A：如何區(qū)分$F$；問題B：如何區(qū)分$G$；
    • 從A規(guī)約到B：區(qū)分$F$的算法輸入按位取反后作為區(qū)分$G$的算法輸入，區(qū)分$G$的算法輸出作為區(qū)分$F$的算法輸出。

26. 一個規(guī)約法證明PRG的例子（續(xù)）

    • 由此，建立了不可區(qū)分定義中概率的聯(lián)系。

構(gòu)造安全的加密方案

27. 一個安全的定長加密方案

    • $|G(k)|=?(|k|)$, m ∈ { 0 , 1 } ? ( n ) m \in \{0,1\}^{\ell(n)} m∈{0,1}?(n)， 一個PRG以長度為$n$的密鑰作為種子，輸出與明文相同長度的pad；
    • $\mathsf{Gen}$: k ∈ { 0 , 1 } n k \in \{0,1\}^n k∈{0,1}n，密鑰作為種子，長度小于明文長度；
    • $\mathsf{Enc}$: $c:=G(k)\oplus m$，加密方法和一次一密一樣；
    • $\mathsf{Dec}$: $m:=G(k)\oplus c$，解密也是；
    • 定理：該定長加密方案是竊聽下不可區(qū)分的。
    • 直覺上，這個方案和一次一密是類似的，除了密鑰更短并且用偽隨機(jī)生成器生成的比特串來與明文異或。因?yàn)閭坞S機(jī)對于任何敵手都可以認(rèn)為是真隨機(jī)，所以對于敵手而言，該方案與一次一密是一樣的。由此，我們得到了一個安全的加密方案，同時避免了一次一密的最大局限性——密鑰過長。

28. 證明不可區(qū)分加密方案

    • 思路：區(qū)分偽隨機(jī)性為難題假設(shè)，破解加密方案為規(guī)約的子函數(shù)。針對偽隨機(jī)生成器$G$的區(qū)分器$D$以$\mathcal{A}$為子函數(shù)，使得當(dāng)$\mathcal{A}$破解了$\Pi$則$D$可以區(qū)分出$G$，與$G$的偽隨機(jī)性矛盾。注意這里我們用了符號$\tilde{\Pi }$來表示$\Pi$的一個變體，來刻畫加密方案中可能使用了真隨機(jī)串來加密；
    • 回顧針對偽隨機(jī)生成器的區(qū)分器$D$的問題是，輸入一個串$w$，輸出一個比特；這里關(guān)鍵問題是輸出的比特從何而來？
    • 將$D$規(guī)約到$\mathcal{A}$。回顧竊聽者不可區(qū)分實(shí)驗(yàn)中，$\mathcal{A}$與一個挑戰(zhàn)者進(jìn)行3輪交互：
      1. $\mathcal{A}$選擇兩個不同明文$m_0,m_1$，并發(fā)送給挑戰(zhàn)者；
      2. 挑戰(zhàn)者生成密鑰，并隨機(jī)挑選一個明文$m_b$加密后得到挑戰(zhàn)密文$c$，并發(fā)送給$\mathcal{A}$；
      3. $\mathcal{A}$輸出對所加密明文的猜測$b^{\prime }$，若$b=b^{\prime }$，則$\mathcal{A}$成功；否則，失??；
    • 區(qū)分器$D$成為竊聽不可區(qū)分實(shí)驗(yàn)中的挑戰(zhàn)者，特別之處在于：在第2步，不需要生成密鑰，而是直接以輸入串$w$作為pad來加密，$c:=w\oplus m_b$；根據(jù)$w$的兩種可能，分兩種情況：
      • 當(dāng)$w$是由$G$生成的，即偽隨機(jī)串，則$c$就是加密方案$\Pi$中密文，$\mathcal{A}$面對的就是$\Pi$；
      • 當(dāng)$w$是真隨機(jī)串，則$c$不同于加密方案$\Pi$中密文，而與一次一密中一樣，$\mathcal{A}$面對的就是$\tilde{\Pi }$一次一密；
    • 回答前面關(guān)于$D$輸出什么的問題：破解加密方案的$\mathcal{A}$成功時，$D$輸出1；否則，$D$輸出0。

29. 證明不可區(qū)分加密方案（續(xù)）

    • 規(guī)約完畢，證明$\mathcal{A}$在實(shí)驗(yàn)中成功的概率是可忽略的
      • 當(dāng)$w$為真隨機(jī)串$r$，就是一次一密，$\mathrm{Pr}[D(r)=1]=\mathrm{Pr}[{\mathsf{PrivK}}_{\mathcal{A},\tilde{\Pi }}^{\mathsf{eav}}(n)=1]=\frac{1}{2}$；
      • 當(dāng)$w$為偽隨機(jī)串$G(k)$，$\mathrm{Pr}[D(G(k))=1]=\mathrm{Pr}[{\mathsf{PrivK}}_{\mathcal{A},\Pi }^{\mathsf{eav}}(n)=1]=\frac{1}{2}+\epsilon (n)$；
      • 根據(jù)偽隨機(jī)生成器定義，上下兩個公式相減，$\left|\mathrm{Pr}[D(r)=1]?\mathrm{Pr}[D(G(k))=1]\right|=\epsilon (n)\le \mathsf{negl}(n)$；
      • 所以$\epsilon (n)$是可忽略的，即$\Pi$是竊聽者不可區(qū)分的。
    • 小結(jié)：通過規(guī)約將$\mathcal{A}$的不可區(qū)分實(shí)驗(yàn)成功的概率與$D$的區(qū)分器實(shí)驗(yàn)輸出1的概率建立等式；分析輸入真隨機(jī)串時$D$輸出1的概率（即不可區(qū)分實(shí)驗(yàn)成功概率）是1/2；根據(jù)PRG的定義，輸入偽隨機(jī)串時$D$輸出1的概率（1/2+$\epsilon (n)$）與輸入真隨機(jī)串時$D$輸出1的概率（1/2）的差異時可忽略的。

30. 處理變長消息

    • 對于一個變長輸出的偽隨機(jī)生成器，前面的加密方案和安全性都成立；這是作業(yè)，其中一個關(guān)鍵是條件2，短串是長串的前綴。

31. 計(jì)算安全與信息安全文章來源地址http://www.zghlxwxcb.cn/news/detail-808332.html

    • 敵手：PPT竊聽者，無限算力竊聽者；
    • 定義：不可區(qū)分性$\frac{1}{2}+\mathsf{negl}$，不可區(qū)分性 $\frac{1}{2}$；
    • 假設(shè)：偽隨機(jī)，隨機(jī)；
    • 密鑰：短隨機(jī)串，長隨機(jī)串；
    • 構(gòu)造：異或pad，異或pad；
    • 證明：規(guī)約法，概率論；

到了這里，關(guān)于【現(xiàn)代密碼學(xué)】筆記3.1-3.3 --規(guī)約證明、偽隨機(jī)性《introduction to modern cryphtography》的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！