密碼學(xué)之消息認(rèn)證碼（MAC）

2021-05-23 02:38 作者:剎那-Ksana- 0人讀過 | 我要投稿

前言

寫一些關(guān)于Message authentication code（簡稱MAC）的東西。內(nèi)容太多了所以準(zhǔn)備分成幾篇文章，這篇文章主要是對MAC進(jìn)行一個大致的方法介紹。

*注意，如下括號里面的中文都是用google translate翻譯過來的，未必專業(yè)。

一、適用情形

MAC的一個基本的功能就是保證密文的integrity（完整性）。假設(shè)我們現(xiàn)在有兩個人A和B進(jìn)行通訊，然后A向B發(fā)送了一段ciphertext（密文），但是這段ciphertext可能會被A和B以外的人C截獲，然后C可以在不破譯ciphertext的情況下，對這段ciphertext進(jìn)行變更（方法有很多種，比如更改某些bit、切換其中的某幾段block的順序）。而B未必知道我們的ciphertext被C給更改了，這個時候我們就希望有一個東西可以驗(yàn)證B收到的內(nèi)容的的確確是A發(fā)送的內(nèi)容。

MAC還可以用于其他情形，比如B需要驗(yàn)證A電腦上某些文件的完整性，這個時候A自己可以任意的更改自己電腦上的文件（比如說游戲存檔），而B不希望A這么做，所以B需要有一個有效的手段來防止A自由地更改文件。

二、基本結(jié)構(gòu)

我們將MAC分為如下的三個算法

Key generation algorithm（密鑰生成算法）Gen：輸入一個security parameter（安全參數(shù)），輸出一個key? $k$ .

Tag generation algorithm（標(biāo)簽生成算法）Mac：輸入一個key? $k$ 和一段message? $m%5Cin%20%5Cleft%5C%7B%200%2C1%20%5Cright%5C%7D%20%5El$ ，輸出標(biāo)簽? $t%3DMac_k(m)$ .

Verification algorithm （驗(yàn)證算法）Verify：輸入一個key? $k$ ，message? $m$ ?和tag $t$ ，輸出一個單一的bit——1代表tag與message相配，0代表tag與message不匹配。

當(dāng)我們手中有key $k$ ，message $m$ 和tag $t$ 后，我們可以再一次執(zhí)行我們的Mac，輸出對應(yīng)的標(biāo)簽 $t'%3DMac_k(m)$ ，然后比較? $t'$ ?與 $t$ ?的值。如果相同，那么我們的 t 和 m 是匹配的。這種驗(yàn)證法方法叫做 canonical verification（規(guī)范驗(yàn)證）.

三、安全性

我們的MAC本身需要有一定的安全性作為保證，假設(shè)我們現(xiàn)在有一名惡意攻擊者C，然后C可以獲取任意的message $m$ 與tag $t$ 的配對，但是C無法從他已獲取的配對中，生成新的 $m$ , $t$ 的配對（這里的“新”指的是C之前沒見過的 $m$ , $t$ 的配對）。

如果MAC具備這個特性，那么我們稱MAC為existentially unforgeable. 以下我都把它稱為“安全的”。

四、建立一個安全的MAC

我們先從message為固定長度出發(fā)，這里我們的key k和我們的message m都是固定的長度n，如果我們需要建立一個安全的MAC，我們只需要讓我們的 $Mac_k(m)$ 是一個pseudorandom function（偽隨機(jī)函數(shù)）。

*注意：pseudorandom function的意思不是指生成偽隨機(jī)數(shù)的函數(shù)，而是指如果攻擊者在無法得知key的情況下，在polynomial-time（多項(xiàng)式時間）內(nèi)無法將此與truly random function區(qū)分開的函數(shù)。比方說，block cipher里面，通過建立一個隨機(jī)表格來進(jìn)行permutation就是一個truly random function.

接下來我們需要一個可以接受任意長度的message的MAC。

在這里，我們想，如果我們把一個message拆分成固定長度的小塊 $m%3D%5Bm_0%2Cm_1%2C...%2Cm_i%5D$ ，每一個小塊通過在我們固定長度的Mac下生成一個tag，最后將tag合并起來，那么我們是不是就可以達(dá)成用固定長度的MAC處理任意長度的message了呢？

但問題是，我們的攻擊者C可以從 $m_0%2Ct_0$ 和 $m_1%2Ct_1$ 中獲得新的組合 $%5Bm_0%2Cm_1%5D%2C%5Bt_0%2Ct_1%5D$ ，所以C在沒有見過 $%5Bm_0%2Cm_1%5D$ 的情況下就知道了它的tag，這違反了我們上述的安全性的條件。

為防止出現(xiàn)上述情況，我們需要在我們的每一個小塊里面添加一些額外信息，確定這個小塊是屬于這段文本，處于這個位置，這個長度。

于是我們就得到了如下的tag generation algorithm：

輸入一個key? $k%5Cin%20%5Cleft%5C%7B%200%2C1%20%5Cright%5C%7D%5En%20$ ?以及一段message? $m%5Cin%20%5Cleft%5C%7B%200%2C1%20%5Cright%5C%7D%20%5El$ ，將m拆分為 $d$ 個長度為 $%5Cfrac%7Bn%7D%7B4%7D%20$ 的小塊，選擇一個identifier? $r%5Cin%20%5Cleft%5C%7B%200%2C1%20%5Cright%5C%7D%20%5E%7Bn%2F4%7D$ , 然后對于每一個小塊 $m_i$ , 計算其對應(yīng)的tag $t_i%3DMac_k'%20(r%2C%20l%2C%20i%2C%20m_i)$ ，最后的tag為 $t%3D%5Br%2Ct_1%2Ct_2%2C...%2Ct_d%5D$ .