加解密模式分析 - ECC 加密算法 | Alice and Bobの神秘小屋

ECC（Elliptic Curve Cryptography）加密算法，作为非对称加密的现代方案之一，基于椭圆曲线上的离散对数问题的困难性，为数据加密和数字签名提供了高效且安全的解决方案。它在实际应用中被广泛采用，尤其是在资源受限的环境中，如移动设备和物联网设备。

在本章中，我们将深入分析 ECC 加密算法的核心原理和实现细节。我们将从 ECC 的数学基础开始，逐步揭示其加密和解密过程中的关键步骤。通过对 ECC 算法的详细解析，你将能够理解它是如何利用椭圆曲线上的离散对数问题的困难性来确保数据安全的。

ECC 加密数学原理 😇

ECC 加密算法的安全性基于椭圆曲线上的离散对数问题的困难性。

椭圆曲线介绍

首先，ECC 定义了一个椭圆曲线 $E_p$，通常采用 Weierstrass 形式的曲线，满足方程 $y^2 = x^3 + ax + b \mod p$，其中 $\Delta = -16(4a^3 + 27b^2) \neq 0$。

这个曲线的数学公式有点复杂，不过可以通过图像来理解。可以进入下面这个链接，改变参数来进行观察椭圆曲线的图像：

椭圆曲线图像

接下来我们介绍一下 ECC 中的群运算。对于椭圆曲线上的点 $A$ 和 $B$，我们定义了点加法和点乘法运算。

点加法是指将两个点 $A$ 和 $B$ 相加得到一个新的点 $C$，即 $C = A + B$。如图所示，点加法的几何意义是：如果 $A$ 和 $B$ 是曲线上的两个点，那么连接 $A$ 和 $B$ 的直线会与曲线相交于第三个点 $C’$，然后以 $C’$ 关于 x 轴的对称点 $C$ 作为结果。

ECC 点加法示例一

如果 $A$ 和 $B$ 是同一个点，那么点加法的结果是 $2A$，即 $C = A + A$。如图所示，点加法的几何意义是：如果 $A$ 和 $B$ 是同一个点，那么连接 $A$ 和 $B$ 的切线会与曲线相交于另一个点 $C’$，然后以 $C’$ 关于 x 轴的对称点 $C$ 作为结果。

ECC 点加法示例二

当然，这个运算是我们定义的，并不是真实存在的运算。我们可以通过一些算法来实现这个运算，比如使用斜率公式来计算点加法的结果。

曲线上的非对称点 $P(x_p,y_p)$ 和 $Q(x_q,y_q)$ 的点加法 $P + Q = R$ 可以通过以下公式计算：

$\begin{align*} \lambda = \frac{y_q - y_p}{x_q - x_p} \mod p \\ x_r = \lambda^2 - x_p - x_q \mod p \\ y_r = \lambda(x_p - x_r) - y_p \mod p \end{align*}$

曲线上的同一点 $P(x_p,y_p)$ 的点加法 $P + P = 2P$ 可以通过以下公式计算：

$\begin{align*} \lambda = \frac{3x_p^2 + a}{2y_p} \mod p \\ x_{2P} = \lambda^2 - 2x_p \mod p \\ y_{2P} = \lambda(x_p - x_{2P}) - y_p \mod p \end{align*}$

本质上就是计算斜率 $\lambda$，然后根据斜率计算出新的点的坐标。

标量积与倍加算法

在 ECC 中，我们还定义了标量积运算，即将一个点 $P$ 与一个整数 $k$ 相乘，得到一个新的点 $Q$，即 $Q = kP$。这个运算可以理解为将点 $P$ 自身相加 $k$ 次。

ECC 标量积示例

倍加算法是一种高效计算标量积的方法，它通过将 $k$ 表示为二进制形式来减少计算次数。具体来说，倍加算法的步骤如下：

将 $k$ 转换为二进制表示。
初始化结果点 $Q$ 为无穷远点。
从二进制表示的最高位开始，依次处理每一位：
- 如果当前位为 1，则将 $Q$ 加上 $P$。
- 将 $P$ 加倍，即 $P = 2P$。
- 继续处理下一位，直到处理完所有位。

