search

entropyxyz / crypto-primes

Random prime generation and primality testing library based on `crypto-bigint`.
https://docs.rs/crypto-primes
Apache License 2.0
17 stars 4 forks source link

Prime verification in const context #42

Open TitouanReal opened 4 months ago

TitouanReal commented 4 months ago

It would be useful to be able to check if a number is prime or not in a const context.

Currently, the library const-primes provides such a feature, but only for built-in integer types. Would it be feasible to have this feature in this library for use with crypto-bigint::Uint ?

tarcieri commented 4 months ago

It's tricky to have an implementation which is both generic (i.e. over Uint and BoxedUint) as well as const fn-friendly, at least until impl const Trait lands. Not impossible (it requires using concrete types everywhere for the const fns) but tricky.

I'm curious what the use case is?

TitouanReal commented 4 months ago

I al working on a pure rust implementation of CSIDH (which is a post-quantum algorithm for secret key exchange.) CSIDH is not yet standardized.

The parameters of the key exchange is any small set of (small, ie ~<500) prime numbers, such that p = (4 times their product minus 1) is prime. I woulk like to provide an API allowing anyone to define such parameters for their use-case (especially research purpose such as side-channel attacks), with a compile-time validation of the parameters.

To the best of my knowledge, doing this as I want would require multiple features of crypto-bigint and/or the Rust language. One of the features I would like is the const primality check of p, which is generally an integer of around 512 bits in CSIDH.

fjarri commented 4 months ago

Another problem besides the const trait thing is that the current primality test requires an RNG. This perhaps can be worked around by seeding an RNG with a hash of the number being tested, but some research is needed to make sure it's actually safe to do. Primality certificates (see #9) are generally non-random, but will take more time to generate (although they could be pre-generated and hardcoded alongside primes, and tested during compilation).