前言
幾乎是密碼學基礎數論，看來也走到這了。
亂來
隨便寫寫，上課不專心真是抱歉。
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%)
- condition: $gcd(x, p) = 1$ for multiplcative inverse $x^{-1}$ exist when modulo $p$
- 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$
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$Whais the discrete logarithm problem? (5%)
對於等式 $y = x^a \mod p$，已知三整數 y, x, p，解出 a 的問題。詳見小步大步算法 baby-step-giant-step，複雜度 $O(\sqrt p)$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，提供高效率的加解密效能。
- public-key cryptosystem
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'$。
- 提供訊息修改檢查，相同的訊息進行雜湊，高機率會是不同。
- 容易計算
將一個長度很大的訊息，壓縮一個固定長度的數值，這數值方便後續算法計算用加密算法的部分。
- 單向不可逆
Please write down the RSA public key encryption and decryption process (including public key and private key generation process). (10%)
- $N = p \times q$
- $\phi(N) = (p-1)(q-1)$
- $gcd(\phi(N), e) = 1, \phi(N) > e > 1$
- $d = e^{-1}, e \times d = 1 \mod ø(N)$
- public $e, N$
- private $p, q, d$
Please develop a left-to-right binary exponentiation algorithm without “conditional jump” which is usually dangerous to some engineering attack. (10%)
Montgomery Ladder12345R[0] = 1, R[1] = pfor i = n-1 to 0, step = -1R[1-a[i]] = R[0] * R[1]R[a[i]] = R[a[i]] * R[a[i]]return R[0]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.
- How to generate an integer $g$ ? (5%)
Please complete the following nissing steps of the scheme. (10%)
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 的簽章方法，少了指數次方運算。
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 是否正確，則依循以下步驟來確認- C 拿出
Y<<C>>，拿 Y 的 public key 進行確認 C 的 public key。 - 再檢查 Y 的 public key，Y 拿出
Z<<Y>>，拿 Z 的 public key 進行確認 Y 的 public key。 - 再檢查 Z 的 public key，Z 拿出
X<<Z>>，拿 X 的 public key 進行確認 Z 的 public key。 - 由於我們知道 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
- C 拿出
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 偷偷在私底下做了黑心勾當，那麼中間人攻擊仍是存在的。
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 必須存在比較長的時間。
數位簽章簽定時不知道對方怎麼簽，但能驗證是他簽的並且只有他簽得出來，文件訊息鑑別通常知道對方用什麼流程輸出一樣的數值。
| 類型\性質 | 加密類型 | 輸出訊息 | 碰撞情況 | 重複使用 |
|---|---|---|---|---|
| 文件訊息鑑別 | 普遍上對稱式 | 不管多長都固定長度 | 存在 | 相同輸入 - 相同輸出 |
| 數位簽章 | 非對稱式 | 視情況而定 | 視情況而定 | 相同輸入 - 可能不同輸出 |