# Authentication Technology
> 資料來源：NCKU 李南逸教授之**密碼學**課程－密碼學應用 1。

## 訊息確認（Message Authentication）

### Message Integrity

到目前為止，我們所研究的加密系統提供了 secrecy 或 confidentiality，但沒有提供 integrity。
然而，有時我們可能甚至不需要 secrecy，而是**必須確保 integrity**。

檢查 Integrity 大略如下圖：

#### Cryptographic Hash Function Criteria
一個 Cryptographic Hash Function 必須滿足以下標準：
- Preimage resistance
- Second Preimage resistance
- Collision resistance

##### Preimage Resistance
該雜湊函數，可以抵抗如下圖之 Preimage Attack（即攻擊者「難以反推」雜湊函數輸入值）：

##### Second Preimage Resistance
該雜湊函數，可以抵抗如下圖之 Second Preimage Attack（設一雜湊 $H(x_1) = h_1$，則攻擊者無法找到一 $x_2$，使 $H(x_2) = h_1$）：

##### Collision Resistance
即雜湊函數不太會有「碰撞問題」。

#### Famous Cryptographic Hash Function

##### MD5
任意訊息 -> MD5 -> 128-bit 訊息。


##### SHA-1
- 由 NIST 發展。
- 小於 264-bit 之訊息 -> SHA-1 -> 160-bit 訊息。


### Message Authentication

Message digest 是不能驗證發送者之身分的。
為了提供訊息驗證，發送者需要提供證據，證明是該發送者在發送訊息。

#### Modification Detection Code（MDC）
由 Cryptographic Hash Function 產生的 digest 通常稱為 **Modification Detection Code（MDC）**。


#### Message Authentication Code（MAC）
而「訊息驗證」所需的，是 **Message Authentication Code（MAC）**。
> MAC 的安全性取決於「底層雜湊演算法」的安全性。


#### Nested MAC

#### HMAC

#### CMAC

## 身分認證（Entity Authentication）

一種技術，旨在「讓某方證明另一方的身份」。

而 Message Authentication 和 Entity Authentication 有兩個區別：
- Message Authentication 可能不會「即時」發生；而 Entity Authentication 會。
- Message Authentication 僅對一條訊息進行驗證，該過程需要對每條新訊息重複進行；Entity Authentication 則在「整個會話期間」對聲明者進行驗證。

### Authentication Categories

#### Something possessed
- 條碼卡
- 有一維條碼及二維條碼二種。
- 二維條碼由於可存資料量比一維條碼多很多。
- 磁卡
- 以磁場信號來表示資訊內容，如早期的電話卡及信用卡，優點為成本較低。
- IC 卡
- 由一或數個積體電路所組成，具有記憶功能；資料還可重寫於 IC 卡。
- 常見的有金融卡、IC 電話卡、及便利商店推出之 i-Cash 卡。

#### Something inherent
- 生理結構唯一性
- 人的生理結構有些具有唯一性。
- 例如指紋 (Finger Print)、手形 (Hand Shape)、及眼紋 (Retina Print) 等等均不相同。
- 行為差異性
- 每個人因為音頻、音律、及音量等等不盡相同，因此都有各自獨特的聲音(Voice)。
- 每個人寫字力道、字型、及字體等等不盡相同，因此每個人都有獨特的筆跡。
- 每個人打鍵盤的速度及力道有所差異，且使用滑鼠之習慣亦不盡相同。

#### Something known
- 使用者名稱
- 密碼

### Password-based Authentication

#### Fixed Password 1

#### Fixed Password 2

#### Fixed Password 3

#### Lamport One-time Password

One-Time Password：
1. 使用者與系統達成「一致的密碼列表」。
2. 使用者與系統同意「按順序更新密碼」。
3. 使用者與系統「使用雜湊函數創建」一個按順序更新的密碼。


### Challenge-Response Authentication

概念：聲明者在「無傳送秘密」的情況下，證明其知道該秘密。

#### Using a Symmetric-Key

#### Using Timestamp

#### Bidirectional Challenge

#### Using Keyed-hash function (即 MAC)

#### Using an Asymmetric-Key Cipher

#### Using an Asymmetric-Key Cipher (Bidirectional)

#### Using Digital Signature

#### Using Digital Signature (Bidirectional)

### Zero-knowledge Authentication

概念：聲明者在「無洩漏秘密」的情況下，證明其知道該秘密。

最經典的即「洞穴問題」：玩越多次，Alice 被揪出來的機率越高－每玩一次，猜出來的機率 $* \frac 1 2$。

#### Fiat-Shamir Protocol

- 其發現一難題：$v=s^2\ mod\ n$。
- 先選擇一 $r$，才作 `1`。
- `3`：Random $c = 0\ or\ 1$。
- `6`：算 $y^2\ mod\ n$ 跟 $xv^c\ mod\ n$ 相不相等。
> 如果 $c = 0，則\ r^2=x$
> 如果 $c = 1，則\ r^2*s^2=x*v$
:::info
Alice 可猜 $c$ 為 0 或 1，但若越猜越錯，之後答錯的機率就越來越高。
設猜 $n = 20$ 次，則剩 $(\frac 1 2)^{20}$ 機率答對。
:::

#### Feige-Fiat-Shamir Protocol
> 要改：
`4`：$y=rS_1^{c_1}S_2^{c_2}....S_k^{c_k}\ mod\ n$。
`6`：$r=s^2\ mod\ n$。(from $xv^c\ mod\ n$)

- k 個 c 值一次問完。
- $s_i$, $i=1...k$。
- `3`：$c_i=0\ or\ 1$。
- $v_i=s^2_i\ mod\ n$。

#### Guillou-Quisquater Protocol
> 要改：
`6`：$y^e\ mod\ n$ (from $x$)。
`6`：$xv^c\ mod\ n$ (from $y^ev^c$)。

- $v=S^e\ mod\ n$。
- $c = 1-e$。