在 rust 上移植 BSGS （ECDSA）

问：

嗨，大家好，我正在将此处显示的示例中的 Baby step Giant Step 算法移植到 Rust 编程语言。https://github.com/ashutosh1206/Crypton 普通版本移植成功，没有问题，这里是一个示例。

use serde::{Deserialize, Serialize};
use num_bigint::BigUint;

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


use rayon::prelude::*;
use num_traits::{One, Zero};
use std::collections::HashMap;
use std::sync::{Mutex, Arc};
// https://github.com/ashutosh1206/Crypton/blob/master/Discrete-Logarithm-Problem/Algo-Baby-Step-Giant-Step/bsgs.py




impl BSGS {
    // """
    // Reference:

    // To solve DLP: h = g^x % p and get the value of x.
    // We use the property that x = i*m + j, where m = ceil(sqrt(n))

    // :parameters:
    //     g : int/long
    //             Generator of the group
    //     h : int/long
    //             Result of g**x % p
    //     p : int/long
    //             Group over which DLP is generated. Commonly p is a prime number

    // :variables:
    //     m : int/long
    //             Upper limit of baby steps / giant steps
    //     x_poss : int/long
    //             Values calculated in each giant step
    //     c : int/long
    //             Giant Step pre-computation: c = g^(-m) % p
    //     i, j : int/long
    //             Giant Step, Baby Step variables
    //     lookup_table: dictionary
    //             Dictionary storing all the values computed in the baby step
    // """
    pub fn new(bsgs: String) -> Self {
        Self(bsgs)
    }
    


    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 pre-computation
        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 found
                return Some(i * &m + j);
            }
            i += BigUint::one();
        }
    
        None
    }
}

但我很难移植定义为：

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 来做键减法。 由于 Rust 中的模块 SECP256K1 遵循不同的模式，因此最佳方法是什么。

temp = Q - (i*m)*P

我的直觉告诉我，这部分只是(i*m)*P

        let secp = Secp256k1::new();
        let pub_key = PublicKey::from_secret_key(&secp, &secret);

其中 secret 是操作。 但是如何在 Rust 中做 Q - New_Pub_Key_points ？(i*m)