關於小額付費

另一個名稱為 微支付 (Micropayment)，簡單來說提供顧客 (Consumer) - 銀行 (Broker) - 商家 (Vendor) 三方的交易。小額付費標明在交易金額小，因此交易成本也應該小，否則交易手續的計算能量就超過交易金額，更別說要扣除交易物品的成本。通常要在以下三點最小化

• 計算資源：
  在先前提到的加密算法中，key 的 bit-length 相當長，導致計算的能量消耗大。倘若只消費 1 元，耗電成本就佔了 1% 以上，甚至更多，那麼是划不來的。
• 儲存空間花費：
  計算每一組交易明細所需要的空間要最小，例如記錄金額需要 32-bit，那麼 n 次交易就需要 n 個 32-bit 的空間，在其他細節中還需要紀錄額外的購買來源、 … 等。
• 管理成本：
  第三方 (通常是銀行) 要管理顧客的金額花費、商家是否能取用顧客的錢。銀行要怎麼紀錄顧客的狀態、如何驗證商家真的有跟顧客交易 … 等。

由於交易金額小，即使被破解對雙方的損失也不大。但通常破解手段需要的時間、資源往往超過交易金額，因此不太會有人去破解這個。

應用層面

網路電子報：

一份電子報可能有一些特別的標題內容，若要深入查閱內文，需要讀者付費觀看。這一部分更具有彈性，對於一份具有相當多面向的電子報而言，有些人只看幾個專欄就必須花費購買一整本的金額，有些時候是浪費的。

網路期刊購買、資料庫詢問

網路學術期刊就跟電子報的情況一樣。資料庫詢問比較特別，花費小金額來交換資料庫服務的次數。

廣告

互動式影片、廣告商為了誘拐大眾仔細觀看廣告，由廣告商付錢給觀看者。例如回答問卷回饋、機率性地抽獎回饋 … 等。

網頁閱讀

類似向大眾徵文，鼓勵分享知識。徵求到的文章，由平台供應者支付。

何時用

使用者付費，而非訂閱長時間的垃圾訊息或服務。在大多數的服務商中，會提供時間內無限使用或按照次數計費兩種方案，在大多數的情況下，時間內無限使用是對商家有利，可以預先得到使用者的投資，但使用者在後續時間內可能沒有去使用、或者沒時間去用。

不是 按照次數計費全然好 ，就如 電話費 ，打了多少通電話、講了多久，只有電信商知道，即便告訴花費相當多金額，通話明細也是由他們提供，很難證明到底花了多少，這是對使用者的不利。相較起來，小額付費比較接近投幣式的公共電話，投了多少就打多少，等到快沒有餘額時，再進行補充。

先付款給商家會對使用者不利，有可能取得不好的服務，後付款給商家會對商家不利，因為使用者可能沒有足夠的金額。正因為小額交易，適時地刷新狀態 (再投幣) 就能在之間達到平衡。

數學

由制定 RSA 那伙人 Rivest, Shamir 提供 Payword scheme 的方法。

首先，概念建立在假設不用數字儲存金額 (減少儲存空間、管理花費)，而是用運算次數來知道花費金額 (用簡單運算來完成，防止能源消耗過大)。金額花費是整數，由最小單位 1 元構成，如果是在通貨膨脹的國家，最小單位可能不一樣？

那麼可以建立一個儲值金額 n 元的串列如下。

由使用者拿一個$x_n$ 初始化，接著利用 hash$x_i = h(x_{i+1})$ 得到每一個硬幣$x_i$。用數學表示遞迴公式$x_i = h^{n-i}(x_n)$。

當顧客跟商家交易時，簽一份簽章 (例如用 RSA 或者是 DSA 等方式) 給商家。簽章內容為

其中 $\text{Cert}$ 是由第三方信任銀行簽署給用戶的內容 (類似銀行帳戶的確認)。最後發送給商家資訊為

由商人去驗證 (檢查簽證內容、拿對方的 public key 打開，再去拿銀行的 public key 驗證 $\text{Cert}$ 是否正確) 是否是可信任的顧客或者是顧客是否存在。

接下來交易採用最笨的方案，每一次交易 1 元，交付 i 元時，顧客就告知$x_i$ 值給商家，這裡顧客得到硬幣方法為重新計算$x_i = h^{n-i}(x_n)$，可以不事先用記憶體儲存$[x_0, x_n]$，保留 $n$ 和$x_n$ 即可。

之後商家拿著 i 元$x_i$ 和$\text{Sign}_C(\text{Merchant-ID} || x_0 || \text{Cert})$ 的資訊給銀行，銀行計算 $i$ 次 hash$x_0 = h^i(x_i)$ 查看是否正確，若檢驗沒問題，則銀行從客戶存簿撥款給商家。

為什麼可行

運算過程中使用 hash，hash 提供不可逆的操作，因此商家無法有更多金額的索取，假設從顧客手中得到$x_i$，無法計算出$x_{i+1}$ 究竟是什麼，具有一定安全性。而顧客必須由銀行索取簽證，來表示當前的狀態是合法的，顧客沒辦法竄改自己的狀態，使得自己有更多的金錢，銀行那裏會有最新一組的簽章在？應該是吧，銀行會在商家發送驗證資訊時發生異狀檢查顧客是否竄改。

數學之美。

前言

幾乎是密碼學基礎數論，看來也走到這了。

亂來

隨便寫寫，上課不專心真是抱歉。

1. Given an integer $x$, what is the requirement to let the multiplcative inverse $x^{-1}$ exist when modulo $p$? if $x^{-1} \mod p$ exists, please write down the equation (based on Fermat’s theorem) used to compute $x^{-1} \mod p$. (5%)

   1. condition: $gcd(x, p) = 1$ for multiplcative inverse $x^{-1}$ exist when modulo $p$
   2. Fermat’s theorem : $x^{p-1} = 1 \mod p \Rightarrow x^{p-2} \times x = 1 \mod p$ $x^{-1} = x^{p-2} \mod p$

2. What is the Euler totient function $\phi(n)$? Please answer $\phi(77) = ?$

   $\phi(n)$ 表示 1 到 n 之內的整數，有多少與 n 互質的個數。
   $\phi(77) = 77 \times (1 - 1 / 7) \times (1 - 1 / 11) = 60$

3. Whais the discrete logarithm problem? (5%)
   對於等式 $y = x^a \mod p$，已知三整數 y, x, p，解出 a 的問題。詳見小步大步算法 baby-step-giant-step，複雜度 $O(\sqrt p)$

4. What is a hybrid cryptography? (5%)
   $$\text{hybrid cryptosystem } = \text{ public-key cryptosystem } + \text{ symmetric-key cryptosystem}$$

   • public-key cryptosystem
     提供 key encapsulation，就是 key 的安全性和簽章認證，保護 key 傳輸、保管上的問題。
   • symmetric-key cryptosystem
     提供 data encapsulation，提供高效率的加解密效能。

5. What are the two primary reasons of using a cryptographic hash before signing a signature? (5%)
   cryptographic hash 密碼雜湊函數，通常會計算 $hash(M)$

   • 單向不可逆
     難以給定一個雜湊值，並且逆推得到當初輸入的數值。
     • 提供訊息修改檢查，相同的訊息進行雜湊，高機率會是不同。
       $hash(M1) \neq hash(M2)$，如果 M1 和 M2 差異只有數個 bits 不同。
     • 防止在傳輸過程中被竄改。對於簽章則更難竄改成相同雜湊值且具有 意義 的訊息 $M'$。
   • 容易計算
     將一個長度很大的訊息，壓縮一個固定長度的數值，這數值方便後續算法計算用加密算法的部分。

6. Please write down the RSA public key encryption and decryption process (including public key and private key generation process). (10%)

   1. $N = p \times q$
   2. $\phi(N) = (p-1)(q-1)$
   3. $gcd(\phi(N), e) = 1, \phi(N) > e > 1$
   4. $d = e^{-1}, e \times d = 1 \mod ø(N)$
   5. public $e, N$
   6. private $p, q, d$

7. Please develop a left-to-right binary exponentiation algorithm without “conditional jump” which is usually dangerous to some engineering attack. (10%)
   Montgomery Ladder

   1 2 3 4 5

   R[0] = 1, R[1] = p for i = n-1 to 0, step = -1 R[1-a[i]] = R[0] * R[1] R[a[i]] = R[a[i]] * R[a[i]] return R[0]

