New Random Number Generator for encryption
in [Cryptography]
|
Prev: Scalable Key Cryptography - The Universal Model.
Next: New Generation Lossless Data Representations
From: orz on 11 Aug 2010 07:07 I've cut & pasted your code in to my RNG experimentation code and set it for testing using both TestU01 SmallCrush/Crush/BigCrush/Rabbit and my own test suite (which is not yet published but should be available on sourceforge within a week or so). Test results are not coming very quickly though, as they expect a fair number of random bits and this is producing them 1 at a time very slowly. I have not been very impressed with Diehard or the NIST stuff or RaBiGeTe or ENT. I have not tried Dieharder yet. The parameterization of MDWP that I'm testing is the one used by default in your sample code: mdwpobj<random_fracobj,vector5t,point5t> Preliminary results say that MDWP output is significantly higher quality than random_fracobj output, but that's not saying much as random_fracobj is horrible. It passes SmallCrush; it passes Rabbit up to 1 megabit so far; it passes my tests up to 1 GB so far (the last may sound like a lot, but my tests are intended to be called on multiple terrabytes for good RNGs - on faster RNGs I test 1 GB every 20 seconds or so, while on this it took 20 minutes). If you have a different parameterization you want testing focused on let me know, but my CPU resources are very limited so not much total testing will get done. Since MDWP requires an internal RNG I'd compare it to an RNG transforming wrapper like a Bays-Durham shuffle rather than to an RNG. In terms of practical usage I don't really see a point to this due to its extremely low speed, but it's possible this could be of interest from a theoretical perspective. Conceivably this could be optimized quite a bit, but there are RNGs that pass all bias tests that are 700+ times faster than this, and cryptographically secure RNGs that are 400+ times faster than this, so even with optimization I doubt it will be truly competitive in speed. I'd suggest taking a glance at RC4 btw. It's an RNG that's at heart about an arrangement of a fixed set of things, with their positions within that arrangement interacting over time. So in that way it's vaguely analogous to this, though it bears no real resemblance any physical system.
From: Lev Dymchenko on 11 Aug 2010 07:37 On Aug 11, 3:07 pm, orz <cdh...(a)gmail.com> wrote: > I've cut & pasted your code in to my RNG experimentation code and set > it for testing using both TestU01 SmallCrush/Crush/BigCrush/Rabbit and > my own test suite (which is not yet published but should be available > on sourceforge within a week or so). Test results are not coming very > quickly though, as they expect a fair number of random bits and this > is producing them 1 at a time very slowly. I have not been very > impressed with Diehard or the NIST stuff or RaBiGeTe or ENT. I have > not tried Dieharder yet. The parameterization of MDWP that I'm > testing is the one used by default in your sample code: > mdwpobj<random_fracobj,vector5t,point5t> > Preliminary results say that MDWP output is significantly higher > quality than random_fracobj output, but that's not saying much as > random_fracobj is horrible. It passes SmallCrush; it passes Rabbit up > to 1 megabit so far; it passes my tests up to 1 GB so far (the last > may sound like a lot, but my tests are intended to be called on > multiple terrabytes for good RNGs - on faster RNGs I test 1 GB every > 20 seconds or so, while on this it took 20 minutes). > If you have a different parameterization you want testing focused on > let me know, but my CPU resources are very limited so not much total > testing will get done. > > Since MDWP requires an internal RNG I'd compare it to an RNG > transforming wrapper like a Bays-Durham shuffle rather than to an > RNG. In terms of practical usage I don't really see a point to this > due to its extremely low speed, but it's possible this could be of > interest from a theoretical perspective. Conceivably this could be > optimized quite a bit, but there are RNGs that pass all bias tests > that are 700+ times faster than this, and cryptographically secure > RNGs that are 400+ times faster than this, so even with optimization I > doubt it will be truly competitive in speed. > > I'd suggest taking a glance at RC4 btw. It's an RNG that's at heart > about an arrangement of a fixed set of things, with their positions > within that arrangement interacting over time. So in that way it's > vaguely analogous to this, though it bears no real resemblance any > physical system. Thanks. Lets see results. Yes, it is a bit slow, however, MDWP rng can have very big rand seed or encryption key with same performance. Even megabytes. Do you know other RNG with such big rand seed? Performance of the reference code is also dependent of compiler. I hope compiler could deal with templates effectively. It uses about 200-500 clocks on one bit on my system.
From: Mok-Kong Shen on 11 Aug 2010 12:17 Lev Dymchenko wrote: > I believe Joseph talks about analysis of sub sequences of bits, each > sub sequence is formed by one particle. I am interested to learn some details of the theory and practice of that analysis technique when applied to attack PRNGs in general. M. K. Shen
From: Cristiano on 11 Aug 2010 12:46 Lev Dymchenko wrote: > What sequence size do you suggest? I usually do: 1, 8, 16, 32, ... MBits up to 128 MBits for the last answer. I use 50 sequences. I wrote a multi-threaded version (still in beta) of RaBiGeTe for Windows which include the GUI (written with wxWidgets). If you are interested in that version, let me know. Cristiano
From: Mok-Kong Shen on 11 Aug 2010 14:37
BTW, in case you are interested to compare your design with others, there is a PRNG by G. Marsaglia named Super KISS, which is claimed to have very large period and good statistical qualities. (You could Google to find it. I personally have unfortunately no knowldege of it.) M. K. Shen |