ECC椭圆曲线加密的特点以及在有限域(Fp)的三点共线问题

1.有限域内平面座标Y平方模P的特点

椭圆曲线方程一般化简式:
y^2=x ^3+ax+b(modp)
4a^3+27 b ^2≠0(modp)

椭圆曲线定义在有限域上,有限域Fp(p为质数),先看看在二维平面内 y1,y2,y3…yn ≤P 若从y1²到yn²模P后有同余的,它们会有什么关系? (y?²≡ r mod P y≤P 同余r,求y)
假设有y1²和y2²模P后同余, 令 y1≥y2; ① y1²=nP+r (即 y1² ≡ r mod P ) ② y2²=mP+r (即 y2² ≡ r mod P ) 由①-②
得 y1²-y2²=(np+r)-(mp+r) 化简后得: (y1+y2)(y1-y2)=(n-m)p
可见 在有限域 ≤P内,当两数相加等于p时,两数平方模P后同余。
比如当P取11时 , 令y1=4, 则 4² ≡ 5mod11 ≡(11-4)² mod11, 这样,当计算出X坐标模P后匹配Y坐标的其中一个数时,可快速计算出Y轴上的另外一个点,

2.为什么直线模P后经过有限域椭圆曲线后任意两点必然经过椭圆曲线的第三个点,这三点还会共线?

y^2=x ^3+ax+b(modp)
4a^3+27 b ^2≠0(modp)
假设离散椭圆曲线上有x和y 符合上面方程等式成立, x 和y 为≤P的整数
即知道 y²=iP+r , x ^3+ax+b²=jP+r 有模P后同余数r
令 x ^3+ax+b-y²=0 ③
设现有一直线 ,过有限域椭圆曲线上的离散点
y=kx+b 且 kx+b≡ r mod P ; 令y=kP+r 代入 ③
x ^3+ax+b-(kP+r)²=0
化简后得
x ^3+ax+ (b-k²p²-r²-2kpr) =0
可见这是一个一元三次方程,b,k,r皆为已知数。因为直线过有限域上的两点,而x1 和 x2 是已知整数,根据卡丹公式,由根与系数关系,必然有第三整数x3(可能与x1或x2相等), x3为整数

    原文作者:lfeid2002
    原文地址: https://blog.csdn.net/lfeid2002/article/details/100185625
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