Ch7

  • Random Numbers :

    • 使用之處 :
      • 鑰匙分送與互相認證
        • Nonce : 加密中只會用到一次的數字，可避免replay attack
      • 對稱加密鑰匙生成
      • RSA公鑰加密鑰匙生成
      • 對稱加密位元流生成
    • 要求 :
      • Randomness(隨機性) :
        • Uniform distribution(均勻分布) : 1和0出現的頻率應該要差不多相等
        • Independence(獨立性) : 子序列(subsequence)無法從其他子序列推斷出來
          • 沒有試驗能證明++獨立性++
          • 但有許多試驗能證明++序列沒有獨立性++
          • 若經過許多試驗皆無法證明序列無獨立，則我們有高度信心該序列是獨立的
      • Unpredictability(不可預測性) :
        • 每個數字都與序列無關 → 不太可能
        • 讓他人無法從前面的元素預測出之後的元素

  • Pseudorandom Numbers(偽隨機數) :

    • 利用演算法技術去生成，若算法良好，則可以通過許多隨機性測驗
    • True Random Number Generator(TRNG) :
      • Input : 來源為熵源(entropy source)，是從電腦中提取出來的，EX: 鼠標移動、系統時鐘瞬時值等等
      • Output : 隨機二進位位元流
    • Pseudorandom Number Generator(PRNG) :
      • 使用固定值seed作為輸入，並利用演算法計算出一連串輸出位元
      • seed通常由TRNG生成
      • 輸出位元流只由輸入值所決定，故他人若知道演算法與seed，則可以推敲出整個輸出位元流
      • 分類 :
        • Pseudorandom number generator (PRNG) :
          • 用於生成無限制的位元序列
          • 應用 : 對稱串流加密
        • Pseudorandom function (PRF) :
          • 用於生成固定長度的偽隨機字串
          • 應用 : 對稱加密金鑰、Nonce
        • 差異 :
          • 輸出位元不同
          • 兩者皆使用相同的演算法，但PRF輸入時還能加入上下文特定(context-specific)的值，EX: 使用者ID、程式ID等等
      • 要求 :
        1. Randomness(隨機性) :
          • SP 800-22規定了所有測試都須符合三種要素 :
            1. Uniformity(均勻性) : 出現1或0的機率相等
            2. Scalability(可擴展性) : 序列或其子序列皆適用於該測試
            3. Consistency(一致性) : 生成器行為必須與seed保持一致
          • SP 800-22測試舉例 :
            1. ++Frequency test++ : 確定1和0的比例是否差不多
            2. ++Runs test++ : Run的總數是否符合隨機序列的預期(Run : 同個數字連續的狀況)
            3. ++Maurer’s universal statistical test++ : 測試是否可以在不丟失信息的情況下壓縮序列
        2. Unpredictability(不可預測性) :
          • Forward unpredictability(向前)
            1. 如果seed為未知，則儘管知道序列的前幾位，接下來輸出的位元仍不可預測
          • Backward unpredictability(向後) :
            1. 無法從seed或生成值之間推得另一者
            2. 序列每個元素看起來都是獨立隨機事件的結果(機率: 1/2)
          • 隨機性測試也可用於測驗不可預測性 → 若序列是隨機的，則無法根據序列去推倒seed
        3. Characteristics of the seed(種子特徵) :
          • seed必須是隨機數
          • 通常由TRNG生成
          • 可以用於串流加密金鑰
      • 演算法種類 :
        1. Linear Congruential Generators :
          • 公式 : $X_{n+1} = (aX_{n} + c)\quad mod\quad m$, $X_0$為seed
          • $a$、$c$和$m$之選擇會影響PRNG的效果
          • 優點 : 選擇好$a$、$c$和$m$的話，可以擁有和隨機序列一樣的效果
          • 缺點 : 知道$a$、$c$和$m$就能破解，甚至只要知道$X_1$、$X_2$與$X_3$就可知道
        2. Blum Blum Shub Generator(BBS) :
          • 加密安全特性 : 給定序列前幾位，仍無法推得下一輸出位元
          • 公式 :
            • 選定兩質數$p$和$q$，得到$n=p*q$
            • 選定初始值$s(= X_0)$
            • $$X_{i+1} = {X_i}^2\quad mod\quad n\B_{i+1} = X_{i+1}\quad mod\quad 2$$
      • Block Cipher Modes of Operation
        • OFB與CTR也可用於當作PRNG來使用
        • 兩種狀況都是一回合生成一個偽隨機位元block
        • OFB : 每次加密，輸入值加一
        • CTR : 該回合的輸入值等於前一回合輸出的值
      • ANSI X9.17 PRNG :
        • 流程
          • $K_1$、$K_2$ : 56bits Key，用於三次EDE加密
          • $DT_i$ : 64bits的偽隨機數，為當下日期與時間
          • $V_i$ : 64bits的seed(從其他生成器成生)，會隨著回合數更新
          • $R_i$ : 64bits的偽隨機數結果
          • $V_{i+1}$ : 64bits的下一回合seed
        • 強度來源 :
          1. 112bits key($K_1$、$K_2$)
          2. 3次EDE加密
          3. $V_i$、$DT_i$
      • CTR_DRBG :
        • 熵源(entropy source)
        • 加密方式為3DES或AES
        • 流程 :
          • Initial function :
            1. seed由K和V組合產生
            2. 至少產出seedlen個bits
            3. 每次加密後V加一
          • Generate function :
            1. 每回合使用相同密鑰
            2. 每回合V加一
          • Update function :
            1. 當計數器達到Reseed Interval時，K和V都會更新

  • Stream Ciphers :

    • Stream Ciphers One-time Pad
      Pseudorandom Number Stream(偽隨機數字流) Genuine Random Number Stream(真隨機數字流)
    • 注意事項 :
      1. 產生加密序列的週期要長 : 生成位元流的重複週期越長，密碼分析就越困難
      2. 密鑰流要類似隨機位元流 : 元素出現的機率要大致相同
      3. 密鑰至少要128bits
      4. 只要隨機數生成器經過適當設計，串流加密可以跟區塊密碼一樣安全
      5. 可以使用強度高的PRNG去製作串流加密
      6. 區塊加密可以重複使用密鑰，串流加密則不行
    • RC4 :
      • 可變密鑰長度的Stream Cipher
      • 每輸出一個位元組的結果僅需要8到16條機器操作指令，軟體實現也很快
      • 用途 : SSL、TLS、WEP、WPA
      • 流程 :
        1. 初始化 :
          • S[i]為0~255的填充
          • K為金鑰(長度為keylen)
          • T[i]為金鑰K的重複填充
        2. 初始化置換 :
          • 對S[i]和S[j]進行置換
          • 不再使用金鑰K
        3. Stream產生 :
        4. 加解密 :
          • 加密的時候，將k與明文的下個byte做XOR
          • 解密的時候，將k與密文的下個byte做XOR
      • 優點 :
        • 目前擁有合理密鑰長度(ex: 128 bits)的RC4尚無破解方法
      • 缺點 :
        • 使用RC4的程式容易受特定之攻擊
        • 生成RC4密鑰的方式存在一些問題

  • True Random Number Generator (TRNG) :

    • Entropy source(熵源) :
      • 利用不確定性的來源產生隨機性
      • 大多數利用不可預測的自然過程來產生，例如 :
        1. Sound/Video Input
        2. Disk drives
        3. Linux使用 : 鼠標和鍵盤活動、磁碟I/O操作與特定中斷
    • 比較 :
      PRNG TRNG
      Efficiency 超快 快
      Determinism 輸出可相同 輸出必不同
      Periodicity 會 不會
      • Efficiency : 短時間能產出的數字
      • Determinism : 同樣起點，可否產出相同輸出
      • Periodicity : 序列會不會重複
    • 偏度(Skew) :
      • TRNG可能會產生某種偏差的輸出，像是皆產出>0的數字
      • Deskewing algorithms(偏度校正算法)
      • RFC4086建議可以從多個來源蒐集輸入，然後使用雜湊函數將其混合並產生隨機輸出

  • Intel Digital Random Number Generator (DRNG) :

    • TRNG用途 :
      1. 密鑰生成
      2. 只能產生少許隨機bits → 因為效率低
    • DRNG優點 :
      1. 實現與PRNG相當的bits生產率
      2. 能完全於硬體中實踐
      3. 使用硬體中的Thermal Noise(熱雜訊)

