New-to-Haskell, i.e. elementary, Haskell questions; extended discussions

Vincent Hanquez | 11 Jan 2013 23:55

ANN: crypto-pubkey: all your public key crypto algorithms belong to us.

Hi Cafe,

I've recently released crypto-pubkey [1][2], which provide a comprehensive
solution for public key cryptography.

Most known RSA modes (PKCS15, OAEP, PSS) are supported, and there's also DSA
and ElGamal signature support. Most of the code originally lived in cryptocipher,
but have now been made better and safer, and support more modes.

I've spend some good chunk of time adding KATs and tests, documentation, and
making sure the performance was ahead of other haskell implementations.

Enjoy,

[1] http://hackage.haskell.org/package/crypto-pubkey-0.1.1
[2] https://github.com/vincenthz/hs-crypto-pubkey

--

-- 
Vincent

Joachim Breitner | 12 Jan 2013 00:34

Picon

Re: ANN: crypto-pubkey: all your public key crypto algorithms belong to us.

Hi,

Am Freitag, den 11.01.2013, 23:55 +0100 schrieb Vincent Hanquez:
> I've recently released crypto-pubkey [1][2], which provide a comprehensive
> solution for public key cryptography.
> 
> Most known RSA modes (PKCS15, OAEP, PSS) are supported, and there's also DSA
> and ElGamal signature support. Most of the code originally lived in cryptocipher,
> but have now been made better and safer, and support more modes.
> 
> I've spend some good chunk of time adding KATs and tests, documentation, and
> making sure the performance was ahead of other haskell implementations.

nice. But in the interest of possible users: Is there a reason why this
code could not live in cryptocipher? Do we need multiple implementations
of the cyphers, and expect our users to find out for themselves why to
use one or the other?

Greetings,
Joachim

--

-- 
Joachim "nomeata" Breitner
  mail <at> joachim-breitner.de  |  nomeata <at> debian.org  |  GPG: 0x4743206C
  xmpp: nomeata <at> joachim-breitner.de | http://www.joachim-breitner.de/

_______________________________________________
Haskell-Cafe mailing list

(Continue reading)

Vincent Hanquez | 12 Jan 2013 05:39

Re: ANN: crypto-pubkey: all your public key crypto algorithms belong to us.

On 01/11/2013 11:34 PM, Joachim Breitner wrote:
> nice. But in the interest of possible users: Is there a reason why this
> code could not live in cryptocipher? Do we need multiple implementations
> of the cyphers, and expect our users to find out for themselves why to
> use one or the other?
The duplicate implementations in cryptocipher have been marked as deprecated
and will be removed in a near future.

The only reason is has been spun off is that i think it was a mistake to
put it along block and stream cipher in the first place, and i prefer
smaller package with dedicated dependencies.

--

-- 
Vincent

Ertugrul Söylemez | 12 Jan 2013 14:12

Picon

Re: ANN: crypto-pubkey: all your public key crypto algorithms belong to us.

Vincent Hanquez <tab <at> snarc.org> wrote:

> I've recently released crypto-pubkey [1][2], which provide a
> comprehensive solution for public key cryptography.
>
> Most known RSA modes (PKCS15, OAEP, PSS) are supported, and there's
> also DSA and ElGamal signature support. Most of the code originally
> lived in cryptocipher, but have now been made better and safer, and
> support more modes.

This seems like a very useful library.  Thanks for that!

> I've spend some good chunk of time adding KATs and tests,
> documentation, and making sure the performance was ahead of other
> haskell implementations.

I suggest looking at Daniel Fischer's arithmoi [1] library, which
implements very fast Integer operations and should provide most
functionality needed.  However, beware of timing attacks.

Also for the particular purpose of generating safe primes I have written
a blazingly fast implementation that uses intelligent sieving and finds
even large primes (>= 4096 bits) within seconds or minutes.  It's on
hpaste [2].  I might turn this into a library at some point.

[1]: <http://hackage.haskell.org/package/arithmoi>
[2]: <http://hpaste.org/79286>

Greets,
Ertugrul

(Continue reading)

Vincent Hanquez | 14 Jan 2013 12:36

Re: ANN: crypto-pubkey: all your public key crypto algorithms belong to us.

On Sat, Jan 12, 2013 at 02:12:44PM +0100, Ertugrul Söylemez wrote:
> > I've spend some good chunk of time adding KATs and tests,
> > documentation, and making sure the performance was ahead of other
> > haskell implementations.
> 
> I suggest looking at Daniel Fischer's arithmoi [1] library, which
> implements very fast Integer operations and should provide most
> functionality needed.  However, beware of timing attacks.

Very cool library and very similar to what crypto-numbers provides albeit less
sophisticated. I wished I knew about it before implementing the same(ish)
functions.

One caveat of the library is the dependence on integer-gmp.

> Also for the particular purpose of generating safe primes I have written
> a blazingly fast implementation that uses intelligent sieving and finds
> even large primes (>= 4096 bits) within seconds or minutes.  It's on
> hpaste [2].  I might turn this into a library at some point.

