easy_ECC：
已知椭圆曲线加密 Ep(a,b)参数为
p = 15424654874903
a = 16546484
b = 4548674875
G(6478678675,5636379357093)
私钥为
k = 546768
求公钥 K(x,y)
、
对于 ECC 系统来说，完成运行系统所必须的群操作比同样大小的因数分解系统或
模整数离散对数系统要慢。不过，ECC 系统的拥护者相信 ECDLP 问题比 DLP 或因数分
解问题要难的多，并且因此使用 ECC 能用小的多的密钥长度来提供同等的安全，在这
方面来说它确实比例如 RSA 之类的更快。到目前为止已经公布的结果趋于支持这个结
论，不过一些专家表示怀疑。
ECC 被广泛认为是在给定密钥长度的情况下，最强大的非对称算法，因此在对带宽要求
十分紧的连接中会十分有用。
美国国家标准与技术局和 ANSI X9 已经设定了最小密钥长度的要求，RSA 和 DSA
是 1024 位，ECC 是 160 位，相应的对称分组密码的密钥长度是 80 位。NIST 已经公布
了一列推荐的椭圆曲线用来保护 5 个不同的对称密钥大小（80, 112, 128, 192, 256）。一
般而言，二进制域上的 ECC 需要的非对称密钥的大小是相应的对称密钥大小的两倍。
椭圆曲线阿贝尔群：
我们已经看到了椭圆曲线的图象，但点与点之间好象没有什么联系。我们能不能建立一个类
似于在实数轴上加法的运算法则呢？这就要定义椭圆曲线的加法群，这里需要用到近世代数
中阿贝尔群。
在数学中，群是一种代数结构，由一个集合以及一个二元运算所组成。已知集合和运算(G,)
如果是群则必须满足如下要求
封闭性：∀a,b∈G，ab ∈ G
结合性： ∀a,b,c∈G ，有 (ab)c = a* (b*c)
单位元：ョ e∈G， ∀a ∈G，有 ea = ae = a
逆元： ∀a ∈G ，ョ b∈G 使得 ab = ba = e
阿贝尔群除了上面的性质还满足交换律公理 a * b = b * a
同样在椭圆曲线也可以定义阿贝尔群。
任意取椭圆曲线上两点 P、Q（若 P、Q 两点重合，则作 P 点的切线），作直线交于椭圆曲线
的另一点 R'，过 R'做 y 轴的平行线交于 R，定义 P+Q=R。这样，加法的和也在
椭圆曲线上，并同样具备加法的交换律、结合律
椭圆曲线上的加法：
我们已经看到了椭圆曲线的图象，但点与点之间好象没有什么联系。我们能不能建立一个类
似于在实数轴上加法的运算法则呢？天才的数学家找到了这一运算法则。 自从近世纪代数
学引入了群、环、域的概念，使得代数运算达到了高度的统一。比如数学家总结了普通加法
的主要特征，提出了加群（也叫交换群，或 Abel（阿贝尔）群），在加群的眼中。实数的加
法和椭圆曲线的上的加法没有什么区别。这也许就是数学抽象把：）。关于群以及加群的具体
概念请参考近世代数方面的数学书。 运算法则：任意取椭圆曲线上两点 P、Q （若 P、Q 两
点重合，则做 P 点的切线）做直线交于椭圆曲线的另一点 R’，过 R’做 y 轴的平行线交于 R。
我们规定 P+Q=R。
同点加法：
若有 k 个相同的点 P 相加，记作 kP
P+P+P=2P+P=3P
椭圆曲线上简单的加密/解密：
公开密钥算法总是要基于一个数学上的难题。比如 RSA 依据的是：给定两个素数
p、q 很容易相乘得到 n，而对 n 进行因式分解却相对困难。那椭圆曲线上有什么难题
呢？
考虑如下等式： K=kG [其中 K,G 为 Ep(a,b)上的点，k 为小于 n（n 是点 G 的阶）的整
数] 不难发现，给定 k 和 G，根据加法法则，计算 K 很容易；但给定 K 和 G，求 k 就相
对困难了。这就是椭圆曲线加密算法采用的难题。我们把点 G 称为基点（base point），
k（k<n，n 为基点 G 的阶）称为私有密钥（privte key），K 称为公开密钥（public key)。
现在我们描述一个利用椭圆曲线进行加密通信的过程： 1、用户 A 选定一条椭圆
曲线 Ep(a,b)，并取椭圆曲线上一点，作为基点 G。 2、用户 A 选择一个私有密钥 k，并
生成公开密钥 K=kG。 3、用户 A 将 Ep(a,b)和点 K，G 传给用户 B。 4、用户 B 接到信
息后 ，将待传输的明文编码到 Ep(a,b)上一点 M（编码方法很多，这里不作讨论），并产
生一个随机整数 r（r<n）。 5、用户 B 计算点 C1=M+rK；C2=rG。 6、用户 B 将 C1、C2
传给用户 A。7、用户 A 接到信息后，计算 C1-kC2，结果就是点 M。因为 C1-kC2=M+rKk(rG)=M+rK-r(kG)=M 再对点 M 进行解码就可以得到明文。
在这个加密通信中，如果有一个偷窥者 H ，他只能看到 Ep(a,b)、K、G、C1、C2 而
通过 K、G 求 k 或通过 C2、G 求 r 都是相对困难的。因此，H 无法得到 A、B 间传送的
明文信息。
脚本代码：
import collections
import random
EllipticCurve = collections.namedtuple('EllipticCurve', 'name p a b g n h')

