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 t...@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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] 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. -- Vincent ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: crypto-pubkey: all your public key crypto algorithms belong to us.
Vincent Hanquez t...@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. signature.asc Description: PGP signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] 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. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: crypto-pubkey: all your public key crypto algorithms belong to us.
Vincent Hanquez t...@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
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 e...@ertes.de
FPrint: BD28 3E3F BE63 BADD 4157 9134 D56A 37FA E5DD 8D11
Keysrv: hkp://subkeys.pgp.net/
signature.asc
Description: PGP signature
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: crypto-pubkey: all your public key crypto algorithms belong to us.
Vincent Hanquez t...@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 -- 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. signature.asc Description: PGP signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] 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 m...@joachim-breitner.de | nome...@debian.org | GPG: 0x4743206C xmpp: nome...@joachim-breitner.de | http://www.joachim-breitner.de/ signature.asc Description: This is a digitally signed message part ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
