施諾爾數字簽名
我試圖重寫橢圓曲線的 Schnorr 簽名算法，但我想確保沒有犯任何錯誤。因此，如果有人可以查看此算法並告訴我是否做錯了什麼或不夠精確，我會非常高興：
讓 $ E $ 是有限域上的橢圓曲線 $ \mathbb{F}_q $ （第一個問題，是不是和 ECDSA 一樣， $ q=p $ 奇數素數或 $ q=2^m $ ?) 帶有這樣的參數 $ E $ 是加密安全曲線。
密鑰生成：
選擇 $ P\in E(\mathbb{F}_q) $ 素數的 $ l $ ， 在哪裡 $ l $ 是一個大素數。
選擇 $ 1 < a < l $ 隨機併計算 $ Q = a*P $ . 那麼公開資訊就是 $ E, \mathbb{F}_q, Q, P $ 並且私有簽名密鑰是 $ a $ .
簽名方案：
- 隨機選擇 $ 1 \leq k < l $
- 計算 $ S_0 = kP = (x_0,y_0) $
- 計算 $ s_1 = H(m||x_0) $ ， 在哪裡 $ H $ 是一個雜湊函式， $ x_0 $ 是整數值 $ x_0 $ 和 $ m $ 是消息。
- 計算 $ s_2 \equiv k + a*s_1 \text{ (mod }l) $
數字簽名是 $ (S_0,s_2) $ 和愛麗絲發送 $ (m, (S_0,s_2)) $ 給鮑勃。
確認
Bob 驗證是否 $ s_2*P=S_0+H(m||x_0)*Q $ .
這有效，因為：
$$ s_2P=S_0+H(m||x_0)Q $$ $$ \Leftrightarrow s_2P-H(m||x_0)Q = S_0 $$ $$ \Leftrightarrow (k+as_1)-H(m||x_0)aP = S_0 $$ $$ \Leftrightarrow kP + aH(m||x_0)P-aH(m||x_0)P=S_0=k*P $$
是的，可用於 ECDSA 的幾乎相同的組可用於 Schnorr 簽名。那是在
$$ Sc91 $$（請參閱此問題中的參考書目）：
可以使用有限群來實現上述簽名和認證方案 $ G $ 除了子群 $ \mathbb Z_p^* $ 單位在 $ \mathbb Z_p $ (..) 合適組的範例是類組和橢圓曲線 $ E(K) $ 在有限域上 $ K $ .
看起來您為橢圓曲線發明了 Schnorr 簽名算法的另一種變體，而不是在這個答案中的大約 6 個中。你的發送一個組元素而不是散列作為簽名的第一部分（因此更直接地將轉換匹配到 Schnorr 辨識協議的簽名，並允許更直接的安全證明）。這對 ISO/IEC 14888-3 ( OID 1.0.14888.3.0.12 )的 EC-FSDSA (Elliptic Curve Full Schnorr Digital Signature Algorithm) 有很強的味道，但是：
出於某種原因，你計算 $ H(m|x_0) $ 而不是 $ H(x_0|y_0|m) $ 在上述標準中；以後我寫 $ H(\dots) $ . 對於 ROM 中的理想散列和證明，散列 $ m $ 第一個或第二個無關緊要，我無法確定它是否對實際雜湊有任何安全影響。不散列 $ y_0 $ 可能會花費一些安全性。
您的驗證程序省略了驗證 $ S_0 $ 是曲線上的一個點，這似乎有風險，因為您對其執行點加法。該標準要求進行此項檢查。
我的理解是標準確實 $ Q=-a\times P $ （正如 Schnorr 建議的那樣$$ Sc89 $$)，以便驗證可以計算 $ s_2\times P+H(\dots)\times Q $ 並將其與 $ S_0 $ ，有兩個優點：
- 的計算 $ s_2\times P+H(\dots)\times Q $ 可以使用最簡單的Shamir 技巧或其他形式
- 檢查 $ S_0 $ 是曲線上的一個點變得多餘。
注意：對於橢圓曲線 $ y^2\equiv x^3–3x+b\pmod p $ 至少（包括 NIST 在素數欄位上的 FIPS 186-4 曲線），而您沒有散列 $ y_0 $ 並使用非標準的東西，你也可以省略 $ y_0 $ 來自簽名，帶有驗證計算 $ s_2\times P+H(\dots)\times Q $ 並比較它 $ x $ 協調到 $ x_0 $ . 這將簽名從 $ 6b $ 至 $ 4b $ 為了 $ b $ -bit 安全性，並且（對於理想的散列）最多花費 1 位安全性（可能沒有），因為 $ y $ 可以從 $ x $ 標誌內。