namedtuple 主要用来产生可以使用名称来访问元素的数据对象，通常用来增强代码的可

读性， 在访问一些 tuple 类型的数据时尤其好用。
curve = EllipticCurve(
'secp256k1',
p=int(input('p=')),

曲线系数

a=int(input('a=')),
b=int(input('b=')),

基本点

g=(int(input('Gx=')),
int(input('Gy='))),

子组顺序

n=int(input('k=')),

子组辅因子

h=1,
)

模运算

def inverse_mod(k, p):
"""返回 k 模 p 的逆。
此函数只返回（x*k）%p==1 的整数 x。
k 必须非零，p 必须是素数。
"""
if k == 0:
raise ZeroDivisionError('division by zero')#除数为 0
if k < 0:

k ** -1 = p - (-k) ** -1 (mod p)

return p - inverse_mod(-k, p)

扩展欧几里德算法。

s, old_s = 0, 1
t, old_t = 1, 0
r, old_r = p, k
while r != 0:
quotient = old_r // r
old_r, r = r, old_r - quotient * r
old_s, s = s, old_s - quotient * s
old_t, t = t, old_t - quotient * t
gcd, x, y = old_r, old_s, old_t
assert gcd == 1
assert (k * x) % p == 1
return x % p

用于曲线点的函数

def is_on_curve(point):
"""如果给定点位于椭圆曲线上，则返回 True。"""
if point is None:

无表示无穷远点。

return True
x, y = point
return (y * y - x * x * x - curve.a * x - curve.b) % curve.p == 0
def point_neg(point):
"""返回-点。 """
assert is_on_curve(point)
if point is None:

-0 = 0

return None
x, y = point
result = (x, -y % curve.p)
assert is_on_curve(result)
return result
def point_add(point1, point2):
"""根据分组法返回 point1+point2 的结果。 """
assert is_on_curve(point1)
assert is_on_curve(point2)
if point1 is None:

0 + point2 = point2

return point2
if point2 is None:

point1 + 0 = point1

return point1
x1, y1 = point1
x2, y2 = point2
if x1 == x2 and y1 != y2:

point1 + (-point1) = 0

return None
if x1 == x2:

This is the case point1 == point2.

m = (3 * x1 * x1 + curve.a) * inverse_mod(2 * y1, curve.p)
else:

This is the case point1 != point2.

m = (y1 - y2) * inverse_mod(x1 - x2, curve.p)
x3 = m * m - x1 - x2
y3 = y1 + m * (x3 - x1)
result = (x3 % curve.p,
-y3 % curve.p)
assert is_on_curve(result)
return result
def scalar_mult(k, point):
"""返回使用 double 和 point_add 算法计算的 k*点。 """
assert is_on_curve(point)
if k < 0:

k * point = -k * (-point)

return scalar_mult(-k, point_neg(point))
result = None
addend = point
while k:
if k & 1:

Add.

result = point_add(result, addend)

Double.

addend = point_add(addend, addend)
k >>= 1#将 k 右移一位
assert is_on_curve(result)
return result

密钥生成和 ECDHE

def make_keypair():
"""生成随机的私钥对。"""
private_key = curve.n
public_key = scalar_mult(private_key, curve.g)
return private_key, public_key
private_key, public_key = make_keypair()
print("private key:",hex(private_key))
print("public key: (0x{:x}, 0x{:x})".format(*public_key))