打破橢圓曲線的 El Gamal
有一個橢圓曲線 El Gamal 數字簽名方案。愛麗絲修復了一條橢圓曲線 $ E $ , 一個素數 $ p $ ， 一個點 $ A $ 上 $ E $ , 一個秘密整數 $ a $ , 併計算 $ B = aA $ . 她做 $ (E, p, A, B) $ 上市。為了簽署消息 m（它是一個整數），她計算一個點 $ R = (x, y) $ 上 $ E $ 和一個整數 $ s $ , 並發送 $ (m, R, s) $ . 驗證是 $ xB + sR = mA $ . 夏娃選擇 $ R1 = B − A = (x1, y1) $ .
我如何找到一個整數 $ s1 $ 和留言 $ m1 $ 以便 $ (m1, R1, s1) $ 是有效的簽名嗎？
我提到這一點是為了將正常的 El Gamal 與橢圓曲線上的那個聯繫起來，但我不能這樣做。另外，為什麼在這種情況下需要散列來防止這種偽造？
作為比雨披更通用的答案，它適用於所有曲線，而不僅僅是那些具有順序點 2 的曲線：我們可以簡單地計算 $$ x_1 B + s_1 R_1 = x_1 B + s_1 (B-A) = (x_1+s_1) B - s_1 A. $$ 因此，採 $ s_1 = -x_1 $ 和 $ m = -s_1 = x_1 $ 給出了一個偽造。
所以“沒有散列函式”的方案顯然是不安全的。但即使“使用散列函式”，也可能無法為這種不合理的構造編寫乾淨的安全證明（類似於 ECDSA 發生的情況）。請讓我們使用 Schnorr。
好吧，一種明顯的方法（假設橢圓曲線上有一個點 $ x=0 $ ，或者驗證者不檢查是否 $ R $ 在曲線上）是：
$$ m1 = 0 $$ $$ R1 = (0, y) $$ $$ s1 = 0 $$
這滿足驗證方程…