我正在使用Javascript生成椭圆曲线,用于基于此示例代码的加密消息应用程序http://www-cs-students.stanford.edu/~tjw/jsbn/ecdh.html
公钥会非常大,我知道可以压缩它们,但是我找不到Javascript或大纲算法来做到这一点。这是一篇http://nmav.gnutls.org/2012/01/do-we-need-elliptic-curve-point.html概述数学的文章。
我想他们会对JavaScript椭圆曲线点压缩解决方案更感兴趣,WebCrypto支持过滤到浏览器中。
我将使用NIST曲线作为示例,因为这些是我在将压缩公钥导入WebCrypto时必须处理的。
Curves and their primes
NIST P-256 (secp256r1) 2^256 - 2^224 + 2^192 + 2^96 - 1
NIST P-384 (secp384r1) 2^384 - 2^128 - 2^96 + 2^32 - 1
NIST P-521 (secp521r1) 2^521 - 1
这些素数都满足等式,p mod 4===3
这意味着您可以跳过有点复杂的通用Tonelly-Shks算法,并使用简单的恒等式来查找平方根。
首先,'点压缩'的压缩部分非常简单。记录Y的符号,然后丢弃Y的值。
/**
* Point compress elliptic curve key
* @param {Uint8Array} x component
* @param {Uint8Array} y component
* @return {Uint8Array} Compressed representation
*/
function ECPointCompress( x, y )
{
const out = new Uint8Array( x.length + 1 );
out[0] = 2 + ( y[ y.length-1 ] & 1 );
out.set( x, 1 );
return out;
}
解压涉及查找平方根,然后根据Y奇偶校验位进行校正。此函数依赖于一个JavaScript大整数库,该库公开了以下函数:add、sub、打、pow、modPow。
// Consts for P256 curve. Adjust accordingly
const two = new bigInt(2),
// 115792089210356248762697446949407573530086143415290314195533631308867097853951
prime = two.pow(256).sub( two.pow(224) ).add( two.pow(192) ).add( two.pow(96) ).sub(1),
b = new bigInt( '41058363725152142129326129780047268409114441015993725554835256314039467401291' ),
// Pre-computed value, or literal
pIdent = prime.add(1).divide(4); // 28948022302589062190674361737351893382521535853822578548883407827216774463488
/**
* Point decompress NIST curve
* @param {Uint8Array} Compressed representation
* @return {Object} Explicit x & y
*/
function ECPointDecompress( comp )
{
const signY = comp[0] - 2, // This value must be 2 or 3. 4 indicates an uncompressed key, and anything else is invalid.
x = comp.subarray(1),
// Import x into bigInt library
xBig = new bigInt( x );
// y^2 = x^3 - 3x + b
var yBig = xBig.pow(3).sub( xBig.multiply(3) ).add( b ).modPow( pIdent, prime );
// If the parity doesn't match it's the *other* root
if( yBig.mod(2) !== signY )
{
// y = prime - y
yBig = prime.sub( yBig );
}
return {
x: x,
y: yBig.toUint8Array()
};
}
将比特币压缩公钥(ECDSA公钥)转换为65字节未压缩公钥的代码,使用secp256k1曲线consts,javascript大整数库最新版本1.6.36,可直接使用十六进制字符串
const bigInt = require("big-integer");
function pad_with_zeroes(number, length) {
var retval = '' + number;
while (retval.length < length) {
retval = '0' + retval;
}
return retval;
}
// Consts for secp256k1 curve. Adjust accordingly
// https://en.bitcoin.it/wiki/Secp256k1
const prime = new bigInt('fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f', 16),
pIdent = prime.add(1).divide(4);
/**
* Point decompress secp256k1 curve
* @param {string} Compressed representation in hex string
* @return {string} Uncompressed representation in hex string
*/
function ECPointDecompress( comp ) {
var signY = new Number(comp[1]) - 2;
var x = new bigInt(comp.substring(2), 16);
// y mod p = +-(x^3 + 7)^((p+1)/4) mod p
var y = x.modPow(3, prime).add(7).mod(prime).modPow( pIdent, prime );
// If the parity doesn't match it's the *other* root
if( y.mod(2).toJSNumber() !== signY ) {
// y = prime - y
y = prime.subtract( y );
}
return '04' + pad_with_zeroes(x.toString(16), 64) + pad_with_zeroes(y.toString(16), 64);
}
私钥示例:55255657523dd1c65a77d3cb53fcd050bf7fc2c11bb0bb6edabdbd41ea51f641
ECPointDecompress('0314fc03b8df87cd7b872996810db8458d61da8448e531569c8517b469a119d267')
返回:'0414fc03b8df87cd7b872996810db8458d61da8448e531569c8517b469a119d267be5645686309c6e6736dbd93940707cc9143d3cf29f1b877ff340e2cb2d259cf'
不幸的是,上面来自@Adria的ECPointDecompress
的代码已经过时,它使用的是一个非常旧版本的JavaScript大整数库
我用大整数库最新版本1.6.36重写了ECPointDecompress
,它可以直接处理十六进制字符串,不需要使用Uint8Array
:
const bigInt = require("big-integer");
// Consts for P256 curve. Adjust accordingly
const two = new bigInt(2),
// 115792089210356248762697446949407573530086143415290314195533631308867097853951
prime = two.pow(256).subtract( two.pow(224) ).add( two.pow(192) ).add( two.pow(96) ).subtract(1),
b = new bigInt( '41058363725152142129326129780047268409114441015993725554835256314039467401291' ),
// Pre-computed value, or literal
// 28948022302589062190674361737351893382521535853822578548883407827216774463488
pIdent = prime.add(1).divide(4);
function pad_with_zeroes(number, length) {
var retval = '' + number;
while (retval.length < length) {
retval = '0' + retval;
}
return retval;
}
/**
* Point decompress NIST curve
* @param {string} Compressed representation in hex string
* @return {string} Uncompressed representation in hex string
*/
function ECPointDecompress( comp ) {
var signY = new Number(comp[1]) - 2;
var x = new bigInt(comp.substring(2), 16);
// y^2 = x^3 - 3x + b
var y = x.pow(3).subtract( x.multiply(3) ).add( b ).modPow( pIdent, prime );
// If the parity doesn't match it's the *other* root
if( y.mod(2).toJSNumber() !== signY ) {
// y = prime - y
y = prime.subtract( y );
}
return '04' + pad_with_zeroes(x.toString(16), 64) + pad_with_zeroes(y.toString(16), 64);
}
这可用于将压缩公钥(ECDSA公钥)转换为65字节的未压缩公钥,但请注意,比特币的压缩公钥是使用secp256k1曲线创建的,这与我们在此代码中使用的曲线不同:NISTP-256(secp256r1)2^256-2^224 2^192 2^96-1
因此,上述代码不能用于转换比特币的压缩公钥,寻找具有secp256k1曲线consts的比特币压缩公钥转换器,参考https://stackoverflow.com/a/53480175/5630352
例子:
ECPointDecompress('030ce2995c738e2320a5dea2df51b99d88bc5dd38356ba72e51ecc0ca660ca4593')
返回:'040ce2995c738e2320a5dea2df51b99d88bc5dd38356ba72e51ecc0ca660ca45936215a67f6e3fa1d72f6ef46aa2b7481991427b8764ff90447c6215d8dc931773'
ECPointDecompress('0267bc6cae41a4579cda2556818bc942a38321cad961028bc74459f36ddca71e0e')
返回:'0467bc6cae41a4579cda2556818bc942a38321cad961028bc74459f36ddca71e0e7c52f0e9f82bd1b2ba81935ba125cb1030d1ade1bd0306b3579a951418b858e8'