今天就來介紹怎麼用橢圓曲線做數位簽章吧！

簽章

先來想想什麼叫做簽章，所謂的簽名就是證明 "訊息是來自於現在對面傳訊息之人"。
一個最簡單的例子就是許多人可能比較熟悉的 RSA 簽章，透過發訊者事先公開公鑰 N, e，自行發出訊息後把它取 Hash 再用只有自己知道的私鑰 d 取 d 次方後對 N 取 mod，作為簽章值。
最後外界

• 算出訊息的 Hash
• 拿公鑰把簽章取 e 次方在對 N 取模

就看看是不是跟訊息的 Hash 一樣就知道是不是由公開公鑰的人發出的了！

ECDSA

首先，會先在曲線（曲線一定是公開的）上取一點 G 並公開、一個私鑰 t，並計算 Q = t * G，把 Q 也公開出來。
接下來的簽章方法是：

（一樣掏出我以前的簡報，排版比較好看）
（這邊的運算都在 mod p 底下）
（如果有 iThome 管理員看到訊息希望以後 Markdown 支援 LaTeX）

注意到 VERIFIER 驗證簽章時取的 u1 * G + u2 * Q 會很巧妙地變成
z * w * G + r * w * t * G
= （k/(z+r*t) * (z+r*t)）G = k * G = R，x座標自然就是 r。
最後注意到 ECDSA 的安全性一樣是基於 DLP 的難解性。

最後，顯然當產生的隨機數 k 重用/有線性關係的時候會發現由於 s 的產生全為線性過程，移項可以解線性方程還原 k 值。
另外，當 k 過小（比 p 的量級小）有一種叫做 CVP 的演算法可以透過接近向量解開。（詳見　[1]）

筆者在 2025 AIS3 Pre Exam 出的題目：
https://github.com/William957-web/My-CTF-Challenges/tree/main/AIS3-Pre-Exam/2025/SlowECDSA [2]

一些 Murmur

講完數學背景後快速說一下為什麼要用 ECDSA，注意到 RSA 數位簽章往往需要 2048 bits 大小左右的公鑰 N，等價於 224 bits 的 ECDSA 安全性，可以看出 ECDSA 所需的計算空間是小很多的！

References

• [1] https://eprint.iacr.org/2021/347.pdf
• [2] https://github.com/William957-web/My-CTF-Challenges/tree/main/AIS3-Pre-Exam/2025/SlowECDSA