9

我正在使用 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。

4

5 回答 5

9

我想他们会增加对 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
这意味着您可以跳过有些复杂的通用Tonelli-Shanks 算法，并使用简单的恒等式来找到平方根。

首先，“点压缩”的压缩部分非常简单。记录 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、multiply、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()
    };
}
于 2015-05-25T05:06:50.007 回答
3

将比特币压缩公钥（ECDSA公钥）转换为65字节未压缩公钥的代码，使用secp256k1曲线常量，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'

于 2018-11-26T11:30:47.953 回答
1

不幸的是，@Adria 上面的代码ECPointDecompress已经过时了，它使用的是非常旧版本的JavaScript 大整数库

我ECPointDecompress用大整数库最新版本 1.6.36重写，它可以直接使用十六进制字符串，不需要使用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 曲线创建的，这与我们在此代码中使用的曲线不同： NIST P-256 (secp256r1) 2^256 - 2^224 + 2^192 + 2^96 - 1

因此，上面的代码不能用来转换比特币的压缩公钥，寻找比特币压缩公钥的转换器，带有secp256k1曲线常量，参考https://stackoverflow.com/a/53480175/5630352

例子：

ECPointDecompress('030ce2995c738e2320a5dea2df51b99d88bc5dd38356ba72e51ecc0ca660ca4593')

返回：'040ce2995c738e2320a5dea2df51b99d88bc5dd38356ba72e51ecc0ca660ca45936215a67f6e3fa1d72f6ef46aa2b7481991427b8764ff90447c6215d8dc931773'

ECPointDecompress('0267bc6cae41a4579cda2556818bc942a38321cad961028bc74459f36ddca71e0e')

返回：'0467bc6cae41a4579cda2556818bc942a38321cad961028bc74459f36ddca71e0e7c52f0e9f82bd1b2ba81935ba125cb1030d1ade1bd0306b3579a951418b858e8'

于 2018-11-26T09:39:15.800 回答
0

椭圆曲线点的压缩是 Certicom 的专利，所以一般情况下你不应该在没有许可的情况下使用它。

更新：根据 Denis bider 下面的评论，Certicom 的专利已于 2014 年到期。

于 2013-06-18T14:39:32.847 回答
0

单独为数学公式申请专利是很困难的。二次方程 y = sqrt(x^3+ax+b) 的使用不能获得专利，如果是，则不能受到保护。人们当然可以从丢番图（公元 200-298 年）那里获得现有技术。以及围绕霍尔猜想（大约 1971 年）关于正方形和立方体之间的最小绝对差 |y^2 - x^3| 的工作 很少小于 x。用 x < b/a 重写它 y^2 - x^3 = ax-b 并注意模块化组中的解决方案将有助于减少整数的蛮力搜索量。

获得专利的是有助于找出 y 符号的位。该位可用于区分 (y 和 My) 中的最大解，或 (y, -y) 中的正解，具体取决于您查看的标准。

但由于专利已被接受，您需要寻求法律意见。

作为精通本领域技能的著名密码学家，Dan Bernstein 博士明智地指出 ( http://cr.yp.to/ecdh/patents.html )，米勒 1986 年提到了从 x 重新计算 y 的想法减少基于内存的系统中椭圆曲线点的足迹的琐碎性。

如果您不使用法线基础作为点坐标的表示，或者在 gf(p) 中的 ecc 的情况下，或者如果您不使用重新编码 y 的压缩值，例如在选择随机性 k 时，P1(x1,y1) 并计算 P2(x2,y2) = [k]P1 直到 tr(y1) == tr(y2) 消除歧义（有点 CPU 成本，但为什么不呢？）。

或者，您可以指出，二次公式的分辨率显然比在通信信道上节省的几比特成本更高，而且这项专利根本没有用，甚至通过建议更换 6 皮瓦的传输成本来破坏环境减少 2 毫瓦 CPU 成本（要被接受，专利提交必须是新的、重要且有用的）。然后，您最好在加利福尼亚找到一位不正当的律师，并且可以肯定的是，考虑到由此造成的延误，当地法官会判给您数十亿美元的赔偿金，以赔偿对环境造成的损害、对您的编程技能和您的钱包造成的困扰在发布您有价值的应用程序时。

否则，正如另一篇文章中所建议的，您可以寻求许可解决方案。

如果您的申请是针对美国政府的，您需要另一位律师来评估该专利以及您计划使用它的方式是否已经属于 NSA 在算法“套件 B”的背景下购买的许可的一部分，在这种情况下许可证可能已经由美国人民支付。

于 2013-12-05T03:39:58.460 回答