| Re: How to generate cryptographically-secure random big-integers? [message #170224 is a reply to message #170220] |
Wed, 20 October 2010 11:11   |
Erwin Moller
Messages: 228
Registered: September 2010
Karma:
|
Senior Member |
|
|
On 10/20/2010 12:08 PM, The Natural Philosopher wrote:
> 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..
Oh. Bad luck. :-(
And how did you solve it then? Just go with mt_rand?
Personally, I have never been in need of a *real* RNG, the pseudorandom
numbers have always been good enough for my purposes.
Regards,
Erwin Moller
--
"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
]