I need a random number generator. Not for pseudo-random numbers, but the truly random kind. It crossed my mind that maybe I could extract bits from the subtle timing differences in loop execution, so I put something together to do just that:
#ifdef _WIN32
#include <windows.h>
unsigned long long tick()
{
unsigned __int64
tock;
QueryPerformanceCounter((LARGE_INTEGER *)&tock);
return (unsigned long long)tock;
}
#elif __linux__
#include <sys/time.h>
unsigned long long tick()
{
timespec
tock;
clock_gettime(CLOCK_REALTIME, &tock);
return (unsigned long long)tock.tv_nsec;
}
#else
#warning "random_bits()/random_word() may run slowly on this system"
#include <time.h>
unsigned long long tick()
{
return (unsigned long long)clock();
}
#endif
#include <limits.h>
unsigned long long random_bits(unsigned short bits)
{
/*
The `threshold` setting determines the smallest sample to extract a bit
from. If set too low the result won't contain enough entropy to be useful.
We don't want to set it so high that we're just wasting CPU cycles either,
so we need to settle on a value somewhere in the middle. Heuristically,
256 seems to be a pretty good compromise.
*/
const unsigned long long
threshold = 256;
unsigned long long
result = 0,
increment,
accumulator,
count,
target;
const unsigned short
size = sizeof(result) * CHAR_BIT;
if(bits == 0 || bits > size)
bits = size;
while(bits-- > 0)
{
increment = 1;
accumulator = 0;
/*
Build up the value to be extracted from. We don't know anything
about the clock resolution, so the increment is repeatedly doubled
until it's large enough to make a difference.
*/
while(accumulator < threshold)
{
count = 0;
target = tick() + increment;
while(tick() < target)
++count;
accumulator += count;
increment <<= 1;
}
/*
Shift the previous bit up one position and insert the newly sample one.
*/
result <<= 1;
result |= (accumulator & 1);
}
return result;
}
unsigned long long random_word(unsigned short length)
{
return random_bits(length * CHAR_BIT);
}
// Example useage:
#include <stdio.h>
int main(void)
{
for(;;)
{
printf(" %u\n", (unsigned)random_word(sizeof(unsigned)));
getchar();
}
}
It appears to work well (passes the TESTU01 test suite)...but I still wonder:
(1) did I implemented everything correctly
(2) do the platform #defines look okay
(3) is there is any (reasonable) likelihood that this could be vulnerable in the case where a hacker gains control of the system time or some such
(4) is there is some better way to achieve this
(5) are there any legitimate arguments that (a) the generated values are in fact not sufficiently random and (b) if so, whether adjusting the threshold
parameter might remedy the situation in such a case
Aucun commentaire:
Enregistrer un commentaire