ECDSA數字簽名演算法

5 人贊了文章

一、ECDSA概述

橢圓曲線數字簽名演算法（ECDSA）是使用橢圓曲線密碼（ECC）對數字簽名演算法（DSA）的模擬。ECDSA於1999年成為ANSI標準，並於2000年成為IEEE和NIST標準。它在1998年既已為ISO所接受，並且包含它的其他一些標準亦在ISO的考慮之中。與普通的離散對數問題（discrete logarithm problem DLP）和大數分解問題（integer factorization problem IFP）不同，橢圓曲線離散對數問題（elliptic curve discrete logarithm problem ECDLP）沒有亞指數時間的解決方法。因此橢圓曲線密碼的單位比特強度要高於其他公鑰體制。

數字簽名演算法（DSA）在聯邦信息處理標準FIPS中有詳細論述，稱為數字簽名標準。它的安全性基於素域上的離散對數問題。橢圓曲線密碼（ECC）由Neal Koblitz和Victor Miller於1985年發明。它可以看作是橢圓曲線對先前基於離散對數問題（DLP）的密碼系統的模擬，只是群元素由素域中的元素數換為有限域上的橢圓曲線上的點。橢圓曲線密碼體制的安全性基於橢圓曲線離散對數問題（ECDLP）的難解性。橢圓曲線離散對數問題遠難於離散對數問題，橢圓曲線密碼系統的單位比特強度要遠高於傳統的離散對數系統。因此在使用較短的密鑰的情況下，ECC可以達到於DL系統相同的安全級別。這帶來的好處就是計算參數更小，密鑰更短，運算速度更快，簽名也更加短小。因此橢圓曲線密碼尤其適用於處理能力、存儲空間、帶寬及功耗受限的場合

二、ECDSA原理

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、如果等式成立，接受簽名，否則簽名無效。

三、JDK中對於ECDSA的實現

特別注意的是：ECDSA簽名演算法，只是在JDK1.7之後才有實現，最常見的場景是在微軟的產品的安裝的產品密鑰的設計

1、KeyPairGenerator

KeyPairGenerator 類用於生成公鑰和私鑰對。密鑰對生成器是使用 getInstance 工廠方法（返回一個給定類的實例的靜態方法）構造的。

特定演算法的密鑰對生成器可以創建能夠與此演算法一起使用的公鑰/私鑰對。它還可以將特定於演算法的參數與每個生成的密鑰關聯。

有兩種生成密鑰對的方式：與演算法無關的方式和特定於演算法的方式。

下面我們將按照指定ECDSA演算法去生成秘鑰KeyPairGenerator.getInstance("EC");

2、ECDSAPublicKey

ECDSA公用密鑰的介面

3、ECDSAPublicKey

ECDSA 專用密鑰的介面

4、PKCS8EncodedKeySpec

PKCS8EncodedKeySpec類繼承EncodedKeySpec類，以編碼格式來表示私鑰。

PKCS8EncodedKeySpec類使用PKCS#8標準作為密鑰規範管理的編碼格式

5、Signature

Signature 類用來為應用程序提供數字簽名演算法功能。數字簽名用於確保數字數據的驗證和完整性。

在所有演算法當中，數字簽名可以是 NIST 標準的 ECDSA，它使用 ECDSA 和 SHA-1。可以將使用 SHA-1 消息摘要演算法的 ECDSA 演算法指定為SHA1withECDSA。

四、實現

其中ECDSA的實現步驟類似於我們之前學習的RSA數字簽名演算法

實現步驟

第一步：初始化化秘鑰組，生成ECDSA演算法的公鑰和私鑰

第二步：執行私鑰簽名， 使用私鑰簽名，生成私鑰簽名

第三步：執行公鑰簽名，生成公鑰簽名

第四步：使用公鑰驗證私鑰簽名

備註：所謂的公鑰與私鑰匙成對出現。 遵從的原則就是「私鑰簽名、公鑰驗證」。

示例代碼如下：

