椭圆曲线y²=x³+11x+19(mod167)点乘结果(102,88)(9,43)计算方法咨询

前置运算规则 #

所有运算都在模167的有限域下执行，给定椭圆曲线方程 y² = x³ + 11x + 19 mod 167，基点G=(2,7)，椭圆曲线点运算规则如下：

1. 点加倍（P=Q时计算2P）

• 切线斜率 s = (3x_P² + 11) * inv(2y_P) mod 167，其中inv代表模逆元，167是素数，可用费马小定理/扩展欧几里得计算逆元
• 新点坐标：x_R = (s² - 2x_P) mod 167，y_R = (s*(x_P - x_R) - y_P) mod 167

2. 点加法（P≠Q时计算P+Q）

• 连线斜率 s = (y_Q - y_P) * inv(x_Q - x_P) mod 167
• 新点坐标：x_R = (s² - x_P - x_Q) mod 167，y_R = (s*(x_P - x_R) - y_P) mod 167

我们使用二进制分解倍乘数的方法快速计算点乘：15=8+4+2+1，22=16+4+2，先逐次倍乘得到2G、4G、8G、16G，再按位相加得到结果。

逐次倍乘得到基础倍点 #

1倍点G #

G=(2,7)

2倍点2G #

对G执行点加倍：
s=(3*2²+11)*inv(2*7) mod 167 =23*12 mod167=109
x=109² - 2*2 mod167=24-4=20
y=109*(2-20)-7 mod167=35
2G=(20,35)

4倍点4G #

对2G执行点加倍：
s=(3*20²+11)*inv(2*35) mod167=42*136 mod167=34
x=34² - 2*20 mod167=154-40=114
y=34*(20-114)-35 mod167=109
4G=(114,109)

8倍点8G #

对4G执行点加倍：
s=(3*114²+11)*inv(2*109) mod167=88*131 mod167=5
x=5² - 2*114 mod167=25-228=131
y=5*(114-131)-109 mod167=140
8G=(131,140)

16倍点16G #

对8G执行点加倍：
s=(3*131²+11)*inv(2*140) mod167=58*34 mod167=135
x=135² - 2*131 mod167=22-262=94
y=135*(131-94)-140 mod167=12
16G=(94,12)

计算15G = 8G + 4G + 2G + G #

我们可以合并相加步骤验证结果：
将8G=(131,140)、4G=(114,109)、2G=(20,35)、G=(2,7)按点加法规则依次累加，最终计算得：
x坐标为102，y坐标为88，即15G=(102,88)，代入椭圆曲线方程验证符合运算规则。

计算22G = 16G +4G +2G #

1. 先算16G+4G=20G：
   s=(109-12)*inv(114-94) mod167=97*142 mod167=80
x=80²-94-114 mod167=54-208=13
y=80*(94-13)-12 mod167=122
   20G=(13,122)
2. 再算20G+2G=22G：
   s=(35-122)*inv(20-13) mod167=(-87)*24 mod167=83
x=83²-13-20 mod167=42-33=9
y=83*(13-9)-122 mod167=332-122=43
   最终得到22G=(9,43)，代入椭圆曲线方程验证符合运算规则。

内容的提问来源于stack exchange，提问作者Tumeng