08_ECC

1. 椭圆曲线的数学基础 (Mathematical Foundations)

1.1 椭圆曲线方程

• 基本方程：椭圆曲线可定义为所有满足方程 \(y^2 = x^3 + ax + b\) 的点 \((x,y)\) 构成的集合。

• 判别式条件：必须满足 \(4a^3 + 27b^2 \neq 0\)。该条件保证了曲线没有重复的因式（即不包含奇点），确保曲线上任意一点都存在切线。

• 对称性：从方程可以看出，对于任意一个 \(x\)，如果存在解，则必有两个互为相反数的 \(y\) 值，因此曲线始终关于 x 轴对称。

• 其名字的由来是因为曲线方程与计算椭圆周长的公式类似，并非指其图形呈现椭圆形状。

1.2 有限域上的椭圆曲线 (Galois Fields)

• 离散化需求：实数域上的椭圆曲线是连续的，不适合用于密码学加密，必须将其转换为离散的点集。

• 有限域定义：将椭圆曲线定义在有限域上（通常为素数域 \(\mathbb{Z}_p\) 或 Galois 域 \(GF(p)\)，其中 \(p\) 为素数）。有限域中元素的个数称为有限域的阶。

• 方程转换：在有限域 \(GF(p)\) 上，曲线方程变为 \(y^2 \equiv x^3 + ax + b \pmod p\)。

• 坐标约束：曲线上点的坐标 \((x,y)\) 必须满足 \(0 \le x, y < p\)，且均为非负整数。所有超出范围的负数或大数都必须通过取模运算映射回该区间。

2. 椭圆曲线上的运算规则 (Group Operations)

有限域上的椭圆曲线点集合构成一个阿贝尔群，支持以下核心运算。

2.1 几何意义上的点加法 (Point Addition)

图片来源

• 不同点相加 (\(P + Q = R\))：连接点 \(P\) 和点 \(Q\) 形成一条直线，该直线交椭圆曲线于第三点 \(-R\)。作 \(-R\) 关于 x 轴的对称点，即为 \(R\)。

• 相同点相加/倍加 (\(P + P = 2P\))：作点 \(P\) 在曲线上的切线，交曲线于另一点 \(-R\)。作 \(-R\) 关于 x 轴的对称点，得到 \(R = 2P\)。

• 无穷远点 (Point at Infinity, \(O\))：如果 \(P\) 和 \(Q\) 关于 x 轴对称（即横坐标相同，纵坐标互为相反数），它们的连线平行于 y 轴，在无穷远处相交于点 \(O\)。此时 \(P + Q = O\)，即 \(P + (-P) = O\)。

2.2 代数公式计算

设 \(P = (x_1, y_1)\)， \(Q = (x_2, y_2)\)，且 \(P+Q = (x_3, y_3)\)。计算需全程在 \(\pmod p\) 下进行：

1. 计算斜率 \(\lambda\)：

   • 若 \(P \neq Q\)： \(\lambda \equiv \frac{y_2 - y_1}{x_2 - x_1} \pmod p\)。

   • 若 \(P = Q\)： \(\lambda \equiv \frac{3x_1^2 + a}{2y_1} \pmod p\)。

2. 计算目标坐标：

   • \(x_3 \equiv \lambda^2 - x_1 - x_2 \pmod p\)。

   • \(y_3 \equiv \lambda(x_1 - x_3) - y_1 \pmod p\)。

2.3 标量乘法 (Scalar Multiplication)

• 定义：\(Q = kP\)，表示 \(k\) 个 \(P\) 点连续相加 (\(P + P + \dots + P\))。

• 计算优化：采用“先做倍数再做加法”的 Double-and-Add 算法。例如计算 \(151P\)，将 151 转化为二进制 \(10010111_2\)，即可拆解为 \(151P = 2^7P + 2^4P + 2^2P + 2^1P + 2^0P\)。(快速幂)

3. ECC 核心要素与安全基础 (Parameters & Security)

3.1 椭圆曲线六大要素

实际应用中，一条椭圆曲线的确定依赖于 6 个参数：

1. \(p\)：大素数，决定了有限域的大小（取模参数）。

2. \(a\)：曲线方程一次项系数。

3. \(b\)：曲线方程零次项系数。

4. \(G\)：基点 (Base Point) 或生成元 (Generator)，曲线上用于生成密钥的公开起点。

