Re: Static version of bignum library

petela_at_gocougs.wsu.edu
Date: 03/31/05 

Date: 30 Mar 2005 17:36:01 -0800

petela@gocougs.wsu.edu wrote:
> > > > So a rough ballpark figure is you need ~45 bignums during an
> exptmod
> > > of
> > > > a 1024-bit exponent. Each occupies 64 digits + header == 272
> bytes *
> > > > 45 == 12KB
> > > >
> > > > So realistically to perform a 1024-bit exptmod out of the box
> with
> > > > LibTomMath you're looking at roughly [with typical malloc
> overhead,
> > > > etc...] 16KB of heap plus about 2KB of stack.
> >
> > > Aha! These are the kind of numbers I'm looking for. But how
> > > predictable is this?
> >
> > ExpMod is a memory determanistic algorithm (or it should be if done
> > right). There is an upper bound and a lower bound.
>
> Great. That's half of what I want to know. The other half is what
> that upper bound is. From what I gathered from Tom's response is
16KB
> of heap and 2KB of stack. And now that I know it is deterministic, I
> am more comfortable in using the software.

Now that we've got LTM incorporated into our design, I thought I'd
update everyone with the memory use we are seeing. But before I give
the numbers, I thought I'd mention our "dynamic" memory manager (if you
want to call it that).

Basically, we set aside a large chunk of memory, about 1MB, to do the
testing. This is _way_ more than we needed, but for testing, its fine.
 Our memory manager basically alots the requested size on a word
boundary. It has an overhead of 4 bytes per allocation to store the
length of the request (to support realloc()). A call to free() does
nothing. Once allocated, it is allocated forever. A call to realloc()
always allocates the newly requested size, rather than just resizing
the requested array (we could be smarter if the new size is smaller to
save an alloc, but we aren't interested).

This is _very_ crude, but it works for us, and took about 20 mins to
write. We just require the static store to be reset every time we want
to start a string of math operations.

Our system uses 1024-bit DSA keys to verify signatures. The
verification is only used in certain, special circumstances, and is not
part of normal, everyday operation. So, we are not worried about
performance or memory use (other than the original request that is it
bounded).

So, now for the numbers. We ran a few sets of keys and signatures and
saw a maximum memory use of about 64k bytes. Now this is the amount
reported by the memory manager (with its overhead and crude realloc()).
 We have lots of memory in our system (about 8MB), so 64k is just fine.

We still need to test with jibberish to make sure things don't blow up
(however, we always check that the keys have appropriate sizes), but so
far, things are looking great.

As for performance, I thought I'd just throw out some numbers.
Ignoring the SHA at the beginning, the DSA takes about 70 seconds on
our system. Now the system is a crappy 50MHz Microblaze based system,
with no cache. The Microblaze is pipelined, but the crappy performance
of the SDRAM controller on the OPB bus is our bottleneck. However,
this doesn't seem too bad considering.

Pete

Relevant Pages