Use case study.

[cheako]

This is an implementation of an EC library over brainpoolP256r1. Goals ECDSA and key derivations borrowing from Bitcoin HD wallets/bip-0032.

https://gitlab.com/cheako/jtm-rs/-/blob/8de6da4c648b9bca3351991673831feb111aa3dc/src/lib.rs

I found some things a little overwhelming. mod_inv() in particular, I ended up copying a Python implementation.

This is an example of how things come out if you just toss equations up into the air and see where they land. There is a lot to learn from here and I'm in a position to learn new things from a review as well.

Thanks!

[dignifiedquire]

hey, happy to hear this is being useful for others :)

Did you find anything missing in particular?

[cheako]

I latched onto BigInt::from_biguint() and I think a section of documentation describing the other methods for converting to BigInt from BigUint would be worthwhile. I think into_bigint/to_bigint may be simpler ways covering what's needed here. For the storage of Point information it became critical that these were always positive, but that meant that a conversion was needed prior to doing the math.

I don't know if it's missing, but ModInverse didn't behave the way I needed. I ended up using the following(taken from Python's tinyec) and I have no idea why this worked for me. I can dig a little more here to see what it is I need. For example I can say that the EDIT(divisor) will always be a "positive" prime number, but the dividend can be either positive or negative and I believe it's the negative case where ModInverse wasn't returning the correct values.

use num_bigint_dig::{BigInt, BigUint, Sign::Plus};
fn egcd(a: BigInt, b: BigInt) -> (BigInt, BigInt, BigInt) {
    if a == 0.into() {
        (b, 0.into(), 1.into())
    } else {
        use num_integer::Integer;
        let (g, y, x) = egcd(b.mod_floor(&a), a.clone());
        (g, x - (b / a) * y.clone(), y)
    }
}

fn mod_inv(a: BigInt, p: BigUint) -> BigUint {
    if a < 0.into() {
        p.clone() - mod_inv(-a, p.clone())
    } else {
        let p = BigInt::from_biguint(Plus, p);
        let (g, x, _y) = egcd(a, p.clone());
        if g == 1.into() {
            use num_integer::Integer;
            x.mod_floor(&p).to_biguint().unwrap()
        } else {
            panic!()
        }
    }
}

[cheako]

There are some in the crypto field that think generic_array is the path forward, but I don't see any math support there.

I think there is a use case for optimisations over/given a finite field. Though any implementation would share a lot of code with bigint, so I feel it would be best to work in cooperation.

I don't know how well the trick used in generic_array would scale to say implement a generic_finite_field type... If there can just be vast numbers of generics. I know I'm not explaining well, but for generic_finite_field the number of generics would literally extend a generic_array many times past a size in exabytes.