密碼學筆記 \huge{密碼學筆記} 密碼學筆記
斯坦福大學密碼學的課程筆記
課程網址：https://www.bilibili.com/video/BV1Rf421o79E/?spm_id_from=333.337.search-card.all.click&vd_source=5cc05a038b81f6faca188e7cf00484f6
概述
密碼學的使用背景
安全信息保護：網絡流量、無線網絡流量
保護加密軟件或者光盤：EFS…
內容保護：CSS（DVD）AACS（藍光）事實證明CSS是比較容易被破解的。
用戶認證等…
主機段與服務器段之間的傳輸協議保證了信息傳輸過程中不會被攻擊者竊聽或者篡改。
TLS協議簡述
①. 傳輸雙端的握手協議：雙端握手之后，雙端會獲得一個只有雙端知道的密鑰，其他用戶無法知道密鑰的內容。
②. 信息記錄方面：雙端使用共享密鑰對于傳遞的信息進行加密傳輸。
磁盤中的信息保護機制保證磁盤中的信息不會被篡改。對于磁盤來講從Alice到Alice，不同的是訪問磁盤信息的時間，這是磁盤在存儲方面的問題。但是從Alice到Bob則是磁盤在信息傳遞方面的問題，這是兩個不同層面的問題。
對稱加密簡圖：
Alice和Bob進行信息交互的時候，Alice使用E（加密算法）對于傳遞信息進行加密形成密文，Bob接收到密文使用D（解密算法）來得到傳遞的信息。
???對于對稱加密整個過程，E.D等其他環節都是完全公開的，只有雙方要傳遞的信息k是不公開的。而且從安全性的角度來講選擇的各種加密算法一定是社會公認的，接受了大量測試認證的加密解密算法，防止使用小眾的加密算法被人簡單的逆向破解。
一次性密鑰：一個密鑰只能加密一條信息。
多次性密鑰：一個密鑰可以加密多條信息。
簡介
密碼學的核心是兩個方面
①. 信息傳送雙方的密鑰建立
②. 雙方利用密鑰進行安全的信息交流
攻擊者不能從截獲的密文中解密出有效的消息，但是通信的雙方能夠通過加解密算法破解出完整且有效的消息（完整性和加密性）。
數字簽名 Digital signatures
數字簽名的本質是一種對應于物理對應物的數字對應物（有點繞）。現實世界中的文件簽署都需要使用相同的簽名作為認證，但是信息世界中的數字化使得簽名可以被很簡單的復制，所以數字簽名需要保持變化，來防止攻擊者竊取數字簽名。通過將數字簽名與相應文件的內容做對應，保證了雙方的一致性，即使數字簽名被竊取，那么在新的文件中，數字簽名也是無效的。
匿名交流 anonymous communicattion
mix net：混合網絡，如果Alice想要匿名聯系Bob，標準的解決方法是使用混合網絡。Alice發送的信息通過中間多個代理服務器，最后傳遞到Bob，但是Bob無從得知是誰發送的消息。這個網絡具有雙向性，Bob匿名向Alice交流時同理。
匿名數字現金 Anonymous digital cash
現實世界中，用戶購買物品時，商家會聚焦于交易，并非用戶的身份，但是如何在網絡中實現匿名的支付？還有就是數字貨幣本身的可復制性，如何防止惡意用戶的雙花攻擊？
同時解決這兩個問題的方法：
用戶使用數字貨幣進行交易第一次保持匿名，一旦用戶自己違規復制貨幣第二次交易的時候就會立即暴露。
協議 Protocols
問題
選舉問題：用戶可以自由投票來選舉支持的政黨，但是希望統計票數的時候能夠不記錄個人的信息。
選舉中心：用戶將加密后的投票結果發送給選舉中心，中心統計后發送出獲勝者的信息，但是對于各個用戶的個人信息，用戶的投票結果一概不知。（六方選舉系統）
拍賣問題：此處以victory auction標準拍賣流程舉例（最高價者獲得物品，但是實際支付的價格是第二高價）解決方法同選舉問題，只不過拍賣中心需要放出勝者和第二高的價格。
Secure multi-play computation（多方安全計算）：多方參與者各自持有秘密輸入，使用函數進行計算：
G o a l ： c o m p u t e f ( x 1 , x 2 , x 3 , . . ) Goal：compute \quad f(x_{1},x_{2},x_{3},..) Goal：computef(x1?,x2?,x3?,..)
但是公布函數的結果的時候，不能泄露個體的投票信息。
解決方式
引入可信第三方
引入一個可信的第三方來進行計票，但是必須確保絕對可信（非常不安全）。
定理
可以消除對于第三方計票的依賴，用戶無需發送信息給第三方，只需要用戶間使用特殊協議進行通信，通信完成后函數結構就會立刻返回給所有的用戶，也不會泄露用戶個人信息。
crypto magic
Privately outsourcing computation
?對于復雜的計算還只停留在理論階段，但是簡單計算已經能夠使用了！（可行性?）
Alice向Google發送加密的信息，Google在密文基礎上進行運算，將結果發送給Alice，然后Alice進行解密，獲得計算后的results。
特點：Google進行了計算，但是不知道加密前的信息是什么。
Zero knowledge (proof of knowledge)
舉例：N是由p與q兩個質數相乘的結果，Alice手頭有這個公式 N = p × q N=p×q N=p×q，Bob手上有N，**Bob本身連因數分解的概念都不知道。**但是Alice有方法可以在Bob什么都不知道的條件下向Bob證明N可以被因數分解，同時Bob也不知道N可以被分成p與q兩個數的乘積。
密碼學的歷史
Symmetric Ciphers
流程：m是要加密的信息，k是加密的密鑰， c = E ( k , m ) c = E(k,m) c=E(k,m)這是加密后的密文c，傳輸到Bob之后，Bob用k與解密算法D來進行解密，獲得原文m。
對稱加密說的是雙方使用的k是相同的。
Few Historic Examples
Substitution cipher
替換密碼是使用特定的字母映射來對原有的密文進行替換。
并且使用的密文k是一種對稱加密，k是不變的（k是對照表）。
Caesar Cipher
凱撒密碼是一種特殊的替換密碼，但是其實嚴格來講他不是一種替換密碼，因為它的加密方式是將每個字母替換為向右平移三個單位的結果：
它沒有密鑰。所謂的替換表是硬表，是固定的，而非隨機生成的替換表，非常容易被破解。
描述26個字母替換表的密文需要多少空間？
替換映射本質是26個字母的排列組合，即26！
如何破解替換加密？
①. 統計英文字母中每個字母出現的頻率。然后統計密文中字母出現的頻率，進行對應。一般適用于前幾個密文中字母的破解，因為有些字母出現的頻率是基本一致的。
②. 統計英文單詞中出現的字母組和頻率，來定位密文中更多字母的替換情況。
以上破解方式稱為 C T o n l y a t t a c k \red{CT \quad only \quad attack} CTonlyattack（唯密文破解）
只是單純的截獲了密文，就能夠對于密文進行破解。
vigener chipher
維吉尼亞加密（相加取模26加密）
對于給定的密鑰k，進行若干重復排列，直到長度與明文m對齊，然后對應位置相加然后取模26，將結果作為加密后的對應位置結果。接收方接收到了加密之后減去k的序列即可得到原文。
如何進行破解？
?假設知道密鑰k的長度（很重要）
破解流程：對于給定的密文c按照k的長度進行分組。對于每組中第一個字母而言，統計最常出現的字母，這個字母很可能就是E加密后得到的字母，反推就可以推出k中對應位置的字母。例如圖中的H在c的每組中第一個字母出現的最多，那么H就有可能是E加密得到的，H-E = C，即k密鑰中第一個字母為C，后續的位置以此類推。這樣就能確定k的詳細內容，從而用c-k來得到加密前信息m（也是唯密文破解）。
特別地，如果連密鑰k長度都不知道，那么必須枚舉長度試探了。
Rotor Machines
單轉子機
key承載在一個物理的圓盤，加密前信息輸入到key中，key對應給出一個加密后的信息（本質是一個替換表），但是里面的替換表會轉動，例如輸入三次C，輸出的分別是T，S，K。這個機器形成的密文也可通過分析字母出現頻率進行破解。
改進后的機器：
多個圓盤并且轉速不同，進行強加密。
離散概率速成
描述一個系統的安全性使用的是語言是離散概率。
簡單的定義：
U：完全空間，包括了所有的元素。
U = ( 0 , 1 ) n U=({0,1})^{n} U=(0,1)n：表示n個比特位的二進制序列。
P：對于U完全空間的中的所有元素都給予一個權重（0<=P<=1），并且所有的元素對應的權重相加的結果是1.
Uniform distrustion
均勻分布，空間中所有元素的概率相等。
Point distraction
點分布，只對于空間中一個元素進行概率賦值（1），對于其他元素的概率均為0。
分布向量：將每個元素的概率構成一個集合，成為分布向量。
Events
事件定義：事件屬于U的子集，事件的概率是時間包含的所有獨立元素的概率和。
The union bound
事件概率相加時的聯合邊界問題（通俗點就是概率加重了）
Random Variables
隨機變量X本質是一個函數的取值。將U空間中的元素按照X的規則映射到V中的元素對應的取值。
X：將n位的二進制字符串，映射到{0,1}集合中，映射規則為，取二進制字符串最低位作為X的取值。
Randomized algorithms
確定算法：給定的輸入數據不變，算法運行的結果必然一致。
隨機算法：即使給定的輸入數據不變，但是算法的運行結果可能會發生改變。
隨機算法中伴隨著輸入信息還會有一個隱式的輸入r，這個r會根據算法自身進行動態調整。使得對于相同的輸入，輸出的結果是一個取值范圍。
Independence
AB兩個時間發生的概率互不影響。
P r [ A a n d B ] = P r [ A ] × P r [ B ] Pr[AandB]=Pr[A]×Pr[B] Pr[AandB]=Pr[A]×Pr[B]
XOR（異或）
An important property of XOR
**內容：**對于一個 ( 0 , 1 ) n (0,1)^{n} (0,1)n空間上的隨機變量（無論遵從什么分布），一個 ( 0 , 1 ) n (0,1)^{n} (0,1)n空間上的隨機變量X（與Y相互獨立并且遵從均勻分布），假設 Z = Y ⊕ X Z=Y⊕X Z=Y⊕X，那么Z將服從均勻分布。
證明如上圖，本質就是將Y的兩個事件取值假設出來，計算就可以了。
?特別提醒：這個定理證明了，即使一個變量本身是惡意分布，那么與一個均勻分布異或之后，得到的變量分布也是均勻的（安全性體現）。
The birthday paradox（生日悖論）
**內容：**對于n個獨立同分布的隨機變量（服從什么分布不重要），如果取樣的數據數量>=樣本空間中總數量的平方根，那么很有可能會取到兩個相同的數據。
**生日悖論：**請問最少需要多少個人就有可能實現有兩個人的生日相同？
此處的 1.2 1.2 1.2是經驗修正系數，讓結果更加準確。最后答案大約是24人。也就是說找到24個人就有可能實現有兩個人的生日是同一天。被稱為悖論的原因是24遠遠小于365天，比較反直覺。
樣本空間元素數量為 1 0 6 10^{6} 106，取樣元素相同的概率曲線圖。1200次時概率就已經到了50%，符合預期。
信息安全論與一次性密碼本
密碼的定義：密碼定義在三元組（K，M，C）之上
K：用于加密的密鑰
M：原信息
C：加密后的密文
密碼本身是一對“高效”的加密解密算法。
E：加密算法
D：解密算法
加密解密的過程： K × M → C K×M→C K×M→C， K × C → M K×C→M K×C→M
一致性方程：
? m ∈ M , k ∈ G : k ? D ( k , E ( k , m ) ) = m \forall m \in M, k \in G: k \cdot D(k, E(k, m)) = m ?m∈M,k∈G:k?D(k,E(k,m))=m
?所有的密碼都必須保證一致性。
E是一個隨機算法，意味著每次生成用于加密的比特位是隨機的。D是解密算法，D是確定算法，給定特定的密文與解密算法，解密出的答案必然是一致的。
The One Time Pad（Vernam 1917）
一次性密碼本，一種“安全”的密碼。
特征：信息與密文都是n位二進制序列串( ( 0 , 1 ) n (0,1)^{n} (0,1)n)，密鑰K的長度與信息長度相同。
一次性密碼本的加密原理就是將原信息與K逐位異或獲得密文C。解密的時候C與K逐位異或，獲得原文M。
如果只是知道原文M與密文C，能不能得到加密密鑰K？
可以并且非常簡單： K = M ⊕ C K = M⊕C K=M⊕C
一次性密碼本加密很適合加密長度很長的信息，因為異或計算的快速性，所以一次性密碼本加密又叫做超高速加密算法。但是這個方法只是理論上比較好用，實際上用處不大。
因為一次性密碼本加密的時候需要傳輸一個與密文登場的密鑰K，但是如果都有能力傳輸K了，還不如直接傳輸M，有點多此一舉。
Information Theoretic Security（Shannon 1949）
完美保密性的定義
什么是好的密碼？如何定義一個密碼的安全性？如何確定一個密碼的好壞？
基礎思想：
一個好的密碼應當是以下這種情況：單單接收到了密文之后，不能獲得關于原文的任何信息。
定義（香農）：
? m 0 , m 1 ∈ M ， ( ln ? ( m 0 ) = ln ? ( m 1 ) ) ∧ ? c ∈ C \forall m_{0}, m_{1} \in M，( \ln ( m _ { 0 } ) = \ln ( m _ { 1 } ) ) \land \forall c \in \mathbb{C} ?m0?,m1?∈M，(ln(m0?)=ln(m1?))∧?c∈C
在密文中間M中， m 0 m_{0} m0?與 m 1 m_{1} m1?等長，且生成的密文c屬于密文空間 C \mathbb{C} C。
P r [ E ( k , m 0 ) = c ] = P r [ E ( k , m 1 ) = c ] \mathrm{Pr}[E(k, m_0) = c] = \mathrm{Pr}[E(k, m_1) = c] Pr[E(k,m0?)=c]=Pr[E(k,m1?)=c]
m 0 m_{0} m0?與 m 1 m_{1} m1?都使用k加密后結果為c的概率相同，即密文空間是均勻的。
where? k is?uniform?in? K ( k ← R K ) \text{where } k \text{ is uniform in } \mathbb{K} (\ k\xleftarrow[]{R}K) where?k?is?uniform?in?K(?kR?K)
?安全性保證：
attacker截獲了一段密文之后，他無法具體判斷密文是來自哪個明文的加密結果，因為所有明文加密成這個密文的概率是相同的。
密文不會提供任何關于明文的信息。
無論攻擊者多么高明都無法從密文中獲取信息。
?不存在唯密文攻擊。
一次性密碼本加密方法的完美保密性證明
Bad News
香農證明了一次性密碼本加密具有完美密碼性之后，也證明了如果一個加密算法具有完美密碼性，那么它的密鑰k長度 >= 明文m 長度。
一次性密碼本加密中 密鑰k長度 = 明文m長度，這個算法是取等號條件下最優的加密算法。
Stream ciphers
前情回顧：
流密碼思想：不使用完全隨機的密鑰，而是使用偽隨機的密鑰進行加密。
假定有一個偽隨機數生成器，將原始的短密鑰k使用偽隨機數生成器擴充與m等長，然后進行與之前一次性密碼本加密相同的操作去加密解密即可。
這種加密方法不安全，密鑰長度遠遠小于原文長度。
PRG must be unpredictable
PRG的不可預測性是非常重要的。
如何認為一段擴充后的密文是不安全的？如果通過密文的一部分可以推理出剩余部分的信息，就說明這個擴充的密文是不安全的。
predictable
存在一種高效的算法并且存在一個位置 1 < = i < = n ? 1 1<=i<=n-1 1<=i<=n?1
P r [ A ( G ( k ) ) ∣ 1 , . . . , i = G ( k ) ∣ i + 1 ] ≥ 1 2 + ε ( n o n ? n e g l ) Pr \left[ A(G(k))\vert_{1,...,i} = G(k)\vert_{i+1} \right] \geq \frac{1}{2} + \varepsilon(non-negl) Pr[A(G(k))∣1,...,i?=G(k)∣i+1?]≥21?+ε(non?negl)
上式說明的是，從擴充的密文中存在一個位置i，對于i之后的位置預測的概率 >= 1 2 + ε \frac{1}{2} + \varepsilon 21?+ε，并且 ε \varepsilon ε無法忽略，就說明這個PRG是可以預測的。
unpredictable
**不可預測性：**對于所有的位置i，都無法根據i處的信息去預測i+1位置的信息，就說明具有不可預測性。
Weak PRGs （do not use for crypto）
絕對不應該被使用的PRG（可預測性太高）
線性同余生成器：
r[i] ← (a·r[i-1] + b) mod p # 線性同余遞推公式
output Few bits of r[i] # 輸出部分低位比特
i++ # 計數器自增
很容易就會被預測。
negligible and non-negligible
流密碼與一次性密碼本加密的攻擊方法
Attack 1：two time pad is insecure
一次性密碼本加密之所以叫做一次性，就是因為加密的時候只能是一個密碼本加密一條信息。如果使用同一個密碼本加密了多條信息，那么整個加密的安全性就會蕩然無存。
上述加密后的密文 C 1 C_{1} C1?與 C 2 C_{2} C2?，兩者異或的結果等于 m 1 m_{1} m1?與 m 2 m_{2} m2?異或。但是英文有著足夠的冗余性，并且英文在系統是以ASCII碼的形式記錄的，所以知道了 m 1 ⊕ m 2 m_{1}⊕m_{2} m1?⊕m2?的結果，就能分別還原出 m 1 m_{1} m1?與 m 2 m_{2} m2?，非常不安全。
Real world examples
Project Venona
蘇聯使用一次性密碼本用來加密，但是蘇聯制作密碼本的時候使用的是人工扔骰子的方法，非常費時，所以為了節約時間就用同一個密碼本加密了多條信息，之后就被美軍截獲，然后輕易破解。
MS—PPTP（windows NT）
客戶端與服務端交互的時候，是客戶端發送信息，服務端相應，循環往復。但是PPTP傳輸協議，將雙方交流方式看作一個流，輸入方輸入的時候將所有的m組成一個流，然后進行加密，到了輸出端將密文進行解密，其實就是使用了同一個密鑰加密了多條信息。所以正確的做法應當是有一對密鑰，K1作為用戶端到服務器端的加密密鑰，K2作為服務器端到用戶端的密鑰。
802.11b WEP
通俗來講就是Wifi數據傳輸的時候，加密的時候生成的拓展密鑰是幀變化的（每幀生成的密鑰都改變），但是生成的拓展密鑰是偽隨機的，也就是說一段時間之后加密的密鑰又與之前使用的某個密鑰相同了（循環），于是發生了使用一次性密碼加密多條信息的不安全情況。
A better construction
解決方式的本質就是讓隨機生成的密鑰k不再發生重復。
Yet another example：disk encryption
本質是磁盤不適合使用一次性密碼本進行加密。
**磁盤加密中的安全漏洞：**對于一份協議Bob簽署之后，生成對應的加密信息。Eve同樣簽署之后，生成的密文與Bob生成的密文來講除了表示名字的密文修改了，其他位置的密文都沒有改變。所以攻擊者雖然無法獲得原文信息，但是可以輕而易舉的定位到原文信息改變的位置。最理想的情況應當是只要有一部分更改，生成的密文就要完全進行更改。
Attack 2：no integrity
完整性攻擊：完整性差的密文是可以被修改的。
m m m與 k k k異或加密之后，使用一個擾動值 p p p與 m k mk mk異或的結果作異或運算，之后使用 k k k解密，解密出的結果就是 m ⊕ p m⊕p m⊕p，對于密文進行操作，會精準地影響到解密后原文的內容。
這種攻擊主要是用于密文偽造。
?一次性密碼本加密沒有完備性。
現實中的流密碼算法
RC4（sofeware）
缺點
①. 加密輸出偏差，RC4加密的前256個字節的加密都會有偏差，所以建議257在使用。
②. ( 0 , 0 ) (0,0) (0,0)序列出現的概率偏高
③. 可以使用上節的關聯密鑰攻擊。
CSS（hardware）
設計出能夠在硬件層面實現的加密方法。
CSS基于線性反饋移位寄存器(LFSR)機制。
LFSR
linear feedback shift register（LFSR）
對于一個寄存器，選取特定的位置作為抽頭，將幾個抽頭處的結果進行異或，保存異或值，然后寄存器向右位移，最右側的數據丟棄，剛才的異或值補充在最左側。
DVD、藍牙中的CSS都已經能夠被破解了。
eStream
對于之前的PRG額外增加一個臨時值一起計算得到新的隨機數。這個臨時值從不重，那么每次PRG生成的隨機數就不會重復，自然加密結果是從不重復的。
Salsa 20（software and hardware）
Salsa非常安全，并且具有不可預測性。
各種流密碼的速率
PRG的安全性定義
PRG的安全性
[ k ← R K , output? G ( k ) ] [k \stackrel{R}{\leftarrow} \mathcal{K}, \text{output } G(k)] [k←RK,output?G(k)]：從整個空間 K \mathcal{K} K中隨機取出 k k k，然后輸入 G ( k ) G(k) G(k)。
[ r ← R { 0 , 1 } n , output? r ] [ r \stackrel{R}{\leftarrow} \{0,1\}^n, \text{ output } r ] [r←R{0,1}n,?output?r]：從整個 { 0 , 1 } n \{0,1\}^n {0,1}n空間中隨機取出的二進制序列 r r r，然后輸出 r r r。
盡管 K \mathcal{K} K與 { 0 , 1 } n \{0,1\}^n {0,1}n表示的密鑰空間不同，但是生成了結果之后，應當不能區分出這種不同（不可區分性）。
Statistical Tests
統計測試實例：測試空間中的字符串是否是隨機的。
對于字符串 A A A，測試 A ( x ) A(x) A(x)，如果字符串是隨機的輸出1，否則輸出0。
A ( x ) = 1 A(x) = 1 A(x)=1：
①. ∣ # 0 ( x ) ? # 1 ( x ) ∣ ≤ 10 ? n \left| \#0(x) - \#1(x) \right| \leq 10 \cdot \sqrt{n} ∣#0(x)?#1(x)∣≤10?n?
如果x中0出現的次數與1出現的次數基本相同（差值很小），就說明這個字符串是隨機的。
②. ∣ # 00 ( x ) ? n 4 ∣ ≤ 10 n \left| \#00(x) - \frac{n}{4} \right| \leq 10 \sqrt n ?#00(x)?4n? ?≤10n?
如果x中00出現的概率與 n 4 \frac{n}{4} 4n?相差不大，就說這個字符串是隨機的。
③. max ? -run-of- o ( x ) ≤ 10 ? log ? 2 ( n ) \max\text{-run-of-}o(x) \leq 10 \cdot \log_2(n) max-run-of-o(x)≤10?log2?(n)
對于一個隨機的字符串中，最長連續0序列的長度大約是 10 ? log ? 2 ( n ) 10 \cdot \log_2(n) 10?log2?(n)，如果當前的字符串的最長連續0序列小于等于這個值就說明是隨機字符串。
Advantage
PRG的優勢：對于一個PRG使用一個數據測試A來對其進行優勢測試。
所謂的優勢測試其實就是：對于這個偽隨機生成器，能否與真正隨機相區分。
A d v P R G [ A , G ] ： ∣ P r [ A ( G ( k ) ) = 1 ] ? P r [ A ( r ) = 1 ] ∣ ∈ [ 0 , 1 ] Adv_{PRG}[A,G]：|P_{r}\left[A(G(k)) = 1\right] - P_{r}\left[A(r) = 1\right]|\in [0,1] AdvPRG?[A,G]：∣Pr?[A(G(k))=1]?Pr?[A(r)=1]∣∈[0,1]
如果Adv的值等于1，說明此PRG偽隨機與真隨機相差太大了。
Adv的值等于0則說明A無法區分PRG偽隨機與真隨機（擬合性更高）。
Secure PRGs：crypto definition
PRG安全性定義：對于所有高效的統計測試A， A d v P R G [ A , G ] Adv_{PRG}[A,G] AdvPRG?[A,G]此優勢值是可以忽略的，則說明這個PRG是安全的。
Easy fact：a sceure PRG is unpredictable
一個安全的PRG必然是不可預測的。
Thm(Yao’82)：an unpredictable PRG is secure
不可預測的PRG是安全的。
對于一個生成器，如果知道后續幾位能夠計算出前幾位，能夠說明這個PRG是可預測的？
答：可以，已知中可以知道該生成器是不安全的，根據Yao定理的逆否，說明該PRG是可以被預測的。
?表示兩個分布相近
如何表示兩個分布是無法區分的？
對于任意高效的統計測試A，兩個分布中 A ( x ) = 1 A(x)=1 A(x)=1的概率基本相同，說明兩個分布優勢基本相同，則說明兩個分布之間的差異基本可以忽略。
語義安全性定義
接下來的重點是如果能夠使用安全的隨機數生成器，那么就能夠得到安全的流密碼。
What is a secure chipher?
假設攻擊者到目前為止只能夠獲得一個密文。
attempt 1：攻擊者不能夠還原加密的密鑰
attempt 2：攻擊者不關心密鑰，更關心的是密文，攻擊者需要還原密文。
回顧香農的完美安全性定義
對于 = 0 =0 =0弱化為 ≈ p \approx_{p} ≈p?，即兩者不需要嚴格相等，只需要計算方面無法區分即可，如果攻擊者的計算力較弱，就滿足該安全性定義。
Semantic Security（one-time key）
E X P ( 0 ) EXP(0) EXP(0)：實驗0
E X P ( 1 ) EXP(1) EXP(1)：實驗1
? 優勢值定義 \red{優勢值定義} 優勢值定義：首先挑戰者生成一個加密的密鑰k，然后攻擊者向挑戰者發出兩個明文 m 0 m_{0} m0?和 m 1 m_{1} m1?（長度相等）。挑戰者加密密文之后，向攻擊者發送（ m 0 m_{0} m0?與 m 1 m_{1} m1?分別對應著兩個加密實驗）。 W 0 W_{0} W0?是實驗0中輸出1的事件， W 1 W_{1} W1?是實驗1中輸出1的事件。 優勢值就是0，1兩個實驗中對應W事件發生的概率的差的絕對值。 如果Adv比較小，說明攻擊者收到密文后無法區分是 m 0 m_{0} m0?加密還是 m 1 m_{1} m1?加密，這就是語義安全性比較好。反之Adv比較大說明攻擊者可以區分，語義安全性比較弱。
? 語義安全性定義 \red{語義安全性定義} 語義安全性定義：對于任何高效的攻擊者，上述的優勢值都是可以忽略的。另一種表述是所有暴露出的明文，加密后的密文在計算方面都是相同的。
??完美安全性：給定密文，無法獲取任何關于原文的信息。
