-
Notifications
You must be signed in to change notification settings - Fork 56
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
num-traits
support (optional)
#158
Comments
Is the absence of I am now compiling a list of all dependencies for the MPC project I am building, and obviously a bigint library is a prerequisite for many higher-level primitives (like the actual group code, for both Paillier and the elliptic curves I am very careful in my analysis, as for me it is important to know exactly the building blocks both theory and implementation wise. It is important for me to not have duplication, so e.g. relying on both crypto-bigint and num-bigint is something I'd go a long way to avoid. There is enough attack surface as it is, I don't want to be exposed to double the attack surface. Now, regarding choosing which bigint library to use, crypto-bigint seemed the obvious choice for me:
But finding out Thanks |
All of the other elliptic curve libraries we maintain (e.g.
The reason It's something we plan to add but just haven't had time for. It would be nice to be able to use traits to abstract between stack and heap-based big integers, so RSA and DSA can be implemented generically and the stack-based big integers used on heapless platforms. |
Thanks for the detailed reply, however I was left even more confused because an apparent lack of knowledge on my side, I'd love if you'll clarify:
Thank you very much |
Some bigint libraries do not use all of the bits of a limb. This is an unsaturated representation. There are a few different reasons for this: sometimes the unsaturated implementation can be more efficient, especially when leveraging e.g. special properties of the field modulus. However, one of the most common reasons was better carry handling. Unsaturated representations could use part of a limb represent carry bits. The need for this has largely been obviated by using machine instructions which provide access to the carry bit, like add-and-carry (ADC), subtraction-with-borrow (SBB), and multiply-and-carry (MAC), all of which are emitted by
The size of a With RSA, it'd be nice to use a 2048-bit Uint for 2048-bit keys, and a 4096-bit Uint for 4096-bit keys. In other words: to pick the number of limbs on the fly at runtime to match the key size. Without a heap, the best you could do is having an enum over a Heap-backed integers would allow dynamic sizes, reusing the same code regardless of the size, at the cost of efficiency.
We could potentially use
The arithmetic operations on the base and scalar fields for
Hopefully a generic implementation would work for all |
Wow, that's an amazing answer. I'll take a deeper look at One thing however, why use Is there no way of generating generic big-num (or at least for a specific modulus size) code using |
The libraries that don't use fiat-crypto have handwritten field arithmetic implementations which outperform the fiat-crypto synthesized code, namely
What would it be generic around? The modulus? (like
|
Sorry that was a problem in my wording. What I meant by generic is that it is not special-purpose for e.g. a specific curve but just a standard 128,256,2024,2048,4096 etc. bits long. I guess that won't suffice for elliptic curves because they are not really using u256 but a ~256-bit (prime sometimes) modulos right? Also, from your questions there seems to be a tradeoff between performance and security here? if you want the formal security grantees of fiat-crypto, you lose a little on performance? |
There is a formal verification versus performance tradeoff, yes. We opt for better performance because that seems to interest our users more than formal verification. Hopefully in the future fiat-crypto will improve performance and add features like lazy normalization. |
I definitely am on the other side, and if formal verification is possible it is worth performance penalties. Esp when performance optimizations in these fields tend to be a factor under 2, at least from what I've seen so far. However, from a brief look on fiat-crypto it seems that the Rust generated code isn't formally verified (no proof). Also, I'm not sure what are the guarantees fiat-crypto formally proves: is it purely correctness, or also side-channel resistance (e.g. constant-time) So I'd have to dig deeper, read the fiat-crypto papers before I decide the path to go. Assuming that I end up deciding to go with fiat-crypto, what would be the best way to assure all my cryptographic building blocks rely on it? My thoughts (although I need to take a deeper look into num-traits) are to rely on num-traits, and to adapt the fiat-crypto generated code to it later upon instantiation. My question to you is - could we in the future rely on num-traits for elliptic-curve and k256? just asking if it's a possibility, not whether you are willing to do it ( I might decide to contribute it myself if I find it necessary, for now I just want to know if it's a valid option)? |
Most of our downstream users would disagree I think, especially about The most common requests we get on We try to improve the performance with each release. The last release shipped variable-time inversions for verification, and the next will hopefully ship wNAF. Another option is to provide both, ala I'm honestly not sure about using For |
I ran some benchmarking, and was really surprised at the results. I published the code so you can see that I haven't made any mistakes. But results are (full trace is found in the readme file of the repo):
How can this be explained? perhaps there's some error on my side? |
Perhaps open an issue on https://github.com/rustcrypto/elliptic-curves |
@tarcieri getting back to the subject of this issue, is this feature something we are planning on delivering? specifically, I care about implementing |
I think a |
Optional as in a crate feature? that works for me. If so, I'll write my code assuming it and might contribute this feature later on. |
Yep |
Started to develop my code based on My original thinking was to implement
But not only that this won't work in-tandem with normal (over So:
An interface that does, however, comply with what I need for Paillier is However, this trait has the same restriction as Would love to hear your thoughts on this @tarcieri |
You should be able to implement
|
I see, so your suggestion is to actually use the output size (i.e. the largest integer I'll work with, e.g. the size of I believe this approach works, but still the Therefore, I believe the best approach for me is to use the Thank you in any-case; if you agree with my reasoning, I guess I wouldn't be requiring this feature anymore. |
It would be nice to impl I'm going to close this and suggest #218 as a place to follow up on |
Currently
num-traits
is only indev-dependencies
.As originally suggested here it would be useful to have some support for traits for abstracting across bignum libraries, which would make it possible for e.g. the
rsa
crate to use eithercrypto-bigint
ornum-bigint-dig
.Though
num-traits
probably lacks all of the requisite functionality to do that, it would get us quite a bit of the way there.The text was updated successfully, but these errors were encountered: