查看“︁橢圓曲線的純量乘法”︁的源代码

'''橢圓曲線點的乘法'''也稱為'''橢圓曲線的純量乘法'''，是將[[椭圆曲线]]上的一點反覆和自身相加的運算。此運算在[[椭圆曲线密码学]]（ECC）中可以用來產生[[單向函數]]。
此條目中將這種乘法用[[标量乘法]]來表示，再配合{{link-en|海賽形式的橢圓曲線|Hessian form of an elliptic curve}}。此運算也稱為'''橢圓曲線點的乘法'''（elliptic curve point multiplication），不過此名稱有時會誤解為二個點之間的乘法（其實是整數純量和點的乘法）。

==基礎==
假定在有限域上定義的曲線''E''（例如''E'': {{math|''y''<sup>2</sup> {{=}} ''x''<sup>3</sup> + ''ax'' + ''b''}}），其點乘定義為重覆的進行在曲線上點的加法，表示為{{math|''nP'' {{=}} ''P'' + ''P'' + ''P'' + … + ''P''}}，其中''n''是係數（整數）以及在曲線''E''上的一點{{math|''P'' {{=}} (''x'', ''y'')}}，這類的曲線稱為魏尔施特拉斯曲線（Weierstrass curve）。

現代橢圓曲線密碼學安全性的基礎是在給定''Q''和''P''，以及{{math|''Q'' {{=}} ''nP''}}的情形下，若''n''很大，無法求得''n''的特性而來（類似其他的[[迪菲-赫爾曼密鑰交換]]問題，此問題稱為橢圓曲線離散對數問題）。此原因是因為橢圓曲線上兩點的相加（或是某一個點加上自身）會得到第三點，而這個點的位置和前一點或前二點沒有明確的關係，重覆很多次之後，''nP''可能會在曲線上的任何位置。在直覺上，橢圓曲線的純量乘法和以下例子類似：假設在圓上選一個點''P''，再將其角度加上42.57度，所得的點離''P''會有一些距離，不過不會太遠，不過若加上1000次或1001次的42.57度，需要需比較複雜的運算才能求出所得的點的位置。回到橢圓曲線的純量乘法，若要進行逆運算，給定''Q=nP''，已知''P''和''Q''，要求''n''，只能一個一個的針對可能的''n''來檢查，若''n''的可能範圍很大的話，這在計算上就是不可行的。

==點運算==
[[Image:ECClines.svg|right|thumb|600px|橢圓曲線的點乘法：相加（圖1）、加倍（圖2和圖4）和反相（圖3）]]

橢圓曲線上的點，一般會定義三種運算：相加、加倍和反相。

===無窮遠點===
無窮遠點{{tmath|\mathcal{O} }}是橢圓曲線算術中的[[單位元]]。任意點和此點相加，相加前和相加後的結果不變。若無窮遠點加上無窮遠點，結果仍為無窮遠點。

也就是：
:<math>\begin{align}
\mathcal{O} + \mathcal{O} = \mathcal{O}\\
\mathcal{O} + P = P
\end{align}</math>

無窮遠點也會寫成{{math|0}}.

===反相===
點的反相是指針對某一個點，可以找到另一個點，與其相加後為無窮遠點（{{tmath|\mathcal{O} }}）。
:<math>\begin{align}
P + (-P) = \mathcal{O}
\end{align}</math>

在橢圓曲線上，一點反相點的''x''座標會和該點相同，而''y''座標會為該點座標的負值：
:<math>\begin{align}
(x, y) + (-(x, y)) &= \mathcal{O}\\
(x, y) + (x, -y) &= \mathcal{O}\\
         (x, -y) &= -(x, y) 
\end{align}</math>

===點的相加===

