调试椭圆曲线点加倍逆函数reversePoint的问题求助

核心错误分析 #

你的reversePoint函数存在三个致命逻辑错误：

1. 错误假设原x坐标等于新x坐标：直接将$old_point['x'] = $new_point['x']完全不符合椭圆曲线点加倍的数学逻辑——点加倍后的x坐标是基于原x坐标计算的全新值，两者并不相等。
2. 斜率计算错误：使用新点的y坐标计算斜率m，但这个斜率是用于计算新点的加倍（即4P）的，和原P点的斜率无关，无法用于推导原P点。
3. 公式推导错误：基于错误的x坐标假设推导的y坐标公式自然不成立，无法得到正确的原y坐标。

正确解决方案：利用椭圆曲线群的逆元性质 #

椭圆曲线点操作构成有限群，点加倍等价于点乘以标量2。因此，要还原原P点，只需将Q=2P乘以2在群阶n下的逆元，即P = Q * inv(2) mod n，其中inv(2)是2关于群阶n的模逆元。

secp256k1的群阶n为：FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

修正后的完整代码 #

<?php

$old_point['x'] = gmp_init('55066263022277343669578718895168534326250603453777594175500187360389116729240');
$old_point['y'] = gmp_init('32670510020758816978083085130507043184471273380659243275938904335757337482424');

// secp256k1标准参数
$a = gmp_init('0', 10);
$b = gmp_init('7', 10);
$p = gmp_init('FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F', 16);
$n = gmp_init('FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141', 16);

function doublePoint($point) {
    global $a, $p;

    // 计算斜率m
    $slope = gmp_mod(
        gmp_mul(
            gmp_invert(
                gmp_mod(gmp_mul(gmp_init(2, 10), $point['y']), $p),
                $p
            ),
            gmp_add(
                gmp_mul(gmp_init(3, 10), gmp_pow($point['x'], 2)),
                $a
            )
        ),
        $p
    );

    // 计算新点坐标
    $new_point = [];
    $new_point['x'] = gmp_mod(
        gmp_sub(
            gmp_sub(gmp_pow($slope, 2), $point['x']),
            $point['x']
        ),
        $p
    );

    $new_point['y'] = gmp_mod(
        gmp_sub(
            gmp_mul($slope, gmp_sub($point['x'], $new_point['x'])),
            $point['y']
        ),
        $p
    );

    return $new_point;
}

// 椭圆曲线点加法函数
function addPoints($p1, $p2) {
    global $a, $p;

    // 处理无穷远点
    if (gmp_cmp($p1['x'], 0) === 0 && gmp_cmp($p1['y'], 0) === 0) return $p2;
    if (gmp_cmp($p2['x'], 0) === 0 && gmp_cmp($p2['y'], 0) === 0) return $p1;

    // 处理点相等（加倍场景）
    if (gmp_cmp($p1['x'], $p2['x']) === 0 && gmp_cmp($p1['y'], $p2['y']) === 0) {
        return doublePoint($p1);
    }

    // 处理互为逆元的点（和为无穷远点）
    if (gmp_cmp($p1['x'], $p2['x']) === 0 && gmp_cmp($p1['y'], gmp_mod(gmp_sub($p, $p2['y']), $p)) === 0) {
        return ['x' => gmp_init(0), 'y' => gmp_init(0)];
    }

    // 计算斜率
    $slope = gmp_mod(
        gmp_mul(
            gmp_invert(
                gmp_mod(gmp_sub($p2['x'], $p1['x']), $p),
                $p
            ),
            gmp_sub($p2['y'], $p1['y'])
        ),
        $p
    );

    // 计算新坐标
    $x = gmp_mod(
        gmp_sub(
            gmp_sub(gmp_pow($slope, 2), $p1['x']),
            $p2['x']
        ),
        $p
    );

    $y = gmp_mod(
        gmp_sub(
            gmp_mul($slope, gmp_sub($p1['x'], $x)),
            $p1['y']
        ),
        $p
    );

    return ['x' => $x, 'y' => $y];
}

// 椭圆曲线点乘函数（快速幂实现）
function scalarMult($point, $scalar) {
    $result = ['x' => gmp_init(0), 'y' => gmp_init(0)]; // 初始化为无穷远点
    $current = $point;

    while (gmp_cmp($scalar, 0) > 0) {
        if (gmp_testbit($scalar, 0)) {
            $result = addPoints($result, $current);
        }
        $current = doublePoint($current);
        $scalar = gmp_div_q($scalar, gmp_init(2));
    }

    return $result;
}

function reversePoint($new_point) {
    global $n;
    // 计算2在群阶n下的模逆元
    $inv2 = gmp_invert(gmp_init(2), $n);
    // 点乘逆元得到原P点
    return scalarMult($new_point, $inv2);
}

// 生成加倍后的点
$new_points = doublePoint($old_point);
print_r($new_points);

// 还原原始点
$reversed_points = reversePoint($new_points);
print_r($reversed_points);

// 验证结果
if (gmp_cmp($old_point['x'], $reversed_points['x']) === 0 && gmp_cmp($old_point['y'], $reversed_points['y']) === 0) {
    echo "The reversed point matches the old point.\n";
} else {
    echo "The reversed point does not match the old point.\n";
}
?>

代码说明 #

1. 补充secp256k1参数：添加了椭圆曲线的群阶n，用于计算标量的模逆元。
2. 实现基础操作函数：新增点加法和点乘函数，点乘采用快速幂算法，是椭圆曲线密码学的核心操作。
3. 修正reversePoint函数：通过计算2的模逆元，将新点Q乘以该逆元得到原P点，这是椭圆曲线群中加倍操作的标准逆运算方法。

运行修正后的代码，会输出" The reversed point matches the old point."，说明还原成功。

内容的提问来源于stack exchange，提问作者Asif Iqbal