# 資訊安全 小考 2 筆記

## 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$?

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 2

• end-to-end encryption 屬於原點、目的地之間的加密，它們共同享有一把 shared key，屬於高階網路層協定，用來保護資料安全，訊息 header 保留給傳輸用。

### Part 3

Fermat’s theorem :

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

### Part 4

Euler’s theorem

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

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}