倍加算法的时间复杂度为 $O(\log k)$，相较于直接相加的 $O(k)$，大大提高了计算效率。

举个例子，如果我们要计算 $kP$，其中 $k = 151$，如果直接暴力运算，我们要进行 $151$ 次点加法但是，我们可以将 $151$ 转换为二进制表示为 $10010111$。

将 $151$ 转化为二进制：

$151 =1 \cdot 2^0 + 1 \cdot 2^1 + 1 \cdot 2^2 + 0 \cdot 2^3 + 1 \cdot 2^4 + 0 \cdot 2^5 + 0 \cdot 2^6 + 1 \cdot 2^7$

所以我们可以通过倍加算法来计算

$151P = 2^7 P + 2^4 P + 2^2 P + 2^1 P + 2^0 P$

倍加算法告诉我们的是：

取一个 $P$
倍乘，我们得到 $2^1 P$
$2^1 P$ 加 $P$（为了得到 $2^1P + 2^0P$）
$2*2P$，我们得到 $2^2P$
$2^2P$ 加到结果上，（$2^2P + 2^1P + 2^0P$）
$2*2^2P$，得到 $2^3P$
扔掉，$2^3P$ 不参加任何加法运算
$2*2^3P$，得到 $2^4P$
加到结果上，（$2^4P + 2^2P + 2^1P + 2^0P$）
…

最后，我们计算151P只用了7次倍乘和4次加法，极大简化了运算速度。

离散化

现在，我们将这个椭圆曲线放入模 $p$ 的有限域中，这样我们就得到了一个有限的点集。对于这个点集，我们定义了一个特殊的点，称为无穷远点，记作 $O$，它是群的单位元。

这样，我们就得到了一个有限的群，群中的元素是椭圆曲线上的点，群运算是我们之前定义的点加法和标量积。而且，我们发现可视化的曲线变成了一个离散的点集，如下图所示：

ECC 离散化示例

我们之前提到的，ECC 的安全性基于椭圆曲线上的离散对数问题的困难性。对于一个足够大的 $p$ 和一个生成元 $P$，计算 $Q = kP$ 的离散对数 $k$ 是非常困难的。这意味着攻击者无法轻易地从公钥 $Q$ 中推断出私钥 $k$，从而无法解密密文。

就像打台球，知道球的起点和终点，但是由于中途碰了几次边，所以球的路径是非常复杂的，无法通过简单的计算来推断出球的路径。以此，我们可以理解为什么 ECC 的安全性是基于离散对数问题的困难性。

ECC 加密过程 😁

一天，Alice 想要向 Bob 发送一条秘密消息。为了确保消息的安全性，Alice 决定使用 ECC 加密算法。

首先通信双方先共享一个椭圆曲线 $E_p$ 和一个基点 $P$，然后构建椭圆曲线上的群，定义群运算（注意和我们平时的运算不同）。

Alice本地随机生成一个私钥 $k$，并计算公钥 $Q = k P$，将 $Q$ 作为公钥发送给 Bob。

Bob收到 $Q$ 后，选择一个随机数 $r$，计算临时公钥 $C_1 = r P$。然后，计算共享密钥 $K = r Q = r k P$。
选取明文 $M$，将其映射到椭圆曲线上的一个点（如果 $M$ 过大，可以分段加密），计算 $C_2 = M + K$。
Bob将密文对 $(C_1, C_2)$ 发送给 Alice。

Alice收到密文对 $(C_1, C_2)$ 后，计算共享密钥 $K = k C_1 = k r P$。使用共享密钥 $K$ 对 $C_2$ 进行解密，计算 $M = C_2 - K$,，从而恢复出明文 $M$。

ECC 加密算法实现 🥰

下面是一个简单的 ECC 加密算法的 Python 实现示例：

from sage.all import EllipticCurve, GF, randint, random_prime

# 1. 初始化 ECC 参数
# 选取足够大的 p 以容纳消息编码后的整数
# 消息"hello_Alice"约88位，编码需要额外空间，故选取 160 位以上素数
bits = 160
p = random_prime(2^bits, lbound=2^(bits-1))
# 随机选取参数 a, b 保证判别式不为 0
while True:
    a = randint(1, p-1)
    b = randint(1, p-1)
    if (4*a**3 + 27*b**2) % p != 0:
        break