8. Below is the DSA signature scheme in which $p$ is a large prime, $q$ is a 160-bit prime factor of (p - 1), $g$ is an integer of order $q$ modulo $p$. Let $x$ be the signer’s private key and $y = g^x \mod p$ be the public key.

   1. How to generate an integer $g$ ? (5%)

   2. Please complete the following nissing steps of the scheme. (10%)

   3. Please describe a trick for speeding up DSA’s on-line signing process. (5%)

      _______________________________________________________________________
      Signing algorithm                 Verification algorithm
      _______________________________________________________________________
      r = (g^k mod p) mod q             w = s^-1 mod q
      k is a random integer             u1 = (SHA(m) * w) mod q
      s = ________________              u2 = (r * w) mod q
      m is the messgae                  v = _________________
      the signature is (s,r)            if v = r then the signature is correct
      

   • $g = h^{(p-1)/q} \mod p$ ，其中隨機亂數 $h$，滿足 $g > 1$ 即可。
     從費馬小定理中，有一個比較特別的計算來得到 order $q$，所謂的 order $q$ 就是在前 $q$ 個 $g^i \mod p$ 下不會出現重複 (循環長度至少為 $q$)，從觀察中得知循環長度 $L$ 滿足 $L | p-1$，也就是說 $L$ 是 $p-1$ 的因數，$q$ 則是要找到一個大循環，讓攻擊者更難找到 $x$，又因為 $L$ 是其因數，由於 $q$ 是 $p-1$ 的其中一個質因數，則保證是一個最小循環節的要求。

   • $s = k(SHA(m) + x \times r)$ $v = g^{u1} y^{u2}$

   • 可以 offline 去預處理隨機亂數 $k$，事先計算一堆的 $r$、$z = k^{-1}x \times r$，那麼計算 $s$ 可以非常的快速，$s = k^{-1} SHA(M) + z \mod p$，假設 hash 計算快速，只動用到一次乘法和加法，相較於 RSA 的簽章方法，少了指數次方運算。

9. Under the following certificate hierarchy, please provide all the details of how end user A checking the correctness of end user C’s public key by verifying a sequence of certificates. Note: User A only knows X’s public key, but does NOT have the root Z’s public key directly. (10%)
   若 A 要確認 C 給的 public key 是否正確，則依循以下步驟來確認

   1. C 拿出 Y<<C>>，拿 Y 的 public key 進行確認 C 的 public key。
   2. 再檢查 Y 的 public key，Y 拿出 Z<<Y>>，拿 Z 的 public key 進行確認 Y 的 public key。
   3. 再檢查 Z 的 public key，Z 拿出 X<<Z>>，拿 X 的 public key 進行確認 Z 的 public key。
   4. 由於我們知道 X 的 public key (藉由實地臨櫃面對面確認 X 的 public key)，最後驗證 C 給的是正確的 public key。

            Z
          ／ ＼          Notation used
         X     Y         X<<A>>:
       ／ ＼    ＼       A's certificate issued by X
      A     B     C
      

10. Pleasewrite down the Diffie-Hellman key exchange protocol (including the public key and private key generation process). (10%) What is the man-in-middle (or the middle person) attack? (5%)

    • 共同決定一個大質數 $p$ 和一個基底 $g$ (全部人都知道)
    • 每個人 A 擁有自己的 private key $x_A$ ($x_A < p - 1$)
    • 每個人 A 計算自己的 public key $y_A$ ($y_A = g^{x_A} \mod p$)

    假設有兩個人 A, B 要通訊，則把自己的 public key 交給對方，共同產生出一把暫時的 key $K_{AB}$ 進行通訊加密。

    • 對於 A 來說會接收到 $y_B$，計算$K_{AB} = (y_B)^{x_A} = g^{x_B \times x_A} \mod p$
    • 對於 B 來說會接收到 $y_A$，計算$K_{AB} = (y_A)^{x_B} = g^{x_A \times x_B} \mod p$
    • 由於離散對數是一個困難問題，很難藉由攔截紀錄來得到對方的 private key $x_A$，因此有一定的安全性。

    假若現在要進行中間人 C 的攻擊，則會在一開始交換 $K_{AB}$ 的時候插入到其中通訊。

    • A 發送 $y_A$ 給 B 時，受到 C 的攔截。
    • C 知道 A 想要跟 B 通訊，則把自己的 $y_C$ 發送給 B，並且也傳一份給 A。
    • B 以為是 A 要進行通訊，實質拿到 $y_C$ 而非 $y_A$。
    • 產生兩把 key$K_{AC}, K_{CB}$，C 就偷偷在中間偷聽，並且作為中繼傳送訊息，需要解密 (拿$K_{AC} \text{ or } K_{CB}$) 之後再進行加密$K_{CB} \text{ or } K_{AC}$ 送給另一方。

    如何防止中間人攻擊，大約有幾種方法，但牽涉到可信任第三方、計算速度。

    • 發送訊息上，計算時間的延遲不得超過一定限制，否則可能存在中間人攻擊。
    • 藉由可信任第三方 CA (Certificate Authority) 來驗證彼此的 public key 歸屬於誰
      由 CA 簽認$Sign_{CA}(\text{public key || owner_id || expiration date || ...})$，如此一來如果存在 C 中間人，則轉交 $y_C$ 給 B 時，B 就會藉由 CA 驗證得到 owner_id 不是通訊對象 A。如果 CA 不可信任，則可以讓 C 簽一個$Sign_{CA}(\text{public key C || owner_A || expiration date || ...})$ 來欺騙 A 和 B，也就是說 CA 和 C 偷偷在私底下做了黑心勾當，那麼中間人攻擊仍是存在的。

11. Both message authentication code (MAC) and digital signature can be used to provide the functionality of message origin and integrity check. Please briefly describe these two techniwues and compare percisely the difference between these two techniques. (10%)
    message authentication code (文件訊息鑑別) 顧名思義就是針對 message 進行驗證，確認發送者身分和資料完整性，相較於 digital signature (數位簽章) 也是做相同的事情，訊息量不同且產生出來的結果也大不相同。通常文件訊息鑑別會破壞儲存資訊，藉由雙方共享的 key 來進行身分認證，可用暫時性的 key，若採用非對稱式則需要額外的數位簽章來輔助驗證發送者。而數位簽章則是提供有效期限內的使用，這把驗證的 public key 必須存在比較長的時間。
    數位簽章簽定時不知道對方怎麼簽，但能驗證是他簽的並且只有他簽得出來，文件訊息鑑別通常知道對方用什麼流程輸出一樣的數值。

DSA

Digital Signature Standard (DSS) 數位憑證標準，而有一個 DSA 演算法來完成憑證。

每一次憑證傳送三個參數 $(r, s, M)$，利用私用金鑰進行加密。讓對方使用公鑰進行驗證。

• $r = (g^k \mod p) \mod q$
• $s = k^{-1}(SHA(M) + x \times r) \mod q$

give receiver $(r, s, M)$, we have random (one-time) $k$ & private key $x$

每一次簽名時，最好使用隨機亂數 $k$ 作為簽章用途，隨用即棄，若發生重複使用，將會發生被攻擊，被攻擊者拿到私鑰後，攻擊者就能進行偽裝。

Attack

if reused $k$

如果重複使用隨機變數 $k$，可以藉由夾擊的方式得到，雖然不知道加密的隨機亂數 $k$ 究竟是什麼，藉由夾擊可以把 $k$ 消除，利用乘法反元素反求 $x$ 是多少，公式如下所述。

• $k = s1^{-1} (SHA(M1) + x \times r) \mod q$ - (1)
• $k = s2^{-1} (SHA(M2) + x \times r) \mod q$ - (2)

subtract (1) - (2)

• $0 = s1^{-1} SHA(M1) - s2^{-1} SHA(M2) + (s1^{-1} - s2^{-1}) x \times r \mod q$
• $s1^{-1} SHA(M1) - s2^{-1} SHA(M2) = (s2^{-1} - s1^{-1}) x \times r \mod q$
• $x = (s1^{-1} SHA(M1) - s2^{-1} SHA(M2)) \times (s2^{-1} - s1^{-1})^{-1} \times r^{-1} \mod q$

get private key. Dangerous !

Verify

驗證的正確性與否，接收者需要計算以下四個步驟來完成驗證。

• $w = s^{-1} \mod q$
• $u1 = (SHA(M) \times w) \mod q$
• $u2 = r \times w \mod q$
• $v = g^{u1} y^{u2} \mod q$

test $v = r$, why correct ?

理論的正確性可以參考以下證明，把公開的 $y = g^x \mod p$ 拿出來，這個安全性取決於離散對數的算法難度。

