《我的第一本算法书》阅读笔记 5-8 消息认证码

Love The Way You Lie 2022-11-16 10:43 163阅读 0赞

消息认证码可以实现“认证”和“检测篡改”这两个功能。密文的内容在传输过程中可能会被篡改，这会导致解密后的内容发生变化，从而产生误会。消息认证码就是可以预防这种情况发生的机制。

--------------------

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70][]

首先，我们来看看什么情况下 需要使用消息认证码。假设A 在B处购买商品，需要将商品 编号abc告诉B。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 1][]

此处，假设A使用共享密钥加 密对消息进行加密。A通过安 全的方法将密钥发送给了B。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 2][]

A使用双方共有的密钥 对消息进行加密。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 3][]

A把 密 文 发 送 给B，B 收到后对密文进行解 密，最终得到了原本的 商品编号abc

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 4][]

以上是没有出现问题时 的流程，然而在这个过 程中可能会发生下面的 情况。

--------------------

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 5][]

假设A发送给B的密文在通信过程中被X恶意篡改了，而B收到密文后没有意识到这个问题

![20210407001638983.png][]

B 对被篡改的密文进行解密，得到消息 xyz。

![20210407001649868.png][]

B 以为 A 订购的是编号为 xyz 的商品，于是将错 误的商品发送给了A。

![2021040700170267.png][]

如果使用消息认证码，就能检测出消息已被篡 改。为了让大家了解实际的处理流程，我们再 一次回到A正要向B发送密文的时候。

--------------------

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 6][]

A生成了一个用于制作消息认证码的密钥，然 后使用安全的方法将密钥发送给了B。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 7][]

接下来，A使用密文和密钥生成一个值。此处生成的是7f05。这个由密钥和密文生成的值就是消息认证码，以下简称为 MAC（Message Authentication Code）。（我们可以把MAC想象成是由密钥和密文组成的字符串的“哈希值”。计算MAC的算法有 HMAC①、OMAC②、CMAC③等。目前，HMAC的应用最为广泛。）

①　Hash-based MAC 的缩写。 ②　One-key MAC 的缩写。 ③　Cipher-based MAC 的缩写。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 8][]

A将MAC（7f05）和密文发送给B。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 9][]

和A一样，B也需要使用密文和密钥来生成MAC。经过对比，B可以确认自己计算出来的7f05和A发来的7f05一致。

![20210407001911587.png][]

接下来，B 只需使用密钥对密文进行解密即可。 最终B成功取得了A发送过来的商品编号abc。

--------------------

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 10][]

X在通信过程中对密文进行了篡改是怎样一种 情况呢？让我们回到A正要向B发送密文的时候。

![2021040700194678.png][]

假设在A向B发送密文和MAC时，X对密文进 行了篡改。

![20210407002001524.png][]

B 使用该密文计算 MAC，得到的值是 b85c，发 现和收到的MAC不一致。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 11][]

由此，B 意识到密文或者 MAC，甚至两者都可能遭到了篡改。于是 B 废弃了收到的密文和 MAC，向 A 提出再次发送的请求。

--------------------

加密仅仅是一个数值计算和处理的过程，所以即使密文被篡改了，也能够进行解密相关的计算。

如果原本的消息是很长的句子，那么它被篡改后意思会变得很奇怪，所以接收者有可能会发现它是被篡改过的。

但是，如果原本的消息就是商品编号等无法被人们直接理解的内容，那么解密后接收者便很难判断它是否被篡改。由于密码本身无法告诉人们消息是否被篡改，所以就需要使用消息验证码来检测。

--------------------

本节以图配文讲解了使用 MAC 检测密文是否被篡改的方法，接着我们来进一步思 考：X 会不会为了让密文的篡改变得合理，而对 MAC 也进行篡改呢？

X 没有计算 MAC 的密钥，所以即便他可以篡改 MAC，也无法让篡改后的密文变得 合理。所以，只要 B 计算出 MAC，发现密文对应的 MAC 与自己算出的不同，就能确认 通信过程中发生了篡改（请参考下图）。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 12][]

就像这样，只要使用消息认证码 MAC，我们就能预防通信过程中的篡改行为。

然而，这种方法也有缺点。在使用消息认证码的过程中，AB 双方都可以对消息进 行加密并且算出 MAC。也就是说，我们无法证明原本的消息是 A 生成的还是 B 生成的。

因此，假如 A 是坏人，他就可以在自己发出消息后声称“这条消息是 B 捏造的”， 而否认自己的行为。如果 B 是坏人，他也可以自己准备一条消息，然后声称“这是 A 发 给我的消息”。

使用 MAC 时，生成的一方和检测的一方持有同样的密钥，所以不能确定 MAC 由 哪方生成。这个问题可以用下一节将会讲到的“数字签名”来解决。

--------------------

《我的第一本算法书》  \[日\]石田保辉 宫崎修一/著    张贝/译

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70]: /images/20221022/785c5d71f09b49228b39f1e967489863.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 1]: /images/20221022/df11e36ff43d49dbb52459407b0e069c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 2]: /images/20221022/f6d14622bab64e379a9c57018abaa64b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 3]: /images/20221022/db98852bcdca473cb4f7bf3a87193b73.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 4]: /images/20221022/2c43758a90f544d7b2693c75652d6593.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 5]: /images/20221022/1f614136ce294bada1220df5aaccd97d.png
[20210407001638983.png]: /images/20221022/578af2454a0b484085c3f45546ca5277.png
[20210407001649868.png]: /images/20221022/09929d3a37294448a620ae99bea8146f.png
[2021040700170267.png]: /images/20221022/332daa4658db43d0a7f28525c8f8b375.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 6]: /images/20221022/d380164a20e2433190fcb56dac699455.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 7]: /images/20221022/d4ffebfa1ce94940bd64cca9487beda0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 8]: /images/20221022/e5c68b64358049aab6a6f7b2b6d26fcc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 9]: /images/20221022/af886d44cd1a47f18736022f8a703f5b.png
[20210407001911587.png]: /images/20221022/80da858063b5493ba52db0dfb2d15651.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 10]: /images/20221022/7d8357fb15094a2592051050f3fc1cbd.png
[2021040700194678.png]: /images/20221022/d1f4a42781344be2a1c8de7eef18d769.png
[20210407002001524.png]: /images/20221022/5653dc6541b941d89c8edee7dac27cca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 11]: /images/20221022/f6fb7236a637448a97bcc80858020327.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 12]: /images/20221022/d2024a9eb1554c48b5c705db4ca0f875.png