Ch8

  • Fermat’s Theorem :
    • 前提 : $p$為質數、$a$為無法被$p$整除的正整數
    • 公式 : $$a^{p-1}\equiv1(mod\quad p)\or\a^p\equiv a(mod\quad p)$$
  • Euler’s Totient Function :
    • $\phi(n)$ : 小於n且和n互質的正整數數量
    • 若$n$為質數，則$\phi(n)=n-1$
    • 若$n$不是質數，則$\phi(n)=\phi(p)\phi(q)=(p-1)(q-1)$($p$與$q$為相異質數)
    • 若n為$p^2$，則$\phi(n)=p*(p-1)$
  • Euler’s Theorem :
    • 前提 : $a$和$n$為互質的質數
    • 公式 : $$a^{\phi(n)}\equiv1(mod\quad n)\or\a^{\phi(n)+1}\equiv a(mod\quad n)$$
  • Miller-Rabin Algorithm :
    • 公式 :
      1. 將輸入值$n$拆解成$(n-1)=2^kq$
      2. 在$1<a<n-1$範圍中取出想測試的$a$
      3. inconclusive (可能是質數) / composite (必定是複合數)
    • 每次測試，非質數被判斷為可能是函數的機率小於1/4
    • 因為所有的偶整數不用判斷，故測試數字$n$平均要做$0.5ln(n)$次測試
  • Discrete Logarithms :
    • 性質 :
      1. 所有序列最後都是1
      2. 最長序列長度為$\phi(n)$
      3. 若$a$的序列長度剛好是$\phi(n)$，則$a$就是$n$的原根(Primitive Roots)
        • $a^i\quad mod\quad n$的值和$n$互質
        • 只有$2, 4, p^a, 2p^a$有原根
    • Logarithms for Modular Arithmetic :
      • $b\equiv a^i(mod\quad p)$ or $i=dlog_{a,p}(b)$