• known $y = g^x \mod p$, $x$ is a private key
• because $s = k^{-1}(SHA(M) + x \times r) \mod q$
• then $k = s^{-1}(SHA(M) + x \times r) \mod q$

want $r = (g^k \mod p) \mod q$

• $r = (g^k \mod p) \mod q = g^{s^{-1}(SHA(M) + x \times r)} \mod q$
• $r = g^{s^{-1} SHA(M)} \times g^{x (s^{-1} \times r)} \mod q$
• $r = g^{s^{-1} SHA(M)} \times g^{x^{(s^{-1} \times r)}} \mod q$
• $r = g^{s^{-1} SHA(M)} \times y^{(s^{-1} \times r)} \mod q$

而我們事實上就是在處理指數部分，

離散對數

解決問題 $y = g^x \mod p$，當已知 $y, g, p$，要解出 $x$ 的難度大為提升，不像國高中學的指數計算，可以藉由 log() 運算來完成，離散對數可以的複雜度相當高，當 $p$ 是一個相當大的整數時，通常會取用到 256 bits 以上，複雜度則會在 $O(2^{100})$ 以上。

實際上有一個有趣的算法 body-step, giant-step algorithm，中文翻譯為 小步大步算法 ，在 ACM-ICPC 競賽中也可以找到一些題目來玩玩，算法的時間複雜度為 $O(\sqrt{p})$，空間複雜度也是 $O(\sqrt{p})$。相信除了這個外，還有更好的算法可以完成。

小步大步算法其實很類似塊狀表的算法，分塊處理，每一塊的大小為 $\sqrt{p}$，為了找尋答案計算其中一塊的所有資訊，每一塊就是一小步，接著就是利用數學運算，拉動數線，把這一塊往前推動 (或者反過來把目標搜尋結果相對往塊的地方推動)。因此需要走 $\sqrt{p}$ 大步完成。

筆記錯誤多多，請以僅供參考的角度去質疑

Problem

1. Below is a key distribution protocol.
   (a) Please describe the details of “replay attack” when $N_1$ is removed from the protocol.
   (b) Please modify the protocol to enable party A to confirm that party B already received $K_s$?

2. Please explain link encryption and end-to-end encryption.

3. (a) Please describe details of the Fermat’s theorem (or called Fermat’s little theorem).
   (b) How to compute the multiplicative inverse of an integer $a$ modulo $p$ based on the Fermat’s theorem?
   (c) What is the requirement for $a^{-1}$ to exist?

4. (a) Please describe details of the Euler’s theorem.
   (b) Based on this theorem, please describe the basic idea of the RSA encryption and decryption process.

5. The Miller-Rabin algorithm is used to test whether an odd integer n is a
   prime. Please complete the following missing steps of teh algorithm. (15%)
   (1) Find integers $k, q$ ($k$ > 0, $q$ odd), so that $(n - 1)$ = __________
   (2) Select a random integer $a$, $1 < a < n - 1$
   (3) if (_______) then return (“maybe prime”)
   (4) for $j = 0$ to $k - 1$ do
   (5) if (_________) then return (“maybe prime”)
   (6) return (“composite”)

6. Please describe details of the Chinese remainder theorem for the case of $n = p \times q$ where both $p$ and $q$ are primes. (Your anseer should include how to transform an ordinary domain integer $A$ to the CRT domain, and the CRT formula used to inverse-transform the CRT domain representation back to the ordinary domain integer).

Notes

Part 1

基礎步驟如下

1
2
3
4
5

(1) A -> KDC : IDA || IDB || N1
(2) KDC -> A : E(Ka, [Ks || IDA || IDB || N1]) || E(Kb, [Ks || IDA])
(3) A -> B   : E(Kb, [Ks || IDA])
(4) B -> A   : E(Ks, N2)
(5) A -> B   : E(Ks, f(N2))

如果沒有 $N_1$，紀錄 IDA || IDB、E(Ka, [Ks || IDA || IDB]) || E(Kb, [Ks || IDA])，就能假冒 KDC 讓 A 用固定的 $K_s$ 去跟 B 連線。再藉由已知明文，就能知道雙方的溝通內容，進行竊聽。

為了讓 A 知道 B 擁有 $K_s$ 修改其中兩個步驟

1
2

modify  (3) E(Kb, [Ks || IDA]) || Nx
        (4) E(Ks, N2 || Nx)

Part 2

• link encryption 屬於 router 之間的通訊，屬於低階網路層協定，在每一條連輸線路各自獨立的加解密，會修改訊息 header，可以增加 padding，保護流量偵測。
• end-to-end encryption 屬於原點、目的地之間的加密，它們共同享有一把 shared key，屬於高階網路層協定，用來保護資料安全，訊息 header 保留給傳輸用。

Part 3

Fermat’s theorem :

$$a^{p-1} \equiv 1 (\text{mod } p)$$

為了要求 $x^{-1}$，則利用費馬小定理 $x^{p-2} \times x \equiv 1 (\text{mod } p)$，因此 $x^{-1} \equiv x^{p-2} (\text{mod }p)$，特別小心 $p$ 一定要是質數，且滿足 $gcd(x, p) = 1$。

Part 4

Euler’s theorem

$$a^{\phi(n)} \equiv 1 (\text{mod } n) \text{ , }gcd(a, n) = 1$$

先來複習一下 RSA 算法的產生與加解密

1. select two large primes $p$ and $q$ at random.
2. Let $N = p \times q$, $\phi(N) = (p-1)(q-1)$
3. select (at random or fixed) the encryption key $e$
   where $1 < e < \phi(N)$, $gcd(e,\phi(N))=1$
   so, $e^{-1} \mod \phi(N)$ exists
4. solve following equation to find decryption key $d = e^{-1}$, $e \times d \mod \phi(N)=1$
5. publish public/encryption key:$KP = \left \{ e,N \right \}$
6. keep secret private/decryption key:$KS = \left \{ d, p, q \right \}$

encrypt a message $M$ the sender:

• obtains public key of recipient $KP = \left \{ e,N \right \}$
• computes: $C = M^e \mod N$

decryption a ciphertext $C$

• uses his private key$KS = \left \{ d, p, q \right \}$
• computes: $M = C^d \mod N$

用來加解密，為什麼會是正確的呢？

這裡很神祕，假設 $n = 21$，則 $phi(n) = 12$，根據歐拉公式 $3^{12} \equiv 15 \mod 21$ 違反歐拉定理，但是在 ACM-ICPC 競賽中，有一點明白到，$a^i$ 在 $\mod n$ 下的餘數循環節長度 L，則滿足 $L | phi(n)$，藉由這一點來正確解密，至於到底算不算利用歐拉定理仍是個有趣問題。

Part 5

1
2
3

(1) 2^k q
(3) a^q == 1 mod n
(5) a^(2^j q) == n-1 mod n

Part 6

雖然題目要求得不多，這裡直接拿 RSA 作範例

1. $N = p \times q$

2. 目標計算 $M = C^d \mod N$
   分開計算得到兩個部分，這裡可以利用歐拉定理加快，因此 $d$ 可以先 $\mod \phi(p)$

   $Mp = C^d \mod p$ $Mq = C^d \mod q$

3. 套用中國餘式定理 CRT，簡單的模型如下：

   $a_i = M \mod m_i$ $M = a_1 c_1 + a_2 c_2 + \text{ ... }$ $Mi = m_1 \times m_2 ... \times m_n / m_i$ $c_i = M_i \times (M_i^{-1}) \mod m_i$

4. 因此 RSA 可以預先處理 $c_p = q \times (q^{-1} \mod p)$ 和 $c_q = p \times (p^{-1} \mod q)$，還原的算法則是 $M = Mp \times c_p + Mq \times c_q \mod N$

結論，由於拆分後的 bit length 少一半，乘法速度快 4 倍，快速冪次方快 2 倍 (次方的 bit length 少一半)，但是要算 2 次，最後共計快 4 倍。CPU 的乘法想必不會用快速傅立葉 FFT 來達到乘法速度為 $O(n \log n)$

但是利用 CRT 計算容易受到硬體上攻擊，因為會造成 $p, q$ 在分解過程中獨立出現，當初利用 $N$ 很難被分解的特性來達到資訊安全，但是卻因為加速把 $p, q$ 存放道不同時刻的暫存器中。

其中一種攻擊，計算得到 $M = Mp \times q \times (q^{-1} \mod p) + Mq \times p \times (p^{-1} \mod q) \mod N$ 當擾亂後面的式子 (提供不穩定的計算結果)。得到 $M' = Mp \times q \times (q^{-1} \mod p) + (Mq + \Delta) \times p \times (p^{-1} \mod q) \mod N$

