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


viff-devel mailing list (http://viff.dk/)

viff-devel mailing list (http://viff.dk/)

Reply via email to