資訊安全 小考 2 筆記

contents

  1. 1. Problem
  2. 2. Notes
    1. 2.1. Part 1
    2. 2.2. Part 2
    3. 2.3. Part 3
    4. 2.4. Part 4
    5. 2.5. Part 5
    6. 2.6. Part 6

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

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$

用來加解密,為什麼會是正確的呢?

$$\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 作範例

  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 算法就會被破解。