素数 prime,又称为质数,是指,除了1和它本身,没有其他因数的数。
素数的定理:
1)在一个大于1的数a和它的2倍之间必定存在至少一个素数;
素数的性质:
1)在所有的大于10的质数中,个位数,只有1,3,5,9;
素数还没有自己的生成函数,只能通过素数检测函数,进行循环判断;
C的基本判断函数:
大数的素数测试,有很多优化的算法,并不是简单的试除法,
确定性的素数判定法:太慢了
非确定性的素数判定法:
素数测试,输入是素数,来检测,该数并没有其他因子;绝不会把素数判断为合数,但可能把合数判断为素数。
合数测试,输入是合数,来检测,该数还有其他因子,米勒-拉宾(Miller-Rabin)测试。
互素,又称为互质,公约数只有1的两个整数,例如8,10的最大公因数是2。
梅森素数,Mersenne prime,是由梅森数来的。
梅森数,是指形如2 - 1的一类数,其中指数p是素数,记为Mp,如果梅森数为素数,就称为梅森素数;
目前仅仅发现了49个梅森素数;
ECC内部的椭圆曲线分为两大类,素数(p),二次多项式(2)
ECC内部计算的blinding操作,在乘法过程中,加入输入的随机数来掩盖其中的中间值;
ECC的基于大素数P的椭圆曲线的方程是:y = x + ax + b mod p
NIST推荐的曲线中,a = -3,这样可以提高计算效率;
cofactor,余因子,必须不是n的因子,NIST推荐的曲线,一般cofactor都是1,2,4
n,基点G的阶,n*cofactor表示一条曲线上的所有点的个数。
ECC中P素域上的椭圆曲线的随机生成,需要一个160bit的seed,经过sha1运算之后,得到c,
a直接定为:-3
计算b:b*c = -27 (mod p)
ECC Shamir trick,同时做两个点乘,内部进行分解,转变为更小的倍点和点加。
R = k*P + l*Q
ECC-C25519/Ed25519基于最新的一种椭圆曲线的方程,y - x = 1 + d*x*y mod p
ECC中的affine coordinate和jacobian coordinate坐标系:
在affine coordinate,曲线的方程为:y = x + ax + b mod p
在jacobian coordinate中,曲线的方程为:y = x + axz + bz
affine coordination 到Jacobian coordination的转换:
x = X/Z mod p
y = Y/Z mod p
Jacobian coordination 到affine coordination的转换:
X = x
Y = y
Z = 1
有些design内部,还可能使用standard projective来做运算,防止一些side-channel attack,这些运算如果使用
Jacobian坐标系不能实现,计算完成在转换为affine projective
Affine(x,y) 到 Standard_Prj(X,Y,Z)转变,
x = X/Z mod p
y = Y/Z mod p
standard_Prj(X,Y,Z) 到 Affine(x,y)转变,
X = x
Y = y
Z = 1
Z变量在standard_prj中的值是不等于Jacobian中的值的。
ecc曲线是关于x轴,可以对称的。曲线上的点的个数总共有order(阶)个。一般的可使用的点的个数会远小于order的值。
因为一般我们都取G点的n点乘的点的集合。n*G的点乘结果表示该曲线对应的无穷远点。
https://blog.csdn.net/hugewaves/article/details/53870397