Ch3

  • Symmetric Cipher :
    • Stream Cipher :
      • 一次加密1 bit或1 byte的資料流
      • 理想狀況下，會使用Vernam Cipher的One-time Pad版本，也就是讓keystream和plaintext bit stream一樣長
      • keystream需要用另外安全信任的管道傳輸給另一方
      • 優點 :
        • 如果keystream是隨機的，則除了得到keystream以外，沒有任何方式能夠破解
      • 缺點 :
        • 如果資料量很大，會遇到傳輸的物理問題
        • 實際上，得將bit-stream generator實踐成演算法，才能讓雙方生成keystream
      • EX : Autokeyed Vigenère cipher、Vernam cipher
    • Block Cipher :
      • 明文被視為一個block，用於生成等長的ciphertext block
      • block大小通常為64 or 128 bits
      • 雙方使用者共用一個對稱加密key，而且key要是可逆的
      • 網路上大多的對稱加密程式都使用block cipher
      • n bits的密文，可能會產生$2^n$種明文組合
      • Encryption and Decryption Mappings :　
        • block size過小 → 可能會被統計分析解密
        • block size過大 → 不易進行密碼分析
      • 對於理想上n bits的block cipher，key的長度定義為$n*(2^n)$bits
    • 密碼學技術分類 :
      • 加密方式 :
        1. Substitutions(替代) : 每個明文元素都有對應替換的密文元素
        2. Permutation(置換) : 更改明文元素出現的順序
      • 演算法設計方法 :
        1. Diffusion(擴散) : 讓一個明文字母能夠儘可能對應多個密文字母(明文$\Leftrightarrow$密文)
        2. Confusion(混淆) : 讓密文的統計數據和key的值之間有著複雜的關係(key$\Leftrightarrow$密文)
          • 即使attacker知道密文的統計數據，但因為key生成密文的方式太複雜，導致很難判斷出key
    • modular運算 :
      • $a = qn + r,\quad0{\le}r{\lt}n,\quad q = \lfloor{a/n}\rfloor$
    • Feistel Cipher
      • 圖例 :
      • 操作步驟 :
        1. plaintext分為$L_0$和$R_0$兩部分
        2. 原始金鑰$K$生成$n$個回合金鑰$K_i$，每個回合金鑰都有自己的round function($F$)
        3. 將$R_0$和該回合金鑰作$F$函數的轉換
        4. 再跟$L_0$做XOR，並作為新的$R_1$
        5. 最後把$R_0$直接作為$L_1$
      • 主要公式 :
        • $LE_i=RE_{i-1}$
        • $REi=LE_{i-1}\bigoplus F(RE_{i-1},K_i)$
      • 重點 :
        • 每回合$L_i$和$R_i$倆倆交換 : 使用了Permutation(置換)
        • 每回合$R_i$先經過$F$函數的轉換，再和$L_i$做XOR : 使用了Substitutions(替代)
      • 加密法依賴於 :
        1. Block大小 : 越大的Block代表安全性越高，但也會讓加解密速度降低
        2. Key大小 : 越大的Key代表安全性越高，但可能會降低加解密速度
        3. 回合數 : 多回合制讓安全性提高
        4. 回合金鑰生成演算法 : 此算法的高複雜度，讓密碼分析不易進行
        5. 回合$F$函數 : 更高的複雜度對於密碼分析更有抵抗力
        6. 快速軟體加解密 : 演算法執行速度影響到軟體加解密的速度
        7. 易於分析 : 如果能輕易地解釋演算法，就能簡單找出密碼分析的漏洞，把演算法的強度再作提升
