對稱加密Symmetric encryption

什么是對稱密鑰加密

在對稱密鑰密碼學中，加密和解密使用相同的密鑰Ks，
Alice和Bob共享一個密鑰Ks，Alice加密明文訊息P以獲得C，并通過一個不安全的通道將它發送給Bob，

• 組成部分：
  - 共享密鑰Ks
  - 加密演算法E(P, Ks)
  - 解密演算法D(C, Ks)使D(C, Ks) = D(E(P, Ks)， Ks) = P
• 兩種操作模式：流密碼、塊密碼，

流密碼 Stream cipher

• 使用與明文x長度相同的密鑰流XOR每次加密一位，
• Keystream是由共享密鑰k使用合適的演算法生成的
• 明文、密文和密鑰流由單個位組成，即xi、yi、si∈{0,1}
  • 加密：E(xi, si) = xi ⊕ si = yi
  • 解密：D(yi, si) = yi ⊕ si = xi

流密碼的兩種模式

1. 同步：s僅取決于共享密鑰k
2. 異步：s取決于共享密鑰k和密文，
   

流密碼加密/解密功能

• 流密碼位元加/解密是mod 2的增加
  • 假設明文、密文、鍵流位為xi，yi，si∈{0,1}
    • 加密:yi = esi(xi)≡xi + si mod 2
    • 解密:xi = dsi(yi)≡yi + si mod 2
  • 對于每個位元的運算，mod 2運算等價于異或運算⊕
    

流密碼-一次一密(OTP, one time pad)

• 在OTP密碼中，密鑰流是完全隨機的，并且只使用一次，
• 如果相同的密鑰流Ks被用于訊息M1和M2
  C1 = M1⊕K1;C2 = M2⊕K1 那么
  CE = C1 ⊕ C2 = (M1 ⊕ K1) ⊕ (M2 ⊕ K1)
  如果M1 = M2, CE = M1⊕M2 = 0
• 如果密鑰流被重復使用，可以用頻率分析來嘗試破解部分訊息，
• OTP是無條件安全的，
• 要求鍵流與訊息一樣長

流密碼的應用

• 實際操作中，Alice和Bob共享一個加密密鑰Ks，
• keystream由Ks生成，
• 流密碼簡單、快速、小：對小設備很有用（如手機GSM A5/1，互聯網的SSL RC4演算法）
• 安全性完全取決于密鑰流keystream：
  • keystream必須是隨機的
  • keystream不能重復——即與明文相同的長度，否則可以使用頻率分析打破

Keystream鍵流

• key的生成方法:
  • CSPRING：加密安全的偽亂數生成器（Cryptographically Secure Pseudo Random Number Generator的縮寫），使用來自Ks的種子，對于CSPRING，在給定初始位的情況下，應當不可能預測密鑰流的剩余位，
  • LFSR：線性反饋移位暫存器，例如GSM的A5/1密碼
  • 三段密碼：使用80位密鑰，三個移位暫存器
  • 在OFB, CTR模式下的分組密碼

LFSR

• 考慮有3個觸發器的LFSR: FF0, FF1, FF2，即度m = 3
• 假設初始狀態:s2 = 1, s1 = 0, s0 = 0
• 輸出:s(i+3)≡s(i+1) + s(i) mod 2
• 定理: m次（m個觸發器）LFSR產生的最大序列長度為2^m?1
  

小結：流密碼

• 流密碼更簡單，需要的資源更少，
• 流密碼需要從共享密鑰派生的長隨機密鑰流（long, random keystream）
• 仔細使用LFSR, CSPRING來獲得具有良好統計特性的keystreams

分組密碼 Block cipher

DES演算法

DES演算法

• 基于NBS(現在的NIST)在1977年向公眾發布的IBM密碼
• 塊大小為64位，
• 密鑰大小為56位，即密鑰空間(keyspace)為256位
• 使用16輪加密：排列，旋轉，用圓形鍵進行替換，
• 圓形密鑰來自共享密鑰，使用一個叫做“鍵計劃（key schedule）”的程序
  
  DES -總體操作

1. 初始排列和最終排列
2. 節日網路-一個可逆的功能
3. f一個不可逆的函式使用一個圓形鍵，替換“s盒”來轉換32位
4. 用于派生16個圓形鍵的鍵時間表
   DES內部：f函式
   
   
   
   e.g. S-box 1 input (100101)2 becomes (1000)2
   
   

DES - s盒和P

• S-boxes會帶來混亂
  • 有8個s -box，這對DES的實力至關重要
  • 將6位輸入轉換為4位輸出
  • 非線性，旨在挫敗高等數學攻擊
• 排列函式，P旨在提供擴散
  

DES的安全性

