Schnorr Signature 的動機
提到電子簽名，最常見的包括以 RSA 為基礎的 RSA，或者以橢圓曲線為基礎的 ECDSA。
這些算法雖然普遍，但普遍來講因為算法複雜，耗時也比較高。
Schnorr Signature 就是基於這個背景下產生的：由於它算法簡單易明，速度也比較快。
Schnorr Signature 的算法簡介
1. 初始化：
- 首先產生一個 Schnorr Group Parameters，得出 generator (g) 和 prime order (q)。
- 選取一個 cryptographic hash function H。
2. 產生 Key：
- 隨機產生一個 x，這個 x 必需與 q 是 relatively prime，這個將成為 Private Key。
- 運用 y = g^x 產生 y，這個成為 Public Key。
3. 簽名：
- 隨機產生一個 k，這個 k 必需與 q 是 relatively prime
- 計算 r = g^k
- 計算 e = H( r || M ) 或可寫作 H ( g^k || M )，當中 M 是訊息，|| 指組連 (concatenate)
- 計算 s = k - xe，或可寫作 s = k - x*H( g^k || M )
- 公布 (s, e) 出去，也可以寫成 ( k-xe, e )，這個就是 Schnorr Signature 簽名 (digest)。
PS：如果 prime order 是小於 2^160 (160 bit) 的話，基本上 s 和 e 各佔不多於 40 bytes (320 bits)。
PS2：過程當中，簽署方必須小心，k 的數值必須每次不同，否則如果有兩條不同 M，其他人就可以透過得出的 s 和 s'，透過相減約走 k，繼而找出 x：
- s - s' = (k-xe) - (k'-xe') = (k-k') - x(e-e') = 0 - x(e-e')
- 因為 e' 和 e' 均是由相同的 g^k 疊加已知的 M 或 M' 再 hash 而成，
所以只要不斷撞，很大機會能找回 concat 的 g^k 值到底是什麼，最後找回 x。
4. 驗證簽名：
- 手持 Public Key y = g^x
- 計算 r_verify = g^s * y^e = g^(k - xe) * g^(xe) = g^( k - xe + xe ) = g^k
- 計算 e_verify = H ( r_verify || M ) = H ( g^k || M )
- 如果 e_verify 與 e 相等，簽名則為有效。
Schnorr Signature 的缺點
由於它計算快捷，普遍來講，相對其他複雜的算法，它更易撞到，也就是更容易破解。
所以，一般而言，密碼學家認為它需要比其他算法長 4 倍，才能達到相近的強度。例如 NIST 256-bit 來講，Schnorr Signature 最少需要 1024 bit 簽名長度，才能達到 ECDSA 的 ECDSAwithSHA256 (256 bit) 簽名相等的安全性。
（也有其他新的論文提到了 Short Schnorr Signature，它的長度能減少至 3t 右右。）
基於橢圓曲線 (Elliptic Curve) 的 Schnorr Signature
有一種算法 EdDSA，正正使用相類似的原理運作。
它採用特殊的曲線，達至相類似的效果。而且廢除了隨機產生的 k，減低密碼外流的風險。
---
參考：
[1] - https://en.wikipedia.org/wiki/Schnorr_signature
