Schnorr Signature 簡介

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