| Re: How to generate cryptographically-secure random big-integers? [message #170220 is a reply to message #170217] |
Wed, 20 October 2010 10:08   |
The Natural Philosoph
Messages: 993
Registered: September 2010
Karma:
|
Senior Member |
|
|
Erwin Moller wrote:
> 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.
>
That is useful.
Wish I had known that 3 days ago when I needed a table of random bytes..
|
|
|
|
Calendar
Search
Help
Members
Register
Login
Home
]