5. \(n\)：基点 \(G\) 的阶 (Order)。即满足 \(nG = O\) 的最小正整数。

6. \(h\)：余因子 (Cofactor)。计算公式为 曲线点的总数 / \(n\)。理想情况下应选取 \(h=1\) 的曲线，以保证整个大群仅有一个子群，提升安全性。

3.2 安全基石：ECDLP 问题

• 定义：椭圆曲线离散对数问题 (Elliptic Curve Discrete Logarithm Problem, ECDLP)。

• 核心逻辑：给定常数 \(k\) 和点 \(P\)，根据加法法则计算 \(Q = kP\) 很容易。但已知公钥点 \(Q\) 和基点 \(P\)，要求反推私钥 \(k\) 是极其困难的（实际应用中素数 \(p\) 取值极大，穷举 \(k\) 不可行）。 (这里的 \(Q\) 是公钥，\(k\) 是私钥，\(P\) 是基点)

由于不同资料中使用的符号不同且存在冲突，以下统一各个量的表示符号：

物理概念	符号	物理含义与约束
基点	\(G\)	椭圆曲线上公开的起点（生成元）
子群的阶	\(n\)	标量运算的取模基数
长期私钥	\(d\)	用户秘密保存的大整数（\(d < n\)）
长期公钥	\(Q\)	曲线上公开的点（\(Q = dG\)）
临时私钥	\(k\)	每次操作随机生成的一次性大整数（\(k < n\)）
临时公钥	\(R\)	曲线上的点（\(R = kG\)）
临时公钥横坐标	\(r\)	标量值，即 \(r = R.x \pmod n\)
消息/明文	\(m\)	需要加密或签名的核心数据/哈希值

• 模数 \(p\) 是给“坐标”取模的，而子群的阶 \(n\) 是给“倍数（私钥）”取模的。

4. 加密与解密过程 (Encryption & Decryption)

4.1 密钥生成

• 私钥 (\(d\))：随机选定一个大整数作为私钥，满足 \(d < n\)。

• 公钥 (\(Q\))：计算 \(Q = dG\)，公钥是椭圆曲线上的一个点。

4.2 加密算法原理

• 方法一：基于点对的加密 (通用 ElGamal 模型)

  • 加密：选择一次性随机数（临时私钥）\(k\)。将消息明文点 \(M\) 转化为密文点对 \(C = (R, S)\)：

    • \(R = kG\) （临时公钥）

    • \(S = M + kQ\) （用对方公钥加密消息）

    • 最终密文对：\(C = (kG, M + kQ)\)

  • 解密：接收方利用自己的长期私钥 \(d\) 解密。计算：

    \[ S - dR = (M + kQ) - d(kG) \]

    由于公钥 \(Q = dG\)，根据乘法交换律，上式等价于：

    \[ M + k(dG) - d(kG) = M + kdG - kdG = M \]

• 方法二：Menezes-Vanstone 机制 (数值乘法验证)

  • 加密：选择随机数 \(k\)。

    1. 计算密文第一部分（临时公钥的横坐标）：\(r = (kG).x\)

    2. 计算密文第二部分：\(s \equiv m \times (kQ).x \pmod n\)（其中 \(Q\) 为接收方公钥）

    3. 最终输出密文对：\((r, s)\)

  • 解密：接收方收到密文 \((r, s)\)：

    1. 利用收到的横坐标 \(r\)，代入曲线方程还原出完整的临时公钥点 \(R = kG\)。

    2. 使用自己的长期私钥 \(d\) 进行点乘，计算共享秘密点：\(d(kG) = k(dG) = kQ\)。

    3. 提取点 \(kQ\) 的横坐标 \((kQ).x\)，通过求逆元执行除法还原明文：

       \[ m \equiv s / (kQ).x \pmod n \]

两种加密方法的共同思想：基于 ECDH 的密钥封装与掩码机制

无论是基于点对的通用模型，还是 Menezes-Vanstone 机制，其底层加密逻辑完全一致，均可概括为“基于椭圆曲线迪菲-赫尔曼（ECDH）密钥交换的混合加密架构”。

