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$
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 Ladder
1
2
3
4
5
R[0] = 1, R[1] = p
for i = n-1to0, step = -1
R[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^-1mod q
k is arandominteger 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 thenthe signature is correct
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
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}$ 進行通訊加密。
產生兩把 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 必須存在比較長的時間。 數位簽章簽定時不知道對方怎麼簽，但能驗證是他簽的並且只有他簽得出來，文件訊息鑑別通常知道對方用什麼流程輸出一樣的數值。
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$?
Please explain link encryption and end-to-end encryption.
(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?
(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.
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”)
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).
$$\begin{align}
& M \equiv (M^e)^d \mod N \\
& M \equiv M^{ed} \mod N \\
& \because ed \equiv 1 \mod \phi(N) \text{ and Euler's theorem} \\
& \therefore M \equiv M^{ed \mod \phi(N)} \mod N \\
& M \equiv M^{1} \mod N
\end{align}$$