接著 $(M' - M) = (\Delta' \times p) \mod N$，若要求 $p$ 的方法為 $gcd(M' - M, N) = gcd(\Delta' \times p, N) = p$，輾轉相除的概念呼之欲出，原來 $p$ 會被這麼夾出，當得到兩個 $p, q$，RSA 算法就會被破解。

先來上競賽中最常見到的快速冪次寫法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

long long mul(long long a, long long b, long long mod) { 
    long long ret = 0; 
    for( ; b != 0; b>>=1, (a<<=1)%=mod) 
        if(b&1) (ret += a) %= mod; 
    return ret; 
}
long long mpow(long long x, long long y, long long mod) {
    long long ret = 1;
    while (y) {
        if (y&1)
            ret = mul(ret, x, mod);
        y >>= 1, x = mul(x, x, mod);
    }
    return ret;
}

這樣的寫法，只運算 64-bits 內的結果相當不錯，與接下來講的算法速度差異並不大。但對於近代加密所需要的離散對數過程，則會有放大速度差異，因為 x, y, mod 三個參數的 bit-length 都相當長。

Right-To-Left

做法就是最普遍見到的。

1
2
3
4
5
6
7
8
9

void pow(x, a) {
    R = 1, g = x
    for i = 0 to n, step 1
        if (a[i] == 1) // a[i] mean i-bit in a
            R = R * g
        g = g * g
    return R
}

1
2
3
4
5
6

example: a = 26 = (11010)
---
#iterator  0   1    2    3     4 
#g         x, x^2, x^4, x^8, x^16, ...
binary     0   1    0    1     1
x^a =         x^2       x^8 x^16 = x^26

Left-To-Right

1
2
3
4
5
6
7
8

void pow(x, a) {
    R = 1
    for i = n-1 to 0, step -1
        R = R ^ 2
        if (a[i] == 1)
            R = R * x
    return R;
}

1
2
3
4
5

example: a = 26 = (11010)
---
#iterator  0   1    2      3     4 
binary     1   1    0      1     0
R         x^1 x^11 x^110 x^1101 x^11010

也就是說，每一次迭代，將會將指數左移 (R = R ^ 2 就是要移動 R^xxxx 變成 R^xxxx0，切著看是否要乘上 x 來變成 R^xxxx1)，這方法雖然不錯，但是計算高位元空迴圈可是不能忽略！當然對於設計電路的人，固定變量的迴圈展開後就不存在這問題。

效能上，期望的乘法次數與 Right-To-Left 是差不多的！長度為 n bits 的數字，期望值會有 $n/2$ 個 1，因此大約需要 $n/2$ 次乘法。

Left-To-Right(2-bits)

1
2
3
4
5
6
7
8
9
10

void pow(x, a) {
    pre-computation: x^2, x^3
    R = 1
    for i = n/2 to 0, step -2
        R = R ^ 4
        if (a[i+1]a[i] != 0)
            R = R * x^(a[i+1]a[i])
    return R
}

1
2
3
4
5
6

example: a = 1737 = (01 10 11 00 10 01)
---
#iterator   0   1    2     3     4     5
R          x^1 x^4  x^24  x^108 x^432 x^1736
               x^6  x^27        x^434 x^1737
a[i+1]a[i] 01  10   11    00    10    01

長度為 n bits 的數字，倆倆一起期望值會有 $3n/8$ 個非 0 (00, 01, 10, 11 中 4 個有 3 個 $!= 0$，計算組數只有 $n/2$)，因此大約需要 $3n/8$ 次乘法。比剛剛快上一點呢 ( $3n/8 < n/2$ )！

Left-To-Right(sliding)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

void pow(x, a) {
    pre-computation: x^3
    R = 1
    for i = n-1 to 0
        if a[i]a[i-1] = (11)
            R = R ^ 4
            R = R * x^3
            i -= 2
        else if a[i]a[i-1] = (00)
            R = R ^ 4
            i -= 2
        else if a[i] = (0)
            R = R ^ 2
            i -= 1
        else if a[i] = (1)
            R = R ^ 2
            R = R * x
            i -= 1
    return R
}

1
2
3
4
5

example: a = (1 10 11 00 10 01)
---
#iterator   0   1    2       3     4      5          6
R          x^11    x^11011     x^11011001      x^11011001001
              x^110     x^1101100    x^1101100100

期望的乘法次數 $n/3$，這很可怕，別問我！

Summary

Attack

上述四種方法中，不外乎都存在 Conditional Jump 出現，會導致執行速度跟程式計數器 (Program Counter) 移動上會有所差別。可以進行實作攻擊，從分析時間、電源不穩攻擊，來找到 $a$ 究竟是何物 (通常要偷的都是 $x^a$ 上面的 $a$)！電源雜訊干擾於當指令執行到 Conditional Jump 時，干擾 $R$ 的計算發生錯誤，如果沒有發生錯誤，表示 $a \left [ i \right ] = 0$，反之就能知道 $a \left [ i \right ] = 1$。

很趣味地是提供一個不需要 Conditional Jump 的寫法 (實作上)，一樣會有這種問題！

error example

1
2
3
4
5

R[1] = 1
for i = n-1 to 0, step -1
    R[1] = R[1] ^ 2
    R[a[i]] = R[1] × g
return R[1]

提供一個不相干的垃圾暫存器 (redundancy register) 來減少 Jump 的問題，很明顯地 電源雜訊干擾 的攻擊仍然存在！這作法很有趣的啊！只是會被攻擊。

Montgomery Ladder

1
2
3
4
5