• 核心数学基础：标量乘法交换律构建共享秘密

  两种方法均利用了椭圆曲线标量乘法的交换律：\(dR = d(kG) = k(dG) = kQ\)。这一特性使得发送方（利用临时私钥 \(k\) 和接收方公钥 \(Q\)）与接收方（利用长期私钥 \(d\) 和临时公钥 \(kG\)）能够在绝对不泄露私钥的前提下，于通信两端独立计算出同一个共享秘密点 \(kQ\)。

• 非对称架构：临时密钥封装传递 (KEM)

  为了让接收方能够重构共享秘密，发送方必须将“解密线索”传递给对方。两种方法都选择将发送方的临时公钥 \(R = kG\)（或其横坐标）作为附加信息直接暴露在明文中传递。这相当于用非对称加密体系“封装”了一次性会话密钥。

• 对称加密思想：利用共享秘密作为数据掩码 (DEM)

  在计算出共享秘密 \(kQ\) 后，两种方法都将其作为掩码（Mask）对明文 \(m\) 进行混淆（加密）。二者的唯一区别仅仅在于混淆算子的不同：

  • 通用模型：采用代数几何中的点加法进行混淆（\(M + kQ\)）。

  • Menezes-Vanstone：采用有限域上的模乘法进行混淆（\(m \times (kQ).x \pmod n\)）。

• 两种加密体制在本质上是殊途同归的，都是先通过 \(kG\) 传递解密线索，再利用 \(kQ\) 作为“一次性对称密钥”将明文锁死。区别仅在于用“点加”上锁，还是用“模乘”上锁。

5. 数字签名算法 (Digital Signatures)

5.1 ECDSA (椭圆曲线数字签名算法)

• 签名生成：选择随机数 \(k\)。

  1. 计算临时公钥 \(R = kG\)，提取其横坐标作为签名第一部分：\(r = R.x \pmod n\)。

  2. 计算签名第二部分（融合私钥与消息）：\(s \equiv k^{-1}(m + rd) \pmod n\)（其中 \(m\) 为消息 Hash，\(d\) 为长期私钥）。

  3. 最终签名结果为：\((r, s)\)。

• 签名验证：接收方收到消息 \(m\) 和签名 \((r, s)\)，利用签名者的长期公钥 \(Q\) 进行验证。

  • 验证公式：计算点 \(T = (\frac{m}{s})G + (\frac{r}{s})Q\)，检查该点 \(T\) 的横坐标是否满足 \(T.x \pmod n == r\)。

  • 原理证明：将 \(s\) 的定义代入验证公式：

    \[ (\frac{m}{s})G + (\frac{r}{s})Q = \frac{mG + rdG}{s} = \frac{(m + rd)G}{(m+rd)/k} = kG = R \]

    因为计算结果恰好等于临时公钥 \(R\)，其横坐标自然与 \(r\) 匹配。

5.2 ECNR 签名机制 (Nyberg-Rueppel)

• 签名生成：选择随机数 \(k\)。

  1. 计算临时公钥 \(R = kG\)。

  2. 计算签名第一部分（用临时公钥横坐标隐藏消息）：\(r = R.x + m \pmod n\)。

  3. 计算签名第二部分（线性模运算）：\(s \equiv k - r \times d \pmod n\)（其中 \(d\) 为长期私钥）。

  4. 最终签名结果为：\((r, s)\)。

• 签名验证：接收方收到消息 \(m\) 和签名 \((r, s)\)，利用长期公钥 \(Q\) 验证。

  • 验证公式：检查是否满足 \(r - (sG + rQ).x == m \pmod n\)。

  • 原理证明：展开括号内的椭圆曲线点运算：

    \[ sG + rQ = (k - rd)G + r(dG) = kG - rdG + rdG = kG = R \]

    将其代回验证公式：

    \[ r - R.x = (R.x + m) - R.x = m \pmod n \]

6. OpenSSL ECC 编程接口参考手册 (API Reference)

6.1 大数运算类 (BIGNUM)

ECC 的密钥长度（如 192 位、256 位等）远超标准 C 语言类型的限制，必须使用 BIGNUM 结构体进行大数运算。

