Ch9

  • Public-Key Encryption :
    • 原理 :
      1. Key distribution :
        • 雙方利用已分享之金鑰
        • 或是利用Key Distribution Center(KDC)
      2. Digital signatures : 是否能偵測訊息為特定來源所發送的
    • 簡單分類 :
      1. 為了Secrecy :
        • 公鑰加密、私鑰解密
      2. 為了Authentication :
        • 私鑰加密、公鑰解密
        • 無法提供安全性
      3. 併重Secrecy和Authentication :
        • 先簽章、後保密
      4. 總結 : Sender不是使用 Sender的私鑰，就是使用 Receiver的公鑰
    • 要求 :
      1. Receievr容易產生公鑰與私鑰
      2. Sender容易加密($C=E(PU_b, M)$)
      3. Receiver容易解密($M=D(PR_b, C)$)
      4. 即使知道公鑰$PU_b$，仍不可能推出$PR_b$
      5. 即使知道密文$C$與公鑰$PU_b$，仍不可能推出明文$M$
      6. 以上要求可以歸咎成陷門函數(Trapdoor One-way Function) :
        • $Y = f(X)$ → 容易
        • $X = f^{-1}(Y)$ → 不可行
    • 攻擊方式 :
      1. Brute-force attack :　
        • 應對 : 使用large keys → 太大會使加解密速度變太慢 → 公鑰加密只用於金鑰管理與簽章程序
      2. 給公鑰計算私鑰 : 目前不可行
      3. Probable-message attack :
        • 測試所有該長度的密鑰
        • 應對 : 訊息加上隨機bits
  • Rivest-Shamir-Adleman (RSA) :
    • 利用指數
    • 明文在Block中加密，Block大小<=log2(n)+1
    • 流程 :
      • Key generation :
        1. 選擇兩質數$p$、$q$
        2. 計算出$n=p*q$
        3. 計算出$\phi(n)=(p-1)(q-1)$
        4. 選擇$e$ :
          • $gcd(\phi(n),e)=1$ $,\quad 1<e<\phi(n)$
        5. 計算$d$ :
          • $e$和$d$在$mod\quad \phi(n)$中為乘法反元素
          • $e$和$d$與$\phi(n)$互質
          • $d\equiv e^{-1}(mod\quad \phi(n))$
        6. 公鑰$PU={e,n}$
        7. 私鑰$PR={d,n}$
      • Encryption : $C=M^e\quad mod\quad n$
      • Decryption : $M=C^d\quad mod\quad n$
    • 實例 :
      • 明文轉換 :
        1. 將明文中每個字母對應成兩個數字
        2. 明文block為4個數字所組成
    • Fast Modular Exponentiation Algorithm :
      • $x^{11}\quad mod\quad n = x^{1+2+8}\quad mod\quad n = ((x)(x^2)(x^8))\quad mod\quad n$
      • 也就是，$a^b\quad mod\quad n$的$b$可以拆解成2進位相乘
    • 提升效率 :
      • 公鑰 :
        • $e$常用 : 65537(2^16^+1), 3, 17
        • $e$不能太小，很容易被中國餘數定理破解
      • 私鑰 :
        • $d$不能太小，很容易被破解
        • 使用CRT加速運算 :
    • 攻擊避免方式 :
      • Brute-force Attack :
        • 應對 : $d$的bits較大
        • 但密鑰生成與加解密很複雜，系統運行緩慢
      • Factoring Problem :
        • n分解的表現可以代表RSA的安全性
        • 分解攻擊種類 :
          • Quadratic Sieve(二次篩選法)
          • Generalized Number Field Sieve(GNFS/普通數域篩選法)
          • Special Number Field Sieve(SNFS/特殊數域篩選法)
        • 應對 :
          1. $n$的長度要長
          2. $p$和$q$要有Constraints :
            • $p$和$q$只差幾個數字
            • $p-1$和$q-1$都要含有大的質因數
            • $p-1$和$q-1$的最大公因數要很小
      • Timing Attack :
        • 可能會出現在所有公鑰密碼系統
        • 在計算$a^b\quad mod\quad n$時，由於是一個一個bit去計算，而1所花的運算比0的運算要多很多，因此若能得到多組訊息與其加密時間，就會有機會可以反推出私鑰的內容。
        • 應對 :
          • Constant exponentiation time : 確保所有指數運算花費相同時間，不過會降低性能
          • Random delay : 增加隨機延遲時間
          • Blinding : 在計算$M=C^d\quad mod\quad n$前，先將$C$乘上隨機數$r$; mod完之後的$M’$，再乘上$r$的乘法反元素$r^{-1}$，即可獲得明文。
      • Fault-Based Attack :
        • 攻擊正在生成RSA數位簽章的處理器 :
          1. 攻擊者擁有目標機器之物理訪問權
          2. 減少處理器之輸入電源
          3. 數位簽章發生故障，使得產生無效的簽章
          4. 攻擊者進行分析並獲得私鑰
      • Chosen Ciphertext Attack (CCA) :
        • 攻擊流程 :
          1. 攻擊者將密文轉換為Chosen Ciphertext($X=(C*2^e)\quad mod\quad n$)
          2. 將Chosen Ciphertext送過解密流程，獲得$Y=X^d\quad mod\quad n$
        • 應對 :
          • 加密前隨機填充明文，使密文隨機化
          • 使用Optimal Asymmetric Encryption Padding(OAEP)來修改明文