import java.security.KeyFactory;import java.security.KeyPair;import java.security.KeyPairGenerator;import java.security.PrivateKey;import java.security.PublicKey;import java.security.Signature;import java.security.interfaces.ECPrivateKey;import java.security.interfaces.ECPublicKey;import java.security.spec.PKCS8EncodedKeySpec;import java.security.spec.X509EncodedKeySpec;/** * 橢圓曲線簽名演算法 * * 速度快 強度高 簽名短 * * 實現方 JDK1.7/BC */public class ECDSAUtil { private static String str = "hello"; public static void main(String[] args) { jdkECDSA(); } public static void jdkECDSA() { try { KeyPairGenerator keyPairGenerator = KeyPairGenerator.getInstance("EC"); keyPairGenerator.initialize(256); KeyPair keyPair = keyPairGenerator.generateKeyPair(); ECPublicKey ecPublicKey = (ECPublicKey) keyPair.getPublic(); ECPrivateKey ecPrivateKey = (ECPrivateKey) keyPair.getPrivate(); // 2.執行簽名 PKCS8EncodedKeySpec pkcs8EncodedKeySpec = new PKCS8EncodedKeySpec(ecPrivateKey.getEncoded()); KeyFactory keyFactory = KeyFactory.getInstance("EC"); PrivateKey privateKey = keyFactory.generatePrivate(pkcs8EncodedKeySpec); Signature signature = Signature.getInstance("SHA1withECDSA"); signature.initSign(privateKey); signature.update(str.getBytes()); byte[] sign = signature.sign(); // 驗證簽名 X509EncodedKeySpec x509EncodedKeySpec = new X509EncodedKeySpec(ecPublicKey.getEncoded()); keyFactory = KeyFactory.getInstance("EC"); PublicKey publicKey = keyFactory.generatePublic(x509EncodedKeySpec); signature = Signature.getInstance("SHA1withECDSA"); signature.initVerify(publicKey); signature.update(str.getBytes()); boolean bool = signature.verify(sign); System.out.println(bool); } catch (Exception e) { e.printStackTrace(); } }}

五、ECDSA標準

ECDSA的標準和標準草案有很多，其中已經過頒發部門批准的有：ANSI X9.62 ,FIPS 186-2,IEEE 1363-2000,ISO 14888-3。ECDSA也被密碼標準化組織（SECG，這是一個從事密碼標準通用性潛力研究的組織）加以標準化。

主要的ECDSA標準

1.ANSI X9.62

該項目始於1995年，並於1999年正式作為ANSI標準頒布。ANSI X9.62具有高安全性和通用性。它的基域可以是Fp，也可以是F2m。F2m中的元素可以以多項式形式或正規基形式來表示。若用多項式形式，ANSI X9.62要求模多項式為不可約三項式，標準中提供了一些不可約三項式，另外還給出了一個不可約五項式。為了提高通用性，針對每一個域提供了一個模多項式。若使用正規基表示方法，ANSI X9.62規定使用高斯正規基。橢圓曲線最主要的安全因素是n，即基點階，ANSI X9.62的n大於2160。橢圓曲線是使用隨機方法選取的。ANSI X9.62規定使用以位元組為單位的字元串形式來表示曲線上的點，ASN.1語法可以清楚地描述域參數，公鑰和簽名。

2.FIPS 186-2

1997年，NIST開始制定包括橢圓曲線和RSA簽名演算法的FIPS 186標準。1998年，NIST推出了FIPS186，它包括RSA與DSA數字簽名方案，這個方案也稱為FIPS 186-1。1999年NIST又面向美國G0vment推出了15種橢圓曲線。這些曲線都遵循ANSI X9.62和IEEE 1363-2000的形式。2000年，包含ANSI X9.62中說明的ECDSA，使用上述曲線的FIPS 186-2問世。

3. IEEE 1363-2000

該標準於2000年作為IEEE標準問世。IEEE 1363的覆蓋面很廣，包括公鑰加密，密鑰協商，基於IFP、DLP、ECDLP的數字簽名。它與ANSI X9.62和FIPS 186完全不同，它沒有最低安全性限制（比如不再對基點階進行限制），用戶可以有充分的自由。

因此IEEE 1363-2000並不是一個安全標準，也不具有良好的通用性，它的意義在於給各種應用提供參照。它的基域可以是，也可以是。 中的元素可以以多項式形式或正規基形式來表示。中元素表示形式是整數，中元素表示形式是字元串。這與ANSI X9. 62和FIPS 186是一致的。

4.ISO/IEC 14888-3

這個標準包含若干簽名演算法，其中ECDSA部分與ANSI X9.62一致。

如果大家有興趣可以研究下，ECDSA演算法在比特幣中用法。