Feature wishlist tracking ticket

Question

Feature wishlist tracking ticket

tarcieri opened this issue 3 years ago · 32 comments

Answer 1 · 2021-06-24T19:52:57.000Z

Prime generation
Random < n
Least common multiple
Negative numbers
Inverse (available if gcd exists but nice convenience)

Answer 2 · 2021-06-27T02:02:25.000Z

@mikelodder7 added to the list

random < n implemented in RustCrypto/utils#508. Will cut a release with that fairly soon.

Re: signed integers, yes that's definitely planned but not on this list yet, so thanks. Tentatively the idea is composing in terms of a UInt using two's complement.

Edit: released in v0.2.2 (#509)

Answer 3 · 2021-07-21T03:11:49.000Z

How about bit tests? Check if bit at position i is set or cleared?

Answer 4 · 2021-07-21T04:06:15.000Z

@mikelodder7 what kind of API are you looking for there?

Would a Choice suffice, or are you looking for a secret-dependent/vartime API?

Answer 5 · 2021-07-21T11:46:40.000Z

Choice will suffice. Vartime not necessary.

Answer 6 · 2021-08-05T19:16:57.000Z

Fast generation of safe primes would be great for RSA applications.

Answer 7 · 2021-08-05T19:19:00.000Z

It’s also great for applications that require groups of unknown order based on prime factoring like accumulator, paillier, camenisch-shoup verifiable encryption

Answer 8 · 2021-08-24T16:19:23.000Z

I'd like to add a +1 for implementingmodpow. It's useful in older protocols such as SRP.

Answer 9 · 2021-08-26T21:10:41.000Z

@mikelodder7 it looks like it might be interesting to adapt the code in glass_pumpkin for (safe) prime generation, that is if we could get your blessing to license the resulting code as Apache 2.0+MIT

Answer 10 · 2021-08-26T23:01:26.000Z

Of course. Glass pumpkin is already licensed as Apache 2 so adapting to be dual licensed is fine too. Consider this post my legal binding statement to authorize that work.

Answer 11 · 2021-08-26T23:12:05.000Z

It will be nice to have it integrated directly into the big int library vs a bolt-on. Many operations can be simplified since the underlying int rep is accessible. We'll need modpow and reduce at a minimum.

Answer 12 · 2021-08-26T23:19:56.000Z

Absolutely, that'd be the goal.

Generic modpow seems a bit tricky, or at least our last attempt at it didn't work.

One option would be to have a trait for it, and implement it for specific moduli.

Answer 13 · 2021-08-27T00:35:41.000Z

What about using modular square and modular multiply and using conditional_select if the exponent bit is 1? Does that not work?

Answer 14 · 2021-08-27T00:53:51.000Z

To be clear @dignifiedquire tried to add generic mulmod in RustCrypto/utils#510 but it was buggy so we backed it out.

It would be great to have a generic implementation.

Answer 15 · 2021-09-08T21:17:15.000Z

Doing a "better random < n" with swiftlang/swift#39143 in bigint is expensive compared to correct bigint rejection sampling (see RustCrypto/utils#618). As that requires multiplication of the modulus and a random number about 128 bits larger than the modulus. Basically that's O(N^2) vs O(N).

Answer 16 · 2021-09-08T21:31:22.000Z

To be clear @dignifiedquire tried to add generic mulmod in RustCrypto/utils#510 but it was buggy so we backed it out.

I'll get there, soon (TM)

Answer 17 · 2021-09-15T00:02:13.000Z

Need to update this list with completed features @tarcieri

Answer 18 · 2021-09-15T00:10:54.000Z

@mikelodder7 should be updated now

Answer 19 · 2021-09-19T09:12:35.000Z

Modular exponentiation?

Answer 20 · 2021-09-20T02:01:05.000Z

It's under "modular arithmetic" as "pow". Hmm "sqrt" and "inversions" should be under the "modular arithmetic" section.

Answer 21 · 2021-09-20T13:45:08.000Z

Sorry, I reorganized the modular arithmetic section, and missed a few things along the way.

Note there is sqrt under modular arithmetic. However, I'll move inversions there.

Answer 22 · 2021-09-21T13:08:12.000Z

Oh I missed that. Is the other "sqrt" for floor(sqrt(n))?

P.S. I just re-found the edit history button and "pow" was added after @newpavlov's question. I thought there was edit history but it wasn't in the "…" menu.

Answer 23 · 2021-09-21T13:28:03.000Z

The other sqrt is for generic number sqrt versus modular sqrt which can take some optimizations.

Answer 24 · 2021-09-21T13:29:25.000Z

Both are important. Integer sqrt is used in the Lucas test for prime numbers for example.

Answer 25 · 2021-09-21T14:56:54.000Z

Modular sqrt could potentially be helpful for the elliptic curve crates, although we're presently using an algorithm (Tonelli-Shank) specialized to the modulus (q mod 16 = 1).

I'm not sure what the best algorithm to use which isn't specialized to the modulus, or if it would make sense to select an algorithm based on the modulus size. The latter might make more sense if the modulus were a const generic parameter so the best algorithm could be selected at compile time.

Answer 26 · 2021-09-22T16:26:36.000Z

I would suggest having the different algorithms behind specific methods, such that downstream implementors can choose the algorithm, eg fn sqrt_tonelli_shank().

Answer 27 · 2021-10-17T15:36:14.000Z

Would completing full num_traits::PrimInt implementation to be a good goal ? I made a test branch with stubbed out functions here, it's not too hard to complete - with an optional num_traits dependency.

The main reason is it allows easily writing generic algos that take T: PrimInt as either bignum or builtin integers.

Answer 28 · 2021-10-17T15:51:54.000Z

Optional num_traits support sounds great.

I would suggest following the same pattern as all the other functions that can presently support it which are currently impl'd on UInt (and Limb) though: add that functionality as const fn inherent methods, then add a trait wrapper for the inherent methods.

Based on a cursory survey of Primint, it looks like that should be possible for most if not all of those methods.

Edit: opened #158 to track num-traits support.

Answer 29 · 2023-05-06T19:07:47.000Z

Seems like it can be updated, all the modular arithmetic is done, and random primes are implemented by crypto-primes.

Answer 30 · 2024-04-03T11:20:51.000Z

Should there be regular pow for Uint and BoxedUint types - like

https://docs.rs/num-bigint-dig/latest/src/num_bigint_dig/biguint.rs.html#501

Answer 31 · 2024-04-03T12:45:53.000Z

@pinkforest all of the functionality in this crate is directly motivated by a specific cryptographic algorithm the functionality is intended to implement. What would be the purpose? Modular exponentiation is useful for DSA and RSA, but to my knowledge we have no use case for a non-modular pow.

We also implement fixed, not arbitrary, precision, and a non-modular pow can quickly overflow fixed-precision integers.

Answer 32 · 2024-04-03T20:44:05.000Z

Thanks - Yeah my naive use-case was 1:1 porting existing use of vartime bigint and now think I should have skipped that -

Specifically deterministic RSA prime factor recovery as described by NIST.SP.800-56Br2 Appendix C.2 as was in rsa crate.

I should have re-evaluated it given the type for e is already below maximum size two.pow(256) and I can just simply do X::from(65536) to check minimum instead of ad-hoc two.pow(16) as you noted correctly - thanks!