針對二個相異點''P''和''Q''，其加法定義為''P''和''Q''所形成的直線，和曲線''E''交點的反相點''R''.<ref name=crypto>{{Cite web |url=https://crypto.stanford.edu/pbc/notes/elliptic/explicit.html |title=存档副本 |access-date=2021-12-20 |archive-date=2021-12-20 |archive-url=https://web.archive.org/web/20211220154906/https://crypto.stanford.edu/pbc/notes/elliptic/explicit.html |dead-url=no }}</ref>
:<math>\begin{align}
                    P + Q &= -R \\
  (x_p, y_p) + (x_q, y_q) &= (x_r, y_r)
\end{align}</math>

假設橢圓曲線的方程式是{{math|''y''<sup>2</sup> {{=}} ''x''<sup>3</sup> + ''ax'' + ''b''}}，可以計算得到：
:<math>\begin{align}
  \lambda &= \frac{y_q - y_p}{x_q - x_p} \\
      x_r &= \lambda^2 - x_p - x_q \\
      y_r &= \lambda(x_p - x_r) - y_p \\
\end{align}</math>
若其中沒有任何一點是無窮遠點{{tmath|\mathcal{O} }}，且這些點的x座標都不同，則上式正確。這在[[椭圆曲线数字签名算法]]（ECDSA）上非常重要，因為[[散列值]]（hash）有可能為0。

===點的加倍===
假設點''P''和''Q''重合（座標相同），其加法類似，但無法依上述方式定義直線，因此使用極限的作法，取曲線''E''在''P''點的切線。

計算同上，取導數(dE/dx)/(dE/dy)可得<ref name=crypto/>：
:<math>\lambda = \frac{3x_p^2 + a}{2y_p}</math>

其中''a''是方程式''E''裡的係數。

==點乘法==
最直接計算點乘法的方式就是反覆的執行加法。不過也有其他更有效率的算法。

===Double-and-add===
最簡單的方式就是double-and-add法<ref name="guide">{{cite book|last1=Hankerson|first1=Darrel|last2=Vanstone|first2=Scott|last3=Menezes|first3=Alfred|title=Guide to Elliptic Curve Cryptography|year=2004|publisher=Springer-Verlag|location=New York|isbn=0-387-95273-X|series=Springer Professional Computing|doi=10.1007/b97644|s2cid=720546}}</ref>，其作法類似模乘幂中的[[平方求幂]]。其演算法如下：

要計算''sP''，要先將''s''以二進制表示{{tmath|s {{=}} s_0 + 2s_1 + 2^2s_2 + \cdots + 2^ms_m }}，其中{{tmath|s_0  ~..~  s_m \in \{0, 1\}, m{{=}}\lfloor \log_2{s} \rfloor }}：

以下是迭代演算法，其迴圈變數i遞減：

    let bits = bit_representation #為s的二進制表示（從MSB到LSB）
    let res = <math>\begin{align}\mathcal{O}\end{align}</math> #無窮遠點
    for bit in bits:
        res = res + res # double
        if bit == 1:            
            res = res + P # add
        i = i - 1
    return res

因Double和add的執行時間不同，根據執行時間就可以知道是執行Double或add，間接可以推算''d''，在[[資訊安全]]上，此方法會有{{le|計時攻擊|timing attack}}的風險。以下的蒙哥馬利階梯（Montgomery Ladder）是可以避免計時攻擊的作法。

以下則是使用遞迴函數的作法：

   f(P, d) is
      if d = 0 then
          return 0                         # 已計算完成
      else if d = 1 then
          return P
      else if d mod 2 = 1 then
          return point_add(P, f(P, d - 1)) # 若d為奇數，進行addition
      else
          return f(point_double(P), d/2)   # d為偶數，進行doubling

其中''f''是乘法的函數，''P''是要乘的座標，''d''是要加的次數。例如''100P''可以寫成 ''{{nowrap|2(2[P + 2(2[2(P + 2P)])])}}''，需要六個點乘二和二個點加運算，''100P''等於''f(P, 100)''。

此一演算法需要執行log<sub>2</sub>(''d'')個運算（點乘二或點加）。有許多演算法是以此為基礎來進行的修改，例如窗口法、滑動窗口法、NAF、NAF-w、vector chains和蒙哥馬利階梯法。

===窗口法===
此演算法的窗口法（windowed version）版本<ref name="guide"/>可以選擇窗口大小w，再計算所有的<math>dP</math>，<math>d = 0, 1, 2, \dots, 2^w - 1</math>。演算法會使用的表示法為<math>d = d_0 + 2^wd_1 + 2^{2w}d_2 + \cdots + 2^{mw}d_m</math> ，其程式是

   Q ← 0
   for i from m to 0 do
       Q ← point_double_repeat(Q, w)
       if d<sub>i</sub> &gt; 0 then
           Q ← point_add(Q, d<sub>i</sub>P) # using pre-computed value of d<sub>i</sub>P
   return Q

演算法的複雜度和Double-and-add相同，但其點相加使用的較少（實務上，點相加比點加倍要花時間）。一般來說，會選擇 ''w'' 為夠小的值，簡化預運算的步驟。若針對NIST建議的曲線，一般來說<math>w = 4</math>會是最好的選擇。''n''位元整數的複雜度會是<math>n + 1</math>個點加倍，<math>2^w - 2 + \tfrac{n}{w}</math>個點相加。

===滑動窗口法===
滑動窗口法（Sliding-window method）會在點相加和點加倍之間取捨，計算的表格類似窗口法，不過只計算<math>dP</math>， <math>d = 2^{w-1}, 2^{w-1} + 1, \dots, 2^w - 1</math>。此方式比較有效率，只計算有設定MSB的那些值。而其演算法使用原始double-and-add的表示法<math>d = d_0 + 2d_1 + 2^2d_2 + \cdots + 2^md_m</math>。

   Q ← 0
   for i from m downto 0 do
       if d<sub>i</sub> = 0 then
           Q ← point_double(Q)
       else 
           t ← extract j (up to w − 1) additional bits from d (including d<sub>i</sub>)
           i ← i − j
           if j < w then
               Perform double-and-add using t 
               return Q
           else 
               Q ← point_double_repeat(Q, w)
               Q ← point_add(Q, tP)
   return Q

此演算法的好處是預運算階段的複雜程度是一般窗口法的一半，也將較慢的點相加改為點加倍。實務上，使用窗口法而不使用滑動窗口法的情形不太多。此演算法會使用<math>w - 1 + n</math>次點加倍，最多只用<math>2^{w-1} - 1 + \tfrac{n}{w}</math>次點加法。
==={{math|w}}-ary非相鄰形式（{{math|w}}NAF）方法===
{{le|非相鄰形式|non-adjacent form}}（NAF）的目的是利用點相減的方式和點相加的方式相同的原理，設法使運算量少於滑動窗口法（頂多也只會和滑動窗口法相同）。被乘數<math>d</math>的NAF方式需要先用以下演算法進行計算

    i ← 0
    while (d &gt; 0) do
        if (d mod 2) = 1 then 
            d<sub>i</sub> ← d mods 2<sup>w</sup>
            d ← d − d<sub>i</sub>
        else
            d<sub>i</sub> = 0
        d ← d/2
        i ← i + 1
    return (d<sub>i−1</sub>, d<sub>i-2</sub>, …, d<sub>0</sub>)

其中有號餘數函數mods定義如下
  
    if (d mod 2<sup>w</sup>) &gt;= 2<sup>w−1</sup>
        return (d mod 2<sup>w</sup>) − 2<sup>w</sup>
    else
        return d mod 2<sup>w</sup>

因此會需要用NAF來進行乘法。此演算法會需要先計算<math> \lbrace 1, 3, 5, \dots, 2^{w-1} - 1 \rbrace P</math>（其中<math>P</math>是要乘的數）這些點，以及這些點的負值。若是標準的Weierstrass曲線，若<math>P = \lbrace x, y \rbrace</math>，可得<math>-P = \lbrace x, -y \rbrace</math>。因此負值很容易計算。接下來要計算<math>dP</math>的乘法：

    Q ← 0
    for j ← i − 1 downto 0 do
        Q ← point_double(Q)
        if (d<sub>j</sub> != 0)
            Q ← point_add(Q, d<sub>j</sub>P)
    return Q

wNAF方式可以保證平均來說點相加法的密度會是<math>\tfrac{1}{w + 1}</math>（比無號的窗口法好一點），其中的預計算會需要一個點加倍及<math>2^{w-2} - 1</math>個點加法。而演算法剩下的部份需要<math>n</math>個點加倍，以及<math>\tfrac{n}{w + 1}</math>個點加法。

NAF的一個特性是可以保證每一個非零元素<math>d_i</math>之後，至少有<math>w - 1</math>個零。其原因是因為演算法在每次計算mods函數後，會清除數字<math>d</math>中，較低的<math>w</math>個位元。在每一個非零元素後面，就會有一定數量的零位元，這些零位元可以不用儲存。

已有人發現，若針對[[OpenSSL]]進行FLUSH+RELOAD的[[旁路攻击]]，約在進行200次簽章後，即可以利用cache-timing找到完整私鑰<ref>{{cite conference | first1=Naomi | last1=Benger | first3=Nigel P. | last3=Smart | first2=Joop | last2=van de Pol | first4=Yuval | last4=Yarom | title="Ooh Aah... Just a Little Bit" : A Small Amount of Side Channel Can Go a Long Way | publisher=Springer | series=Lecture Notes in Computer Science | volume=8731 | conference=Cryptographic Hardware and Embedded Systems – CHES 2014 | year=2014 | pages=72–95 | doi=10.1007/978-3-662-44709-3_5 | isbn=978-3-662-44708-6 | editor1-first=Lejla | editor1-last=Batina | editor2-first=Matthew | editor2-last=Robshaw | url=https://www.iacr.org/archive/ches2014/87310103/87310103.pdf | access-date=2022-12-13 | archive-date=2022-12-13 | archive-url=https://web.archive.org/web/20221213093148/https://www.iacr.org/archive/ches2014/87310103/87310103.pdf | dead-url=no }}</ref>。

===蒙哥馬利階梯法===
蒙哥馬利階梯法（Montgomery ladder）<ref>{{cite journal | first=Peter L. | last=Montgomery | title=Speeding the Pollard and elliptic curve methods of factorization | journal=[[Math. Comp.]] | year=1987 | volume=48 | issue=177 | pages=243–264 | mr=0866113 | doi=10.2307/2007888| jstor=2007888 | doi-access=free }}</ref>會用固定的運算時間來進行點乘法，運算時間只會隨''d''的長度而變化，不會因為''d''的各位元內容而變化。這可以抵抗[[旁路攻击]]中的功率攻擊或是計時攻擊。此演算法的實現方式和double-and-add相同。

   R<sub>0</sub> ← 0
   R<sub>1</sub> ← P
   for i from m downto 0 do
       if d<sub>i</sub> = 0 then
           R<sub>1</sub> ← point_add(R<sub>0</sub>, R<sub>1</sub>)
           R<sub>0</sub> ← point_double(R<sub>0</sub>)
       else
           R<sub>0</sub> ← point_add(R<sub>0</sub>, R<sub>1</sub>)
           R<sub>1</sub> ← point_double(R<sub>1</sub>)
   return R<sub>0</sub>

此演算法的速度類似double-and-add，但是在處理''d''的每一位元時，都會進行點相加以及點加倍。因此演算法本身不會因為時間或是功率而洩漏''d''的資料。
不過若利用旁路攻击中的FLUSH+RELOAD對OpenSSL進行攻擊，已證實只需要經由一次簽名，用cache計時攻擊，以很低的成本得到完整的私鑰<ref>{{cite journal |last1=Yarom |first1=Yuval |last2=Benger |first2=Naomi |date=2014 |title=Recovering OpenSSL ECDSA Nonces Using the FLUSH+RELOAD Cache Side-channel Attack |url=https://eprint.iacr.org/2014/140 |journal=IACR Cryptology ePrint Archive |access-date=2021-12-24 |archive-date=2021-12-05 |archive-url=https://web.archive.org/web/20211205174641/https://eprint.iacr.org/2014/140 |dead-url=no }}</ref>。

==參考資料==
{{Reflist}}

[[Category:椭圆曲线]]