core-only "heapless" support

[roblabla]

Right now, there is a PR open (#22) that will allow the RSA crate to be used in core+alloc environments (e.g. environments without libstd, but where a dynamic allocator is available).

The next step is for the RSA crate to support core-only environments. This would require multiple changes: num-bigint-dig would need to be represented either as a stack-allocated array (GenericArray? ArrayVec?) or a slice reference (wooo lifetimes) instead of a heap-allocated vector. Furthermore, we'll need to make extra sure that all the operations are bounded within a certain numeric range.

[dignifiedquire]

it will be hard, but very valuable to be able to make the bigint lib usable with genericarray,

[tarcieri]

You could potentially use heapless::Vec to simplify usage of GenericArray with something closer to the ergonomics of alloc::vec::Vec.

Unfortunately they haven't updated to generic-array v0.14 yet, which is annoying:

rust-embedded/heapless#166

[dignifiedquire]

Yes heapless::Vec has some nice utilities that we would need. I would love to keep the ability for returning larger numbers, eg multiply that returnst the full result and not just the truncated, might make sense to implement the std operations like std lib, with overflow panic, and having wrapping, checked and a new variant sth like full which would return the fully expanded version

[newpavlov]

I would love to keep the ability for returning larger numbers, eg multiply that returnst the full result and not just the truncated

IIUC it should be possible to do completely on stack, with something like:

fn mul<const N: usize>(a: [Word; N], b: [Word; N]) -> [Word; 2*N] { .. }

[tarcieri]

For what it's worth, I started working on a crate with traits to abstract over the details between containers like Vec and heapless::Vec (or arrayvec if so desired), with all operations fallible for use with fixed-sized containers:

• https://github.com/RustCrypto/utils/tree/master/collectable
• https://docs.rs/collectable/0.0.1/collectable/ (note I published an 0.0.2 but reverted the changes, I prefer this API)

Not using it for anything yet and it could probably use some work, but I think it has a similar inspiration to this sort of use case.

[dignifiedquire]

@newpavlov it is possible, but as we don't have const generics yet this gets quite ugly and complex quickly, especially if your interfaces have to rely on the certain size, as they would for RSA given a fixed bitwitdth

[tarcieri]

@dignifiedquire if you'd like any help doing typenum arithmetic for computing GenericArray sizes, I've done a lot of it in the other crates. Here's an example:

https://docs.rs/ecdsa/0.6.0/ecdsa/asn1_signature/struct.Asn1Signature.html

[tarcieri]

crypto-bigint has a stack-allocated Uint type based on const generics.

It might be interesting to switch to that if it also provided a heap-allocated type like UintVec which could replace the existing usages of num_bigint_dig::BigUint, along with traits to abstract across both options. Unfortunately it doesn't have support for that yet.

[bradjc]

With the switch to crypto-bigint merged, how feasible is this now? I looked a little at what it would take to template everything on traits from crypto-bigint to allow using either heap or stack versions, and it seems like crypto-bigint isn't quite designed for this use case (e.g. inv_mod is implemented on the types and not as part of a trait).

[tarcieri]

inv_mod is implemented on the types and not as part of a trait)

There's an InvMod trait, and a Gcd trait as well.

Though I would probably suggest holding off until we land RustCrypto/crypto-bigint#755 which should simplify some things (and even make it possible to add the InvMod trait to the bounds of the Integer trait.