密码学 ｜ 第4章 4.3 Elgamal 数字签名与DSA
Chapter 4 Digital Signatures
4.3 Elgamal Digital Signatures and DSA
在 4.2 一节我们可以看到，我们从 RSA 加密方案转变到 RSA 签名方案，整体上还是比较自然的。但是对于基于离散对数问题的比如 Elgamal 加密方案来说就没那么好转了。
在1985年，推出了一个 Elgamal 版本的电子签名方案，1991 年提出了 **Digital Signature Algorithm (DSA) ** ，并于1994年规范为 **Digital Signature Standard (DSS)**。在这一节，我们先从好理解的 Elgamal 方案开始介绍，随后再解释 DSA 是如何工作的。
Samantha，或者某个可信的第三方，选择一个大素数 ，和一个模 下的原根 。然后 Samantha 再选择一个秘密签名指数 并计算
那么 就组成了 Samantha 的公开验证密钥。
假设现在 Samantha 想要签属文档 ，其中 。她先选择一个数 ，满足 ，然后计算两个值
注意到 是在模 下进行计算的，不是模 ，那么 Samantha 关于文档 的电子签名就是 。
Victor 在验证签名的时候只需要通过计算 是否与
相等即可。
整个流程方案如表 4.2 所示
那么为什么验证可以通过呢，我们来看一下，
所以如果签名 合法，则能通过验证。
注意到我们之前对 的计算是在模 下的，其作为 的指数，我们又知道 ，所以对于表达式 ，我们可以用任意与 在模 下同余的数去替换它。
如果 Eve 知道如何解决离散对数问题，那么他就可以解决 从而获取 Samantha 的签名密钥，继而就可以伪造 Samantha 的签名了。然而，并不清楚这是否是伪造签名的唯一方法。对于 Eve 来说，给到 ，他需要找到 满足
这个式子是一个比较奇怪的问题，因为变量 同时出现在底数和指数上，我们对两边对 求对数，可以写为
注 4.6 使用表面上安全的数字签名方案（如Elgamal）有许多微妙之处。参见 练习4.7和4.8 了解一些可能出错的例子。
例 4.7 Samantha 选择素数 ，原根 ，然后选择签名密钥 并计算公开验证密钥
然后再用随机值 对文档 签名
Samantha 公开签名 和电子文档 。 Victor 验证签名的时候则计算
然后计算
两者相同，验证通过。
一个 Elgamal 的签名 包含一个模 下的元素，和一个模 下的元素，所以长度大约是 比特。那么为了抵抗正对离散对数的 index calculus 攻击，素数 通常需要 1000-2000 比特，所以签名大约为 2000-4000 比特。
DSA 一个比较重要的点就是其通过在 下的具有阶 的一个子群下进行计算从而缩短了签名的长度。其基于的假设是，通过 index calculus 去解在子群下的离散对数问题并不会比解 下的离散对数问题简单，因此，只需取一个子群，并且在该子群中，用BSGS等碰撞算法求解离散对数问题是不可行的即可。现在我们来介绍一下 DSA 的一些细节。
Samantha 或者某可信的第三方，选择两个素数 满足 ，（实际上一般选择 ），
然后选择一个具有阶 的元素 ，这并不难其实。她可以找一个原根 ，然后计算 即可。
接着选一个秘密签名密钥 并计算
那么 和公开参数 就组成了 Samantha 的公开验证密钥。
假设现在 Samantha 想要签属文档 ，其中 。她先选择一个数 ，然后计算两个值
注意到式 和式 还是很像的。但是有一个很重要的不同，就是在计算 的时候，首先计算的是 ，然后再 reduce 到了模 下。 此时，Samantha 对于文档 的电子签名为 ，是两个模 下的元素。
Victor 在验证的时候首先计算
然后验证 是否与 相等。
整体流程如表 4.3 所示
DSA 签名方案看起来好像有点复杂，但是正确性验证还是挺简单的。我们看到验签部分
因此
例 4.8 我们用小一点的数字再来回顾一下 DSA 的整个流程。
Samantha 使用公开参数 ，（元素 是通过 计算而来，其中 7 是模 下的原根）Samantha 选择一个签名密钥 并公开验证密钥
然后 Samantha 使用随机元素 加密文档 ，计算签名
Samantha 公开关于文档 的签名
Victor 验证签名时计算
然后计算
然后
签名验证通过。
Elgamal 数字签名方案 和 DSA 其实都可以使用离散对数问题更难解决的其他群结构，例如使用椭圆曲线群，于是我们引出 **Elliptic Curve Digital Signature Algorithm (ECDSA)**，具体细节我们将在 6.4.3 一节进行介绍。