Sunday, May 17, 2020

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