# 定义椭圆曲线 y^2 = x^3 + ax + b mod p
E = EllipticCurve(GF(p), [a, b])
print(f"模数 p (前20位): {str(p)[:20]}...")
print(f"椭圆曲线方程参数 a={a}, b={b}")

G = E.gens()[0] # 基点
n = G.order()   # 基点的阶
print(f"基点 G: {G.xy()}")

# 2. Key Generation (Alice)
# Alice 生成私钥 k
k_private = randint(1, n-1)
# Alice 计算公钥 Q = k * G
Q_public = k_private * G
print(f"Alice 私钥: {k_private}")
print(f"Alice 公钥: {Q_public.xy()}")

# 3. Encryption (Bob)
msg_str = "hello_Alice"

# 辅助函数：将消息映射到椭圆曲线上的点 M
def encode_message(msg, curve):
    m = int.from_bytes(msg.encode(), 'big')
    scale = 100 # 辅助系数
    # 检查消息是否过大导致 x 坐标超过 p
    if m * scale >= int(curve.base_ring().order()):
        raise ValueError(f"消息过大 (数值={m*scale})，超过了模数 p")

    for j in range(scale):
        x = m * scale + j
        try:
            # lift_x 会尝试找到对应的 y，如果 x^3+ax+b 是二次剩余则成功
            P = curve.lift_x(x)
            return P
        except ValueError:
            continue
    raise ValueError("无法将消息编码为曲线上的点")

def decode_message(point, scale=100):
    if point.is_zero():
        raise ValueError("解密得到无穷远点")
    x = int(point[0])
    m = x // scale
    byte_len = (m.bit_length() + 7) // 8
    return m.to_bytes(byte_len, 'big').decode()

M = encode_message(msg_str, E)
print(f"消息 '{msg_str}' 编码后的点 x坐标: {M[0]}")

# Bob 选择随机数 r
r = randint(1, n-1)
# 计算 C1 = r * G
C1 = r * G
# 计算共享密钥 K = r * Q
K_shared = r * Q_public
# 计算密文 C2 = M + K
C2 = M + K_shared

print(f"密文 C1 x坐标: {C1[0]}")
print(f"密文 C2 x坐标: {C2[0]}")

# 4. Decryption (Alice)
# Alice 计算共享密钥 K = k * C1
K_alice = k_private * C1
# 恢复消息点 M = C2 - K
M_decrypted = C2 - K_alice
# 解码消息
decrypted_str = decode_message(M_decrypted)

print(f"解密结果: {decrypted_str}")

简单说明一下辅助系数的意义，椭圆曲线的点必须满足方程 $y^2 = x^3 + ax + b \mod p$，这就意味着：不是所有的 $x$ 都能找到对应的 $y$，只有当 $x^3 + ax + b$ 是模 $p$ 的二次剩余时，才存在对应的点。

这个时候，把整数 $m$ 乘以一个辅助系数（比如 100），然后在这个基础上加上一个小的偏移量 $j$，形成一个区间，我们在这个区间内寻找一个 $x$，使得 $x^3 + ax + b$ 是二次剩余，从而找到一个对应的点。这种方法可以增加找到对应点的概率，同时也能确保消息能够被正确编码为曲线上的点。

举个例子：

假设消息 “hi” 转化成整数 $m$ 是 12345。
scale 设为 100，那么我们会尝试 $x$ 从 $1234500$ 开始，依次增加 $j$（0, 1, 2, …），直到找到一个 $x$ 使得 $x^3 + ax + b$ 是二次剩余。
假设 $x = 1234507$ 满足条件，那么我们就将消息 “hi” 编码为点 $(1234507, y)$，其中 $y$ 是通过方程计算得到的。
解密时， $x = 1234507$，我们通过 $x // scale$ 就能得到原始消息的整数形式 $m = 12345$，然后再转回字符串 “hi”。

上一章：加解密模式分析 - ElGamal 加密算法 👈
下一章：加解密模式分析 - 背包加密算法 👈
回到开始：关于我 👈