| Re: How to generate cryptographically-secure random big-integers? [message #170217 is a reply to message #170213] |
Wed, 20 October 2010 09:51   |
Erwin Moller
Messages: 228
Registered: September 2010
Karma:
|
Senior Member |
|
|
On 10/20/2010 8:57 AM, Robert Maas, http://tinyurl.com/uh3t wrote:
> I need to generate a random integer uniformly distributed from 0 to
> 165704257009980305087908956205223296585688096305918417966291411066008093135 190411324365527113804568013399264982255120906812142560021321323875432044092 494966970218269418334085525290028472777766273110227504712320
> The following code:
> srand(time());
> $random = (rand()%9); ...etc...
> :is no good because time returns 1287555603 currently, and it would
> be relatively easy for somebody who has access to my source code to
> try all possible values for the time seed, a 10-digit integer, and
> thus crack my cryptosystem. I'm doing personal research to try to
> find something that is truly random for two hundred and ten
> independently random cryptographically secure digits. My current
> idea is to call the microsecond-time function a moderately large
> number of times in succession, subtract adacent values (result
> usually 4, often 5, rarely any other value), build a Markovian
> model for the sequence, and then apply interval refinement directly
> to the interval where I want the value until the length of the
> interval is small enough to specify a single integer. But before I
> go to a lot of effort to develop this idea, maybe one of you has an
> idea for some method somebody else already did that I could use
> instead?
>
> P.S. Here's a sample run of the microsecond-time differences:
> 33 6 4 4 4 5 4 4 6 4 4 5 5 5 4 4 5 4 4 4 4 5 4 4 4 4 4 4 5 4 4 4 5 4 5 4 4 4 4 5 4 4 4 5 4 4 6 5 4 4 4 5 4 4 4 4 4 4 4 5 5 4 4 5 5 4 4 5 4 4 4 4 4 5 4 4 4 4 5 4 4 5 5 4 5 3 5 4 4 4 4 5 4 4 4 4 4 4 4 4 5 4 4 4 4 4 4 4 4 5 4 4 4 4 4 4 4 4 4 4 4 5 4 4 4 5 6 4 7 4 4 4 4 5 4 4 4 4 4 4 4 3 5 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 4 4 4 4 5 4 4 4 4 7 5 3 5 4 4 4 4 4 4 4 5 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 4 4 4 5 4 4 4 4 4 4 4 4 5 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 4 4 8 4 4 4 4 4 5 3 5 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 4 4 4 4 4 4 4 4 4 4 4 4 4 3 4 5 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 4 3 5 4 4 4 4 3 4 5 3 4 5 3 4 5 4 3 5 4 3 5 4 3 5 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 3 4 5 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 3 5 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 4 4 4 4 4 4 4 4 4 4 4 4 4 4
4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 4 4 4 4 4 10 5 4 4 4 4 4 4 4 4 4 5 4 4 4 5 4 4 4 5 4 4 4 5 4 4 5 4 4 5 4 4 5 4 4 4 5 4 4 4 5 4 4 4 4 5 4 4 4 4 5 4 4 4 4 4 5 4 4 4 4 5 4 4 4 4 5 4 4 4 5 4 4 4 4 5 4 4 4 4 5 4 4 4 4 4 5 4 4 4 4 5 4 4 4 4 5 4 4 4 4 5 5 4 4 4 4 4 5 4 4 4 4 5 4 4 4 4 5 4 4 4 4 5 4 4 4 4 4 5 4 4 5 4 4 4 4 4 5 4 4 4 4 5 4 4 4 4 5 4 4 4 4 5 4 4 4 4 4 5 4 4 4 4 5 4 4 4 5 4 4 4 4 5 4 4 4 5 4 4 4 4 5 4 4 4 5
> and here's the corresponding null-context tally:
> Array
> (
> [3] => 14
> [4] => 570
> [5] => 106
> [6] => 4
> [7] => 2
> [8] => 1
> [10] => 1
> [33] => 1
> )
> Unfortunately, adjacent differences are highly correlated, as you
> can see by visual examination of the raw differences, so the
> null-context tally is not a good model for the data. Only a small
> number of sequences of data are likely, hence only a small number
> of the values from 0 to the maximum integer would actually be
> likely to appear, and somebody could guess them all and thus crack
> my cryptosystem. Instead, I'll need to dynamically choose a set of
> non-null left-contexts, which is messy to optimize, especially in
> real time as I'm bootstrapping a cryptosystem to a remote site, and
> then compile a set of tallies for each left context being used, and
> then consider each difference in the appropriate left context i.e.
> use the appropriate tally for converting that difference into an
> interval refinement.
Hi Robert,
I noticed you used:
srand(time());
But the manual says:
===================================================================
Note: As of PHP 4.2.0, there is no need to seed the random number
generator with srand() or mt_srand() as this is now done automatically.
===================================================================
But the manual is not very clear on the exact implementation it uses
when you do not call srand().
But there are a few other approaches you could consider:
1) /dev/random
And in case you are on Linux, have a look at /dev/random/
http://en.wikipedia.org/wiki//dev/random
It says: "It allows access to environmental noise collected from device
drivers and other sources.", which sounds promising, as in impossible
for the man-in-the-middle to predict.
2) Use one of these online random generators, based on nuclear fission.
But this is probably a bad idea since that communication can be heard by
the man-in-the-middle.
3) If you are really serious about randomness, you could buy one of
these cards that generate true random numbers.
Possible /dev/random can do the same. I never looked into it any deeper
than this. ;-)
Another approach (I don't like) that was mentioned in the user
contributions on the PHP manual was: request some webpage and measure
the time needed (micros) to fetch it. And use that number as the seed.
One last thing: Why not use mt_rand()? It seems to be better:
http://nl2.php.net/manual/en/function.mt-rand.php
Regards,
Erwin Moller
Disclaimer: I am not random number generator expert.
--
"There are two ways of constructing a software design: One way is to
make it so simple that there are obviously no deficiencies, and the
other way is to make it so complicated that there are no obvious
deficiencies. The first method is far more difficult."
-- C.A.R. Hoare
|
|
|
|
Calendar
Search
Help
Members
Register
Login
Home
]