2021SC@SDUSC

在libsecp256k1位元幣密碼演算法開源庫（四）中定義了有限域下橢圓曲線的相關運算，在那一篇中對于橢圓曲線幾何加法運算的程序有了非常詳細的說明，但是在那一篇中，對與不同的兩點P和Q，計算其幾何加法結果R必須要經過非常重要的一步，即求斜率m：
m = y P ? y Q x P ? x Q ? m o d ? p = ( y P ? y Q ) ( x P ? x Q ) ? 1 m o d ? p m=\frac{y_P-y_Q}{x_P-x_Q} \,mod\,p=(y_P-y_Q)(x_P-x_Q)^{-1} mod\,p m=xP??xQ?yP??yQ??modp=(yP??yQ?)(xP??xQ?)?1modp在這一步中不可避免地要求一個乘法逆元，即 ( x P ? x Q ) ? 1 (x_P-x_Q)^{-1} (xP??xQ?)?1，計算乘法逆元可以使用擴展歐幾里得演算法，這個開銷或許不是很大，但這里的 x P x_P xP?和 x Q x_Q xQ?都是非常大的數（BigInt），用擴展歐幾里得演算法計算相應的乘法逆元是非常困難的，除此之外，計算橢圓曲線的標量乘法也有非常關鍵的一步，也就是計算最開始兩個相同數的幾何加法，其中也要計算斜率m：
m = 3 x P 2 + a 2 y P ? m o d ? p = ( 3 x P 2 + a ) ( 2 y P ) ? 1 ? m o d ? p m =\frac {3 x_P^2 + a} { 2 y_P }\, mod\,p=(3 x_P^2 + a)(2 y_P)^{-1}\, mod\,p m=2yP?3xP2?+a?modp=(3xP2?+a)(2yP?)?1modp在這一步中還是不可避免地要求乘法逆元 ( 2 y P ) ? 1 (2 y_P)^{-1} (2yP?)?1，

除此之外，在介紹橢圓曲線群中的元素中，除了那些滿足橢圓曲線方程具有橫縱坐標的點之外，我還提到一個“無窮遠點”，這個無窮遠點從何而來，本文將會進行解答，

那么在實際演算法實作程序中，避開擴展歐幾里得演算法，以求更加快速高效地求大數的乘法逆元是很重要的一個問題，實際上，在橢圓曲線上點的表示有兩種形式：仿射坐標Affine表示和射影坐標表示，通過將橢圓曲線上的點坐標從仿射坐標轉換到射影坐標中，就可以巧妙地避開擴展歐幾里得演算法，下面開始：

Affine 仿射坐標

雖然這里給仿射坐標放了一個title，但其實這里已經沒有必要給仿射坐標講太多東西了，之前幾篇講的橢圓曲線的方程表示和坐標運算其實都是基于仿射坐標的，也就是說，橢圓曲線的仿射方程就是 y 2 ＝ x 3 ＋ a x ＋ b y^2＝x^3＋ax＋b y2＝x3＋ax＋b，在有限域中，這個方程也就表達為 y 2 ＝ ( x 3 ＋ a x ＋ b ) ? m o d ? p y^2＝(x^3＋ax＋b)\,mod\,p y2＝(x3＋ax＋b)modp，也就是說，在仿射坐標下才存在要使用擴展歐幾里得演算法求解乘法逆元的問題，

Projection射影坐標

射影坐標分為：標準射影坐標、Jacobi射影坐標、Chudnovsky射影坐標，在橢圓曲線中使用的是Jacobi射影坐標，Chudnovsky射影坐標和這里的橢圓曲線沒什么關系，所以不講它，為了說明白Jacobi射影坐標，先從最基本的標準射影坐標開始，

標準射影坐標

在仿射坐標中，我們有橢圓曲線方程： y 2 ＝ x 3 ＋ a x ＋ b y^2＝x^3＋ax＋b y2＝x3＋ax＋b，對應點的坐標就是 ( x , y ) (x,y) (x,y)，射影坐標是三維的，一個點的坐標表示為 ( x , y , z ) (x,y,z) (x,y,z)，這里我們規定：
在標準射影坐標中，點 ( x , y , z ) (x,y,z) (x,y,z)對應仿射坐標中的點 ( x z , y z ) (\frac xz,\frac yz) (zx?,zy?)；
同理有，在仿射坐標中的點 ( x , y ) (x,y) (x,y)對應標準射影坐標中的點 ( x , y , 1 ) (x,y,1) (x,y,1)，

有了這樣的一個對應關系，我們令橢圓曲線方程 y 2 ＝ x 3 ＋ a x ＋ b ? y^2＝x^3＋ax＋b\, y2＝x3＋ax＋b中 ? x = x z ? \,x=\frac xz\, x=zx?， ? y = y z ? \,y=\frac yz\, y=zy?就得到了標準射影坐標中的橢圓曲線方程： y 2 z ＝ x 3 ＋ a x z 2 ＋ b z 3 ? y^2z＝x^3＋axz^2＋bz^3\, y2z＝x3＋axz2＋bz3可以看到，由于點 ( x , y , z ) (x,y,z) (x,y,z)對應仿射坐標中的點 ( x z , y z ) (\frac xz,\frac yz) (zx?,zy?)，這就使得z不能為0，如果z為零，在射影坐標中的點 ( 0 , y , 0 ) (0,y,0) (0,y,0)就找不到一個對應的仿射坐標值，但實際上橢圓曲線的點還是以射影坐標為準，也就是說就是有這樣一個點 ( 0 , y , 0 ) (0,y,0) (0,y,0)，于是在仿射坐標中稱這個點為“無窮遠點”，也就是在射影坐標中這個z=0的點，

