ECC(椭圆曲线加密)

标签（空格分隔）： ECC

简介

ECC 全称为椭圆曲线加密，EllipseCurve Cryptography，是一种基于椭圆曲线数学的公钥密码。与传统的基于大质数因子分解困难性的加密方法不同，ECC 依赖于解决椭圆曲线离散对数问题的困难性。它的优势主要在于相对于其它方法，它可以在使用较短密钥长度的同时保持相同的密码强度。目前椭圆曲线主要采用的有限域有

以素数为模的整数域 GF(p)，通常在通用处理器上更为有效。
特征为 2 的伽罗华域 GF（2^m），可以设计专门的硬件。

##基本知识
我们首先来了解一下有限域上的椭圆曲线，有限域上的椭圆曲线是指在椭圆曲线的定义式

$y^2+axy+by = x^3 + cx^2 + dx +e$

在以域为P下的方程也就是GF(p)
并非所有的方程都适用于加密，最常用的加密就是

$y^2 = x^3 +ax+b$

运算相关

注意：所有运算都是在 GF(p) 中，除法实际上是乘以模逆元
在一条曲线的点的相乘和相加是特殊的

两点相加

1
2
3
4
5
6
# 已知 P = (x1, y1), Q = (x2, y2)
# 计算 R = (x3, y3)

λ = (y2 - y1) / (x2 - x1)    # 斜率
x3 = λ² - x1 - x2
y3 = λ(x1 - x3) - y1

点的倍乘

1
2
3
4
5
6
# 已知 P = (x1, y1), y1 ≠ 0
# 计算 2P = (x3, y3)

λ = (3x1² + a) / (2y1)       # 切线斜率
x3 = λ² - 2x1
y3 = λ(x1 - x3) - y1

二进制分解算法

ECC 公钥计算的核心是标量乘法：K = k × G
初始化结果点 R = O（无穷远点，加法单位元）
从二进制最高位到最低位遍历：
每一步先将当前结果 加倍：R = 2R
如果当前位为 1，再 加上基点：R = R + G
遍历结束后，R 就是 k × G

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def scalar_multiply(k, G, p, a):
    """计算 k × G"""
    binary_k = bin(k)[2:]  # 转换为二进制字符串
    R = None  # 无穷远点
    current = G
    
    for bit in reversed(binary_k):  # 从最低位开始
        if bit == '1':
            if R is None:
                R = current
            else:
                R = point_add(R, current, p, a)
        current = point_double(current, p, a)
    
    return R