# ECDSA & ECDH

## ECDSA & ECDH

有三個類似名詞為**ECC、ECDH、ECDSA，第一個是**Elliptic Curve Cryptography的縮寫，而後面兩個都是基於ECC的加密演算法

```
（1）相同密鑰長度下，安全性能更高，如160位ECC已經與1024位RSA、DSA有相同的安全強度。
（2）計算量小，處理速度快，在私鑰的處理速度上（解密和簽名），ECC遠 比RSA、DSA快得多。
（3）存儲空間占用小 ECC的密鑰尺寸和系統參數與RSA、DSA相比要小得多， 所以占用的存儲空間小得多。
```

```
 ECDH和ECDSA產生公私鑰的方式都相同
```

橢圓曲線公式類似如下

## ![](/files/-M0u4_vLrh5SKalynonY)相等於![](/files/-M0u4_vNuAXra3fRW2Zz)

其中 p 是 2²⁵⁶-2³²-2⁹-2⁸-2⁷-2⁶-2⁴-1，是一個很大的質數

例如以下範例座標 (x, y) 就是這曲線中的一點

```
p = 2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 - 1
x = 55066263022277343669578718895168534326250603453777594175500187360389116729240
y = 32670510020758816978083085130507043184471273380659243275938904335757337482424
(x**3 + 7 - y**2) % p
0
```

## ECC (Elliptic curve cryptography)

列出可用OpenSSL可用曲線

```
openssl ecparam -list_curves
```

以下網站可看到各曲線的Base Point

<https://safecurves.cr.yp.to/base.html>

曲線方程式 Ep(a, b) 為以下型態:

```
y**2 = x**3 + ax + b (mod p)
```

## ECDH

用途:

```
讓兩人不透漏私密訊息的情況下獲得一把共同的密鑰
```

ECDH可視為ECC + DH (Diffie-Hellman)

Ex:

```javascript
var crypto = require('crypto');

// 1.
var ecdh = crypto.createECDH('secp256k1');
ecdh.generateKeys();
var publicKey = ecdh.getPublicKey(null, 'compressed');

// 2.
var ecdh2 = crypto.createECDH('secp256k1');
ecdh2.generateKeys();
var publicKey2 = ecdh2.getPublicKey(null, 'compressed');

// 3.
var ecdh3 = crypto.createECDH('secp256k1');
ecdh3.generateKeys();
var publicKey3 = ecdh3.getPublicKey(null, 'compressed');

// 4.
var ecdh4 = crypto.createECDH('secp256k1');
ecdh4.generateKeys();
var publicKey4 = ecdh4.getPublicKey(null, 'compressed');


//以下倆倆為一組，因用A之ecdh與B之public key 算出之結果與用 B之ecdh 與A之public key 相同
var secret = ecdh.computeSecret(publicKey2);
console.log('Secret1: ', secret.length, secret.toString('hex'));

var secret2 = ecdh2.computeSecret(publicKey);
console.log('Secret2: ', secret2.length, secret2.toString('hex'));

var secret3 = ecdh3.computeSecret(publicKey4);
console.log('Secret3: ', secret3.length, secret3.toString('hex'));

var secret4 = ecdh4.computeSecret(publicKey3);
console.log('Secret4: ', secret4.length, secret4.toString('hex'));
```

結果如下:

\> 以下倆倆為一組，因用A之ecdh與B之public key 算出之結果與用 B之ecdh 與A之public key 相同

![](/files/-M0u4_vQ7KsIrzif7ebd)

> 但你可能會問兩個人算出共同密鑰可以做什麼?

通常過程是:兩人只要把自己的public key給對方來算出secret key，之後用這把secret去做AES之類加密，即可在不傳遞真正密鑰的情況下只有兩人可以解密

原理:

![](/files/-M0u4_vSmG3EOQu7EXy_)

```
小明與阿東 兩人協議好要使用 p=23以及 g=5.

小明選擇一個秘密整數a=6, 計算A = (g ** a) % p 然後傳給給阿東。
A = (5 ** 6) % 23 = 8.

阿東選擇一個秘密整數b=15, 計算B = (g ** b) % p 然後傳給小明。
B = (5 ** 15) % 23 = 19.

小明計算s = (B ** a) % p
(19 ** 6) % 23 = 2.
阿東計算s = (A ** b) % p
(8 ** 15) % 23 = 2.
```

## ECDSA（The Elliptic Curve Digital Signature Algorithm）

ECDSA也可視為ECC+DSA(Digital Signature Algorithm)

視覺化網站:<https://cdn.rawgit.com/andreacorbellini/ecc/920b29a/interactive/reals-add.html>

