密碼學 | 如何安全量化

安全分兩種：

• ⽆條件安全：⽆法攻破密碼算法。
• 計算安全：攻破密碼算法的機率可忽略。

加密算法包括三個子算法：

1 密鑰⽣成⼦算法(Gen)

算法輸⼊：安全參數n；算法輸出：滿⾜特定分布的密鑰k

2 加密⼦算法(Enc)

算法輸⼊：密鑰k和明⽂m；算法輸出：密⽂c，c ß Enc(k, m)

3 解密⼦算法(Dec)

算法輸⼊：密鑰k和密⽂c；算法輸出：明⽂m，m = Dec(k, c)

滿⾜： Dec(k, Enc(k, m)) = m

唯密文攻擊實驗：

1. 運⾏密鑰⽣成算法Gen，确定密鑰k。
2. 随機加密若⼲明⽂，并将密⽂發送給攻擊者。
3. 攻擊者發送明⽂空間中的兩條消息m0和m1。
4. 随機加密其中⼀條明⽂，并将對應密⽂發送給攻擊者。（詢問且進行欺騙。在美日的例子中對應美國開放一天信道故意讓日本進行檢測：中途島沒淡水補給了）
5. 随機加密若⼲明⽂，并将密⽂發送給攻擊者。（對應美國發現日本艦隊中增加了幾天淡水補給船，則是對第四點的驗證）
6. 攻擊者根據密⽂猜測對應的明⽂是m0還是m1。

若一個算法是計算安全的，雖然我能在第二步和第五步能夠收集到很多密文對，但是我收集到的并不是全集，而是多項式時間内的子集。

即使在理論上證明一個算法是計算安全的，但在實際應用中也不一定是計算安全，因為要考慮到各種機器語言的影響。我們設計一個算法的流程是在理論上線進行安全設計，再在實踐上設計。