前言

写一些关于Message authentication code（简称MAC）的东西。内容太多了所以准备分成几篇文章，这篇文章主要是对MAC进行一个大致的方法介绍。

*注意，如下括号里面的中文都是用google translate翻译过来的，未必专业。

一、适用情形

MAC的一个基本的功能就是保证密文的integrity（完整性）。假设我们现在有两个人A和B进行通讯，然后A向B发送了一段ciphertext（密文），但是这段ciphertext可能会被A和B以外的人C截获，然后C可以在不破译ciphertext的情况下，对这段ciphertext进行变更（方法有很多种，比如更改某些bit、切换其中的某几段block的顺序）。而B未必知道我们的ciphertext被C给更改了，这个时候我们就希望有一个东西可以验证B收到的内容的的确确是A发送的内容。

MAC还可以用于其他情形，比如B需要验证A电脑上某些文件的完整性，这个时候A自己可以任意的更改自己电脑上的文件（比如说游戏存档），而B不希望A这么做，所以B需要有一个有效的手段来防止A自由地更改文件。

二、基本结构

我们将MAC分为如下的三个算法

Key generation algorithm（密钥生成算法）Gen：输入一个security parameter（安全参数），输出一个key .

Tag generation algorithm（标签生成算法）Mac：输入一个key 和一段message ，输出标签 .

Verification algorithm （验证算法）Verify：输入一个key ，message  和tag ，输出一个单一的bit——1代表tag与message相配，0代表tag与message不匹配。

当我们手中有key ，message 和tag 后，我们可以再一次执行我们的Mac，输出对应的标签，然后比较  与  的值。如果相同，那么我们的 t 和 m 是匹配的。这种验证法方法叫做 canonical verification（规范验证）.

三、安全性

我们的MAC本身需要有一定的安全性作为保证，假设我们现在有一名恶意攻击者C，然后C可以获取任意的message 与tag 的配对，但是C无法从他已获取的配对中，生成新的, 的配对（这里的“新”指的是C之前没见过的, 的配对）。

如果MAC具备这个特性，那么我们称MAC为existentially unforgeable. 以下我都把它称为“安全的”。

四、建立一个安全的MAC

我们先从message为固定长度出发，这里我们的key k和我们的message m都是固定的长度n，如果我们需要建立一个安全的MAC，我们只需要让我们的是一个pseudorandom function（伪随机函数）。

*注意：pseudorandom function的意思不是指生成伪随机数的函数，而是指如果攻击者在无法得知key的情况下，在polynomial-time（多项式时间）内无法将此与truly random function区分开的函数。比方说，block cipher里面，通过建立一个随机表格来进行permutation就是一个truly random function.

接下来我们需要一个可以接受任意长度的message的MAC。

在这里，我们想，如果我们把一个message拆分成固定长度的小块，每一个小块通过在我们固定长度的Mac下生成一个tag，最后将tag合并起来，那么我们是不是就可以达成用固定长度的MAC处理任意长度的message了呢？

但问题是，我们的攻击者C可以从和中获得新的组合，所以C在没有见过的情况下就知道了它的tag，这违反了我们上述的安全性的条件。

为防止出现上述情况，我们需要在我们的每一个小块里面添加一些额外信息，确定这个小块是属于这段文本，处于这个位置，这个长度。

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

输入一个key  以及一段message ，将m拆分为个长度为的小块，选择一个identifier , 然后对于每一个小块, 计算其对应的tag ，最后的tag为.

后记

下一篇文章写具体的MAC的算法。

参考资料：

Jonathan Katz; Yehuda Lindell - Introduction to Modern Cryptography

使用工具：DrawIO https://app.diagrams.net/

THE END.