《我的第一本算法书》阅读笔记 5-9 数字签名

蔚落 2022-11-16 10:44 196阅读 0赞

数字签名不仅可以实现消息认证码的认证和检测篡改功能，还可以预防事后否认问题的发 生。由于在消息认证码中使用的是共享密钥加密，所以持有密钥的收信人也有可能是消息的发 送者，这样是无法预防事后否认行为的。而数字签名是只有发信人才能生成的，因此使用它就 可以确定谁是消息的发送者了。

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70][]

首先，我们来看一看数字 签名的特征。假设A要向 B发送消息。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 1][]

在发送前A给消息加上数 字签名。数字签名只能由 A生成。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 2][]

只要发送的消息上有A的数字签名，就能确定消息的发送者就是A。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 3][]

B可以验证数字签名的正确性，但无法生成数 字签名。

![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][]

我们先来复习一下前面 的 知 识。 公 开 密 钥 加 密 中，加密使用的是公开密 钥 P ，解密使用的是私 有密钥 S 。任何人都可以 使用公开密钥对数据进行 加密，但只有持有私有密 钥的人才能解密数据。然 而，数字签名却是恰恰相 反的。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 6][]

下面，我们就来看一看使 用了数字签名的消息交换 流程。首先由A准备好需 要发送的消息、私有密钥 和公开密钥。由消息的发 送者来准备这两个密钥， 这一点与公开密钥加密有 所不同。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 7][]

A将公开密钥发送给B。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 8][]

A使用私有密钥加密消息。加密后的消息就是 数字签名。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 9][]

A将消息和签名都发送给了B。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 10][]

B使用公开密钥对密文（签名）进行解密。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 11][]

B对解密后的消息进行确认，看它是否和收到的消息一致。流程到此结束。

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

在步骤 07~ 步骤 12 中，生成的是“只能由持有私有密钥的 A 来加密，但只要有公 开密钥，谁都可以进行解密的密文”。这个密文作为密码似乎没有任何意义。但是换一个 角度来看就会发现，它可以保证这个密文的制作者只能是持有私有密钥的 A。

在数字签名中，是将“只能由 A 来加密的密文”作为“签名”来使用的。严格来说，也有使用加密运算以外的计算方法来生成签名的情况。但是，用私有密钥生成签名、 用公开密钥验证签名这一机制是相同的，所以为了方便我们就以上文的方式进行了说明。

在公开密钥加密中，用公开密钥加密的数据都可以用私有密钥还原。而本节讲解的 数字签名利用的是用私有密钥加密的数据，用公开密钥解密后就能还原这一性质。也就 是说，即使密钥的使用顺序不同，运行结果也都是一样的。并不是所有的公开密钥加密 都具有这个性质，不过 RSA 加密算法是可以的。

能够用 A 的公开密钥解密的密文，必定是由 A 生成的。因此，我们可以利用这个结 论来确认消息的发送者是否为 A，消息是否被人篡改。

由于 B 只有公开密钥，无法生成 A 的签名，所以也预防了“事后否认”这一问题的 发生。

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

公开密钥加密的加密和解密都比较耗时。为了节约运算时间，实际上不会对消息直接进行加密，而是先求得消息的哈希值，再对哈希值进行加密，然后将其作为签名来使用（请参考下图）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 12][]

虽然数字签名可以实现“认证”“检测篡改”“预防事后否认”三个功能，但它也有 一个缺陷。

那就是，虽然使用数字签名后 B 会相信消息的发送者就是 A，但实际上也有可能是 X 冒充了 A。

其根本原因在于使用公开密钥加密无法确定公开密钥的制作者是谁。收到的公开密 钥上也没有任何制作者的信息。因此，公开密钥有可能是由某个冒充 A 的人生成的。

使用下一节将要讲到的“数字证书”就能解决这个问题。

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

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70]: /images/20221022/d7806ffb48fe480db61e39c877eee4fa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 1]: /images/20221022/b7e9f061aea14df093f62e3a7fe7a90b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 2]: /images/20221022/306d454a8aa245dfbca81fae0f71488c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 3]: /images/20221022/14227b34cf654870b4a2ad54c9e8aa5d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 4]: /images/20221022/7df0f73a9c414dcf884f792587426ae7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 5]: /images/20221022/a71a247afb034564b36faf2a8d8108c5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 6]: /images/20221022/ad7a2fcbe7f74f86a3ebbe3e075b9c77.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 7]: /images/20221022/45fe87ba40cb40cbbe7e54654963071d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 8]: /images/20221022/5947ea8cde714c40b127bf9c25875f82.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 9]: /images/20221022/ed84cb397df2470aa466f913630e6684.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 10]: /images/20221022/d6aa9d93ff504b9082b6026dd765f64e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 11]: /images/20221022/42f5b0922b584fa799efd11d65027428.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 12]: /images/20221022/9fddf03508d74eec94b9ecc31c121f68.png