提高Objective-C中随机性的质量

Question

你站在地牢里.在你之前,有一组5级书呆子.他们希望您为他们运行"龙与地下城"活动.

你运行了几个阶段,你的球员正在升级,而且事情通常会膨胀.但是战斗有点慢.你决定拿出你的+4 Halberd of Objective-C并编写一个iPad应用来自动化NPC骰子在战斗中滚动.威胁说,书呆子向你走来."算法生成的数字,"一个人咆哮道,"是对真正随机性的空洞模仿!你不应该用你的伪随机污秽来玷污我们的神圣战役!"

你滚动说服他arc4random_uniform()不仅仅是足够......而且失败了.书呆子会满足于真正的随机性.当你拼命地依赖MacBook时,他们会把你当作囚犯,写一个从random.org中检索数据的课程.

NSDateFormatter *formatter = [[NSDateFormatter alloc] init];
[formatter setDateFormat:@"YYYY/YYYY-MM-dd"];
NSURL *url = [NSURL URLWithString:[NSString stringWithFormat:@"%@%@%@", 
                @"http://www.random.org/files/", 
                [formatter stringFromDate:[NSDate date]],
                @".bin"]];
NSURLConnection *theConnection = [[NSURLConnection alloc] initWithRequest:
                [NSURLRequest requestWithURL:url] delegate:self];

保存数据后,允许从下载的字节生成随机数0-255.

-(int) nextInt:(int)start end:(int)end
{
    int upperBound = end - start + 1;
    unsigned char result;
    int maxModulo = 255 - (255 % upperBound);
    do {
        NSRange range = {index, sizeof(char)};
        [randos getBytes:&result range:range];
        index += sizeof(char);
    } while (result > maxModulo); //avoid modulo bias
    result = result % upperBound;
    result += start;
    return result;
}

书呆子似乎很满意,但是出现了一个新的敌人:另一个地牢大师!他要求你出于自己的目的给他一份软件副本.问题很明显 - 如果你们都在同一天使用random.org数据,你将获得相同的骰子卷!

所以我的问题如下:我如何修改random.org数据,使其保留"真正的随机性"之类的东西,但在程序的每个实例中都有所不同？我可以想象一个解决方案,需要从用户那里得到一些(据称是随机的)触摸板动作,就像TrueCrypt那样,但是一旦我有了这个常数,我不确定从那里去哪里.以某种方式使用我的常量哈希所有数字？这将产生更大的数字; 我在统计上是好的,如果我只是截断或模数到骰子卷？我不知道采取什么算法步骤.

Answer 1

我有一个不同的解决方案.一个能满足每个人的,我希望.每次要生成新的掷骰子时,都要这样做:

显示进度条,并提示用户摇动设备.

• 在等待时,适当地过滤加速度数据(一些低通IIR应该做得很好)并寻找具有一定给定幅度的尖峰.使用滞后计数级别更改.显示一个显示摇晃量的进度条.
• 同时,将原始加速度数据提供给合适的加密哈希函数,例如SHA-2.

当进度条一直向右移动时,播放骰子滚动的声音并使用散列函数的输出(256位)生成骰子值.这不会超过59d20.您还可以将散列函数状态保存为下一个掷骰子的输入.

这就是你告诉那些书呆子的事情:模具卷绝不是算法上可预测的.确定模具卷的唯一信息是你如何摇动设备,这对于真正的骰子也是如此.在理论上,你可以摇动设备以同样的方式两次,就如同在理论高度熟练的赌徒可以滚骰子真正让他们拿出他希望的方式.

如何使用输出:你有256位随机数据​​,并希望得到掷骰子.

struct bits {
    unsigned data[8];
    unsigned pos;
};

// Get next n bits, or -1 if out of entropy.
int get_bits(struct bits *b, int n);

// Roll an n-sided die, or -1 if out of entropy
int uniform(struct bits *b, int n)
{
    int nbits, x;
    for (nbits = 0; (1 << nbits) < n; ++nbits);
    do {
        x = get_bits(b, nbits);
        if (x < 0)
            return -1;
    } while (x >= n);
    return x + 1;
}

这个功能的工作原理是一次切割几个熵的骰子.因此对于d8,您需要切3位并使用结果.对于d20,你为d32切掉5位,如果结果大于20则重新滚动.如果你碰巧用完给定的掷骰子的熵(不太可能,但可能),那么我建议打印一个"骰子"高举"消息,并要求用户为剩余的骰子摇一摇.

脚注:除非你滚动大量的骰子,否则你的熵耗尽的可能性非常低.256位就足够了.在熵耗尽之前需要24d20甚至达到1%.