DES
  • DES(Data Encryption Standard) $\approx$ DEA(Data Encryption Algorithm)
    • 輸入64 bits的block，使用56 bits的Key加密成64 bits的輸出
    • 使用相同的步驟與Key來加解密
  • 整體明文操作 :
    1. 輸入64 bits的明文
    2. 經過Initial permutation (IP)，重新排列明文
    3. 跑過總共16個回合
  • 各回合明文操作 :
    1. 輸入64 bits的明文
    2. 分為$L_i$(32 bits)和$R_i$(32 bits)兩塊
    3. 右半部 :
      • F函數 :
        • $R_i$經過E table，從32 bits擴增至48 bits
        • 和回合金鑰$K_i$(48 bits)做XOR
        • 再經過S-box，從48 bits縮減回32 bits
        • 最後再經過一次置換(Permutation)
      • 和$L_i$做XOR
      • 最後產出$R_{i+1}$
    4. 左半部 :
      • 直接把$R_i$變為$L_{i+1}$
  • E table :
    假設 32 bits input : …efgh ijkl mnop…
    就會變成 48 bits output : ..defghi hijklm lmnopq…
  • S-box :
    1. 把48 bits切割成S1~S8，每組各6 bits
    2. 假設S1 = 011001
    3. row = 前後兩碼 = 01 = 2
    4. column = 中間剩餘四碼 = 1100 = 12
    5. 找出S1-box第2列第12行的數字 : 9 = 1001
    6. 將8組的4bits綜合起來，共32 bits
  • 整體Key操作 :
    1. 輸入64 bits的Key
    2. 經過Permuted Choice One (PC-1)
      • 每第8個bit都刪除 → 讓key從64 bits變為56 bits
      • 將Key分為$C_i$和$D_i$，各28 bits
    3. 兩者都Left Shift一次，位移量依回合數去對照特定schedule(通常都是1 or 2)
    4. 此成為下一回合的input key
    5. 另外，再經過Permuted Choice Two (PC-2)，從56 bits變為48 bits
    6. 此結果就是該回合的回合金鑰$K_i$
  • 各回合Key操作 :
  • Avalanche Effect(雪崩效應) :
    • 明文或Key改變一個bit，會造成密文的巨大改動
  • Time attack :
    • 通常可以運用加解密時輸入不同明文所花費的時間差，去推測明文或Key
    • 但在DES和更好的對稱加密中，不太可能成功
  • Feistel Cipher強度來源 :
    1. Number of Rounds :
      • 回合數越多，越難進行Cryptanalysis(密碼分析)
      • 一般而言，已知密碼分析工作量 > 暴力攻擊工作量
      • 當Round < 15時，暴力攻擊工作量 > Differential Cryptanalysis(差分密碼分析)工作量
    2. Design of the function F :
      • F函數越是nonlinear(非線性)，任何類型的密碼分析都越困難
      • SAC和BIC都加強了Confusion(混淆)的效果
        • Strict avalanche criterion (SAC/嚴格雪崩效應) : 每個輸入進S-box的bit，都有50%機率發生變化
        • Bit independence criterion (BIC) : 對於輸入位元i和輸出位元j、k，當i被反轉時，j和k應要獨立改變
    3. Key Scheduling Algorithm :
      • 一般狀況 : 把以下兩者難度提升到最高
        1. 推導單個回合金鑰的難度
        2. 還原為主Key的難度
      • 最低要求 :
        1. 確保Key或是密文有滿足SAC和BIC

