[Haskell-cafe] ANN: crypto-pubkey: all your public key crypto algorithms belong to us.

[Vincent Hanquez]

On Tue, Jan 15, 2013 at 03:27:29PM +0100, Ertugrul Söylemez wrote:
> Vincent Hanquez <tab at snarc.org> wrote:
> 
> > Yes, the performance are terrible in term of integers. As the library
> > is specific to public key algorithm, i just can't reasonable work on
> > 64 bits integer :-), and multiprecision integers is the only way to
> > go.
> >
> > I'm on-and-off working on some mutable mpi library to be able to
> > define pure function that do the necessary stuff (i.e. expmod, mulmod,
> > etc..)
> >
> > I'm hoping this could be reasonably competitive with a C mpi library,
> > but time will tell.
> 
> It's a waste of time.  In my benchmarks Haskell Integer outperformed
> equivalent (sane) C implementations using GMP's mpz_* interface.  You
> would be reinventing GMP's mpn_* interface and a custom memory manager
> to be able to match the speed of Integer.

I don't plan to match (or outperform) the speed of integer for simple
operations. My experiment is about overtaking haskell's Integer in composite
operations (mainly for non naive expmod) by operating with mutable integers and
direct access to the representation (the second point is somewhat what Daniel
is doing using integer-gmp).

One valid way to solve this problem, would be to export more GMP function to
haskell without wrapping them for referencial transparency. However the GMP
dependencies is not always welcome and the integration of GMP is slightly
special (primops), which is why i'm not taking this course of action.

> The things that were slower than equivalent C code were not related to
> Integer, but mostly to data structures like Set in my case, which was
> the motivation for me to write the 'quickset' library.

AFAIK, Haskell's Integer expmod algorithms have no way to rival with real world
implementation of expmod, which make all pubkey operations quite slow compare
to their C friends. There's also the question of timing security with a pure &
GCed interface.

-- 
Vincent