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

older
Feedback on FFI bindings for C++...

Vincent Hanquez

11 Jan 2013 11 Jan '13

10:55 p.m.

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

Show replies by date

Joachim Breitner

11 Jan 11 Jan

11:34 p.m.

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@joachim-breitner.de | nomeata@debian.org | GPG: 0x4743206C xmpp: nomeata@joachim-breitner.de | http://www.joachim-breitner.de/

Vincent Hanquez

12 Jan 12 Jan

4:39 a.m.

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

1:12 p.m.

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

Vincent Hanquez

14 Jan 14 Jan

11:36 a.m.

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

12:49 p.m.

New subject: 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.

...

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

15 Jan 15 Jan

8:49 a.m.

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

Ertugrul Söylemez

2:27 p.m.

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

Vincent Hanquez

18 Jan 18 Jan

10:35 a.m.

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

Ertugrul Söylemez

14 Jan 14 Jan

2:33 p.m.

Vincent Hanquez 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 2^101 - 9009 ... 2^398 - 128981 2^399 - 191301 ** timings: real 11.047 user 38.194 krnl 3.833 cpu% 380% At some point I'm going to parallelize even individual prime searches. =) Greets, Ertugrul -- Key-ID: E5DD8D11 "Ertugrul Soeylemez " FPrint: BD28 3E3F BE63 BADD 4157 9134 D56A 37FA E5DD 8D11 Keysrv: hkp://subkeys.pgp.net/

4552

Age (days ago)

4559

Last active (days ago)

List overview

Download

9 comments

4 participants

participants (4)

Daniel Fischer
Ertugrul Söylemez
Joachim Breitner
Vincent Hanquez