R[0] = 1, R[1] = g
for i = n-1 to 0, step -1
    R[1-a[i]] = R[0] × R[1]
    R[a[i] = R[a[i]] × R[a[i]]
return R[0]

這作法避開之前的問題，解決其中一種被攻擊的方案。

過程中都滿足 $R \left [ 0 \right ] = R \left [ 1 \right ] \times g$，同時 $R \left [ 0 \right ]$ 會是最後的答案。

1
2
3
4
5
6

example: a = 26 = (11010)
---
#iterator  0   1    2      3      4     5
binary     0   1    1      0      1     0
R[0]       1   x    x^3   x^6   x^13  x^26
R[1]       x   x^2  x^4   x^7   x^14

明顯地，$R \left [ 1 \right ]$ 的計算是為了下一次為 $a \left [ i+1 \right ] = 1$ 而存在的！

筆記錯誤多多，請以僅供參考的角度去質疑

Problem

1. Please compare the CFB mode the OFB mode by providing a table indicating at least 5 of their advantage and corresponding disadvantage.

2. This question is about issues of random access of encryption and decryption. Define notations or symbols you need before providing your answer. Please describe how to use CFB mode and CTR mode to randomly encrypt and decrypt a file Why OFB mode is inappropriate to randomly encrypt and decrypt a file?

3. What is the one-time pad (please provide a figure to explain it) and what is the main security requirement ?

4. Follow

   1. What is the main weakness (disadvantage) of ECB mode ?
   2. How CBC resolves this security problem (explained in mathematical approach) ?

5. Follow

   1. Block ciphers process messages in blocks like an extremely large substitution, but this is very difficult to implement for a very big block size. What is Shannon’s idea to realize a block cipher with big block size ?
   2. Feistel cipher structure provides a real implementation of Shannon’s idea. Please explain the main features of Feistel cipher structure.

6. What is the avalanche effect of a block cipher ?

7. What is the Triple -DES with two keys ? Please explain the process the derive the complexity of meet-in-the-middle attack on Triple-DES with two keys.

8. For all AES round operations, which operation(s) provides substitution and which operations(s) provides diffusion ?

9. Please describe the details of BBS pseudorandom number generator.

10. Below is the pseduo code of RC4. Please design a modified RC4 version with message dependent property of key stream.

1
2
3
4
5
6
7
8
9

init(master_key) // shuffle S-array with master_key
i = j = 0
for each message byte M
    i = (i + 1) mod 256
    j = (j + S[i]) mod 256
    swap(S[i], S[j])
    t = (S[i] + S[j]) mod 256
    C = M xor S[t]

Notes

Part 1

請參照 《資訊安全 小考筆記》

Part 2

請參照 《資訊安全 小考筆記》

Part 3

one-time pad 概念圖如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14

                +------------+               +------------+               
                | random key |               | random key |               
                | generator  |               | generator  |               
                +------------+               +------------+               
                      |                             |                     
                      |                             |                     
                      | Ki                          | Ki                  
                      |                             |                     
                      |                             |                     
       Pi          +--v--+           Ci          +--v--+       Pi         
------------------>+ XOR +---------------------->+ XOR +----------------> 
                   +-----+                       +-----+                  
                                                                          
                   From Alice                    To Blob

one-time pad 主要是靠 key 不重複使用來維護資料安全，但是雙方同時產生出相同的 random key 是很困難。由於不重複使用，靠一個 random key 的產生提供 random mask 消除明文和祕聞之間的關係。但是雙方都要相同 random key 是相當困難的，通常 generator 是由某個偽隨機數產生器，由演算法產生的到底是不是隨機數呢？

一定要 random key，不能有任何的 dependent、 不能重複 (reuse) ，否則會有 已知明文攻擊 。

Part 4

ECB mode 在相同明文對應相同的密文，這容易受到大多數的攻擊，如收集已知明文或密文所進行的攻擊。由於明文和密文的關係明確，也因此在 圖片資料 加密傳送，會出現 大量重複 的密文。

CBC mode 提供 random mask 的效果

從$C_{i-1} \text{ XOR } P_{i}$ 操作中可以發現到，讓相同的明文對應到不同的密文 (在前一個密文不同時)，解決 ECB 在相同明文加密只會對應種密文。

Part 5

Shannon’s idea 請參照 《資訊安全 小考筆記》

Feistel cipher structure 藉由三個規則實作

• 多個回合 (round)
• 藉由一半的訊息加密另一半的訊息
• 兩個半段訊息位置交換

Part 6

Avalanche effect 讓相似的明文 Pi, Pj (漢明距離 $H(Pi, Pj) = 1$ … 之類的) 對應的密文 Ci, Cj 能有相當大的差異 (漢明距離 $H(Ci, Cj) = \text{half-bit}$ 的期望值)，將只有一點不同的差異，擴散到密文的每個地方，放大差異的效果。

Part 7

Triple-DES

當指使用兩次的 DES，受到中間相遇法的攻擊，理論上的複雜度與 1 個 DES 一樣，複雜度大約都在 $O(2^{56})$，因此效果並沒有變得更好。然而在 Triple-DES 複雜度就提升到 $O(2^{112})$。

中間相遇法攻擊

從已知的明文、密文，目標是讓 $X = Y$，窮舉 key，如果發生 $X = Y$ 則表示找到一組可行的解。窮舉得到 $X$ 的複雜度為 $O(2^{56} \times 2^{56}) = O(2^{112})$，而 $Y$ 則需要 $O(2^{56})$，當 $X = Y$ 符合時，則表示 key 找到！

當然也可以抽換相遇的地點，如下是另外一種

不管怎麼切割，都至少要窮舉兩把 key 來得到其中一個相遇結果，複雜度都落在 $O(2^{112})$。如果說對應兩個表的結果需要 $O(log \text{ n})$ 的時間，則複雜度為 $O(112 \times 2^{112})$。

Part 8

比較討厭的是 Shift Rows 為什麼提供是 diffusion，明明對於兩個相似明文加密上，漢明距離沒有增加！但是 diffusion 不只是讓差異數量增加，還要考量差異位置的變動，相鄰差異的位置被轉移到兩個遠處，就能提供 diffusion！這會讓攻擊者無從判定差異的對應。

Part 9

Blum Blum Shub

Part 10

message dependent RC4

第一版本

1
2
3
4
5
6
7
8
9
10
11

i = j = 0, Cprev = 0
for each message byte M
    i = (i + 1) mod 256
    j = (j + S[i]) mod 256
    swap(S[i], S[j])
    t = (S[i] + S[j] + Cprev) mod 256
    C = M xor S[t]
    if sender
        Cprev = C
    if receiver
        Cprev = M

好像不管怎麼寫兩邊似乎都很難相同。

第二版本

1
2
3
4
5
6
7

i = j = 0, C = 0
for each message byte M
    i = (i + C) mod 256
    j = (j + S[i]) mod 256
    swap(S[i], S[j])
    t = (S[i] + S[j]) mod 256
    C = M xor S[t]

感覺上述的寫法，萬一 C 被竄改，會導致錯誤擴散，而且是全部失效，這讓我非常納悶。

Problem

在 AES 中，利用 Galois fields$GF(2^{8})$ 為運算單位，有效地在 8-bits CPU 上高效地實作。

Galois Fields$GF(p^{n})$ 限定在質數 p 的 n 次方，便可存在有限的元素集合，支持加減乘除，同時可以利用 擴充歐幾里算法 得得到乘法反元素。從最簡單的 p = 2 開始看起，將 f(x) 視為一個元素。則

當 p = 2 時，f(x) 就跟一般的二進制數字儲存相同。當選定在 p 的 n 次方時，必須找一個 degree = n 的多項式，不被集合內的任何元素整除，來約束所有的運算保持在一個大小內。特別的是當 p = 2 時，加法和減法是等價運算 (在 p = 2 下，1 乘法反元素是自己本身)。

AES 取 8-bits 作為運算單位的用意很多，其一反元素可以在極小空間內儲存，可以用查表的方式得到。之所以選定 p = 2 的好處在於計算機的儲存架構，若在某些特殊硬體可以支持三進位的情況下，p = 3 則會比較有效率的使用，不然取用 p = 3 在二進制的電腦架構，需要轉換的儲存單位是很沒效率，並且覆蓋的集合大小也沒辦法全部使用。

GF 有什麼好處呢？其一的道理在於加解密設計要 防止線性關係 (線性代數太邪惡，很多種攻擊可以繞過線性關係的運算，拋開未知數也能求解)，對於 AES 的設計概念來說 GF 恰好符合這個條件。

AES

AES 選用$GF(2^{8})$，並且取$m(x) = x^8 + x^4 + x^3 + x + 1$ 作為模數，然後再設計一個以 GF 作為常數類型的多項式 Polynominal

每一個$s_{i}$ 都是一個 8-bits 的儲存單位，也就是說這個多項式是 32-bits 儲存。並且取用$m(x) = x^4 + 1$ 作為多項式的模數。AES 藉由 多項式相乘 ，將 4 個 8-bits 的資料交互影響產生出新的 4 個 8-bits，這在密碼學裡面造成 雪崩效應 。

跟之前講的一樣，GF 一定存在反操作，也就是乘法反元素，因此取用$03 x^{3} + 01 x^{2} + 01 x^{1} + 02$ 其乘法反元素為$0B x^{3} + 0D x^{2} + 09 x^{1} + 0E$。

接著，寫一個程式驗證反元素的計算吧！

備註：GF 裡面套用 GF 相當有趣，感覺可以無限擴充大小，當然任意質數也可以找反元素，但也只有 梅森質數 比較適合在電腦二進制系統中吧？

Sample Input

1

no input

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

00 01 8D F6 CB 52 7B D1 E8 4F 29 C0 B0 E1 E5 C7
74 B4 AA 4B 99 2B 60 5F 58 3F FD CC FF 40 EE B2
3A 6E 5A F1 55 4D A8 C9 C1 0A 98 15 30 44 A2 C2
2C 45 92 6C F3 39 66 42 F2 35 20 6F 77 BB 59 19
1D FE 37 67 2D 31 F5 69 A7 64 AB 13 54 25 E9 09
ED 5C 05 CA 4C 24 87 BF 18 3E 22 F0 51 EC 61 17
16 5E AF D3 49 A6 36 43 F4 47 91 DF 33 93 21 3B
79 B7 97 85 10 B5 BA 3C B6 70 D0 06 A1 FA 81 82
83 7E 7F 80 96 73 BE 56 9B 9E 95 D9 F7 02 B9 A4
DE 6A 32 6D D8 8A 84 72 2A 14 9F 88 F9 DC 89 9A
FB 7C 2E C3 8F B8 65 48 26 C8 12 4A CE E7 D2 62
0C E0 1F EF 11 75 78 71 A5 8E 76 3D BD BC 86 57
0B 28 2F A3 DA D4 E4 0F A9 27 53 04 1B FC AC E6
7A 07 AE 63 C5 DB E2 EA 94 8B C4 D5 9D F8 90 6B
B1 0D D6 EB C6 0E CF AD 08 4E D7 E3 5D 50 1E B3
5B 23 38 34 68 46 03 8C DD 9C 7D A0 CD 1A 41 1C
03 x^3 + 01 x^2 + 01 x^1 + 02 x^0
0B x^3 + 0D x^2 + 09 x^1 + 0E x^0
00 x^3 + 00 x^2 + 00 x^1 + 01 x^0
0B x^3 + 0D x^2 + 09 x^1 + 0E x^0

Solution

暴力實作，模擬運算，不考慮電路架構，用最樸素的方式儲存每一個欄位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304

#include <stdio.h> 
#include <string.h>
// in AES, GF(2^8), m(x) = x^8 + x^4 + x^3 + x + 1
class GaloisField {
public:
    unsigned char v[32];
    int n;
    GaloisField() {
        n = 8;
        memset(v, 0, sizeof(v));
    }
    GaloisField(int val) {
        n = 8;
        memset(v, 0, sizeof(v));
        for (int i = 0; i < 8; i++)
            v[i] = (val>>i)&1;
    }
    GaloisField(const int a[], int an) {
        memset(v, 0, sizeof(v));
        n = 8;
        for (int i = 0; i <= an; i++)
            v[i] = a[i];
    }
    GaloisField operator+(const GaloisField &a) const {
        GaloisField r;
        for (int i = 0; i <= r.n; i++)
            r.v[i] = v[i] xor a.v[i];
        r.normal();
        return r;
    }
    GaloisField operator-(const GaloisField &a) const {
        return (*this) + a;
    }
    GaloisField operator*(const GaloisField &a) const {
        GaloisField r;
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= a.n; j++) 
                r.v[i+j] = r.v[i+j] xor (v[i] and a.v[j]);
        r.normal();
        return r;
    }
    GaloisField shift(int sn) const {
        GaloisField r;
        for (int i = 0; i < n; i++)
            r.v[i + sn] = v[i];
        return r;
    }
    bool operator<(const GaloisField &a) const {
        for (int i = 16; i >= 0; i--) {
            if (v[i] == 1 && a.v[i] == 1)
                return true;
            if (v[i] == 1 && a.v[i] == 0)
                return false;
            if (v[i] == 0 && a.v[i] == 1)
                return false;
        }
        return false;
    }
    GaloisField operator/(const GaloisField &a) const {
        for (int i = 16; i >= 0; i--) {
            if (a.v[i] == 1 && v[i] == 0)
                return GaloisField();
            if (a.v[i] == 0 && v[i] == 1)
                break;
        }
        GaloisField r, b = (*this), c;
        
        for (int i = n; i >= 0; i--) {
            c = a.shift(i);
            if (c < b) {
                r.v[i] = 1;
                for (int j = 16; j >= 0; j--)
                    b.v[j] = b.v[j] xor c.v[j];
            }
        }
        r.normal();
        return r;
    }
    GaloisField operator%(const GaloisField &a) const {
        GaloisField ret = (*this) - (*this) / a * a;
        return ret;
    }
    bool isZero() const {
        for (int i = 16; i >= 0; i--)
            if (v[i])	return 0;
        return 1;
    }
    GaloisField inverse() {
        const int m[] = {1, 1, 0, 1, 1, 0, 0, 0, 1}, mn = 8; // m(x) = x^8 + x^4 + x^3 + x + 1
        GaloisField y(m, mn);
        GaloisField g, a, b;
        
        exgcd((*this), y, g, a, b); // a x + b y = g
        return a;
    }
    void exgcd(GaloisField x, GaloisField y, GaloisField &g, GaloisField &a, GaloisField &b) {
        if (y.isZero()) {
            g = x, a = GaloisField(1), b = GaloisField(0);
        } else {
            exgcd(y, x%y, g, b, a), b = b - (x / y) * a;
        }
    }
    void normal() {
        const int m[] = {1, 1, 0, 1, 1, 0, 0, 0, 1}, mn = 8; // m(x) = x^8 + x^4 + x^3 + x + 1
        for (int i = 16; i - mn >= 0; i--) {
            if (v[i] == 1) {
                for (int j = mn, k = i; j >= 0; j--, k--)
                    v[k] = v[k] xor (m[j]);
            }
        }
    }
    void print() const {
        for (int i = 7; i >= 0; i--) {
            printf("%d", v[i]);
            if (i%4 == 0)	printf(" ");
        }
        puts("");
    }
    int getHbits() const {
        return v[7]<<3 | v[6]<<2 | v[5]<<1 | v[4];
    }
    int getLbits() const {
        return v[3]<<3 | v[2]<<2 | v[1]<<1 | v[0];
    }
};
void testGF() {
    int va[] = {1, 1, 1, 0, 1, 1, 0, 0};
    int vb[] = {0, 1, 0, 0, 0, 0, 1, 0};
    for (int i = 0; i < 256; i++) {
        GaloisField a(i);
        GaloisField b = a.inverse();
        printf("%X%X ", b.getHbits(), b.getLbits());
        if (i%16 == 15) puts("");
    }
}
class GF_Polynominal {
public:
    GaloisField v[32];
    int n;
    GF_Polynominal() {
        n = 4;
        for (int i = 0; i < 16; i++)
            v[i] = GaloisField();
    }
    GF_Polynominal(const GaloisField a[], int an) {
        n = 4;
        for (int i = 0; i <= an; i++)
            v[i] = a[i];
    }
    GF_Polynominal operator+(const GF_Polynominal &a) const {
        GF_Polynominal r;
        for (int i = 0; i <= r.n; i++)
            r.v[i] = v[i] + a.v[i];
        r.normal();
        return r;
    }
    GF_Polynominal operator-(const GF_Polynominal &a) const {
        return (*this) + a;
    }
    GF_Polynominal operator*(const GF_Polynominal &a) const {
        GF_Polynominal r;
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= a.n; j++) 
                r.v[i+j] = r.v[i+j] + (v[i] * a.v[j]);
        r.normal();
        return r;
    }
    GF_Polynominal shift(int sn) const {
        GF_Polynominal r;
        for (int i = 0; i < n; i++)
            r.v[i + sn] = v[i];
        return r;
    }
    bool operator<(const GF_Polynominal &a) const {
        for (int i = 8; i >= 0; i--) {
            if (!v[i].isZero() && !a.v[i].isZero())
                return true;
            if (v[i].isZero() != a.v[i].isZero())
                return false;
        }
        return false;
    }
    GF_Polynominal operator/(const GF_Polynominal &a) const {
        for (int i = 8; i >= 0; i--) {
            if (!a.v[i].isZero() && v[i].isZero())
                return GF_Polynominal();
            if (a.v[i].isZero() && !v[i].isZero())
                break;
        }
        GF_Polynominal r, b = (*this), c;
        
        for (int i = n; i >= 0; i--) {
            c = a.shift(i);
            if (c < b) {
                GaloisField t, x, y;
                for (int j = 16; j >= 0; j--) {
                    if (!c.v[j].isZero()) {
                        y = c.v[j], x = b.v[j];
                        break;
                    }
                }
                t = y.inverse() * x;
//				b.print();
//				c.print();
//				printf("gg %d\n", i);
//				y.print();
//				x.print();
//				y.inverse().print();
//				t.print();
                r.v[i] = t;
                for (int j = 8; j >= 0; j--)
                    b.v[j] = b.v[j] - c.v[j] * t;
            }
        }
//		printf("---> mod "); b.print();
//		puts("");
//		puts("div begin");
//		print();
//		a.print();
//		r.print();
//		(r * a).print();
//		(r * a + b).print();
//		puts("div end\n");
        r.normal();
        return r;
    }
    GF_Polynominal operator%(const GF_Polynominal &a) const {
        GF_Polynominal ret = (*this) - (*this) / a * a;
        return ret;
    }
    bool isZero() {
        for (int i = 8; i >= 0; i--)
            if (!v[i].isZero())	return 0;
        return 1;
    }
    GF_Polynominal inverse() {
        const GaloisField m[] = {GaloisField(1), GaloisField(0), GaloisField(0), GaloisField(0), GaloisField(1)};
        const int mn = 4; // m(x) = x^4 + 1
        GF_Polynominal y(m, mn);
        GF_Polynominal g, a, b;
        
        exgcd((*this), y, g, a, b); // a x + b y = g
        
        return a / g;
    }
    void exgcd(GF_Polynominal x, GF_Polynominal y, GF_Polynominal &g, GF_Polynominal &a, GF_Polynominal &b) {
//		puts("exgcd -----------------");
//		x.print();
//		y.print();
//		getchar();
        if (y.isZero()) {
            const GaloisField m1[] = {GaloisField(1)};
            const GaloisField m0[] = {GaloisField(0)};
            g = x, a = GF_Polynominal(m1, 1), b = GF_Polynominal(m0, 1);
            // a = g.inverse();
        } else {
            exgcd(y, x%y, g, b, a), b = b - (x / y) * a;
        }
    }
    void normal() {
        const GaloisField m[] = {GaloisField(1), GaloisField(0), GaloisField(0), GaloisField(0), GaloisField(1)};
        const int mn = 4; // m(x) = x^4 + 1
        for (int i = 16; i - mn >= 0; i--) {
            if (!v[i].isZero()) {
                GaloisField t = v[i];
                for (int j = mn, k = i; j >= 0; j--, k--)
                    v[k] = v[k] - (m[j] * t);
            }
        }
    }
    void print() const {
        for (int i = 3; i >= 0; i--) {
            printf("%X%X ", v[i].getHbits(), v[i].getLbits());
            printf("x^%d", i);
            if (i)	printf(" + ");
        }
        puts("");
    }
};
void testPoly() {
    const GaloisField m[] = {GaloisField(2), GaloisField(1), GaloisField(1), GaloisField(3)};
    const GaloisField m2[] = {GaloisField(14), GaloisField(9), GaloisField(13), GaloisField(11)};
    const int mn = 3, mn2 = 3;
    GF_Polynominal a(m, mn), b(m2, mn2);
    
    a.print();
    b.print();
    
    GF_Polynominal c = a * b;
    c.print();
    
    GF_Polynominal d = a.inverse();
    d.print();
}
int main() {
    testGF();
    testPoly();
    return 0;
}