常見用於:[TLS](https://tools.ietf.org/html/rfc4492) [PGP](https://tools.ietf.org/html/rfc6637) [SSH](https://tools.ietf.org/html/rfc5656) 和部分加密貨幣

(以下範例需使用python2)

```python
#coding=utf-8

Pcurve = 2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 -1 # The proven prime 
N=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 # Number of points in the field
Acurve = 0; Bcurve = 7 # This defines the curve. y^2 = x^3 + Acurve * x + Bcurve
Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240
Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424
GPoint = (Gx,Gy) # This is our generator point. Tillions of dif ones possible

#Individual Transaction/Personal Information
privKey = 75263518707598184987916378021939673586055614731957507592904438851787542395619 #replace with any private key
RandNum = 28695618543805844332113829720373285210420739438570883203839696518176414791234 #replace with a truly random number
HashOfThingToSign = 86032112319101611046176971828093669637772856272773459297323797145286374828050 # the hash of your message/transaction

def modinv(a,n=Pcurve): #Extended Euclidean Algorithm/'division' in elliptic curves
    lm, hm = 1,0
    low, high = a%n,n
    while low > 1:
        ratio = high/low
        nm, new = hm-lm*ratio, high-low*ratio
        lm, low, hm, high = nm, new, lm, low
    return lm % n

def ECadd(xp,yp,xq,yq): # Not true addition, invented for EC. It adds Point-P with Point-Q.
    m = ((yq-yp) * modinv(xq-xp,Pcurve)) % Pcurve
    xr = (m*m-xp-xq) % Pcurve
    yr = (m*(xp-xr)-yp) % Pcurve
    return (xr,yr)

def ECdouble(xp,yp): # EC point doubling,  invented for EC. It doubles Point-P.
    LamNumer = 3*xp*xp+Acurve
    LamDenom = 2*yp
    Lam = (LamNumer * modinv(LamDenom,Pcurve)) % Pcurve
    xr = (Lam*Lam-2*xp) % Pcurve
    yr = (Lam*(xp-xr)-yp) % Pcurve
    return (xr,yr)

def EccMultiply(xs,ys,Scalar): # Double & add. EC Multiplication, Not true multiplication
    if Scalar == 0 or Scalar >= N: raise Exception("Invalid Scalar/Private Key")
    ScalarBin = str(bin(Scalar))[2:]
    Qx,Qy=xs,ys
    for i in range (1, len(ScalarBin)): # This is invented EC multiplication.
        Qx,Qy=ECdouble(Qx,Qy); # print "DUB", Qx; print
        if ScalarBin[i] == "1":
            Qx,Qy=ECadd(Qx,Qy,xs,ys); # print "ADD", Qx; print
    return (Qx,Qy)

print; print "******* Public Key Generation *********"
xPublicKey, yPublicKey = EccMultiply(Gx,Gy,privKey)
print "the private key (in base 10 format):"; print privKey; print
print "the uncompressed public key (starts with '04' & is not the public address):"; print "04",xPublicKey,yPublicKey

print; print "******* Signature Generation *********"
xRandSignPoint, yRandSignPoint = EccMultiply(Gx,Gy,RandNum)
r = xRandSignPoint % N; print "r =", r
s = ((HashOfThingToSign + r*privKey)*(modinv(RandNum,N))) % N; print "s =", s

print; print "******* Signature Verification *********>>"
w = modinv(s,N)
xu1, yu1 = EccMultiply(Gx,Gy,(HashOfThingToSign * w)%N)
xu2, yu2 = EccMultiply(xPublicKey,yPublicKey,(r*w)%N)
x,y = ECadd(xu1,yu1,xu2,yu2)
print r==x; print
```

## 另一個範例使用jsrsasign模組

<https://www.npmjs.com/package/jsrsasign>

```javascript
var r = require('jsrsasign');
var ec = new r.ECDSA({ 'curve': 'secp256r1' });
var keypair = ec.generateKeyPairHex();
var pubhex = keypair.ecpubhex; // hexadecimal string of EC public key
var prvhex = keypair.ecprvhex; // hexadecimal string of EC private key

console.log(pubhex)
console.log(prvhex)

msg1 = 123;

var sig = new r.Signature({ "alg": 'SHA256withECDSA' });
sig.init({ d: prvhex, curve: 'secp256r1' });
sig.updateString(msg1);
var sigValueHex = sig.sign();

var sig = new r.Signature({ "alg": 'SHA256withECDSA' });
sig.init({ xy: pubhex, curve: 'secp256r1' });
sig.updateString(msg1);
var result = sig.verify(sigValueHex);
if (result) {
  console.log("valid ECDSA signature");
} else {
  console.log("invalid ECDSA signature");
}
```

### #或是可使用Node.js的Crypto模組之ECDH來產生相同曲線之公私鑰

然後使用 jsrsasign 的Signature函式，並用同樣之secp256k1 curve來進行sign的動作

```javascript
// 使用Node.js的ECDH來產生公鑰與私鑰
const crypto = require('crypto');
const bob = crypto.createECDH('secp256k1');
bob.generateKeys();
prvhex = bob.getPrivateKey().toString('hex')
pubhex = bob.getPublicKey().toString('hex')
console.log(prvhex)
console.log(pubhex)

msg1 = 123;


// 使用jsrsasign 的Signature函式，並用同樣之secp256k1  curve來進行sign的動作
var r = require('jsrsasign');
var ec = new r.ECDSA({ 'curve': 'secp256k1' });

var sig = new r.Signature({ "alg": 'SHA256withECDSA' });
sig.init({ d: prvhex, curve: 'secp256k1' });
sig.updateString(msg1);
var sigValueHex = sig.sign();

var sig = new r.Signature({ "alg": 'SHA256withECDSA' });
sig.init({ xy: pubhex, curve: 'secp256k1' });
sig.updateString(msg1);
var result = sig.verify(sigValueHex);
if (result) {
  console.log("valid ECDSA signature");
} else {
  console.log("invalid ECDSA signature");
}
```

#### secp256k1

為比特幣私鑰產生公鑰時所使用的曲線

算出來後其結構可分為02或04 後面接上 x 在接上 y

02開頭為compress(只有x座標前面接上02因為有了x就可以代數進去方程式求得y，可以減少字串長度)

<http://www.secg.org/sec2-v2.pdf>

\>![](/files/-M0u4_vU4hPvt4jSyFhk)

![](/files/-M0u4_vWqgs2ycH9i5a7)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://easonwang.gitbook.io/crypto/ecdsa.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.