• 主要缺點-小鍵空間，容易暴力攻擊，
• 如果至少有一對明文和密文，則嘗試所有256個密鑰，使解密后的密文與明文匹配，
• 因此,平均嘗試次數1/2 * 256 = 255
• 斷裂時間: 6.4天使用特殊的開裂設備，如科帕卡巴納 COPACABANA，深裂縫Deep Crack
  多個DES
• 有兩個鍵K1 K2的2-pass- des怎么樣?
• C ’ = E (P, K1),再一次,C = E (C ’ K2) = E (E P, K1, K2)
• 問題:有效密鑰大小是多少?
• 中間相遇攻擊：有效的密鑰大小只有57位!!

三重DES (3 DES)

• 加密EDE: C = E(D(E(x, k1)， k2)， k3)
• 解密DED: D(E(D(x, k3)， k2)， k1) = x
• 3×56 bits keys: k1, k2, k3，即keysize是168位或
• 2×56位鍵k1, k2, k3 = k1，即keysize是112位
  

3DES的力量

• 如果K1 = K2 = K3，則3DES的效果和DES是一樣的
• 當K1 = K2 = K3時，有效的鍵強度是多少呢？

AES操作

• 關鍵添加層
  密鑰調度——從原始的輸入密鑰(128位、192位或256位)派生子密鑰
• 使用s -box進行位元組替換
• 擴散層- shiftRows和MixColumn
• 最后一輪-不混合柱
• 輪數:
  128位鍵- 10輪
  192位鍵- 12發
  256位密鑰- 14發
  

總結：AES

• 軟體和硬體中非常高校
• 商用ASIC或FPGA實作
• 目前沒有已知的分析攻擊
• 廣泛應用于現代系統中：如WPA, IPsec, TLS等，

塊密碼 Black Ciphers modes

塊密碼模式中：

• 明文報文被分成64位或128位的單獨塊
• 每個塊單獨加密
• 幾個模式：
  • 加密明文
    • ECB -電子代碼書
    • CBC—密碼塊鏈接
  • XOR明文
    • CFB -密碼反饋
    • OFB -輸出反饋
    • CTR-計數器

ECB模式

• 加密:yi = ek (xi)， i≥1
• 解密:xi = ek?1(yi)， i≥1
• 相同的明文塊被加密為相同的密文塊
• 加密是確定的
• 攻擊:
  • 流量分析 Traffic analysis
  • 頻率分析 Frequency analysis
  • 替換攻擊 Substitution attack

CBC模式

密碼塊鏈接模式（CBC – Cipher Block Chaining mode）

• 加密
  第一個塊:y1 = ek (x1⊕IV)，隨后的塊:yi = ek (xi⊕yi?1)，i≥2
• 解密是反向程序
  (x1 = ek?1(y1⊕IV)，則xi = ek?1(yi⊕yi?1)
• 加密是概率性的，
• 通常IV是一個nonce，而不是secret：可以用明文發送，或者計數器值，從ID等派生，

CFB模式

密碼反饋模式（CFB – Cipher Feed Back mode）

• 第一個區塊:密鑰用IV加密，然后XOR用明文區塊加密:y1 = ek (IV)⊕x1
• 后續塊:密鑰與前一個密文加密，與明文XOR: yi = ek (yi?1)⊕xi i≥2
• 解密:x1 = ek (IV)⊕y1, i≥2 xi = ek (yi?1)⊕yi, i≥2
• 概率加密
• IV應該是一個nonce，可以以明文發送，

OFB模式

輸出反饋模式（OFB – Output Feed Back mode）

• 第一個區塊，IV用密鑰加密，然后XOR與明文區塊加密，si = ek (IV)， y1 = s1⊕x1
• 后續區塊:之前加密的密鑰使用key加密，XOR使用明文:
  si = ek (si?1)，yi = si⊕xi, i≥2
• 解密:s1 = ek (IV)， x1 = s1⊕y1
  si = ek (si?1)，xi = si⊕yi, i≥2
• 概率性的加密
• “加密密鑰”si可以獨立于明文進行計算，例如預先計算，

CTR

CTR -計數器模式（CTR – Counter mode）

• 密鑰用CTR加密
• CTR由IV和counter value組成
• 生成一個關鍵流塊
• 可獨立生成明文-并行操作
• 不確定的
  - 加密:
  yi = ek (IV k CTRi)⊕xi, i≥1
  - 解密:
  xi = ek (IV k CTRi)⊕yi, i≥1

小結-分組密碼

• 廣泛使用的密碼學:DES, 3DES, AES，塊模式
• ECB, OFB, CTR:塊輸出獨立于其他明文塊——確定性
• OFB、CTR模式可用于生成密鑰流、亂數，
• CBC, CFB:塊輸出取決于以前的明文-——概率
• 除ECB外，所有模式都要求共享IV
• 加密和解密使用相同的共享密鑰
• 問題:如何共享密鑰?