6.4.2 Elliptic Elgamal Public Key Cryptosystem
同样的我们也能够很轻易的将椭圆曲线应用到 2.4 一节介绍的 Elgmal 公钥密码系统中。简单来说， Bob 和 Alice 首先协商一个公用的素数 和 曲线 ，以及基点 。Alice 选择一个秘密乘数 ，并公开点 作为她的公钥。Bob 的信息转化为一个在曲线 上的点 ，他选择一个随机数 并计算
整个过程如表 6.6 所示
理论上我们使用椭圆曲线结构的 Elgmal 公钥密码系统没有什么问题，但是这里有几点实践起来会比较困难：
-
没有一个公认的方法将一段消息映射到椭圆曲线 的一个点上。
-
椭圆曲线下的 Elgmal 密码系统具有 4:1 的消息拓展（即传递一个单位的信息需要发送四个单位的数据），相比之下有限域 下的椭圆曲线只有 2:1 的消息拓展。
根据 Hasse 定理（定理 6.11），椭圆曲线 下大约有 个点，因此只能映射 个不同的明文消息。
而之所以椭圆曲线下的 Elgmal 密码系统具有 4:1 的消息拓展，是因为密文 ，每个点包含 2 个坐标，因此总共有4个模 下的数。而消息一般只映射到一个点的单个坐标中（例如 坐标）
为此，人们已经提出了各种方法来解决这些问题。例如，通过随机选择 并将其用作实际明文的掩码（与明文异或），可以避免如何将明文与点相关联的困难。另外，也有相应的减少消息扩展的方法。
为了减少消息拓展，一个很自然的想法就是只发送密文 的 轴坐标，不过，由于 Alice 需要计算 ，所以他需要正确的 的 轴坐标以及 轴坐标。（注意 和 是两个完全不一样的点）但是，由于 轴坐标决定了 坐标的绝对值，因此 Bob 可以再额外发送一个 比特信息，例如，如果 ，则额外比特为 0；如果 ，则额外比特为 1。这样，Bob只需要发送 和 的 轴坐标，再加上两个额外的比特。这种想法有时被称为点压缩。
6.4.3 Elliptic Curve Signatures
表6.7中描述的椭圆曲线数字签名算法（ECDSA）是第4.3一节中表4.3中描述的数字签名算法的直接模拟。ECDSA在现实中被广泛使用，特别是（但不仅限于）在签名大小很重要的情况下。《Table 6.7: The elliptic curve digital signature algorithm (ECDSA)》，《Standards for Efficient Cryptography, SEC 2: recommended elliptic curve domain parameters (Version 1)》中描述了实施ECDSA的官方规范。（另请参阅第8.8节，了解现实世界中如何使用ECDSA实现数字现金）
为了证明ECDSA有效，即验证步骤成功验证了有效签名，我们计算
原文始发于微信公众号（山石网科安全技术研究院）：密码学｜6.4.2 椭圆Elgamal公钥密码系统
评论