基于时间的(真正的)随机数？

Question

我需要一个随机数发生器.不是伪随机数,而是真正的随机数.我想到,也许我可以从循环执行中的微妙时序差异中提取位,所以我把一些东西放在一起做到这一点:

#ifdef _WIN32
#include <windows.h>
unsigned long long tick()
{
    unsigned __int64 
        tock;
    QueryPerformanceCounter((LARGE_INTEGER *)&tock);
    return (unsigned long long)tock;
}
#else
#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 sampled 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();
    }
}

它看起来效果很好(通过TESTU01测试套件)......但我仍然想知道:

(1)我是否正确实施了一切

(2)做平台#defines看起来还行

(3)在黑客获得系统时间控制或某些此类控制的情况下,是否存在任何(合理的)可能性

(4)有更好的方法来实现这一目标

(5)是否存在任何合理的论据:(a)生成的值实际上不是足够随机的;(b)如果是,调整threshold参数是否可以纠正这种情况

编辑

在最终能够在几个Linux机器上测试代码之后,事实证明特定tick()于Linux的代码没有正确实现.幸运的是,标准clock()函数似乎工作正常,所以我只是简单地恢复使用那些系统.

Answer 1

您无法使用算法创建真正的随机性.

"任何考虑产生随机数字的算术方法的人当然都处于犯罪状态." - 约翰冯诺伊曼

因为,无论如何,有人可以复制完全相同的计算环境并获得完全相同的结果.

但是,你可以相当接近.内核提供了使用尽可能多的操作噪声的方法,因为它们可以提供具有可变熵级别的一些相当可靠的随机性.例如,在Unix平台上,这是通过从/dev/random或中抽样完成的/dev/urandom.在Windows上,它是CryptGenRandom.他们只使用几乎任何可能的东西 - 从分配的内存到CPU活动 - 来进行更广泛的描述,以提高熵.

如果你想要真正的随机性,没有人可以穿透,那么你将不得不使用现实世界的输入 - 例如,www.random.org从大气中采样他们的数字.您可以使用例如麦克风或网络摄像头上的噪音,但根据使用情况,这些噪音很容易被挫败.

综上所述:

• 如果您需要一个真正随机的源,请获取硬件随机生成器(通常采样本地大气).最新的ARM/Intel CPU内置了一个,但值得注意的是,他们担心实现的实际安全性.
• 如果你可以稍微妥协,只需使用可用的系统随机性,就像/dev/random这些对大多数人来说足够好.不要重新发明比这更弱的东西.