函数原型	核心作用	用法说明
BIGNUM *BN_new(void); void BN_free(BIGNUM *a);	内存管理	分配与释放大数结构体的内存。
BN_CTX *BN_CTX_new(void);	上下文环境	生成大数运算的临时变量上下文，传递给大多数模运算函数以优化内存。
int BN_hex2bn(BIGNUM **a, const char *str); char *BN_bn2hex(const BIGNUM *a);	进制转换	BN_hex2bn 将 16 进制字符串转为大数（如加载固定的曲线参数）；BN_bn2hex 将大数转为 16 进制字符串以便打印输出。
BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret);	数据加载	将二进制数组（如明文数据 plaintext）转换为大数参与加密计算。
int BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx);	模加法运算	计算 \(r \equiv a + b \pmod m\)。常用于计算签名要素。
int BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx);	模乘法运算	计算 \(r \equiv a \times b \pmod m\)。
BIGNUM *BN_mod_inverse(BIGNUM *r, const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx);	求乘法逆元	计算 \(r \equiv a^{-1} \pmod n\)。ECC 中禁止直接除法，如需计算 \(m/s\)，必须先用此函数求出 \(s\) 的逆元，再通过 BN_mod_mul 执行乘法。
int BN_rand(BIGNUM *rnd, int bits, int top, int bottom);	生成随机数	生成指定 bits 长度的随机大数。常用于生成加密过程中的随机数 \(k\)。

6.2 曲线与群操作类 (EC_GROUP)

用于初始化与配置椭圆曲线方程及群参数（对应椭圆曲线六大要素）。

函数原型	核心作用	用法说明
EC_GROUP *EC_GROUP_new(const EC_METHOD *meth);	创建曲线群	初始化一个新的群结构。通常传入 EC_GFp_mont_method() 表示使用基于素数域 \(GF(p)\) 并采用蒙哥马利乘法优化的算法。
int EC_GROUP_set_curve_GFp(EC_GROUP *group, const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx);	设置曲线三要素	定义曲线方程 \(y^2 = x^3 + ax + b \pmod p\)。需要传入已初始化的群对象以及参数 \(p, a, b\)。
int EC_GROUP_set_generator(EC_GROUP *group, const EC_POINT *generator, const BIGNUM *order, const BIGNUM *cofactor);	设置生成元	定义群的后三要素：基点 \(G\) (generator)、基点的阶 \(n\) (order) 以及余因子 \(h\) (cofactor，工程中常设为 BN_value_one() 即 \(1\))。

6.3 椭圆曲线点操作类 (EC_POINT)

用于执行点加、标量乘法、坐标解析等几何与代数运算。

函数原型	核心作用	用法说明
EC_POINT *EC_POINT_new(const EC_GROUP *group);	创建点实例	为曲线上的一个点分配内存，此时点内坐标为空。
int EC_POINT_set_affine_coordinates_GFp(const EC_GROUP *group, EC_POINT *p, const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx);	设置仿射坐标	在已知完整横纵坐标 \((x, y)\) 的情况下，将其赋给指定的点 \(P\)。常用于配置基点 \(G\)。
int EC_POINT_get_affine_coordinates_GFp(const EC_GROUP *group, const EC_POINT *p, BIGNUM *x, BIGNUM *y, BN_CTX *ctx);	提取仿射坐标	从点实例中提取出实际的大数坐标 \((x, y)\)，常用于获取点乘后结果的横坐标 \(x\)。
int EC_POINT_set_compressed_coordinates_GFp(const EC_GROUP *group, EC_POINT *p, const BIGNUM *x, int y_bit, BN_CTX *ctx);	设置压缩坐标	核心解密函数。在仅已知横坐标 \(x\) 时调用。函数内部自动代入曲线方程求解两个可能的 \(y\) 值。y_bit 为 0 时选取偶数根，为 1 时选取奇数根。
int EC_POINT_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *n, const EC_POINT *q, const BIGNUM *m, BN_CTX *ctx);	标量乘法运算	完整形态计算 \(R = n \times G + m \times Q\)。 1. 仅基点标量乘 (\(kG\))：将 q 和 m 置为 NULL。 2. 仅普通点标量乘 (\(kR\))：将 n 置为 NULL。 3. 组合运算：在 ECDSA 验证签名阶段，可一次性算出 \((m/s)G + (r/s)R\)。
int EC_POINT_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx);	点加法	执行基础的椭圆曲线点相加运算 \(R = A + B\)。
int EC_POINT_set_to_infinity(const EC_GROUP *group, EC_POINT *point);	设为无穷远点	将点置为无穷远点（零点 \(O\)）。切忌直接对点指针赋值为 NULL 或 0。