ECC Node.js

前情

上篇《基于 ECC 的私钥转为公钥的过程》讲到求椭圆曲线上的点时,用的是基于 Python 的 SAGE。为了方便 Node.js 程序员理解和实现完整流程代码,本篇用 Node.js 库实现椭圆曲线点的计算。

用 Node.js 求椭圆曲线的点

库的选型考虑 eosjs 用的 ecurveelliptic

1. ecurve

1
2
3
4
5
6
7
8
const ecurve = require('ecurve')
const BigInteger = require('bigi')

const k1 = ecurve.getCurveByName('secp256k1')
const pk = BigInteger.fromHex('d2653ff7cbb2d8ff129ac27ef5781ce68b2558c41a74af1f2ddca635cbeef07d')
const pub = k1.G.multiply(pk)
pub.affineX.toHex()
pub.affineY.isEven()

得到 x 值为 c0ded2bc1f1305fb0faac5e6c03ee3a1924234985427b6167ca569d13df435cf,y 为偶数,和 SAGE 计算结果一样。

2. elliptic

流程基本一样,所以这里给出完整转换代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
* @author UMU618 <umu618@hotmail.com>
* @copyright MEET.ONE 2019
* @description Use block-always-using-brace npm-coding-style.
*/


'use strict'


const bsc = require('bs58check')
const ripemd160 = require('ripemd160')
const bs = require('bs58')
const elliptic = require('elliptic')
const BN = require('bn.js')

function encodePublicKey(payload) {
const checksum = new ripemd160().update(payload).digest()

return bs.encode(Buffer.concat([
payload,
checksum.slice(0, 4)
]))
}

function privateKeyToPublicKey(privateKey) {
const buf = bsc.decode(privateKey)
if (0x80 !== buf[0]) {
throw new Error('Not a private key.')
}
const k1 = elliptic.curves.secp256k1
const pvt = new BN(buf.slice(1), 'be')
const pub = k1.g.mul(pvt)
const y = pub.getY().isEven() ? 2 : 3
return 'EOS' + encodePublicKey(Buffer.from([y].concat(pub.getX().toArray())))
}

const privateKey = '5KQwrPbwdL6PhXujxW37FSSQZ1JiwsST4cqQzDeyXtP79zkvFD3'
const publicKey = privateKeyToPublicKey(privateKey)

console.log(privateKey)
console.log(publicKey)

3. 对比

elliptic 比较好用,比较快。

代码

https://github.com/UMU618/secp256k1-tools

基于 ECC 的私钥转为公钥的过程

基本知识

ECC 体系中,私钥是一个大型随机数,而公钥则是私钥乘以椭圆曲线上的基点后对应的点。

meet-one/private-to-public 是 MEET.ONE 开发的私钥转公钥工具。

EOS 支持的 EC 有两种:secp256k1(以下简称 k1)、secp256r1,下面以 k1 为例,结合 Node.js 和 Python 代码介绍转换过程。

涉及算法

  • BASE58:编解码私钥、公钥。
  • SHA-256:校验私钥,本文忽略此步。
  • ECC, secp256k1:计算公钥。
  • RIPEMD-160:校验公钥。

转换过程

1. 解码私钥

假设私钥为:5KQwrPbwdL6PhXujxW37FSSQZ1JiwsST4cqQzDeyXtP79zkvFD3,这是 base58 编码,用 bs58 库解码:

1
2
3
const bs = require('bs58')

bs.decode('5KQwrPbwdL6PhXujxW37FSSQZ1JiwsST4cqQzDeyXtP79zkvFD3')

得到 <Buffer 80 d2 65 3f f7 cb b2 d8 ff 12 9a c2 7e f5 78 1c e6 8b 25 58 c4 1a 74 af 1f 2d dc a6 35 cb ee f0 7d aa 08 64 4a>,其中第 1 个字节 0x80 是类型,末尾的 4 字节是校验码。

这里我们不关心校验码,也可以直接用 bs58check 解码:

1
2
3
const bsc = require('bs58check')

