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產生公私鑰的方式都相同

橢圓曲線公式類似如下

相等於

其中 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:

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 相同

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

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

原理:

小明與阿東 兩人協議好要使用 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 PGP SSH 和部分加密貨幣

(以下範例需使用python2)

#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

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的動作

// 使用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

>