椭圆曲线密码基于离散对数难题
公钥密码
ECC 非对称密钥功能：加密、签名、密钥交换
ECC是RSA的后继更短的密钥长度、更快的签名、更快的密钥协商
私钥长度为256bits， 32字节。大小在曲线的域范围内（field size），256bits的整数。此范围内任意整数都是合法的私钥。
公钥为曲线上的点（EC points），坐标为{x,y}.能够压缩为一个坐标长度+1bit，为压缩的公钥（compressed public key）。
不同的椭圆曲线具有不同的安全级别、不同的性能、不同的密钥长度。
ECC曲线的一些术语：
名字：secp256k1、Curve25519
域长度：定义密钥长度，如256bits
安全强度：域长度/2 或更小
性能：operations/sec
密钥长度：OpenSSL, OpenSSH and Bitcoin 默认256bits。
256-bit (curves secp256k1 and Curve25519),384-bit (curves p384 and secp384r1),…
ECC算法：基于有限域上的数学
ECC数字签名： ECDSA (for classical curves) EdDSA (for twisted Edwards curves)
ECC加密： ECIES EEECC (EC-based ElGamal).
ECC 密钥交换：ECDH, X25519 and FHMQV.
所有这些算法采用公钥、私钥对。私钥是整数，公钥是曲线上的点EC point。
包含所有的{x,y}
简化后的曲线（Weierstras form）y^2 = x ^ 3 + ax + b
令： a = 0 and b = 7
y^2 = x ^ 3 + 7 （ NIST curve secp256k1 (used in Bitcoin)）。如下：
图形生成参考链接： https://www.desmos.com/calculator/ialhd71we3?lang=zh-CN
ECC使用的椭圆曲线定义在有限域𝔽p上，p是素数，p>3
𝔽2m 域大小为 p = 2m 为一方阵（the field is a square matrix of size p x p）
曲线上的点不连续，限定为离散的整数。域内的点加、点乘结果还在曲线上。
有限域𝔽p上的椭圆曲线等式：
y^2 ≡ x ^ 3 + ax + b (mod p)
RSA的密钥空间为域ℤp上的整数 [0…p-1] 。
ECC的密钥用点{x,y},在Galois field 𝔽p 上，x和y都是 [0…p-1]的整数。
有限域𝔽p 上的椭圆曲线满足：
整数坐标 {x, y}集合，满足0 ≤ x, y < p
{x,y}在曲线上: y^2 ≡ x ^ 3 + ax + b (mod p)
一个有限域𝔽17的例子：
y ^ 2 ≡ x ^3 + 7 (mod 17)
一些计算：
是否在曲线上：
x^3 + 7 - y ^ 2 ≡ 0 (mod 17)
如 P {5, 8} 在曲线上 因为 (53 + 7 - 82) % 17 == 0
点乘：
曲线上的两个点相加得到曲线上另一个点——点加. G 加上自己, 结果 G + G = 2 * G. I类推 3 * G … 结果也在域内，这是域的封闭性。 这就是点乘的定义。
P = k * G
当k=0时，得到无穷点O “infinity”.
例子：
P = k * G = 6 * {15, 13} = {5, 8}
点加的计算方法：
假定P点为(x1, y1)，Q点为(x2, y2)，P+Q为(x3, y3)，因此P+Q由以下规则确定：
若椭圆曲线上两个点相同，则
若椭圆曲线上两个点不同
[https://blog.csdn.net/Catherine_qingzhu/article/details/107288195]
图示参考：http://star.aust.edu.cn/xjfang/crypto/add.html
上面涉及到分数取模，如下：
假设求
, 等价于求
第一种用快速幂模：
由费马小定理
进一步：
取模运算：
(ab)%c=(a%c)(b%c)%c
a^b%c
对于b我们可以拆成二进制的形式
b=b0+b12+b22 ^ 2+…+bn2^n
那么我们的a^b运算就可以拆解成
a ^ b0 * a ^ b1 2^ 1… * a ^ (bn2^n)
我们真正想要的其实是b的非0二进制位
a ^ (2 ^ x)…a^ (2^n)
实例化容易理解：a^11%p
11=1011b=2^ 0 + 2 ^1 + 0 * 2 ^2 + 2 ^3 @1
a^ (2^ 0 + 2 ^1 + 2 ^3)%p = (a ^ 1 * a ^ 2 * a^ 8)%p =
((a%p * a ^ 2%p)%p * a^ 8%p)%p @2
再结合下面代码，b&1说明上面@1式：1011对应位置为1(通过了b>>=1的不断右移)，也即@2式，对应的(aa)%c会添加进@2里面。如@1的第3个二进制位为0. 对应a = ((a ^ 2%p) * (a ^ 2%p)) % p = (a ^ 2 * a ^ 2) %p = a ^4 %p.
但是b>>=1后 刚好b最低位为0，a ^4 %p不会加入@2.依次类推。
#include
int fast_pow(int a,int b,int c)
{
int ans=1; ///记录结果
a=a%c; ///预处理，使得a处于c的数据范围之下
while(b!=0)
{
if(b&1)///奇数
{
ans=(ans*a)%c;///消除指数为奇数的影响
}
b>>=1; ///二进制的移位操作,不断的遍历b的二进制位
a=(a*a)%c; ///不断的加倍
}
return ans;
}
//递归方法
/*
typedef long long ll;
ll fast_pow(ll x,ll n,ll p)
{
ll temp;
x=x%p;
if(n==0)///终止条件
{
return 1;
}
temp=fast_pow((x*x)%p,n>>1,p);
if(n&1)
{
temp =temp*x%p;///消除指数为奇数的影响
}
return temp%p;
}
*/
int main() {
long point[2] = {15, 13};
int a = 0;
int p = 17;
long x,y,Rx,Ry;
long val;
long aaa=(3*point[0]*point[0] + a);
long bbb=(2*point[1]);
if (aaa % bbb !=0){
//y = (aaa * bbb^-1)%17 = ((aaa % 17) * (bbb^-1%17))%17 = ((aaa % 17) * (bbb^(17-2)%17))%17
y = ((aaa % 17) * fast_pow(bbb,(17-2),17))%17;
}
else
y=(aaa/bbb) % 17;
Rx=(y * y-point[0] - point[0])%17;
Ry=(y*(point[0]-Rx) - point[1])%17;
printf("x %ld, y %ld\n", Rx, Ry);//{2,10}
}
第二种方法，用拓展欧几里得算法求逆元
a^-1 为a 和 p的乘法逆元,也就是说 a 与 a ^ -1 的乘积模 p 的余数为 1.
计算乘法逆元，可以通过拓展欧几里得计算得到。
[https://www.jianshu.com/p/eece4117cb63]
先看看欧几里得算法求最大公约数，最大公约数（Greatest Common Divisor, GCD），是指2个或N个整数共有约数中最大的一个。a，b的最大公约数记为(a, b)。相对应的是最小公倍数，记为[a, b]。
在求最大公约数的几种方法中，欧几里得算法（辗转相除法）最为出名：
计算(a, b)， 若b是0，则最大公约数为a；否则。将a除以b得到余数r，a和b的最大公约数就是b和r的最大公约数，即：(a, b) = (b, r)。
static int gcd(int a ,int b){
if(b == 0){
return a;
}else{
return gcd(b, a%b);
}
}
求a模p的逆元x,使得 (a * x ) % p = 1, 该方程等价于 a * x = 1 + y * p （y为整数），也等价于 a * x - y * p = 1。因此求解x的过程就是求解该二元一次方程（a和p已知，求解x,y），即求a模p的逆元x。[https://www.cnblogs.com/GjqDream/p/11537934.html]
扩展欧几里德算法:
引理：存在 x , y 使得 gcd(a,b)=ax+by
证明：
当 b=0 时，gcd(a,b)=a，此时 x=1 , y=0
当 b!=0 时，
设 a * x1 + b * y1 = gcd(a, b) = gcd(b, a % b)=b * x2 + (a % b) * y2
又因a % b = a - a / b * b
a * x1 + b * y1 = b * x2 + a * y2 - a / b * b * y2
a * x1 + b * y1 = a * y2 + b * x2 - b * a / b * y2
a * x1 + b * y1 = a * y2 + b * (x2 - a / b * y2)
解得 x1 = y2 , y1 = x2 - a / b * y2
因为当 b=0 时存在 x , y 为最后一组解
而每一组的解可根据后一组得到
所以第一组的解 x , y 必然存在
得证
根据上面的证明，在实现的时候采用递归做法
先递归进入下一层，等到到达最后一层即 b=0 时就返回x=1 , y=0
再根据 x1=y2 , y1=x2-a/b*y2 ( x2 与 y2 为下一层的 x 与 y ) 得到当层的解
不断算出当层的解并返回，最终返回至第一层，得到原解
代码如下：
#include
long get_gcd(long a, long b) {
long remainder = a % b;
while(remainder != 0) {
a = b;
b = remainder;
remainder = a % b;
}
return b;
}
//拓展欧几里得算法求线性方程的x与y a * x = 1 + y * b （y为整数）
//a * x => 1 mod b 最终的x即为a的乘法逆元
void get_(long a, long b, long *x, long *y){
long k,yu, x1, y1;
if (b == 0) {
*x = 1;
*y = 0;
} else{
k = a / b;
yu = a % b;
get_(b, yu, &x1, &y1);
*x= y1;
*y = x1 - k * y1;
}
}
long inverse(long a, long b) {
long m = b;
long x, y;
if (get_gcd(a,b) == 1) {
get_(a,b,&x,&y);
return x;
}
return -1;
}
int main() {
long point[2] = {15, 13};
int a = 0;
int p = 17;
long x,y,Rx,Ry;
long val;
long aaa=(3*point[0]*point[0] + a);
long bbb=(2*point[1]);
if (aaa % bbb !=0){
val=inverse(bbb,17);
y=(aaa*val) % 17;
}
else
y=(aaa/bbb) % 17;
Rx=(y * y-point[0] - point[0])%17;
Ry=(y*(point[0]-Rx) - point[1])%17;
printf("x %ld, y %ld\n", Rx, Ry);//{2,10}
}
可视图：
[http://star.aust.edu.cn/xjfang/crypto/add.html]
最后是多倍点KG的计算：
方法1 平方和算法
#include
void addG(long point[2], long a) {
long Rx,Ry,y;
long aaa=(3*point[0]*point[0] + a);
long bbb=(2*point[1]);
if (aaa % bbb !=0){
//val=yunsle(bbb,17);
//y=(aaa*val) % 17;
//y = (aaa * bbb^-1)%17 = ((aaa % 17) * (bbb^-1%17))%17 = ((aaa % 17) * (bbb^(17-2)%17))%17
y = ((aaa % 17) * fast_pow(bbb,(17-2),17))%17;
}
else
y=(aaa/bbb) % 17;
Rx=(y * y-point[0] - point[0])%17;if (Rx < 0) Rx += 17;//-9 mod 17 = 8 不同的语言不一样，c得-9，Python得8，手动纠正一下，因为域在正整数内
Ry=(y*(point[0]-Rx) - point[1])%17;if (Ry < 0) Ry += 17;
point[0] = Rx;
point[1] = Ry;
}
//G1=G1+G2; G1!=G2
void addG1G2(long G1[2], long G2[2]){
long Rx,Ry,y;
if (G1[0] == 0 && G1[1] == 0) {
G1[0] = G2[0];
G1[1] = G2[1];
return;
}
long aaa=(G2[1] - G1[1]);
long bbb=(G2[0] - G1[0]);
if (aaa % bbb !=0){
//val=yunsle(bbb,17);
//y=(aaa*val) % 17;
//y = (aaa * bbb^-1)%17 = ((aaa % 17) * (bbb^-1%17))%17 = ((aaa % 17) * (bbb^(17-2)%17))%17
y = ((aaa % 17) * fast_pow(bbb,(17-2),17))%17;
}
else
y=(aaa/bbb) % 17;
Rx=(y * y-G2[0] - G1[0])%17;if (Rx < 0) Rx += 17;
Ry=(y*(G2[0]-Rx) - G2[1])%17;if (Ry < 0) Ry += 17;
G1[0] = Rx;
G1[1] = Ry;
}
void pingfanghe_kp(unsigned int k, long point[2], long G[2]){
if (k <= 0){
return;
}
int i = sizeof(unsigned int) * 8 - 1;
for (; i >= 0; i--) {
if (k & (1 << i))
break;
}
G[0] = point[0];
G[1] = point[1];
while(--i >= 0) {
addG(G, 0);
if (k & (1 << i)) {
addG1G2(G, point);
}
}
}
int main() {
long point[2] = {15, 13};
long a = 0;
long p = 17;
long G[2] = {0};
pingfanghe_kp(2, point, G);
printf("kG = {%ld, %ld}\n", G[0], G[1]);
}
椭圆曲线的阶(order) 是椭圆曲线上所有EC点的个数，包含无穷远点。
椭圆曲线上点的阶： P为椭圆曲线上的点，nP=无穷远点，n取最小整数，既是P的阶；(n-1)P= -P; n为其阶。
基点(base point)，用G表示，是椭圆曲线上的一个点；用倍乘KG生成循环子集上的其他点。K范围[0…r]。r为循环子集的阶，也即循环子集中的点的个数。见下文。
余因子(cofactor)： 用h表示，为椭圆曲线点的个数（即椭圆曲线的阶）/基点的阶
素数域:
(p，a，b，G，n，h)
其中，p为素数，确定Fp，a和b确定椭圆曲线方程，G为基点，n为曲线的阶，h为余因子。确保秘钥空间足够大，以满足安全强度要求。
h = n / r
其中
n 曲线的阶 (曲线上所有点的个数)
h 曲线的余因子 (不相交的子群个数)
r 子群的阶 (每个子群的点的个数, 包含各个子群的无穷远点)
换句话说, 曲线上的点包含在一个或多个循环子集内. 子集的数量叫做余因子 “cofactor”. 所有循环子集的点的总和叫做曲线的阶 “order” of the curve 用 n表示. 若曲线只包含一个循环子集, h = 1. 若曲线包含许多循环子集 cofactor > 1.
cofactor = 1 secp256k1.
cofactor = 8 Curve25519.
cofactor = 4 Curve448.
cofactor = 1 时 表示只有一个循环子集，n = r. 其他的点可用KG 表示，其中K在[1…n], G 为基点。
r 与 具体的基点G相关，通过G获得，可能和曲线的阶不相等（cofactor > 1时 ），r定义了所有这个曲线下的私钥数量。
曲线的循环子集上有很多基点，选择其中之一生成整个子群。但是不同的基点生成的循环子群的阶大小不一样。也即有些点生成的群的阶很小，即包含的曲线点少，安全强度低。h > 1时，不同的基点产生不同的循环子群，所含点的数量不同，也就是选择了一个基点，相当于选择了曲线上的一个点子集
实例：
y2 ≡ x3 + 7 mod 17
基点G = {15, 13} n = 18, h =1
曲线具有17个正常的EC point，和一个无穷点。见上面的图示。
若 G ={5, 9}，则只能生成3个EC point {5, 8}, {5, 9} and infinity
Generator Point - Example
At the above example (the EC over finite field y2 ≡ x3 + 7 mod 17), if we take the point G = {15, 13} as generator, any other point from the curve can be obtained by multiplying G by some integer in the range [1…18]. Thus the order of this EC is n = 18 and its cofactor h = 1.
Note that the curve has 17 normal EC points (shown at the above figures) + one special “point at infinity”, all staying in a single subgroup, and the curve order is 18 (not 17).
注意到，上面曲线的阶 n = 18，不是素数。不同的基点可能产生不同的循环子集，子集的阶不同。
有限域𝔽p上的ECC曲线的基点G、私钥k (整数)、公钥P （点）
非对称 (快速乘，反向难题) 叫做ECDLP （ Elliptic Curve Discrete Logarithm Problem）.
公钥K的压缩
P {x, y} ==> C {x, odd/even)
解压：
y1 = mod_sqrt(x^3 + ax + b, p)
y2 = - mod_sqrt(x^3 + ax + b, p) + p
椭圆曲线有不同的表达形式，它们是等价的（birationally equivalent (isomorphic)）
Weierstrass 曲线:
y^2 = x ^ 3 + ax + b
Weierstrass 曲线在 ECC的例子：secp256k1, y^2 = x ^3 + 7
Montgomery 曲线:
By^2 = x ^ 3 + Ax ^ 2 + x
Montgomery 曲线在 ECC 例子Curve25519, y^2 = x ^ 3 + 486662x ^ 2 + x
Edwards 曲线:
x^2 + y ^2 = 1 + d * x ^ 2 * y ^2
Edwards 曲线在 ECC 的例子 Curve448, x ^2 + y ^2 = 1 - 39081 x ^2 *y ^2
图示例：
if d = 300, Edwards 曲线 x ^2 + y ^2 = 1 + 300 * x ^2 * y ^2 如下:
Curve25519, X25519 and Ed25519
y2 = x3 + 486662x2 + x
在有限素数域 𝔽p, p = 2255 - 19 (曲线是 255-bit).
Curve25519 包含所有的点{x, y} ，x，y为整数坐标, 由下式定义:
y2 ≡ x3 + 486662x2 + x (mod 2255 - 19)
Curve25519 ，阶 n = 2252 + 0x14def9dea2f79cd65812631a5cf5d3ed ； cofactor h = 8 ；提供125.8-bit 安全强度 私钥长度 251 bits ，通常编码为 256-bit 整数 (32 bytes, 64 hex digits). 公钥也编码为 256-bit 整数(255-bit y-coordinate + 1-bit x-coordinate) .
基于 Curve25519 ， ECDH , 叫作X25519 ，以及数字签名算法, 叫作Ed25519, 基于EdDSA 算法. 注意 X25519 and Ed25519 对EC 点使用不同的编码, 不直接兼容，需要转换。
Curve448, X448 and Ed448
T Curve448 (Curve448-Goldilocks) 是 untwisted Edwards 曲线,
x ^2 + y ^2 = 1 - 39081 * x ^2 * y^2
在有限素数域 𝔽p, p = 2^448 - 2 ^ 224 - 1. It has order of n = 2 ^ 446 - 0x8335dc163bb124b65129c96fde933d8d723a70aadc873d6d54a7bb0d , cofactor h = 4.
Curve448 提供~ 224-bit 安全. Curve448 私钥长度 446 bits 通常编码为 448-bit 整数(56 bytes, 112 hex digits). 公钥编码为 448-bit 整数.
Curve448适合于 ECDH 秘钥交换 ( X448) ，快速签名(EdDSA 算法, 叫作 Ed448 or edwards448). X448 和 Ed448 对 EC points采用不同的编码。
Curve448 比Curve25519 慢3倍，使用 更长的秘钥长度和签名长度。