Jacobi雅可比坐標

在Jacobi射影坐標與標準射影坐標方法類似，在Jacobi射影坐標中，一個射影點的坐標表示為 ( x , y , z ) (x,y,z) (x,y,z)，這里我們規定：
在Jacobi射影坐標，點 ( x , y , z ) (x,y,z) (x,y,z)對應仿射坐標中的點 ( x z 2 , y z 3 ) (\frac {x}{z^2},\frac {y}{z^3}) (z2x?,z3y?)；
同理有，在仿射坐標中的點 ( x , y ) (x,y) (x,y)對應標準射影坐標中的點 ( x , y , 1 ) (x,y,1) (x,y,1)，

有了這樣的一個對應關系，我們令橢圓曲線方程 y 2 ＝ x 3 ＋ a x ＋ b ? y^2＝x^3＋ax＋b\, y2＝x3＋ax＋b中 ? x = x z 2 ? \,x=\frac {x}{z^2}\, x=z2x?， ? y = y z 3 ? \,y=\frac {y}{z^3}\, y=z3y?就得到了Jacobi射影坐標中的橢圓曲線方程： y 2 ＝ x 3 ＋ a x z 4 ＋ b z 6 ? y^2＝x^3＋axz^4＋bz^6\, y2＝x3＋axz4＋bz6同樣可以看到，由于點 ( x , y , z ) (x,y,z) (x,y,z)對應仿射坐標中的點 ( x z 2 , y z 3 ) (\frac {x}{z^2},\frac {y}{z^3}) (z2x?,z3y?)，當z為零，有射影坐標中的點 ( x , y , 0 ) (x,y,0) (x,y,0)，該點同樣的在仿射坐標中稱為“無窮遠點”，也就是在射影坐標中這個z=0的點，

有了上面的從仿射坐標到射影坐標的映射關系，可以定義在射影坐標下的幾何幾何加法運算，令P和Q為不相等的兩點， P ( x 1 , y 1 , z 1 ) P(x_1,y_1,z_1) P(x1?,y1?,z1?)， Q ( x 2 , y 2 , z 2 ) Q(x_2,y_2,z_2) Q(x2?,y2?,z2?)，令 R ( x 3 , y 3 , z 3 ) R(x_3,y_3,z_3) R(x3?,y3?,z3?)，且R=P+Q（幾何加法運算），在橢圓曲線引數a=0時，射影坐標下的幾何加法運算程序如下： u 1 = x 1 z 2 2 u 2 = x 2 z 1 2 s 1 = y 1 z 2 3 s 2 = y 2 z 1 3 h = u 2 ? u 1 r = s 2 ? s 1 x 3 = r 2 ? h 3 ? 2 u 1 h 2 y 3 = r ( u 1 h 2 ? x 3 ) ? s 1 h 3 z 3 = z 1 z 2 h u_1=x_1z_2^2\\u_2=x_2z_1^2\\s_1=y_1z_2^3\\s_2=y_2z_1^3\\h=u_2-u_1\\r=s_2-s_1\\x_3=r^2-h^3-2u_1h^2\\y_3=r(u_1h^2-x_3)-s_1h^3\\z_3=z_1z_2h u1?=x1?z22?u2?=x2?z12?s1?=y1?z23?s2?=y2?z13?h=u2??u1?r=s2??s1?x3?=r2?h3?2u1?h2y3?=r(u1?h2?x3?)?s1?h3z3?=z1?z2?h

對于標量乘法中，我們首先需要計算兩個相等點P+P，即計算2P，令 P ( x 1 , y 1 , z 1 ) P(x_1,y_1,z_1) P(x1?,y1?,z1?)， R ( x 3 , y 3 , z 3 ) R(x_3,y_3,z_3) R(x3?,y3?,z3?)，在橢圓曲線引數a=0時，射影坐標運算程序如下：
x 3 = 9 x 1 4 ? 8 x 1 y 1 2 y 3 = 3 x 1 2 ( 4 x 1 y 1 2 ? x 3 ) ? 8 y 1 4 z 3 = 2 y 1 z 1 x_3=9x_1^4-8x_1y_1^2\\y_3=3x_1^2(4x_1y_1^2-x_3)-8y_1^4\\z_3=2y_1z_1 x3?=9x14??8x1?y12?y3?=3x12?(4x1?y12??x3?)?8y14?z3?=2y1?z1?

可以看到，在這兩個程序中沒有除法運算，也就不需要定義乘法逆元，那么這時候想要避開擴展歐幾里得演算法求乘法逆元就很簡單了：只需將橢圓曲線在仿射坐標中的點，轉化為在射影坐標中的點，用射影坐標幾何加法運算得到結果點，最后再把這個點的射影坐標轉化為仿射坐標就可以了，

在libsecp256k1中就采用了這樣從仿射坐標到雅可比坐標再到仿射坐標的程序，libsecp256k1采用的坐標就是Jacobi雅可比坐標，這個方法避開了擴展歐幾里得演算法求乘法逆元，大大提高了演算法效率，

同時注意，在secp256k1中定義橢圓曲線引數a=0，b=7，那么就可以得到Jacobi射影坐標中的secp256k1橢圓曲線方程： y 2 ＝ x 3 ＋ 7 z 6 ? y^2＝x^3＋7z^6\, y2＝x3＋7z6