2015-05-29

學校課程/資訊安全

資訊安全小考 2 筆記

1. Problem
2. Notes

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

Problem

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).

Notes

Part 1

基礎步驟如下

(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 算法的產生與加解密

select two large primes $p$ and $q$ at random.
Let $N = p \times q$, $\phi(N) = (p-1)(q-1)$
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
solve following equation to find decryption key $d = e^{-1}$, $e \times d \mod \phi(N)=1$
publish public/encryption key:$KP = \left \{ e,N \right \}$
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$

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

$$\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}$$

這裡很神祕，假設 $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 作範例

$N = p \times q$
目標計算 $M = C^d \mod N$
分開計算得到兩個部分，這裡可以利用歐拉定理加快，因此 $d$ 可以先 $\mod \phi(p)$
$Mp = C^d \mod p$ $Mq = C^d \mod q$
套用中國餘式定理 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$
因此 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 算法就會被破解。

Morris' Blog