Problem

1. Follow

   1. What is a monoalphabetic cipher ?
   2. How large is the key space of the monoalphabetic cipher applied to English (just consider lower case letters) ?
   3. What is the main security weakness of a monoalphabetic cipher ?
   4. Please provide at least 4 approaches to prevent the above weakness.

2. Block ciphers process messages in blocks like an extremely large substitution, but this is very difficult to implement for a very big block size. What is Shannon’s idea to realize a block cipher with big block size ?

3. The S-box of DES round operation is not invertable, but why DES can decrypt ?

4. Follow

   1. Please explain the OFB mode.
   2. In the OFB mode, we never reuse the same sequence (key+IV). If we reuse the key, then the attacker can recover message. Please describe very precisely (mathematiclly with symbols) how the attack works.

5. Please compare the CFB mode the OFB mode by providing a table indicating at least 5 of their advantage and corresponding disadvantage.

6. This question is about issues of random access of encryption and decryption. Define notations or symbols you need before providing your answer. Please describe how to use CFB mode and CTR mode to randomly encrypt and decrypt a file Why OFB mode is inappropriate to randomly encrypt and decrypt a file?

7. Describe the details (as much as you remember) of AES operation and describe how efficiently implement AES on an 8-bit CPU ?

8. How avalanche happens in AES within the first tow rounds ?

