第十三個知識點：概述投影點表達的用途的優點

原文連結：http://bristolcrypto.blogspot.com/2015/01/52-things-number-13-outline-use-and.html

這是52密碼學系列中第13篇,我們繼續數學背景部分,通過概述投影點表達的使用和優點.

TLDR - 在橢圓曲線點上的翻倍和加法操作需要一個域取逆和幾個乘法操作.我們考慮域\(K\)(特征值既不是2也不是3).給定\(K\)上的一個逆運算是比乘法更花費時間的,是以用投影點坐标去計算這些操作是更有效率的.

什麼是射影點？

對于橢圓曲線\(E\)，Weistrass等式（橢圓曲線的一種表示形式）的射影表達是一種可選的表達，這種表達和原曲線是等價的。我們沒有獲得任何額外的功能，但是實際上，我們定義了一種等價關系。讓\(c\)和\(d\)都是正整數，\(K\)是一個域（域的特征既不是2也不是3），然後我們定義一個等價關系\(\sim\)，在集合\(K^3 \backslash \{0,0,0\}\)（\(K\)的超域中非零點構成的集合）就是

\((X_1,Y_1,Z_1) \sim (X_2,Y_2,Z_2) 當且僅當 X_1 = \lambda^c X_2,Y_1 = \lambda^d Y_2,Z_1= \lambda Z_2 , 其中\lambda \in K^{*}\)

上述等價關系的等價類是

\[(X:Y:Z) = \{(\lambda^c X, \lambda^d Y, \lambda Z) : \lambda \in K^*\}

\]

我們現在就有了射影點\((X:Y:Z)\)，和它的表達式\((X,Y,Z)\)。

在文獻中有不同的射影坐标系，但是在這篇部落格裡我們隻考慮Jacobian坐标系統。在這個表達中，射影點\((X:Y:Z)\)對應的仿射點\((x,y)=(\frac{X}{Z^2},\frac{Y}{Z^3})\)。

使用放射坐标系統的優點是什麼？

使用射影點表示來計算點的加法和倍增會産生更少的逆運算和更多的乘法(與使用仿射坐标相比)。這可以通過将射影點轉換為仿射坐标并嘗試簡化加法和乘法運算來證明。得到的方程清除了分母，進而消除了取逆。從表面上看，這似乎不是什麼了不起的成就，然而，計算一個域的逆運算要比計算乘法複雜得多。為了給出仿射坐标和雅各比（Jacoabian）坐标的操作數，我們列出了下面的表格：

表示形式	加倍	加法
仿射坐标	1I，2M，2S
雅各比坐标	4M，4S	12M，4S

上面的表格采取的橢圓曲線形式是\(y = x^3 - 3x + b\)，其中I是取逆運算，M是乘法運算，S是平方運算。

确切的性能比較比較複雜，因為它們依賴于底層平台和實作。然而，隻要取逆仍然比乘法要昂貴得多，那麼使用仿射坐标将導緻對投影點的高性能損失。

是否存在缺點？

據我所知沒有(盡管我不認為自己是這方面的專家)。與以往一樣，總是存在着将實作導緻的問題，可以通過洩露離散對數問題的一些位産生攻擊[1]。

[1] https://www.iacr.org/archive/eurocrypt2004/30270258/projective.pdf