素数 prime,又称为质数,是指,除了1和它本身,没有其他因数的数。

素数的定理:

  1)在一个大于1的数a和它的2倍之间必定存在至少一个素数;

素数的性质:

  1)在所有的大于10的质数中,个位数,只有1,3,5,9;

素数还没有自己的生成函数,只能通过素数检测函数,进行循环判断;

  C的基本判断函数:

    ECC-LMLPHP

大数的素数测试,有很多优化的算法,并不是简单的试除法

确定性的素数判定法:太慢了

非确定性的素数判定法:

  素数测试,输入是素数,来检测,该数并没有其他因子;绝不会把素数判断为合数,但可能把合数判断为素数

  合数测试,输入是合数,来检测,该数还有其他因子,米勒-拉宾(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

05-11 19:35