Notes

Part 1

monoalphabetic cipher 簡單來說比凱薩加密難一點，從每個字母都 shift 固定的數量來說，變成變動式的。換句話說就是單純的英文字母替換 (substitute)。由於要維持可逆的解密，替換必須符合一對一，所以方法數為 26! = 403291461126605635584000000。

但這種替換方式容易受到語言統計的攻擊，也就是說在英文的特性中，不是每個字母都出現相同的頻率，因為很多冗詞的使用，導致有些字母會特別多。也因此在找對應時，可以藉由這一個觀點，反向查找可能的替換，大幅度地降低搜索可能，讓解密變得相當容易。

為了解決這一語言統計的攻擊，可以藉由

• 壓縮明文，破壞語言特性，但是壓縮算法有儲存的字典部分，仍可能發生字典結構被攻擊，進而進行解壓縮。
• 增加垃圾字，撥點冗詞穿插在其中，把頻率不均的問題消彌。
• 多個字符一起加密，相對於單一字母的替換，可以同時替換兩個以上，如 AA -> WT 之類的。
• 使用多種替換，在不同時刻使用不同的替換表，同樣地可以把頻率問題解決。
• 參照後續區段加密的一些技巧，如 CFB、OFB … 等，讓替換表進行變動。

Part 2

區段加密具有相當大的強度，當一次加密 64 bits 時，可以達到的對應種類高達 (2^64)!，沒有辦法將這種表格存放在記憶體，因為也要消耗 2^64 bits。

因此有 Shannon’s idea，利用 substitution (S-box)、permutation (P-box) 來完成對應，藉由 S-P 的組合，提供 混淆(confusion) 和 差異 (diffusion)。組合的效應遠比想像中的還大，儘管組合的方法數遠小於 (2^64)!，連兆分之一都不到，但簡單的概念可以在 64KB 記憶體大小內完成，效應上算相當划算。

Part 3

DES 的 S-box 屬於不可逆的操作 (8-bits to 6-bits)，然而 DES 在解密時，不需要將 S-box 往回推導，也就是不需要逆向操作，因為加密的 key 來自於 master key 和另一段的訊息 L(i) ，最後用 key 加密 R(i) 得到 L(i+1)。解密時，只需要將 R(i+1) (L(i) 會變成 S(i+1))帶入 S-box，就能重新產生出 key。

至於 DES 為什麼可以正確加解密，定義對於所有的任意明文 A, B，產生的密文 E(A) != E(B)。若明文差異在 L(i)，則在 R(i+1) 一定會不同。若明文差異在 R(i)，則在 key 相同，做 L(i+1) = R(i) XOR key 時，L(i+1) 也必定會不同。

Part 4

為什麼 OFB 不能重新使用 key + IV 呢？原因是因為 已知明文攻擊 (Known plaintext attack) 。假設每一天都重新啟動，那麼攻擊者可以在事後得到密文對應的明文 (可能隔天才知道，儘管對應仍然是很難的)，那麼可以藉由數學概念來完成解密，無須考慮 key 是什麼內容。

假設 i 和 j 重複使用 key，那麼會發生已知密文$C_{i}, C_{j}$ (傳輸上一定會被發現) 和已知明文$P_{i}$，只要夾擊做 XOR，就可以直接得到$P_{j}$，當已知明文相當長時，竊取的效果就越好。

Part 5

比較 CFB 和 OFB。

• 自同步 (self-synchronization) ，不用告知對方加密狀態，可以藉由數次的傳輸訊息，自動地將兩邊的狀態一致，在此之前會造成一段雜訊。斷線時，不必重複使用 IV 讓兩邊同步 (狀態相同時，才能正確解密)。
• 錯誤擴散 (error propagation) ，也因為自同步的設計，導致在同步前都會有雜訊，或者在訊息被攻擊者竄改時，會影響該週期的狀態 ($C_{i-k}, C_{i-k+1}, ..., C_{i-1}$ )。
• 預先計算 (preprocess key) ，預先計算 key 可以加快加解密速度，同時便可支持平行運算，這原因是因為 message-independent/dependent 之間的差異，狀態不依靠正在傳遞的訊息時，就可以預先處理。
• 隨機存取 (random access) ，當要解析某個密文時，CFB 可以往前查找密文$C_{i-k}, C_{i-k+1}, ..., C_{i-1}$，得到當前的解密器所需要的狀態，放上 master key 就能進行解密。OFB 辦不到這一點，狀態不依賴訊息，那就要知道當前是哪個回合，從 IV 開始推導狀態，若密文在第 n 個位置，需要 O(n) 的時間來得到狀態，相對於 CFB 的 O(k) = O(1)來說相當耗時。
• 資訊安全性 (message security) ，由於狀態與訊息獨立，會導致被攻擊者竄改內容時不易發現。在 CFB 中，由於依賴傳遞的訊息，當攻擊者竄改某個密文時會造成錯誤擴散，影響的解密時的明文不只一個，這也讓安全性提高。可以說是一體兩面的特性。

Part 6

• CFB 狀態為 master key +$C_{i-k}, C_{i-k+1}, ..., C_{i-1}$
• CTR 狀態為 master key + counter

CFB 解密某個密文時，往前查找密文即可解密。CTR 知道密文 offset 便可得到 counter。在獲得資訊上都是 O(k) 常數，因此支持隨機存取。

OFB 辦不到這一點，狀態不依賴訊息，那就要知道當前是哪個回合，從 IV 開始推導狀態，若密文在第 n 個位置，需要 O(n) 的時間來得到狀態，相對於 CFB 的 O(k) = O(1)來說相當耗時。

CFB 和 CTR 到底誰的隨機存取能力好呢？若檔案儲存會切割成數個，那 CFB 的隨機存取能力就更高一點。CTR 必須計算 offset，相較於 CFB 的紀錄架構會稍微地麻煩。

Part 7

