前言
ECC英文全称"Ellipse Curve Cryptography"。与传统的基于大质数因子分解困难性的加密方法不同，ECC通过椭圆曲线方程式的性质产生密钥。ECC 164位的密钥产生的安全级相当于RSA 1024位密钥提供的保密强度，且计算量较小、处理速度更快，存储空间和传输带宽占用较少。目前我国居民二代身份证正在使用256位的椭圆曲线密码，虚拟货币比特币也选择ECC作为加密算法。
从射影平面讲起
古希腊数学家欧几里得的《几何原本》提出了五条公设：
- 由任意一点到任意一点可作直线。
- 一条有限直线可以继续延长。
- 以任意点为心及任意的距离可以画圆。
- 凡直角都相等。
- 同一平面内一条直线a和另外两条直线b、c相交，若在a某一侧的两个内角的和小于两直角，则b、c两直线经无限延长后在该侧相交。
《几何原本》中前28个命题可不依靠第五公设推出。1820年代，俄国喀山大学罗巴切夫斯基用“至少可以找到两条相异的直线，且都通过P点，并不与直线R相交”代替第五公设，结合前四个公设得出罗氏几何（双曲几何）。现存非欧几何类型：
- 坚持第五公设：欧几里得几何。
- “可以引最少两条平行线”为公设：罗氏几何（双曲几何）。
- “一条平行线也不能引”为公设：黎曼几何（椭圆几何）。
射影平面性质：
- 一条直线只有一个无穷远点；一对平行线有公共的无穷远点。
- 任何两条不平行的直线有不同的无穷远点。
- 平面上全体无穷远点构成一条无穷远直线。
射影平面点的定义：
对普通平面上点(x,y)，令x=X/Z，y=Y/Z（Z≠0），投影为射影平面上的点(X:Y:Z)。
- 例：点（1,2）在新坐标体系下为（1:2:1）（2:4:2）等形如（Z:2Z:Z）（Z≠0）的坐标。
- 例：平行线L1：X+2Y+3Z=0与L2：X+2Y+Z=0相交的无穷远点为（-2:1:0）等形如（-2Y:Y:0）（Y≠0）的坐标。
椭圆曲线
椭圆曲线是在射影平面上满足威尔斯特拉斯方程（Weierstrass）所有点的集合：
[ Y^2Z + a_1XYZ + a_3YZ^2 = X^3 + a_2X^2Z + a_4XZ^2 + a_6Z^3 ]
性质：
- 椭圆曲线方程是齐次方程。
- 曲线上每个点必须非奇异（光滑），即偏导数 ( F_X(X,Y,Z)、F_Y(X,Y,Z)、F_Z(X,Y,Z) ) 不同为0。
- 椭圆曲线的形状并非椭圆，因方程类似计算椭圆周长的方程而得名。
椭圆曲线示例：
- ( Y^2Z = X^3 + XZ^2 + Z^3 )
- ( Y^2Z = X^3 - XZ^2 )
- 普通方程：( y^2 = x^3 + x + 1 )、( y^2 = x^3 - x )
非椭圆曲线示例：
- ( Y^2Z = X^3 + X^2 )
- ( Y^2Z = X^3 )
- 原因：在（0:0:1）点处无切线，不满足光滑性。
椭圆曲线普通方程：
[ y^2 + a_1xy + a_3y = x^3 + a_2x^2 + a_4x + a_6 ]
- 无穷远点：(0, Y, 0)
- 平常点(x,y)斜率 ( k = \frac{3x^2 + 2a_2x + a_4 - a_1y}{2y + a_1x + a_3} )
椭圆曲线阿贝尔群
群的定义：集合及二元运算满足封闭性、结合性、单位元、逆元；阿贝尔群还满足交换律。
椭圆曲线加法定义：
- 任意取椭圆曲线上两点P、Q（若重合则作切线），直线交椭圆曲线于另一点R'，过R'作y轴平行线交于R，定义P+Q=R。
- 同点加法：k个相同点P相加记作kP（如2P、3P）。
有限域椭圆曲线
椭圆曲线需定义在有限域上（离散化）：
- 有限域Fp：p为质数，元素为0,1,2,…,p-1，运算满足模p加法、乘法、除法（逆元）。
- 椭圆曲线Ep(a,b)：( y^2 \equiv x^3 + ax + b \ (\text{mod}\ p) )，需满足 ( 4a^3 + 27b^2 \not\equiv 0 \ (\text{mod}\ p) )。
有限域椭圆曲线加法规则：
- 无穷远点 ( O_\infty ) 是零元。
- P(x,y)的负元为(x, p-y mod p)。
- 若P≠Q，斜率 ( k = \frac{y_2 - y_1}{x_2 - x_1} \mod p )；若P=Q，斜率 ( k = \frac{3x^2 + a}{2y_1} \mod p )。
- 和点坐标：( x_3 \equiv k^2 - x_1 - x_2 \mod p )，( y_3 \equiv k(x_1 - x_3) - y_1 \mod p )。
例题：已知E23(1,1)上两点P(3,10)，Q(9,7)，计算：
- -P = (3, 13)
- P+Q = (17, 20)
- 2P = (7, 12)
点的阶：最小正整数n使得nP = ( O_\infty )，例：P(3,10)的阶为28。
椭圆曲线加密
原理：K = kG，已知k和G求K容易，反之困难（离散对数问题）。
- 基点G，私钥k，公钥K = kG。
保密通信算法流程（以E29(4,20)为例）：
- Alice选定曲线和基点G(13,23)，私钥p=25，公钥K=25G=(14,6)。
- Bob将明文3编码为M=(3,28)，随机数r=6，计算C1=M+6K=(6,12)，C2=6G=(5,7)。
- Alice解密：C1 - kC2 = M。
技术要求：
- p越大越安全，200-bit左右满足一般需求。
- n为质数，h≤4，( 4a^3 + 27b^2 \not\equiv 0 \ (\text{mod}\ p) )。
应用：
- 比特币使用secp256k1参数（p=2^256-2^32-…-1，a=0，b=7等）。
优缺点：
- 优点：安全强度高、处理速度快、带宽和存储需求低。
- 缺点：设计复杂，序列号过短可能影响安全性。