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

On Tue, Jan 15, 2013 at 03:27:29PM +0100, Ertugrul Söylemez wrote:

Vincent Hanquez 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