Seconds or minutes ? that's very different 
But in any case, it would be a nice addition i think.

My safe prime generation function is probably the most naive possible.

--

-- 
Vincent

Daniel Fischer | 14 Jan 2013 13:49

Re: ANN: crypto-pubkey: all your public key crypto algorithms belong to us.

On Monday 14 January 2013, 12:36:22, Vincent Hanquez wrote:
> On Sat, Jan 12, 2013 at 02:12:44PM +0100, Ertugrul Söylemez wrote:
> > > I've spend some good chunk of time adding KATs and tests,
> > > documentation, and making sure the performance was ahead of other
> > > haskell implementations.
> > 
> > I suggest looking at Daniel Fischer's arithmoi [1] library, which
> > implements very fast Integer operations and should provide most
> > functionality needed.  However, beware of timing attacks.
> 
> Very cool library and very similar to what crypto-numbers provides albeit
> less sophisticated.

I see you're doing a lot of x `shiftR` 1 with Integers. That's pretty bad for 
performance (at least for integer-gmp, might be not for integer-simple or 
implementations other than GHC [last I looked, JHC didn't have arbitrary 
precision Integers and used 64-bit ones, so it'd be fast there]).

> I wished I knew about it before implementing the
> same(ish) functions.
> 
> One caveat of the library is the dependence on integer-gmp.

It was meant to be fast, so exploiting the internal representation of Integers 
in some places was the way to go. I intend to make it portable, but so far am 
too good at procrastinating.  (Making it portable without losing too much 
performance is nontrivial in some places, that contributes.)

Getting a request would make it happen sooner.

(Continue reading)

Vincent Hanquez | 15 Jan 2013 09:49

Re: ANN: crypto-pubkey: all your public key crypto algorithms belong to us.

On Mon, Jan 14, 2013 at 01:49:44PM +0100, Daniel Fischer wrote:
> On Monday 14 January 2013, 12:36:22, Vincent Hanquez wrote:
> > On Sat, Jan 12, 2013 at 02:12:44PM +0100, Ertugrul Söylemez wrote:
> > > > I've spend some good chunk of time adding KATs and tests,
> > > > documentation, and making sure the performance was ahead of other
> > > > haskell implementations.
> > > 
> > > I suggest looking at Daniel Fischer's arithmoi [1] library, which
> > > implements very fast Integer operations and should provide most
> > > functionality needed.  However, beware of timing attacks.
> > 
> > Very cool library and very similar to what crypto-numbers provides albeit
> > less sophisticated.
> 
> I see you're doing a lot of x `shiftR` 1 with Integers. That's pretty bad for 
> performance (at least for integer-gmp, might be not for integer-simple or 
> implementations other than GHC [last I looked, JHC didn't have arbitrary 
> precision Integers and used 64-bit ones, so it'd be fast there]).

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.

--

--

(Continue reading)

Ertugrul Söylemez | 15 Jan 2013 15:27

Picon

Re: ANN: crypto-pubkey: all your public key crypto algorithms belong to us.

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.

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.

Greets,
Ertugrul

--

-- 
Not to be or to be and (not to be or to be and (not to be or to be and
(not to be or to be and ... that is the list monad.

(Continue reading)

Vincent Hanquez | 18 Jan 2013 11:35

Re: 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 <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.

(Continue reading)

Ertugrul Söylemez | 14 Jan 2013 15:33

Picon

Re: ANN: crypto-pubkey: all your public key crypto algorithms belong to us.

Vincent Hanquez <tab <at> snarc.org> wrote:

> > Also for the particular purpose of generating safe primes I have
> > written a blazingly fast implementation that uses intelligent
> > sieving and finds even large primes (>= 4096 bits) within seconds or
> > minutes.  It's on hpaste [2].  I might turn this into a library at
> > some point.
>
> Seconds or minutes ? that's very different 
> But in any case, it would be a nice addition i think.
>
> My safe prime generation function is probably the most naive possible.

Ok, let me give you an actual number.  I want, for an integer b > 3, the
smallest integer d such that 2^b - d is a safe prime.  Let's find all
safe primes for b <- [100..399]:

    % time ./primes {100..399}
    2^100 - 12389
    2^101 - 9009
    ...
    2^398 - 128981
    2^399 - 191301
     ** timings:  real 32.355  user 32.105  krnl 0.113  cpu% 99%

But of course I have four cores, and as a Haskell programmer I feel that
I should use them:

    % time ./primes {100..399} +RTS -N
    2^100 - 12389

(Continue reading)

Return

Return to gmane.comp.lang.haskell.cafe.

Search Archive

Language

Change language

Options

Current view: Threads only / Showing only 20 lines / Not hiding cited text.
Change to All messages, whole messages, or hide cited text.

Post a message
NNTP Newsgroup
Classic Gmane web interface
XML

XML

RSS Feed
List Information

About Gmane