bsc.decode('5KQwrPbwdL6PhXujxW37FSSQZ1JiwsST4cqQzDeyXtP79zkvFD3')

得到 <Buffer 80 d2 65 3f f7 cb b2 d8 ff 12 9a c2 7e f5 78 1c e6 8b 25 58 c4 1a 74 af 1f 2d dc a6 35 cb ee f0 7d>,去掉首字节后为:

d2 65 3f f7 cb b2 d8 ff 12 9a c2 7e f5 78 1c e6 8b 25 58 c4 1a 74 af 1f 2d dc a6 35 cb ee f0 7d

这是 256bit 整数的 Big endian 字节流表示,转为 16 进制整形为 0xd2653ff7cbb2d8ff129ac27ef5781ce68b2558c41a74af1f2ddca635cbeef07d,记为 pk

2. 构造椭圆曲线,求公钥的坐标

根据 SECG 规定的 k1 的参数,我们用基于 Python 的 SAGE 构造 k1 对应的椭圆曲线,然后计算 pk * G

1
2
3
4
5
6
7
8
9
a = 0
b = 7
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
Gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
E = EllipticCurve (GF(p), [a, b])
pk = 0xd2653ff7cbb2d8ff129ac27ef5781ce68b2558c41a74af1f2ddca635cbeef07d
G = E(Gx, Gy)
pk * G

结果为:(87237761414843254130560834629777710286905276524352264071298714336416392033743 : 108016191455113306196371645921919775466659772908675410052799661524790827329728 : 1)

注:这里的 (x : y : z) 是射影坐标,一般采用笛卡尔坐标系表示,为 (x/z, y/z)。

3. 编码公钥

取 x 值:87237761414843254130560834629777710286905276524352264071298714336416392033743

16 进制为:0xc0ded2bc1f1305fb0faac5e6c03ee3a1924234985427b6167ca569d13df435cf

Big endian 字节流表示为:[0xc0, 0xde, 0xd2, 0xbc, 0x1f, 0x13, 0x05, 0xfb, 0x0f, 0xaa, 0xc5, 0xe6, 0xc0, 0x3e, 0xe3, 0xa1, 0x92, 0x42, 0x34, 0x98, 0x54, 0x27, 0xb6, 0x16, 0x7c, 0xa5, 0x69, 0xd1, 0x3d, 0xf4, 0x35, 0xcf]

由于 y 值是偶数,所以添加一个前缀 2,得到:[2, 0xc0, 0xde, 0xd2, 0xbc, 0x1f, 0x13, 0x05, 0xfb, 0x0f, 0xaa, 0xc5, 0xe6, 0xc0, 0x3e, 0xe3, 0xa1, 0x92, 0x42, 0x34, 0x98, 0x54, 0x27, 0xb6, 0x16, 0x7c, 0xa5, 0x69, 0xd1, 0x3d, 0xf4, 0x35, 0xcf]

注:若 y 为奇数,则前缀为 3。

注:为什么这么规定?只用 x 值和 y 值的奇偶性表示一个点,这叫公钥的压缩格式。因为只要有 x,就可以通过 k1 的椭圆曲线方程式 $y^2 = x^3 + 7 \mod p$ 求出 y,但此时 y 会有两个解,又由于 p 是一个大质数,必定为奇数,故两个 y 解的和 mod p 一定等于 0,即一奇一偶,所以用 x 和 y 的奇偶性标志即可代表这个点。

接着求校验码:

1
2
3
const ripemd160 = require('ripemd160')

new ripemd160().update(Buffer.from([2, 0xc0, 0xde, 0xd2, 0xbc, 0x1f, 0x13, 0x05, 0xfb, 0x0f, 0xaa, 0xc5, 0xe6, 0xc0, 0x3e, 0xe3, 0xa1, 0x92, 0x42, 0x34, 0x98, 0x54, 0x27, 0xb6, 0x16, 0x7c, 0xa5, 0x69, 0xd1, 0x3d, 0xf4, 0x35, 0xcf])).digest()

