ECDSA簽名算法介紹

橢圓曲線數字簽名算法（ECDSA）是使用橢圓曲線密碼（ECC）對數字簽名算法（DSA）的模擬。與普通的離散對數問題（DLP）和大數分解問題（IFP）不同，橢圓曲線離散對數問題沒有亞指數時間的解決方法。因此橢圓曲線密碼的單位比特強度要高于其他公鑰體制。

數字簽名算法（DSA）在聯邦信息處理標準FIPS中有詳細論述，稱為數字簽名標準。它的安全性基于素域上的離散對數問題?？梢钥醋魇菣E圓曲線對先前離散對數問題（DLP）的密碼系統的模擬，只是群元素由素域中的元素數換為有限域上的橢圓曲線上的點。橢圓曲線離散對數問題遠難于離散對數問題，單位比特強度要遠高于傳統的離散對數系統。因此在使用較短的密鑰的情況下，ECC可以達到于DL系統相同的安全級別。這帶來的好處就是計算參數更小，密鑰更短，運算速度更快，簽名也更加短小。

ECDSA是ECC與DSA的結合，整個簽名過程與DSA類似，所不一樣的是簽名中采取的算法為ECC，最后簽名出來的值也是分為r,s。
 簽名過程如下：
   1、選擇一條橢圓曲線Ep(a,b)，和基點G；
   2、選擇私有密鑰k（k<n，n為G的階），利用基點G計算公開密鑰K=kG；
   3、產生一個隨機整數r（r<n），計算點R=rG；
   4、將原數據和點R的坐標值x,y作為參數，計算SHA1做為hash，即Hash=SHA1(原數據,x,y)；
   5、計算s≡r - Hash * k (mod n)
   6、r和s做為簽名值，如果r和s其中一個為0，重新從第3步開始執行
驗證過程如下：
   1、接受方在收到消息(m)和簽名值(r,s)后，進行以下運算
   2、計算：sG+H(m)P=(x1,y1), r1≡ x1 mod p。
   3、驗證等式：r1 ≡ r mod p。
   4、如果等式成立，接受簽名，否則簽名無效。