logo标签列表

椭圆曲线点压缩算法

javascriptcryptographyelliptic-curve
12
对于ECDH，实际上不需要点压缩。在许多情况下，仅使用一个坐标就足够了。 - CodesInChaos
1
@CodesInChaos，你能再解释一下吗？或者你有参考资料吗？谢谢。 - Ian Purton
看起来他混淆了计算结果和公钥存储。在大多数标准中，ECDH点的x坐标被用作共享密钥的来源。 - Nickolay Olshevsky
5个回答
15

我想随着WebCrypto支持浏览器，JavaScript椭圆曲线点压缩解决方案会受到越来越多的关注。
我将使用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()
    };
}
这是一个非常出色的回复，但并没有得到足够的重视。@Adria，谢谢你！ - denis bider
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'

1

单独申请数学公式的专利将会很困难。使用二次方程式y = sqrt(x^3+ax+b)是无法被专利保护的，即使被专利保护了也不能得到保护。可以从Diophantes（公元200-298年）和Hall猜想（约1971年）中提出先前的技术。关于平方和立方之间最小绝对差|y^2 - x^3|很少小于x的问题，可以重写为y^2 - x^3 = ax-b，其中x < b/a，并指出在模群中的解决方案有助于减少整数的暴力搜索量。

被专利保护的是帮助确定y符号的部分。这一部分可用于区分解(y和M-y)中的最大值，或者正解(y，-y)中的正解，具体取决于您所看到的标准。

但由于该专利已经获得批准，您需要寻求法律建议。

作为一位精通密码学技能的知名密码学家，丹·伯恩斯坦博士明智地指出（http://cr.yp.to/ecdh/patents.html），在基于内存的系统中，从x重新计算y的想法在Miller 1986年被提及，是为了减少椭圆曲线点在内存中的占用。

专门从事专利索赔的律师可以帮助您评估专利是否仍然适用，如果您不使用正常基作为点坐标的表示，或者在gf(p)中使用ecc，或者如果您不使用一个比特来重新编码压缩值y，例如在选择随机数k、P1(x1,y1)和计算P2(x2,y2)=[k]P1直到tr(y1)==tr(y2)时消除歧义（稍微耗费一些CPU，但为什么不呢？）。

或者，你可以指出二次方程式的解析度显然比在通信渠道上节省的几个位数更加昂贵，因此这项专利毫无用处，甚至会对环境造成损害，因为它建议用2毫瓦的CPU成本替换6皮卡瓦特的传输成本（为了被接受，专利提交必须是新的、非平凡的和有用的）。然后你找到一个最好在加利福尼亚州的不诚实的律师，肯定会有当地的法官授予你数十亿美元的赔偿金，以弥补对环境造成的损害，对你的编程技能和钱包造成的困扰，考虑到你宝贵应用程序发布的延迟。

否则，如另一篇文章所建议的那样，你可以选择许可证解决方案。

如果你的应用程序是为美国政府服务的，你需要另一位律师评估这项专利和你计划使用它的方式是否已经包含在NSA在算法“Suite B”背景下购买的许可证中，如果是的话，该许可证可能已经由美国人民支付。

1

椭圆曲线点的压缩由Certicom公司拥有专利，因此通常情况下您不应在未获得许可的情况下使用它。

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

我不想涉及政治问题，但是哪个管辖区允许软件专利？ - Ian Purton
几乎每个国家，包括美国。您可以在http://en.wikipedia.org/wiki/ECC_patents上了解更多关于ECC专利的内容。 - Nickolay Olshevsky
1
也许在美国可以，但在欧盟不行。在欧洲，“作为这样的计算机程序”被排除在可专利范围之外，因此欧洲专利局的政策是，如果计算机程序没有超出硬件和软件之间固有技术交互的“进一步技术效果”，则该计算机程序不可专利化。 - Ian Purton
实际上，专利并不是针对计算机程序，而是数学方法。无论如何，我不是欧洲/美国专利法方面的专家，只是想提醒你。在大多数互联网标准中，由于那个愚蠢的专利，压缩点是不被支持的。 - Nickolay Olshevsky
谢谢，我感激你提醒我。 - Ian Purton
显示剩余2条评论
1

上面的ECPointDecompress代码来自@Adria，但很遗憾它已经过时了，它使用了一个非常旧的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曲线创建的，该曲线与我们在此代码中使用的曲线不同：NIST P-256（secp256r1）2 ^ 256 - 2 ^ 224 + 2 ^ 192 + 2 ^ 96 - 1

因此，上述代码不能用于转换比特币的压缩公钥，如果要查找具有secp256k1曲线常量的比特币压缩公钥转换器，请参考https://dev59.com/_2Qn5IYBdhLWcg3wAjLJ#53480175

示例：

ECPointDecompress('030ce2995c738e2320a5dea2df51b99d88bc5dd38356ba72e51ecc0ca660ca4593')

返回：'040ce2995c738e2320a5dea2df51b99d88bc5dd38356ba72e51ecc0ca660ca45936215a67f6e3fa1d72f6ef46aa2b7481991427b8764ff90447c6215d8dc931773'

ECPointDecompress('0267bc6cae41a4579cda2556818bc942a38321cad961028bc74459f36ddca71e0e')

返回值: '0467bc6cae41a4579cda2556818bc942a38321cad961028bc74459f36ddca71e0e7c52f0e9f82bd1b2ba81935ba125cb1030d1ade1bd0306b3579a951418b858e8'

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接