Ellipse Curve Cryptography

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

1.什么是ECC

ECC 是基于椭圆曲线数学结构的一类公钥密码系统。

这里的“椭圆曲线”并不是椭圆,而是满足如下方程的一类曲线:

\[ y^2 = x^3 + ax + b \]

在密码学中,这个方程通常定义在有限域上,而不是实数域

2.有限域上的椭圆曲线

对于实数域上的椭圆虚线:

\[ y^2 = x^3 + ax + b \]

如果 x, y 是实数,那么:

  • 曲线是连续的
  • 有无限多个点
  • 看起来像一条平滑的曲线
  • 关于x轴对称

ecc1

对于有限域上的椭圆曲线:
例如模素数域

记作:

\[ \mathbb{F}_p \]

即所有计算都在modp下进行

当p=7时,那么域中的元素明显就是

\[ \{0,1,2,3,4,5,6\} \]

由于曲线定义在有限域上,变量 x 和 y 只能取集合 {0,1,2,3,4,5,6}中的值。因此,我们不再是在实数平面上画一条连续曲线,而是在有限个候选点中检查哪些点满足方程
因此,有限域上的椭圆曲线本质上不是一条连续图像,而是一个满足方程的离散点集

ecc2

3.椭圆曲线群

在密码学中,我们关心的不仅仅是椭圆曲线的“形状”,更重要的是:

曲线上的点能否构成一个“群”

因为 ECC 的所有操作(密钥交换、签名)本质上都是在做:

\[ Q = kP \]

也就是在一个群里反复做“加法”。

回顾近世代数

若满足封闭性,结合律,单位元,逆元和交换律,称为交换群(阿贝尔群)

3.1什么是椭圆曲线上的“加法”

在实数域上,椭圆曲线:

\[ y^2 = x^3 + ax + b \]

上,我们可以定义一种特殊的加法规则:

  • 连接 P 和 Q 作一条直线
  • 这条直线会和曲线再交一个点 R’
  • 把 R’关于 x 轴对称,得到 R

定义:

\[ P + Q = R \]

记p(1,1),Q(0,-1)

ecc3

特殊情况:

特别地,当取 Q=(1,-1) 时,直线变为竖直线,不再与曲线产生第三个有限交点

为了满足群的要求:

  • 必须有单位元
  • 必须保证加法总是有结果

数学上做了一个非常关键的补充:

\[ 引入一个无穷远点\mathcal{O} \]

并定义:

\[ P + (-P) = \mathcal{O} \]

记小写p为模数,-P 不是负数,而是P关于 x 轴对称的点(在有限域中就是 -y mod p)。

4.椭圆曲线离散对数问题

ECC 利用了椭圆曲线上的一种特殊运算规则:

1.给定曲线上的两个点,可以定义“点加法”
2.可以进一步定义“点乘”(重复加法)

例如:

\[ Q = kP \]

表示点 P 自加 k次得到点 Q

对于逆向计算

给定:

  • P
  • Q = kP

求:

\[ k = ? \]

这就是:椭圆曲线离散对数问题(ECDLP)

5.应用

ECC 本身是一个数学结构,可以构建多种密码协议,常见包括

5.1ECDH

椭圆曲线迪菲-赫尔曼密钥交换(Elliptic Curve Diffie–Hellman Key Exchange,ECDH)是基于椭圆曲线密码学的匿名密钥协商协议,由Neal Koblitz和Victor Miller于1985年分别独立提出椭圆曲线密码学基础 。该协议允许通信双方在不安全信道中通过交换公钥生成共享密钥,具体使用公共参数(大质数p与整数g)生成私钥a/b及对应公钥(ga mod p与gb mod p),最终通过计算获得相同共享机密值用于派生对称加密密钥材料

公共参数

  • 椭圆曲线 E
  • 基点 G
  • 阶 n

Alice

选私钥:

\[ a \]

计算公钥:

\[ A = aG \]

Bob

选私钥:

\[ b \]

计算公钥:

\[ B = bG \]

交换后

Alice:

\[ S = aB = a(bG) = abG \]

Bob:

\[ S = bA = b(aG) = abG \]

5.2ECDSA

ECDSA(Elliptic Curve Digital Signature Algorithm)是一种基于椭圆曲线的数字签名算法,用于验证消息的来源和完整性。ECDSA是ECC与DSA的结合,整个签名过程与DSA类似,所不一样的是签名中采取的算法为ECC,最后签名出来的值也是分为r,s

签名流程

设:

  • 私钥:d
  • 公钥:Q = dG
  • 基点:G
  • 阶:n

1.对消息做哈希

\[ z = H(M) \]

2.选随机数 k

\[ k \in [1, n-1] \]

3.计算点

\[ (kG) = (x_1, y_1) \]

把点 G 在椭圆曲线上“加自己 k 次”,得到一个新的点,这个点的坐标是 (x₁, y₁)

4.计算r

\[ r=x_1modn \]

若r=0,重新选k

5.计算s

\[ s=k^{−1}(z+rd)modn \]

若s=0,重新选k

6.输出签名

\[ \text{Signature} = (r, s) \]