得到:<Buffer eb 05 f9 d2 c6 dd 62 f7 f2 a0 f7 61 ea 1d 8c 0b 84 4a 3b 52>,取前 4 字节,添加到末尾,得到:[2, 0xc0, 0xde, 0xd2, 0xbc, 0x1f, 0x13, 0x05, 0xfb, 0x0f, 0xaa, 0xc5, 0xe6, 0xc0, 0x3e, 0xe3, 0xa1, 0x92, 0x42, 0x34, 0x98, 0x54, 0x27, 0xb6, 0x16, 0x7c, 0xa5, 0x69, 0xd1, 0x3d, 0xf4, 0x35, 0xcf, 0xeb, 0x05, 0xf9, 0xd2]

然后,base58 编码:

1
2
3
const bs = require('bs58')

bs.encode(Buffer.from([2, 0xc0, 0xde, 0xd2, 0xbc, 0x1f, 0x13, 0x05, 0xfb, 0x0f, 0xaa, 0xc5, 0xe6, 0xc0, 0x3e, 0xe3, 0xa1, 0x92, 0x42, 0x34, 0x98, 0x54, 0x27, 0xb6, 0x16, 0x7c, 0xa5, 0x69, 0xd1, 0x3d, 0xf4, 0x35, 0xcf, 0xeb, 0x05, 0xf9, 0xd2]))

得到:6MRyAjQq8ud7hVNYcfnVPJqcVpscN5So8BhtHuGYqET5GDW5CV,加上前缀 EOS,即为公钥。

零知识证明

定义

零知识证明(Zero—Knowledge Proof)起源于最小泄露证明。

  • 设 P(Prover)表示掌握某些信息,并希望证实这一事实的实体;
  • 设 V(Verifier)是验证这一事实的实体。

假如某个协议向 V 证明 P 的确掌握某些信息,但 V 无法推断出这些信息是什么,我们称 P 实现了最小泄露证明。

如果 V 除了知道 P 能够证明某一事实外,不能够得到其他任何知识,我们称 P 实现了零知识证明,相应的协议称作零知识协议。

零知识证明需要满足以下性质:

  1. 正确性:P 无法欺骗 V。换言之,若 P 不知道一个定理的证明方法,则 P 使 V 相信他会证明定理的概率很低。

  2. 完备性:V 无法欺骗 P。若 P 知道一个定理的证明方法,则 P 使 V 以绝对优势的概率相信他能证明。

  3. 零知识性:V 无法获取任何额外的知识。

本质

零知识证明并不是数学意义上的证明,因为它存在小概率的误差,欺骗者有可能通过虚假陈述骗过证明者。换句话来说,零知识证明是概率证明而不是确定性证明。但是也存在有技术能将误差降低到可以忽略的值。

举例

  1. 16 世纪的文艺复兴时期,意大利有两位数学家为竞争一元三次方程求根公式发现者的桂冠,就采用了零知识证明的方法。当时,数学家塔尔塔里雅和菲奥都宣称自己掌握了这个求根公式,为了证明自己没有说谎,又不把公式的具体内容公布出来,他们摆开了擂台:双方各出 30 个一元三次方程给对方解,谁能全部解出,就说明谁掌握了这个公式。比赛结果显示,塔尔塔里雅解出了菲奥出的全部 30 个方程,而菲奥一个也解不出。于是人们相信塔尔塔里雅是一元三次方程求根公式的真正发现者,虽然当时除了塔尔塔里雅外,谁也不知道这个公式到底是个什么样子。

  2. 稣吹牛说自己掌握椭圆曲线的除法,即可以通过公钥计算私钥。

1
2
3
公钥 = G * 私钥

私钥 = 公钥 / G

但是这个技术价值千亿美元,稣当然不可能开源,所以稣把中本聪的私钥算出来,然后:

1
2
3
4
5
6
7
稣 != 中本聪

=> 稣没有中本聪的私钥


=> 中本聪的私钥是计算出来的


=> 稣定义了椭圆曲线的除法

注意:这个除法目前并不存在,只是吹牛。

参考

大海捞针是不靠谱的:https://thippo.github.io/