Ch10

  • Diffie-Hellman Key Exchange(DH/迪菲-赫爾曼密鑰交換) :

    • 有效性取決於計算離散對數的難度
    • 此演算法僅限於交換秘密值
    • 流程 (以Alice為例) :
      1. 選擇好質數$q$和其原根$\alpha$
      2. 選擇自己的私鑰$X_A$($X_A<q$)
      3. 計算出自己的公鑰$Y_A={\alpha}^{X_A}\quad mod\quad q$
      4. 跟Bob交換公鑰，並收到$Y_B$
      5. 計算出Secret Key$K={(Y_B)}^{X_A}\quad mod\quad q$
    • 多人於一個協議時 :
      • $K={(Y_i)}^{X_j}\quad mod\quad q$
      • 安全性 : 只有i和j知道$K$
      • 認證性 : i知道只有j能利用$K$去新增訊息
      • 但無法抵擋replay attacks
    • 安全性來源 :
      • 利用離散對數不好計算的性質，讓公鑰難以回推私鑰
      • ex: $X_B=dlog_{a,q}(Y_B)$
    • 攻擊方式 :
      • Brute force : 只有數字小才可行
      • Man-in-the-Middle Attack :
        • 中間人發送假的公鑰給雙方，之後獲得雙方各自的K值便可破解
        • 可能會發生在參與者不用進行身分驗證的協議中
        • 應對 : 使用數位簽章與公鑰基礎建設架構

  • ElGamal Cryptography(ElGamal加密算法) :

    • 流程 :
    • 注意事項 :
      • 對於一則訊息，將其分解為多個blocks並作為加密block序列發送
      • 而每個block的隨機整數$k$一定要不一樣
    • 安全性來源 : 離散對數
      • 避免從公鑰$X_A$回推私鑰$Y_A$
      • 避免從明文$C_1$回推隨機數$k$

  • Elliptical Curve Cryptography(ECC/橢圓曲線密碼學) :

    • 方程式 : $y^2=x^3+ax+b$
    • Over Zp :
      • 方程式 : $y^2\quad mod\quad p=(x^3+ax+b)\quad mod\quad p$
      • 三個在曲線上的點也在同條直線上的話，他們的總和為$O$
      • if $P=(x_P,y_P)$, then $-P=(x_P,-y_P)$
      • Point Addition :
      • Point Doubling :
      • Point Multiplication :
      • 公式 : $$x_R=(\lambda^2-x_P-x_Q)\quad mod\quad p\y_R=(\lambda(xP-xR)-y_P)\quad mod\quad p\\lambda=\begin{cases}(\frac{y_Q-y_P}{x_Q-x_P})\quad mod\quad p,&\text{if P$\neq$Q}\(\frac{3{x_P}^2+a}{2{y_P}})\quad mod\quad p,&\text{if P$=$Q}\end{cases}$$
      • 補充公式 : $$(1/m)\quad mod\quad N ≡ -p\quad mod\quad N\(1+p*m)\quad mod\quad N = 0$$
    • over GF(2^m^) :
      • 方程式 : $y^2+xy=x^3+ax^2+b$
        • if $P=(x_P,y_P)$, then $-P=(x_P,x_P+y_P)$
      • 算法流程 :
        1. ex: 曲線$y^2+xy=x^3+g^4x^2+1$與GF(2^4^)的$f(x)=x^4+x+1$
        2. 計算g^4^$$f(g)=g^4+g+1=0\g^4=-g-1=g+1$$
        3. 將所求點$(g^5, g^3)$代入$f(x)$，得到$g^6 + g^8 = g^{15} + g^{14} + 1$
        4. 利用g的倍數去計算，ex: $g^6=(g^4)(g^2)=(g+1)(g^2)=g^3+g^2=1100$
        5. 就可以換算成$1100 + 0101 = 0001 + 1001 + 0001$
        6. $+$為AND
      • 公式 :
        • R = P + Q :
        • R = 2P :
    • 單向功能(One-way feature) :
      * 利用$Q=kP$，已知$Q$、$P$，但很難回推$k$的特性
    • ECC Diffie-Hellman Key Exchange(ECDH) :
      • 流程 :
        1. 公開元素 :
          • $E_q(a,b)$ : 方程式$E$與值域$q$
          • $G$ : 基點
        2. 雙方選擇各自私鑰 $n_A$、$n_B$
        3. 雙方計算各自公鑰$$P_A=n_AG\P_B=n_BG$$
        4. 交換公鑰後，將對方公鑰與自己私鑰相乘，便可獲得Secret Key$K=n_AP_B=n_BP_A$
    • ECC Encryption/Decryption :
      • 流程 :
        1. 公開元素 : 基點$G$
        2. 經過ECDH後，獲得對方的公鑰
        3. 選擇隨機數$k$、訊息$P_m$
        4. Encrypt : $C_m={kG,\quad P_m+kP_B}$
        5. Decrypt : $(P_m+kP_B)-n_B(kG)$$=P_m$
      • 安全性 : 已知$G$、$kG$，很難推出$k$
        • 也就是Trapdoor Function
    • ECC安全性整體來源 :
      1. 已知$P$、$kP$，很難推出$k$ → 依靠Elliptic Curve Discrete Logarithm Problem(ECDLP/橢圓曲線離散對數問題)
      2. 已知最快技術 : Pollard rho method演算法
      3. 差別 :
        • RSA :
          • 安全性↑，金鑰長度↑
          • 處理器需要較多處理
        • ECC :
          • 相同安全層級，金鑰長度較短
          • 減少處理器工作量
          • 信心程度比RSA低