AES 的計算結構都落在 GF(2^8)，一個 cell 的內容都是 GF(2^8)

• substitue 需要 8-bits to 8-bits
• shift rows 對於 8-bit 關聯不大 (移動記憶體的位置)
• mixColume 上是 8-bits x 8-bits
• add round key 對於每一個 cell XOR 8-bit keys

因此 AES 可以在 8-bits CPU 上有更好的實作效能，所需要的 clock cycle 會比較短。

Part 8

假設有兩個明文的 漢明距離 (Hamming distance) 為 1，在 128 bits 中有一個 1 bits 不同，意即$H(P, Q) = 1$。

• 在 Substitue bytes 步驟時，S-box 會設計成期望當有一個 1-bits 不同，則替換出來的結果會有 4-bits 不同 (一個 cell 具有 8-bits。替換 8-bits 時，差異最少 0 bits、最多 8-bits，期望值是 4-bits)。
• 在 Shift rows 步驟時，單純移動 cell 不影響差異。
• 在 Mix Columes 步驟時，每一個 colume 會根據上一個 colume 的 4 個元素相互影響，因此會增加 4 倍。
• 在 Add Round key 步驟時，由於 XOR 相同的 key，因此差異並不會改變。

最後，在 Round 2 時，能得到平均 64 bits 的差異。加密的明文一次 128 bits，差異期望值也就是一半的情況 64 bits，因此很快地就能達到期望的差異性。在隨後的 Round X 中，差異會在 64-bits 上下浮動都是有可能的。

本篇筆記，僅為個人淺見

什麼是區段加密

先了解 stream ciphers 和 block ciphers 的差異

• stream ciphers 特別在於加密用的 key 不斷地變更，並且以極少數的情況下重複使用，每一次加密針對一個 byte 或者是 bit 進行加密。加解密的兩方，可以同時產生出相同 random key。

• block ciphers 只用同一份 key，把加密文件一次用一個 block 文字進行加密，利用換位 (位置交換)、替換 (文字替換) … 等方式，讓相似內容的明文，可以產出差異極大的密文 (訊息獨立)。

從概念上，串流加密是絕對安全，如果雙方有辦法在不通訊下，可以產生出 random key，而且不重複使用 key，攻擊者會無從下手。但是現今很多 random 的產生方法仍然是演算法的數學模型，因此一定有規則。

而區段加密的好處，在於換位、替換、 … 等方式，將密文的相似度降低，即使明文長得很相似，攻擊者無法誘導相似明文的傳遞，導致 key 快速被發現，因為密文的差異性導致規則難以被破解。

加密設計基礎原則

• confusion 困惑
  密文跟 key 的關係盡可能混亂，根據加密的方式，有可能某些 key 會造成特殊的密文規則，這種弱 key 要不不存在、要不不使用。減少攻擊者對密文的觀察，就可以找到 key。

• diffusion 散播
  當明文相當相似時，也許只有幾個 bit 不同，產生出來的密文的差異性也要相當高，否則攻擊者可以推導加密原理，藉由 bitwise 將密文修改，讓解密者受到誤導。

Data Encryption Standard (DES)

• 每一次加密 64 -bit 的資料，用 56 -bit 的 key。
  這是一個很詭異的現象，通常 key 的長度會比 data 的長度來得大。
• 經過 16 回合的加密，並且每一個回合用 56 -bit 的 key 產生出 48 -bit 的 subkey 針對 64 -bit 的資料加密。
• 加密過程會有擴充 subkey 和選擇一部分的 subkey，並且拿一部分的明文對 subkey 加密。

將明文對切成兩個部分，一部分加密 subkey，另一部分根據加密過的 subkey 進行加密。在下一個回合，交換部分明文和部分密文的位置，讓所有的明文都進入到混亂狀態。

在解密時，知道 subkey 的產生規則，然後拿部分明文，加密 subkey 後，得到部分密文的加密要件，逆推回去。這一個繁複的過程，主要是製造 confusion，而 diffusion 的部分，則是在擴充 key 和拿部分明文加密 subkey 時，發生雪崩效應，因為拿部分明文進行加密 subkey，會造成 key 差異性放大。

儘管明文相似程度很高，卻會因為處理過程將差異轉移到 subkey 很多的位置的不同，經過輪替加密。無法利用頻率的方式，找到明文差異會造成密文的哪一個部分的差異。

正確性

為什麼 DES 可以被正確解密？概念上，一個密文只能對應一個明文，這樣才符合正確解密的定義。因此不同的明文，也要產生出來不同的密文。

證明從輪替下手，部分明文 A 會保留到下一個輪替，而部分明文 A 會加密部分明文 B，假設兩個明文在 A 部分不同，則在密文部分就會不同 (因為保留)，假設是 B 部分不同，加密 (XOR 加密) 後也會不同。數學歸納法得證。

加密強度分析

因為 subkey 產生方式和換位、替換的規格是明定，與 key 無關。因此 key 長短將影響加密的強度，從現在分析 56 -bit 在數個小時內就會被解出來。

為什麼 subkey 產生方式和換位、替換的規格是明定？
因為雪崩效應的造成需要某些放大效果，因此表格要符合某些設計規則。

攻擊方法

• Timing Attacks 加密時間攻擊，因為電腦運算的速度受輸入要件影響，如果 bit 變換數大，會導致加密時間拉長，藉以分析明文。

• Power Attacks 偵測能源消耗，因為運算所需要的能量不同，隨著時間能到得到能源使用圖，就能分析加密過程的情況。也有為了防止這種偵測，考慮將所有運算做得一樣耗電，這有可能本末倒置。

• Analytic Attacks 分析攻擊，從統計學的角度進行攻擊，從密文差異下手、從已知密文、明文解方程式、key 與加密結果的關聯性 … 等。

Block mode

ECB

Electronic CodeBook (ECB)，不變的 key，需要加密器和解密器，加解密的複雜度可能不同。

• 優點：
  構造簡單、容易實做
• 缺點：
  長時間下，容易被偵測。影像資料的差異性不大，很容易被辨識到重複性，相較於文字很容易受前後文的影響。

CBC

Cipher Block Chaining (CBC)，不變的 key，以及前一個密文會先針對明文加密。

• 優點：
  相同明文，會因為前一個的密文不同造就出不同的密文，也就是加密器多一個新的狀態。
• 缺點：
  • 一個密文 Ci 的錯誤，會導致兩個明文解析錯誤 (Pi & Pi+1)。
  • 第一次加密很容易被抽換 bitwise，因為每次驅動的 Initial Vector 都相同。

CFB

Cipher FeedBack (CFB)，類似 CBC，但前一個密文的結果只影響一部分的加密關係，然後將前一段密文狀態加密 key，再對明文加密。

• 優點：
  • 支持即時 (real-time) 通訊
  • 只需要加密器，加密做兩次相當於解密。
  • 支持自同步 (self-synchronization)，即使中斷連線、訊息錯誤，可以在數個週期後再次同步運作。
  • 藉由自同步的概念，可以捨棄掉 Initial Vector。
  • 後半部的明文，可以透過週期性的部分密文建立解密狀態，支持 random access。
• 缺點：
  • error propagation 錯誤增長，當一個訊息錯誤時，需要好幾個週期後才能修正回來，這導致中間的解密訊息都不能用。
  • 雜訊過多的情況下，不宜使用。

OFB

Output FeedBack (OFB)，類似於 CFB，將前一段的加密 key 拿回來加密，不依賴接收的密文狀態。

• 優點：
  • 支持即時 (real-time) 通訊
  • 只需要加密器，加密做兩次相當於解密。
  • 相較於 CFB，沒有錯誤增長的情況。
  • 依序使用的 key，可以事先算出來，然後依次使用。
  • 雜訊下支持的能力好。
• 缺點：
  • 必須一直保持同步
  • 訊息被修改時，不易被發現，只單純影響單一明文 (沒有錯誤增長)。
  • 起始狀態的 Initial Vector，不能重複使用，否則很容易被攻擊者抓到。
  • 加設沒有預先算 key，沒辦法解密出後半部的明文。

CTR

Counter (CTR)，類似於 OFB，直接利用計數器作為加密 key。

• 優點：
  • 加解密可以平行化處理，如果加解密速度耗時，可以選擇這一種。
  • 支持 random access。
• 缺點：
  • 必須一直保持同步
  • 訊息被修改時，不易被發現，只單純影響單一明文 (沒有錯誤增長)。
  • 起始狀態的 Initial Vector，不能重複使用，否則很容易被攻擊者抓到。