From: Nicolas C. <war...@fr...> - 2003-03-20 10:18:04
|
Hi, I'm quite disapointed about the current silence on this list... After a short period of time where everyone really wanted to contribute, there seems to be no more will to do so (excepted Brian modules post), but perhaps most of people there only wanted to give advices about how to name such module and not really develop and implement the ExtLib :)) For people who are still interested, I'll keep on gathering modules, and since we have a 3-days WeekEnd here in Japan starting tomorrow, I'll try to come on monday with a first ExtLib version implementing all suggestions being made, so we can put it on some CVS. Nicolas Cannasse |
From: Brian H. <bri...@ql...> - 2003-03-20 16:05:36
|
Oh, and I have more to contribute. Basic status of my work at this point: - bitset is being rewritten into bitarray, with the new features suggested by the change in name. The goal is to produce something you could write elliptic curve cryptosystems in at least semi-efficiently. - I have the beginings of what I'm currently calling an XString library, which stores a string as an unbalanced tree of of substrings. The big advantage here is that concats are O(1), and then converting the XString to a normal string is O(n). In-place modification won't be supported. This will be usefull in constructing strings by concating substrings efficiently. Sort of like Java's StringBuffer. - A resizable array module- rather like Java's Vector or Python's List. Life has been rather hectic of late for me- sorry I haven't been more timely on this. But this weekend is looking dull, so I should be able to spend some serious coding time. Longer term, libraries I'd like (and that I think would be usefull) would include: - A BLAS-like library. Although I need to think about this design some- OOLALA has shown me that BLAS itself is probably not the best overall library design. - A regular expressions library- although I think this might already be out there. - An elliptic curve crypto systems library. Brian On Thu, 20 Mar 2003, Nicolas Cannasse wrote: > Hi, > > I'm quite disapointed about the current silence on this list... After a > short period of time where everyone really wanted to contribute, there seems > to be no more will to do so (excepted Brian modules post), but perhaps most > of people there only wanted to give advices about how to name such module > and not really develop and implement the ExtLib :)) > For people who are still interested, I'll keep on gathering modules, and > since we have a 3-days WeekEnd here in Japan starting tomorrow, I'll try to > come on monday with a first ExtLib version implementing all suggestions > being made, so we can put it on some CVS. > > Nicolas Cannasse > > > > ------------------------------------------------------- > This SF.net email is sponsored by: Tablet PC. > Does your code think in ink? You could win a Tablet PC. > Get a free Tablet PC hat just for playing. What are you waiting for? > http://ads.sourceforge.net/cgi-bin/redirect.pl?micr5043en > _______________________________________________ > ocaml-lib-devel mailing list > oca...@li... > https://lists.sourceforge.net/lists/listinfo/ocaml-lib-devel > |
From: William D. N. <wne...@cs...> - 2003-03-20 17:37:59
|
On Thu, 20 Mar 2003, Brian Hurt wrote: > - bitset is being rewritten into bitarray, with the new features suggested > by the change in name. The goal is to produce something you could write > elliptic curve cryptosystems in at least semi-efficiently. Umm...when you say EC cryptosystems, I assume you're just talking about a package that's good for doing generic work over GF(2^n), right? That'd be pretty handy to have around... > - An elliptic curve crypto systems library. Well, I've got my modifications to Xavier's cryptokit library that I could contribute (I'd want to clear it with Xavier first though). I haven't done too much to it yet, the changes I've made are listed at the end of this mail. Anyway, I've been wanting to add an EC module to this library along with a number of other changes and additions, such as: - Repackage some stuff to create a byte-array type with easy conversion between 8bits/byte (for working with internally) 4bits/byte (for working with in a readible format), and appropriate manipulation routines (shifts, rotates, boolean functions, etc.). I need to put more thought into this, I've just been tossing things together in an ad-hoc fashion when I need something for work -- perhaps your bitarrays would be all that I'm really looking for. - Fix arcfour so it can take a full 2048 bit key (I think Xavier misread the specs and limited it to 128 bits). - Add a generic Fiestel cipher construction. - Add other ciphers like Blowfish, RC5, and some of the AES and NESSIE applicants. I'd like to add SEAL, but I'm not sure what IBM's stance is on its licensing is. - Add a construction that allows for easy creation of Luby-Rackoff ciphers. - Add some qth root versions of PK ciphers. - Add some more number theory tools (so far all I have is CRT-enabled modular exponentiation used in the RSA module). - Add some secret sharing tools. - Figure out why the included implementation of SHA-1 runs so freakin' slow on the PPC G4 processor... - Perhaps add factoring and DL computation routines, but I'm not sure this belongs here... - Oh yeah...and fix my screwed up Ocamldoc documentation. If you can think of anything else that should be added (or if you want to help with the development of this let me know. --- My changes to cryptokit (v1.0) so far: * Replaced the bigint part of the library with much faster calls to GMP using mlgmp (so I suppose I might need to talk to David Monniaux as well -- I forget what the license situations are). * Changed the RSA module so that it now has two keytypes, public and private, and uses those key types appropriately (note: this breaks compatability with the original cryptokit. Obviously.) * Added DSA signatures (with the fix for Bleichenbacher's potential attack) * Added SHA-256, SHA-384, and SHA-512 (currently only compiles with compilers that support the 64-bit long long type, e.g. gcc) * Added Markus Jakobsson style hash chains. * Added two new PRNGs (the crappy GMP default PRNG -- good for testing -- and a stronger, slower PRNG described by Peter Guttman) * Added some random number routines for generating a specific number of bits, rather than bytes, and returning the number either as a string or as a GMP MP Integer. * Added a number of random prime generation routines (probabilistic primes, strong primes, proveable primes, and DSA primes) * Added the cipherX construction that allows you to build DESX style extensions out of any block cipher. William D. Neumann --- "Well I could be a genius, if I just put my mind to it. And I...I could do anything, if only I could get 'round to it. Oh we were brought up on the space-race, now they expect you to clean toilets. When you've seen how big the world is, how can you make do with this? If you want me, I'll be sleeping in - sleeping in throughout these glory days." -- Jarvis Cocker |
From: Brian H. <bri...@ql...> - 2003-03-20 17:45:11
|
On Thu, 20 Mar 2003, William D. Neumann wrote: > On Thu, 20 Mar 2003, Brian Hurt wrote: > > > - bitset is being rewritten into bitarray, with the new features suggested > > by the change in name. The goal is to produce something you could write > > elliptic curve cryptosystems in at least semi-efficiently. > > Umm...when you say EC cryptosystems, I assume you're just talking about a > package that's good for doing generic work over GF(2^n), right? That'd be > pretty handy to have around... Yes. That is precisely what I meant. EC crypto is just the hardest, most complicated, most performance important GF computations I know of. > > - Repackage some stuff to create a byte-array type with easy conversion > between 8bits/byte (for working with internally) 4bits/byte (for working > with in a readible format), and appropriate manipulation routines > (shifts, rotates, boolean functions, etc.). I need to put more thought > into this, I've just been tossing things together in an ad-hoc fashion > when I need something for work -- perhaps your bitarrays would be all > that I'm really looking for. Hmm. Should add a function to return bits n..n+k with k <= Sys.word_size as a combined in. And set and invert as well. > - Add other ciphers like Blowfish, RC5, and some of the AES and NESSIE > applicants. I'd like to add SEAL, but I'm not sure what IBM's stance is > on its licensing is. Blowfish I'm less interested in. I'm a fan of Twofish myself- especially given some of the weaknesses discovered in AES/Rijndael recently... > - Add some more number theory tools (so far all I have is CRT-enabled > modular exponentiation used in the RSA module). I'd like an easy, reasonably fast, library to find primitive polys in GF(2^n) for some n. > * Added two new PRNGs (the crappy GMP default PRNG -- good for testing -- > and a stronger, slower PRNG described by Peter Guttman) Is there a Yarrow-based PRNG? Brian |
From: William D. N. <wne...@cs...> - 2003-03-20 18:38:49
|
On Thu, 20 Mar 2003, Brian Hurt wrote: > Blowfish I'm less interested in. I'm a fan of Twofish myself- especially > given some of the weaknesses discovered in AES/Rijndael recently... I share your feelings on Blowfish, but it's still popular and I have an OCaml interfaced version lying around that I could pretty much copy and paste into cryptokit. it has all sorts of hooks in there for peeking at and mussing with the internal state, but I might just leave those in for folks who want to have some fun... BTW: Which Rijndael weaknesses are you referring to? Not the Filiol mistake (let's be charitable and call it a mistake)? Or are you referring to the Courtois & Pieprzyk XSL work? Or something else? > I'd like an easy, reasonably fast, library to find primitive polys in > GF(2^n) for some n. Hmmm...I'll have to look at that. I haven't needed it yet (hence its non-existance in my code), but I could see needing it in the future. I'm just not sure if that kind of stuff should really go in a crypto library though. It would probably be better to have a number theory/algeba library that is used by the crypto library instead. > Is there a Yarrow-based PRNG? No. I don't usually care about having a strong source of randomness, since most of what I do is testing, but I agree that a strong PRNG should be included in any publicly released version, so I suppose I could add yarrow (I'd have to look at the code and see when I can fit it into my schedule, though). William D. Neumann --- "Well I could be a genius, if I just put my mind to it. And I...I could do anything, if only I could get 'round to it. Oh we were brought up on the space-race, now they expect you to clean toilets. When you've seen how big the world is, how can you make do with this? If you want me, I'll be sleeping in - sleeping in throughout these glory days." -- Jarvis Cocker |
From: Nicolas C. <war...@fr...> - 2003-03-24 06:37:34
|
> - bitset is being rewritten into bitarray, with the new features suggested > by the change in name. The goal is to produce something you could write > elliptic curve cryptosystems in at least semi-efficiently. Nice ! > - I have the beginings of what I'm currently calling an XString library, > which stores a string as an unbalanced tree of of substrings. The big > advantage here is that concats are O(1), and then converting the XString > to a normal string is O(n). In-place modification won't be supported. > This will be usefull in constructing strings by concating substrings > efficiently. Sort of like Java's StringBuffer. Very good also, but what then does not call it StringBuffer ? The name came by itself, so... :) > - A resizable array module- rather like Java's Vector or Python's List. Yes we realy need this Vector one > Life has been rather hectic of late for me- sorry I haven't been more > timely on this. But this weekend is looking dull, so I should be able to > spend some serious coding time. Yes, I would like to apologize for my previous post, and after some thinking, I think now we're walking the good way, and we have no need to hurry more. I'm currently still working on the List implementation... okay , some words about it : I'm currently at Kyoto, and having everyday at lunch some ocaml-talks with Jacques Garrigue, and when I told him about this setcdr trick, is first reaction was that it would be nice but perhaps there is some GC issues since that can create pointers from the major to the minor heap, and then causing speed overhead. Right now I'm aiming at tricking the compiler with mutable structures , with the goal to have at least the ExtList.map speed be as good as the ExtList.map one. Even if I don't manage to do it, I will move the non-tails functions List.map , List.fold_right, etc. into a "Fast" ExtList sub-module ( I'll test for speed only for native code version under Windows OCaml/VC++, since when you compile to bytecode you not care so much about speed, and since I don't have access to other platforms right now - I'll post here the test samples and results to know about other platforms speeds ) > Longer term, libraries I'd like (and that I think would be usefull) would > include: > > - A BLAS-like library. Although I need to think about this design some- > OOLALA has shown me that BLAS itself is probably not the best overall > library design. > > - A regular expressions library- although I think this might already be > out there. > > - An elliptic curve crypto systems library. Except the reg expr library ( and the new Regexp is the third one after the Str module and PCRE ) I can't tell theses could be massively used enough to be included in the ExtLib :) Keep going on ! Nicolas Cannasse |
From: Brian H. <bri...@ql...> - 2003-03-24 16:43:00
|
On Mon, 24 Mar 2003, Nicolas Cannasse wrote: > > - bitset is being rewritten into bitarray, with the new features suggested > > by the change in name. The goal is to produce something you could write > > elliptic curve cryptosystems in at least semi-efficiently. > > Nice ! Status report on this: I spent the weekend writting and rewritting and rerewritting the damned rotate functions. Everything else looks like it's about ready to go. I'm going to take another swing at the rotates tonight, and see if I can kick my brain into working. > > > - I have the beginings of what I'm currently calling an XString library, > > which stores a string as an unbalanced tree of of substrings. The big > > advantage here is that concats are O(1), and then converting the XString > > to a normal string is O(n). In-place modification won't be supported. > > This will be usefull in constructing strings by concating substrings > > efficiently. Sort of like Java's StringBuffer. > > Very good also, but what then does not call it StringBuffer ? > The name came by itself, so... :) I may. > > > - A resizable array module- rather like Java's Vector or Python's List. > > Yes we realy need this Vector one As a side note, I do way too much numerical programming to like the term 'vector' to denote extensible arrays. This annoys me no end in Java. I'm likely to call this library 'xarray' or something instead. > > > Life has been rather hectic of late for me- sorry I haven't been more > > timely on this. But this weekend is looking dull, so I should be able to > > spend some serious coding time. > > Yes, I would like to apologize for my previous post, and after some > thinking, I think now we're walking the good way, and we have no need to > hurry more. It's OK. > I'm currently still working on the List implementation... okay , > some words about it : I'm currently at Kyoto, and having everyday at lunch > some ocaml-talks with Jacques Garrigue, and when I told him about this > setcdr trick, is first reaction was that it would be nice but perhaps there > is some GC issues since that can create pointers from the major to the minor > heap, and then causing speed overhead. I'm only using setcdr on list elements I just recently allocated, which makes it signifigantly less likely that I would be adding a pointer from the major to the minor heap. Possible, but not likely. Brian |
From: Nicolas C. <war...@fr...> - 2003-03-25 01:52:17
|
> > I'm currently still working on the List implementation... okay , > > some words about it : I'm currently at Kyoto, and having everyday at lunch > > some ocaml-talks with Jacques Garrigue, and when I told him about this > > setcdr trick, is first reaction was that it would be nice but perhaps there > > is some GC issues since that can create pointers from the major to the minor > > heap, and then causing speed overhead. > > I'm only using setcdr on list elements I just recently allocated, which > makes it signifigantly less likely that I would be adding a pointer from > the major to the minor heap. Possible, but not likely. Actually, it depends ! For example the map function is calling an user function, that can do lots of things, resulting a minor heap collection, and then back to ExtList.map your root has been moved to major heap. But Damien Doligez conclusion was that it will only occur once at a time, since next GC will put everything in the major heap, so the cost is very low. Nicolas Cannasse |
From: Brian H. <bh...@sp...> - 2003-03-25 16:32:16
|
On Tue, 25 Mar 2003, Nicolas Cannasse wrote: > > > I'm currently still working on the List implementation... okay , > > > some words about it : I'm currently at Kyoto, and having everyday at > lunch > > > some ocaml-talks with Jacques Garrigue, and when I told him about this > > > setcdr trick, is first reaction was that it would be nice but perhaps > there > > > is some GC issues since that can create pointers from the major to the > minor > > > heap, and then causing speed overhead. > > > > I'm only using setcdr on list elements I just recently allocated, which > > makes it signifigantly less likely that I would be adding a pointer from > > the major to the minor heap. Possible, but not likely. > > Actually, it depends ! > For example the map function is calling an user function, that can do lots > of things, resulting a minor heap collection, and then back to ExtList.map > your root has been moved to major heap. But Damien Doligez conclusion was > that it will only occur once at a time, since next GC will put everything in > the major heap, so the cost is very low. > Even with append it's possible. I have to allocate the next node in the list before calling setcdr (obviously). Allocating the next node could cause a collection (minor heap being full) moving the previous node into the major heap. Then, when I call setcdr, I'm still setting a pointer from the major heap to point to the minor heap. So this is a problem that needs to be handled correctly no matter what. On the other hand, it doesn't have to be the most efficient- because for every time we write a pointer into the major heap, we also have to do a garbage collection. In your example, the map with a complex function, the cost of the function itself becomes a major cost. These costs will overwhealm the cost of setting the pointer itself. Some back of the envelope calculations. Assume the minor heap is 16K words (64K bytes). And we allocate 1 word every 6 instructions (about average for ML programs). This means we do a GC every 96K instructions on average. Even if setting a pointer from a major to a minor heap is 1K instructions, this is still less than 1% of the execution cost (not counting the cost of the garbage collection itself). Which is, effectively, the conclusion you came to. Brian |