在Rust中移植椭圆曲线版BSGS（ECDSA）算法的点减法实现问题咨询

背景与问题概述 #

我已经成功将普通版本的Baby Step Giant Step算法从Crypton项目移植到了Rust语言，代码运行完全正常，先贴出这部分可行的代码：

use serde::{Deserialize, Serialize};
use num_bigint::BigUint;
use rayon::prelude::*;
use num_traits::{One, Zero};
use std::collections::HashMap;
use std::sync::{Mutex, Arc};

#[derive(Debug, Serialize, Deserialize, Clone)]
pub struct BSGS(String);
pub struct Parallel(String);

// 参考：Crypton项目中的BSGS实现
impl BSGS {
    pub fn new(bsgs: String) -> Self {
        Self(bsgs)
    }

    /// 求解离散对数问题：h = g^x % p，返回x
    pub fn run(g: &BigUint, h: &BigUint, p: &BigUint) -> Option<BigUint>  {
        let mod_size = p.bits();
        println!("[+] Using BSGS algorithm to solve DLP");
        println!("[+] Modulus size: {}. Warning! BSGS not space efficient\n", mod_size);

        let m = (*&p - BigUint::one()).sqrt() + BigUint::one();
        let mut lookup_table: HashMap<BigUint, BigUint> = HashMap::new();

        // Baby Step
        let mut j = BigUint::zero();
        while &j < &m {
            let key = g.modpow(&j, &p);
            lookup_table.insert(key.clone(), j.clone());
            j += BigUint::one();
        }

        // Giant Step 预计算：c = g^(-m) % p
        let c = g.modpow(&(&m * (*&p - BigUint::from(2u32))), &p);

        // Giant Steps
        let mut i = BigUint::zero();
        while &i < &m {
            let temp = &(h * &c.modpow(&i, &p)) % p;
            if let Some(j) = lookup_table.get(&temp) {
                // 找到x
                return Some(i * &m + j);
            }
            i += BigUint::one();
        }

        None
    }
}

但在移植椭圆曲线版本的BSGS时遇到了瓶颈，参考的Sage实现代码如下：

from sage.all import *

def bsgs_ecdlp(P, Q, E):
    if Q == E((0, 1, 0)):
        return P.order()
    if Q == P:
        return 1
    m = ceil(sqrt(P.order()))
    lookup_table = {j*P: j for j in range(m)}
    for i in range(m):
        temp = Q - (i*m)*P
        if temp in lookup_table:
            return (i*m + lookup_table[temp]) % P.order()
    return None

if __name__ == "__main__":
    import random
    E = EllipticCurve(GF(17), [2, 2])
    try:
        for i in range(100):
            x = random.randint(2, 19)
            assert bsgs_ecdlp(E((5, 1)), x*E((5, 1)), E) == x
    except Exception as e:
        print(e)
        print "[-] Something's wrong!"

我现在最头疼的是如何实现Sage代码里的temp = Q - (i*m)*P这一行。我知道(i*m)*P可以通过Rust的secp256k1库，用PublicKey::from_secret_key生成对应的公钥点，但完全搞不懂怎么完成Q - New_Pub_Key_points这个点减法操作。

解决方案思路与代码示例 #

椭圆曲线上的点减法Q - P本质上等价于Q + (-P)，也就是把点P取反后再和Q做加法操作。在Rust的secp256k1库中，我们可以通过以下步骤实现：

核心步骤 #

1. 计算k = i*m，并确保这个值落在椭圆曲线的阶范围内（避免溢出导致错误）
2. 将k转换为secp256k1库要求的SecretKey类型
3. 用PublicKey::from_secret_key生成k*P对应的公钥点K
4. 对K执行取反操作（使用PublicKey::negate方法）得到-K
5. 将Q和-K执行点加法（使用PublicKey::combine方法），结果就是Q - K，对应Sage中的Q - (i*m)*P

具体代码实现 #

use secp256k1::{Secp256k1, PublicKey, SecretKey, Error};
use num_bigint::BigUint;

/// 计算 Q - k*P 的椭圆曲线点
fn compute_q_minus_kp(
    secp: &Secp256k1<()>,
    q: &PublicKey,
    p: &PublicKey,
    k: &BigUint
) -> Result<PublicKey, Error> {
    // 首先确保k在曲线阶范围内，避免无效计算
    let curve_order = BigUint::from_bytes_be(&secp256k1::constants::CURVE_ORDER);
    let k_mod_order = k % &curve_order;

    // 将BigUint类型的k转换为32字节的大端格式（secp256k1要求的格式）
    let mut secret_bytes = [0u8; 32];
    let k_bytes = k_mod_order.to_bytes_be();
    let offset = 32 - k_bytes.len();
    secret_bytes[offset..].copy_from_slice(&k_bytes);

    // 转换为SecretKey
    let secret_key = SecretKey::from_slice(&secret_bytes)?;

    // 计算 k*P
    let kp = PublicKey::from_secret_key(secp, &secret_key);

    // 对kp取反，得到 -kp
    let mut neg_kp = kp;
    neg_kp.negate(secp);

    // 计算 Q + (-kp)，即 Q - kp
    q.combine(secp, &neg_kp)
}

注意事项 #

• 曲线阶取模：一定要对k做曲线阶取模操作，因为椭圆曲线上的点乘法是基于阶循环的，超出阶的数值会导致计算结果错误
• 字节序转换：secp256k1使用大端字节序存储私钥，所以BigUint转字节数组时要注意用to_bytes_be，并填充到32字节长度
• 上下文实例：所有的点操作（取反、加法）都需要传入Secp256k1的上下文实例，确保线程安全和操作合法性

备注：内容来源于stack exchange，提问作者PrinceZee