时间：2021年12月29日
微博：比特币布道者
一、背景
1、椭圆曲线
（1）有限域（Fp）椭圆曲线
有限域椭圆曲线Ep(a,b)，p为质数，x,y∈[0,p-1]
y^2 = x^3 + ax + b (mod\ p)其中，a、b是小于p的非负整数，且满足：
4a^3 + 27b^2 ≠ 0 (mod\ p)
（2）椭圆曲线加密（ECC）参数要求
通常将有限域上的一条椭圆曲线描述为T = (p,a,b,G,n,h)。
其中，p、a、b确定一条椭圆曲线，p为质数，(mod p)运算，G为基点，n为点G的阶（即nG = 0），h为协因子，是椭圆曲线上所有点的个数m与n相除的商的整数部分。
参量选择要求：
- p越大安全性越好，但会导致计算速度变慢，200bits左右可满足一般安全要求；
- n应为质数；
- h ≤ 4；
- p ≠ n × h ；
- pt ≠ 1 (mod n) (1 ≤ t ＜ 20)；
- 4a^3 + 27b^2 ≠ 0 (mod\ p)。
（3）比特币所选椭圆曲线
比特币系统选用的secp256k1中，参数为
p = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F，即2^{256} − 2^{32} − 2^9 − 2^8 − 2^7 − 2^6 − 2^4 − 1
a = 0， b = 7
G=(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
n = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
h = 01
（3）公钥坐标
公钥 = 私钥k * 基点G，公钥是椭圆曲线上的点，可以用坐标(x,y)表示。
椭圆曲线y^2 = x^3 + 7在实数域的图形如下
可知，曲线以x轴为对称轴上下对称，且曲线上的点的坐标(x,y)中的y值可以通过方程式由x计算出来。
所以，公钥坐标可以采用“x值”加“y值的正负标志位” 来表示。
由于，在有限域上y值只能为正值，因为-y mod p = p – y，坐标(x,-y)%p等价于(x,y)%p，可以参考下图
所以，无法通过y值直接判断y值的正与“负(来自-y mod p) ” ，理论上存在的判断方法至少有两种：
1）将公钥坐标(x,y) 带入实数域曲线方程y^2 = x^3 + 7。如果等式成立，说明y值为正，否则y为“负”，来自-y mod p。
2）利用公钥坐标(x,y)中y值的奇偶性来判断y值正负，原理如下：
由于p是质数，所以当y是偶数时，p – y (即-y mod p)是奇数，当y是奇数时，p – y (即-y mod p)是偶数，且由于通过x值和方程式计算出的y值只会在正数域。
所以，当公钥y值在“负”数域时 ，那么其在正数域的对称点p – y（即为通过x值和方程式计算出的y值）的奇偶性必然与其相反。
那么，就可以通过y的计算值与真实值的奇偶性的对比，来判断y值的正负。当二者一致时，y值为正；当二者不一致时，y值为负，来自-y mod p。用公钥前缀表示y的真实值的奇偶性，02表示y的真实值是偶数，03表示y的真实值是奇数。
2、节省区块空间
在实施SegWit之前，每笔交易的见证数据（Sigscript）包括签名及公钥是占区块空间的，通过实施压缩公钥，可以有效降低见证数据大小，从而节省区块空间。
（1）非压缩公钥：04+x坐标+y坐标。
（2）压缩公钥：y坐标的奇偶标志位+x坐标。当y为偶数时，奇偶标志位记为偶数标志02；当y为奇数时，奇偶标志位即为奇数标志03。
二、JS代码实现
1、二次剩余
计算y^2 = x^3 + 7 (mod\ p)中的y值：
（1）首先，计算(x^3 + 7) mod\ p，根据模计算公式，可知：
(x^3 + 7) mod\ p
= (x^3\ mod\ p + 7) mod\ p
=n
（2）最后，计算y^2 = n (mod\ p)，这其实就是在求解二次剩余问题。
根据定理：如果p是质数，p mod 4 = 3，且n是模p的二次剩余，那么±n^{\frac {p+1}{4}}是y模p的平方根。
又根据secp256k1参数p，可知p mod 4 = 3，所以可以用上述定理求解y值。
1）根据费马小定理：如果p是质数，而整数y不是p的倍数，那么y^{p-1} ≡ 1(mod\ p) ，来证明上面的定理。
∵y^2 = y^2 × 1 = y^2 × y^{p-1} = y^{p+1}(mod\ p)
∴y = ±y^{\frac {p+1}{2}}(mod\ p)
∵p\ mod\ 4 = 3
∴(p+1)mod\ 4 = 0，即p+1可以整除4。
∴y = ±y^{2 × {\frac {p+1}{4}}}(mod\ p)
=±(y^2)^{\frac {p+1}{4}}(mod\ p)
=±n^{\frac {p+1}{4}}(mod\ p)
2）根据欧拉判别条件：如果p是奇质数（大于2的质数），整数n不是p的倍数，n是模p的二次剩余的充要条件是n^{\frac {p-1}{2}} ≡ 1(mod\ p) ，来证明上述定理。
∵y^2 = y^2×1 = n×n^{\frac {p-1}{2}} = n^{\frac {p+1}{2}}(mod\ p)∵p\ mod\ 4 = 3
∴(p+1)mod\ 4 = 0，即p+1可以整除4。
2、JS代码
注：压缩公钥及非压缩公钥验证生成工具https://startbitcoin.org/bitcoin
需要引入bitcoinjs-min.js文件
见压缩包：CompressToUnompressPubkey
var compressedPubkey = "0399c976ed4adf6a58acd8dc7c916f8aa23df82c181125ac3d9d1e8cf2b110a2b3";
var x_bn = BigInteger.fromByteArrayUnsigned(Crypto.util.hexToBytes(compressedPubkey.slice(2,66)));
var p = "fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f";
var p_bn = BigInteger.fromByteArrayUnsigned(Crypto.util.hexToBytes(p));
//根据模公式，可知y^2 = (x^3 + 7) mod p = (x^3 mod p + 7) mod p
var y_squre = x_bn.pow(3).mod(p_bn).add(BigInteger.fromByteArrayUnsigned([7])).mod(p_bn); //a.pow(b)，表示a^b，其中a为BigInteger类，指数b必须是int类型
//根据二次剩余定理，可知y=y_squre^((p+1)/4)mod p
var y = y_squre.modPow(p_bn.add(BigInteger.ONE).divide(BigInteger.fromByteArrayUnsigned([4])),p_bn); //a.modPow(b,c)，表示a^b%c，其中a、b、c均为BigInteger类
var prefix = compressedPubkey.slice(0,2);
//如果y的推导值的奇偶性与真实y值的奇偶性不一致，则y在负半轴。
if (y.mod(BigInteger.fromByteArrayUnsigned([2])) != parseInt(prefix)%2) {
y = y.negate().mod(p_bn);
}
var uncompressedPubkey = "04" + compressedPubkey.slice(2,66) + Crypto.util.bytesToHex(integerToBytes(y));
document.write(uncompressedPubkey);