Skip to main content

椭圆曲线 密码学

椭圆曲线密码学（Elliptic Curve Cryptography, ECC）涵盖了多种基于椭圆曲线数学的算法，主要用于加密、解密、数字签名和密钥交换。以下是一些主要的椭圆曲线算法：

1. 椭圆曲线数字签名算法（ECDSA）​

  • 用途：数字签名
  • 描述：ECDSA 是基于椭圆曲线的数字签名算法，用于提供消息的完整性和身份验证。它是传统的数字签名算法（DSA）的椭圆曲线版本。

2. 椭圆曲线 Diffie-Hellman 密钥交换（ECDH）​

  • 用途：密钥交换
  • 描述：ECDH 是一个密钥交换协议，允许两个通信方在不安全的通道上共享密钥材料，然后可以用这些材料来派生出一个共享的安全密钥。这个过程不传输私钥本身，而是通过椭圆曲线上的点的运算来实现。

3. 椭圆曲线集成加密方案（ECIES）​

  • 用途：加密和解密
  • 描述：ECIES 是一个基于椭圆曲线的公钥加密方案，结合了椭圆曲线密钥交换和对称加密。这种方案通常用于加密数据，确保数据的机密性和安全性。

4. 椭圆曲线 Qu-Vanstone 密钥协商方案（ECMQV）​

  • 用途：密钥协商
  • 描述：ECMQV 是一种改进的椭圆曲线密钥交换协议，提供了额外的安全特性。它是一种双向协议，可以更安全地处理密钥交换过程。

5. Edwards-curve Digital Signature Algorithm（EdDSA）​

  • 用途：数字签名
  • 描述：EdDSA 是一个更现代的数字签名方案，使用特定类型的椭圆曲线（Edwards 曲线）。它被设计为更快、更安全，特别是在抵抗侧信道攻击方面。

6. 椭圆曲线密钥封装机制（EC-KEM）​

  • 用途：密钥封装
  • 描述：EC-KEM 是一种基于椭圆曲线的密钥封装机制，用于安全地封装和解封密钥。这通常用于公钥加密场景，以确保密钥材料的安全传输。

这些算法都利用了椭圆曲线数学的困难问题，如椭圆曲线离散对数问题，来提供安全性。椭圆曲线算法在密码学中的应用广泛，因为它们在相同安全级别下比非椭圆曲线算法需要更短的密钥长度，从而提供了更高的效率和速度。

如何计算​

椭圆曲线密码学算法的核心在于椭圆曲线上的点的运算。椭圆曲线上的点加法和标量乘法是这些算法的基础。这里，我们将探讨几种主要的椭圆曲线算法（ECDSA, ECDH, ECIES, EdDSA）的基本计算方法。

1. 椭圆曲线点的基本运算​

椭圆曲线通常定义为形式 y2=x3+ax+by^2 = x^3 + ax + b 的方程，在有限域 F_p\mathbb{F}\_p 上。点加法和标量乘法是基本运算：

  • 点加法：给定曲线上的两个点 PP 和 QQ，点 R=P+QR = P + Q 是通过找到 PP 和 QQ 的直线，这条直线将与曲线再次相交于第三点 −R-R，然后通过 xx 轴对称得到 RR。
  • 标量乘法：给定曲线上的一个点 PP 和一个整数 kk，点 Q=kPQ = kP 是通过将点 PP 与自己加 k−1k-1 次来计算的。

2. 椭圆曲线 Diffie-Hellman 密钥交换（ECDH）​

  • 密钥生成：每个参与者选择一个私钥 aa（随机数），并计算公钥 A=aGA = aG，其中 GG 是曲线上的一个基点。
  • 密钥交换：两个参与者交换公钥，然后使用自己的私钥和对方的公钥计算共享密钥。例如，如果 Alice 的私钥是 aa 且 Bob 的公钥是 BB，则 Alice 计算 S=aBS = aB。

3. 椭圆曲线数字签名算法（ECDSA）​

  • 签名过程：
    • 选择随机数 kk，计算 (x1,y1)=kG(x_1, y_1) = kG。
    • 计算 r=x1mod  nr = x_1 \mod n 和 s=k−1(H(m)+dr)mod  ns = k^{-1}(H(m) + dr) \mod n，其中 H(m) H(m) 是消息的哈希值，dd 是私钥。
  • 验证过程：
    • 计算 w=s−1mod  nw = s^{-1} \mod n，u1=H(m)wmod  nu_1 = H(m)w \mod n，u2=rwmod  nu_2 = rw \mod n。
    • 验证 (x1,y1)=u1G+u2Q(x_1, y_1) = u_1G + u_2Q 是否满足 x1mod  n=rx_1 \mod n = r。

4. Edwards-curve Digital Signature Algorithm（EdDSA）​

  • 签名过程：
    • 计算随机数 rr 从 H(a∗priv,m)H(a*{priv}, m)（a∗priva*{priv} 是私钥的一部分，mm 是消息）。
    • 计算 R=rGR = rG 和 S=(r+H(R,A,m)⋅a)mod  nS = (r + H(R, A, m) \cdot a) \mod n，其中 AA 是公钥。
  • 验证过程：
    • 验证 S⋅G=R+H(R,A,m)⋅AS \cdot G = R + H(R, A, m) \cdot A。

5. 椭圆曲线集成加密方案（ECIES）​

  • 加密：
    • 选择随机数 kk，计算 R=kG R = kG 和共享密钥 K=kQ K = kQ （QQ 是接收者的公钥）。
    • 使用 KK 作为对称加密的密钥来加密数据。
  • 解密：
    • 使用私钥 dd 计算共享密钥 K=dRK = dR。
    • 使用 KK 解密数据。

这些算法的安全性基于椭圆曲线离散对数问题的难解性，即给定 PP 和 Q=kPQ = kP，很难找到 kk。