Ch4

  • Divisibility :
    • $a=qn+r$ :
      • a : dividend(被除數)
      • n : divisor(除數)
      • q : quotient(商數)
      • r : remainder(餘數)
    • $b|a$ : a整除b
  • The Euclidean algorithm
    • GCD :
      • gcd(0, 0) = 0
      • gcd(a, b) = gcd(|a|, |b|)
      • gcd(a, 0) = |a|
  • Extended Euclidean Algorithm
    • 公式 : $ax+by=gcd(a ,b)$
  • Modular arithmetic
    • modular運算 :
      • $a=mb+r$
      • $a\quad mod \quad n =a-\lfloor{a/n}\rfloor*n$
      • $a\equiv b(mod\quad n)\quad\Rightarrow\quad (a\quad mod\quad n)=(b\quad mod\quad n)$
      • $a\equiv 0(mod\quad n)\quad\Rightarrow\quad n|a$
      • $[(a\quad mod\quad n)+(b\quad mod\quad n)]\quad mod\quad n=(a+b)\quad mod\quad n$(減法&乘法也適用)
    • Additive Inverse(加法反元素) : 兩元素相加mod n為0
    • Multiplicative Inverse(乘法反元素) : 兩元素相乘mod n為1
    • mod n之餘數的集合稱為$Z_n$
      1. 也稱為residue classes (mod n)
      2. $Z_n={0, 1,…, (n-1)}$
  • Groups, rings, and fields
    • Group :
      • The order of the group : Group中元素的數量
      • A4 : 可以找到加法反元素
      • 若Group滿足A1~A5，則稱為Abelian group
        1. 整數set under Addition是Abelian group
        2. 非零實數set under Multiplication是Abelian group
      • 若Group = ${a^k; k \in \mathbb{Z} }$，則稱為Cyclic Group
        • Cyclic Group也屬於Abelian group
    • Ring :
      • 滿足A1~M3
      • 在Ring中，可以做加、減(a+(-b))與乘法，但都不能離開該集合
      • 若Ring又滿足M4(對所有元素而言，ab=ba皆成立)，則稱為Commutative Ring
        1. 整數set under Addition and Multiplication是Commutative Ring
        2. 前面提的$Z_n$也屬於Commutative Ring
      • 若Ring還滿足M5、M6，則稱為Integral Domain
        1. 整數set under Addition and Multiplication是Integral Domain
    • Field :
      • 滿足A1~M7
      • M7 : 可以找到乘法反元素
      • 在Field中，可以做加、減($a-b = a+(-b)$)、乘法與除法($a/b=a*b^{-1}$)，但都不能離開該集合
      • EX : $\mathbb{Q}$、$\mathbb{R}$、$\mathbb{C}$ $\iff$ $\mathbb{Z}$不是Field
  • Inite fields of the form $GF(p^n)$
    • $GF(p^n)$ : order為$p^n$的有限Field
    • $GF(p)$ : order為質數$p$的有限Field
      • $GF(p)$ = $Z_p$ = ${0, 1, …, p-1}$
    • 當$p$為質數時，$Z_p$中的所有整數都可以找到乘法反元素
      → 使用Extended Euclidean Algorithm
  • Polynomial arithmetic :
    • 多項式運算包含加法、減法與乘法
    • 除法的話，S必須是Field
      • EX :　實數、有理數或$Z_p$ for p prime
  • Finite fields of the form $GF(2^n)$ :
    • Addition變成XOR
    • Multiplication需要Shift，再XOR :
      1. Modulo Reduction :
        • 假設m(x)最高次方為8，可以把$f(x)*g(x)$結果中高於8次方的多項式mod m(x)
        • EX :
          $$
          m(x) = x^8 + x^4 + x^3 + x + 1 \
          f(x) = b_7x^7 + b_6x^6 + b_5x^5 + b_4x^4 + b_3x^3 + b_2x^2 + b_1x + b_0 \
          g(x) = x \
          if\quad b_7 = 0,\
          f(x) * g(x) = b_6x^7 + b_5x^6 + b_4x^5 + b_3x^4 + b_2x^3 + b_1x^2 + b_0x \
          if\quad b_7 = 1,\
          f(x) * g(x) = \color{blue}{b_7x^8}+ b_6x^7 + b_5x^6 + b_4x^5 + b_3x^4 + b_2x^3 + b_1x^2 + b_0x \
          = b_6x^7 + b_5x^6 + b_4x^5 + b_3x^4 + b_2x^3 + b_1x^2 + b_0x + \color{blue}{[b_7x^8\quad mod\quad m(x)]} $$
      2. Binary Notation