multiple precision

[tomstdenis]

One thing we found productive is TFM can be fairly easily ported to be variable precision. This in turn saves a lot of memory at a small (trivial) cost in performance.

I can't contribute code (right now) but it's something that is worth looking into. It would also make FP_MAX_SIZE obsolete.

[tomstdenis]

Poke. I'd like this to be a goal for the following release cycle. It saves on memory considerably and realistically doesn't hurt performance that much.

[sjaeckel]

+1 I already discussed with @sebastianas via email about that and he already made an implementation proposal, that I currently can't find... probably @sebastianas can just put it in here as well...

[tomstdenis]

FWIW I actually made this change at my last professional gig (where we used TFM as our de facto math lib). On small targets it makes all the difference specially for RSA/ECC where many bignums are stupid small things like e=65537 or whatever.

The trick is to allocate in blocks of say 128-bits so that you're not constantly doing allocs. The changes only took me a week or so and bug hunting another few weeks :-)

[sebastianas]

On 2016-01-31 10:12:40 [-0800], Steffen Jaeckel wrote:

+1 I already discussed with @sebastianas via email about that and he already made an implementation proposal, that I currently can't find... probably @sebastianas can just put it in here as well...

The way things are right now is:

typedef struct { fp_digit dp[FP_SIZE]; int used; int sign; } fp_int;

Back then we talked about providing an alloc' andfree' to get/free the `fp_int'. I think if would do instead

typedef struct { int used; int sign; fp_digit *dp; };

fp_init() would memset() everything to zero and the following set/add/whatever would see dp beeing NULL and alloc the required memory. Also it could re-alloc memory and demand if we suddenly go towards 4k RSA or so.

Library wise what we need:

• fp_init(), zero, copy, … should not remain as defines. Those should be pulled into C code. With a versioned
• I am not sure if it is a good thing making it an anonymous struct. I remember pro and con for it
• This will be major so bump since we change the struct. I think that renaming the struct away fp_int is a good think so people are forced to look at code instead of just re-compiling. The fp_init() will probably catch all "inits" but we need to free the memory at some point.

Sebastian

[ronaaron]

Big up-vote for this feature! I'm very anxious to have more flexibility on the size of the bigints in 8th.

[rofl0r]

otoh, there are also applications like bruteforcing where you would want to avoid dynamic allocation, since even on fast malloc impls you have a cost of about 300 cpu cycles per call. in such a case it would be optimal if you could allocate a sufficiently big buffer beforehand, and then assigning it to the fp_int struct. for example:

size_t bignum_max = BIGNUM_STORAGE_BITS(4096);
void* bignum_storage = malloc(bignum_max);
fp_int bignum;
bignum_set_storage(&bignum, bignum_storage, bignum_max);

edit: note that you might also want to avoid malloc and friends for extreme size optimization in static linking scenarios.