( 尚須改進 )
Intro
令一條橢圓曲線 \(E: y^2 = x^3 + ax + b\) 模 \(p\) 下的解個數為 \(|E|\)，則 \(|E - (p + 1)| \le 2 \sqrt{p}\) (Hasse's Theorem)，如果 \(|E|\) 的質因數都很小的話 (smooth number)，離散對數很容易被 Pohlig-Hellman 破解，這建議我們使用那些 \(|E|\) 是質數的橢圓曲線。但如果 \(|E| = p\) 時，這種曲線被叫做 anomalous curve，且 Smart's Attack 可以很輕易的計算這種曲線的離散對數。
定義域
平常利用橢圓曲線加密時，我們都只考慮 \(x\), \(y\) 座標模 \(p\)，但是如果也想模 \(p^2\), \(p^3\) 或更高的次方呢？我們可以把所有整數寫成 \(p\) 進位，也就是
\[a_0 + a_1p + a_2p^2 + \cdots\]
其中 \(a_i\) 是介於 \(0\) 到 \((p-1)\) 之間的整數，在模 \(p^k\) 時就只需考慮前 \(k\) 項。那我們該如何表示 \(-1\) 呢？如果 \(p = 3\)，我們可以表示成
\[2 + 2 \cdot 3 + 2 \cdot 3^2 + \cdots\]
雖然這個級數不會收斂，可是在模 \(p^k\) 的情況下後面的高次項會被刪掉，所以不用擔心收斂的問題。至於有理數的話則寫成
\[a_{-k}p^{-k}+ \cdots + a_{-2} p^{-2} + a_{-1}p + a_0 + a_1 p + a_2 p^2 + \cdots\]
我們只考慮有限小數，所以 \(p=3\) 時，\(0.5\) 是不存在的。有了負數次方的擴展，模 \(p^{-k}\) 次方就可以定義成把所有高次項刪掉後得到的數字。
由於我們只是換個數字的表達方式，橢圓曲線的方程式不用改。例如說 \(p=3\) 時，曲線 \(E: y^2 = x^3 + 14x + 1\) 原來有六個點 \((0,\,\pm 1)\), \((1,\,\pm 1)\), \((2,\,\pm 1)\)。但現在，\((1,\,1)\) 雖然滿足
\[y^2 = x^3 + 14x + 1 \pmod {p}\]
但不滿足
\[y^2 = x^3 + 14x + 1 \pmod {p^2}\]
所以 \((1,\,1)\) 不是曲線上的點。而 \((2 + 2 \cdot 3 + 2 \cdot 3^2 + \cdots,\,1 + 1\cdot 3)\) 和 \((1 + 2\cdot 3,\,2 + 1 \cdot 3 + 1 \cdot 3^2)\) 滿足方程式，所以是一個曲線上的點。
對於這個新系統，一種不錯的看待方式是把 \(p\) 想成是一個很小的正數，像是剛剛 \(-1\) 的無窮級數中，我們把所有的 \(3\) 換成 \(0.1\)： \[2 + 2 \cdot 0.1 + 2 \cdot (0.1)^2 + \cdots\] 那收斂就不會有問題，而模 \(p^k\) 就是無條件捨去到第 \(k\) 位。
我們稱呼原來模 \(p\) 時的曲線 \(E(F_p)\)，而擴展之後的曲線 \(E(Q_p)\)，注意到前者只有 \(p\) 個點 (因為是 anomalous curve)，但後者有無窮多個點。
擴展
換了數字的表達方式後，有些點似乎不見了，例如剛剛說的 \((1, \, 1)\) 並不在曲線 \(E: y^2 = x^3 + 14x + 1\) 上，因為模 \(p^2\) 的時候等號不成立，然而實際上這些點並沒有不見。一開始我們說 \((1, \, 1)\) 在曲線上時，意思是 \((1,\,1)\) 是
\[y^2 \equiv x^3 + ax + b \pmod{p}\]
的解，但我們沒有說 \((1,\, 1)\) 究竟是 \((1, \, 1)\) 還是 \((1 + p, \, 1)\) 又或是 \((1 + 2p, \, 1)\)，這些點在 \(E(F_p)\) 裡是同個點，但在 \(E(Q_p)\) 時卻不一樣，所以如果有一個 \((1 + kp, \, 1)\) 在 \(E(Q_p)\) 裡面，那 \((1, \, 1)\) 並沒有消失，只是換了一個型態。
Hansel's Lemma 告訴我們這些點真的沒有消失。用同樣的例子，我們想要找到 \(k\) 使得 \((1 + kp, \, 1)\) 是 \[y^2 = x^3 + 14x + 1 \pmod{p^2}\] 的解，也就是說 \[1 \equiv (1 + kp)^3 + 14(1 + kp) + 1 \pmod{p^2}\] 這是一個 \(kp\) 的多項式，常數項一定會消成 \(p\) 的倍數，然後 \((kp)\) 二次方以上的都可以直接消掉，最後得到 \[17 kp \equiv -15 \pmod {p^2}\] 只有恰好一個 \(k\) 滿足條件，所以我可以找到一個點 \((1 + kp, \, 1)\)在模 \(p^2\)的時候是正確的，同樣的方法可以找到 \((1 + kp + k'p^2, 1)\) 模 \(p^3\) 時是正確的，然後一直往上推。總結來說，所有 \(E(F_p)\) 的點都可以擴展成 \(E(Q_p)\) 的點。
反過來的話，從 \(E(Q_p)\) 的點轉換成 \(E(F_p)\) 只需要模 \(p\)，照著前面的比喻的話也就是無條件捨去到第一位，而那些有 \(p\) 的負數次方的數字，就全部當成 \(E(F_p)\) 中的無窮遠點 \(O\)。下面的轉換表格使用同樣的曲線且 \(p = 3\)。
| \(E(F_p)\) | \(E(Q_p)\) |
|---|---|
| (-1, 1) | (2 + 6 + 18 + \(\cdots\), 1 + 3) |
| (-1, 1) | (1 + 6 + 9 + 18 + \(\cdots\), 1) |
| (1, 1) | (1, 4) |
| 無窮遠點 | 非整數點(有負數次方) |
可以發現 \(E(F_p)\) 中同樣的點可以對應到好幾種 \(E(Q_p)\) 的點，剛剛上面提到的方法 (Hansel's Lemma) 只是給我們其中一個可能。另外在 \(E(Q_p)\) 中不管什麼點，只要乘上常數 \(|E|\) 就一定會出現負數次方，神奇吧！
這樣的轉換並不會影響橢圓曲線的加法，原來的離散對數是找到 \(n\) 使得 \(Q = nP\) 且 \(P, Q \in E(F_p)\)，現在只需先把 \(P\), \(Q\) 拓展成 \(P'\), \(Q'\)，然後找到 \(n\) 滿足 \(Q' - nP' = O'\)，其中 \(O'\) 是某個非整數點。之後的討論我們都聚焦在 \(E(Q_p)\) 上。
參數化
橢圓曲線雖然沒辦法用很簡單的式子參數化，但我們可以用類似泰勒展開的形式寫成無窮級數，讓所有東西回歸我們熟悉的多項式。
考慮 \(y^2 = x^3 + ax + b\)，我們可以把它換成 \(x = \frac{-x^3 + (y^2 - b)}{a}\)，然後透過不斷的代入得到新的式子，例如說代入一次得到的是
\[x = \frac{1}{a}\left(-\left(\frac{-x^3 + (y^2 - b)}{a}\right)^3 + (y^2 - b)\right)\]
我們期待不斷代入的過程可以讓右式中的 \(x\) 次數越來越大，最後整個式子會收斂成某個 \(x = f(y)\)，然而這樣的操作卻只是一團糟 — 如果 \(a = 0\) 就直接爆炸，就算 \(a \ne 0\)，( 對 \(x\) 來說的 ) 常數項一開始是 \(\frac{y^2 - b}{a}\)，代入一次後多了 \(-\frac{1}{a}\left(\frac{y^2 - b}{a}\right)^3\)，代入次數越多，常數項也越來越多。
我們可以透過改寫式子解決這個問題。令 \(w = \frac{-1}{y}\), \(z = \frac{-x}{y}\)，我們可以把式子改寫成
\[w = z^3 + azw^2 + bw^3\]
這樣的好處是右式的次數都是 \(3\)，所以在代入的過程，右式的次數會越滾越大，而不像剛剛每次代入都會產生新的常數項。作為演示，第一次代入後得到
\[w = z^3 + az\left(z^3+azw^2+bw^3\right)^2 + b\left(z^3+azw^2+bw^3\right)^3\]
\(z^3\) 是裡面次數最小的，所以 \(z^3 \mid w\) (不斷代入並不會產出任何 \(1, z, z^2\) 項)，因此
$\(w = z^3 + az^7 + 2az^5w^2 + bz^6 + z^12(\cdots)\)
可以發現我們已經幾乎推出前 \(12\) 個係數了。最後我們宣稱能找到一個橢圓曲線的參數式 \(w = f(z)\)。雖然 \(f(z)\) 是無窮多項的多項式，而且不太可能收斂，但如果 \(z\) 是 \(p\) 的倍數，那在 \(Q_p\) 的世界下這就是收斂的，因為 \(p\) 的次數越大數字越小。
Isomorphism
有了參數化後我們可以用 \(P(z)\) 來代表一個橢圓曲線上的點 \((\frac{z}{f(z)}, \frac{-1}{f(z)})\)，我們的目標是找到函數 \(\phi: \mathbb{Q} \to \mathbb{Q}\) 使得
\[P(z_1) + P(z_2) = P(z_3) \Leftrightarrow \phi(z_1) + \phi(z_2) = \phi(z_3)\]
注意到左邊的加法是橢圓曲線上的加法，而右邊則是大家熟知的加法。換句話說，我們可以把橢圓曲線的加法「轉換」成正常的加法，所以
\[Q = nP \Leftrightarrow \phi(Q) = n\phi(P)\]
也就是離散對數問題變成簡單的除法：\(n = \frac{\phi(P)}{\phi(Q)}\)。如果不是很清楚這個轉換在做什麼，這邊舉個例子：
\[xy = z \Leftrightarrow \log{x} + \log{y} = \log{z}\]
所以 \(\log\) 把乘法「轉換」成加法，而 \(\log\) 就是我們要的 \(\phi\)
Logarithm Formula
定義 \(F(z_1, z_2) = P^{-1}(P(z_1) + P(z_2))\)，或者說把參數為 \(z_1\) 的點加上參數為 \(z_2\) 的點會得到參數為 \(F(z_1, z_2)\) 的點。上述的目標可以改寫成
\[F(x, y) = z \Leftrightarrow \phi(x) + \phi(y) = \phi(z)\]
如同前面的參數化，\(F\) 也可以用泰勒展開表達成 \(x\) 和 \(y\) 的無窮多項式
\[F(x, y) = F(0, 0) + \frac{\partial F}{\partial x}(0,0)x + \frac{\partial F}{\partial y}(0,0)y + \cdots = x + y + \cdots\]
(\(\frac{\partial F}{\partial x}(0,0) = \lim_{dx \to 0}\frac{F(dx, 0) - F(0, 0)}{dx} = 1\))
一個神奇的公式告訴我們只要 \(F(x, y)\) 滿足
- \(F(0, x) = F(x, 0) = x\)
- \(F(x, F(y, z)) = F(F(x, y), z)\)
- \(F(x, y) = F(y, x)\)
則可以找到想要的 \(\phi\) 函數
\[\phi_F(x) = \int \frac{1}{\frac{\partial F}{\partial y}(x, 0)}dx\]
注意到分母是一個 \(x\) 的多項式，比起真的積分這個多項式的倒數，我們可以利用 \(\frac{1}{1 - x} = 1 + x + x^2 + \cdots\) 這個公式來讓要被積分的式子變成無窮多項式。另外積分一定要有積分常數，所以很自然的我們要求 \(\phi_F(0) = 0\)。
舉個簡單的例子：考慮 \(F'(x, y) = x + y + xy\)，則 \(\frac{\partial F'}{\partial y}(x, 0) = 1 + x\)，所以
\[\phi_{F'}(x) = \int \frac{1}{1 + x} dx = \int (1 - x + x^2 - x^3 + \cdots)dx = x - \frac{1}{2}x^2 + \frac{1}{3} x^3 - \frac{1}{4}x^4 + \cdots\]
最後得出來的式子其實就是 \(\log{(1 + x)}\) 的泰勒展開，而的確 \(\phi(x) + \phi(y) = \log{(1+x)(1+y)}=\phi(F'(x, y))\)。
回頭看 \(F(x, y)\) 需要滿足的條件，由第一條我們可以知道 \(F(x, y) = x + y + \cdots\)，後面省略的是次數比較高的項，根據第二條， \(F\) 有結合率，第三條告訴我們 \(F\) 是對稱的。很明顯三項我們都符合，否則橢圓曲線的加法就不是加法了，所以我們可以得到我們要的\(\phi\) \[\phi_F(x) = \int \frac{1}{1 + x(\cdots)}dx = \int 1 + (x(\cdots)) + (x(\cdots))^2 + \cdots dx = x + x^2(\cdots)\]
收斂
我們得到了想要的 \(\phi\) 但是他不一定會收斂。在 \(Q_p\) 的世界下，如果 \(p \mid z\) 那級數一定會收斂，因為後面的項都是 \(p\) 的好多次方，但如果 \(p\nmid z\)，這個級數八成會發散。究竟什麼時候 \(z\) 會是 \(p\) 的倍數呢？\(z\) 的定義是 \(\frac{-x}{y}\)，在 \(E(F_p)\) 裡只有 \(x = 0\) 時 \(z\) 才會是 \(p\) 的倍數，但是在 \(E(Q_p)\) 裡，如果 \(x\) 和 \(y\) 不是整數，假設 \(x\), \(y\) 在 \(p\) 進位中次方最小的分別是 \(p^{-a}\), \(p^{-b}\) (\(a, b > 0\))，那觀察橢圓曲線 \[y^2 = x^3 + ax + b\] 左式最小次方會是 \(p^{-2b}\) 而右式是 \(p^{-3a}\)，所以 \(3a = 2b\)，這保證 \(a < b\)，也就是說 \(z = \frac{-x}{y}\) 一定是 \(p\) 的倍數。
等一下會用到一個重要的性質：對於非整數點 \(P(z)\)，我們有 \(\phi(z) = z + z^2(...) \equiv z \pmod{p^2}\)。
Smart's Attack
當初計算 \(\phi\) 是為了計算離散對數，然而 \(\phi\) 卻只在非整數點上有定義，所以為了找出 \(Q' - nP' = O'\) 的 \(n\)，直接計算 \(\frac{\phi(Q')}{\phi(P')}\) 是不行的，但是我們可以把整個式子乘上 \(p\) 倍，也就是 \[pQ' - npP' = pO'\] 所以 \[\phi(pQ') - n \phi(pP') = p \phi(O')\] 利用 \(\phi(P(z)) \equiv z \pmod{p^2}\)，我們可以得到 \[n \equiv \frac{\phi(pQ')}{\phi(pP')} \equiv \frac{P^{-1}(pQ')}{P^{-1}(pP')} \pmod{p}\] 注意到最後的分數要先在\(\bmod p^2\)下約掉一個\(p\)才可以記算。總結來說，Smart's Attack 的想法如下：
- 將 \(P\), \(Q\) 擴充成 \(E(Q_p)\) 下的點 \(P'\), \(Q'\)，我們要找到 \(n\) 使得 \(O' = Q'-nP'\) 不是整數點。
- 為了套上 \(\phi\)，我們把式子乘上 \(p\) 倍，得到 \(pO' = pQ' - npP'\)。
- 套上 \(\phi\) 函數得到，\(n \equiv \frac{\phi(pQ')}{\phi(pP')} \pmod p\)
注意到雖然 \(E(Q_p)\) 把所有點擴充到 \(p\) 的好幾次方，但實際上計算時並沒有用到高次項，可以直接省略。另外我們只在乎 \(\phi\) 模 \(p^2\) 的餘數，所以直接計算 \(\frac{-x}{y}\) 就可以了。總而言之，計算 \(\frac{\phi(pQ')}{\phi(pP')}\) 只需要 \(O(\log p)\) 的時間。
Special thanks
ariana and their wonderful blog. 還有余紘勳幫我翻譯了許多艱澀的大學數學用詞。