Of course it is also worth mentioning that this is a very quick and
dirty implementation of BBS. I am sure you can save a lot of time by
implementing this in a clever way.
No tricks were used except for gmpy.
Citat af Mikkel Krøigård <m...@cs.au.dk>:
By the way, I just implemented the Blum Blum Shub generator in
Python just to see how fast it would be compared to urandom. Note
here that urandom is significantly slower than the default Python
PRNG, but we can't use the normal one anyway.
The BBS generator must square modulo n (product of two Blum primes)
and then extract log log n lower-order bits from that. I picked a
2048 bit n and extracted 10 bits per squaring.
I then generated 10 random bits a million times using urandom and BBS:
urandom: 30 seconds
BBS: 80 seconds
Not THAT bad really. This is the ideal situation for BBS though.
However, if you use for example random() instead (random float in
[0;1) ), then you must either pool bits (which takes time) or throw
away bits per call, because you need about 53 bits per number (I'm
assuming they ARE double-precision, not a Python geek :) ). There I
got:
urandom: 29 seconds
BBS: 435 seconds (not surprising, since 80*6 = 420)
This is of course horrible.
PS: There are probably better crypto-secure PRNGS out there, I just
picked BBS because I know that one quite well.
Also, the CryptGenRandom generator in Windows is claimed to have
been patched and fixed for Windows XP and Vista (presumably Windows
7 too). However, it's probably not good practice to take their word
for it :)
Citat af Thomas P Jakobsen <thomas....@gmail.com>:
I agree that tests should be reproducible. But it is also very
important to use a cryptographically secure PRNG.
I don't know whether these two requirements can be satisfied by the
same number generator. If not, the best solution is to have two
"modes" of operation:
- A test mode where the execution can be reproduced and
- a secure mode using a cryptographically secure PRNG
Regards,
Thomas
_______________________________________________
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
_______________________________________________
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk