8

代码在 Objective C 中，但是即使你不了解 Objective C，如果你仔细查看它应该是可以理解的。基本上它是一个 RNG 对象，你实例化一个新实例，如果你想要设置种子并开始抓取随机数。

那么是否可以回溯给定的一系列数字以确定用于生成数字的种子？我猜任何给定的算法都不能生成任何随机数字集，或者可以吗？

假设我执行以下操作：

rng.seed = 1024;
for (int i=1; i<11; i++)
    DLog(@"%lu", [rng randomBetween:0 and:10]);

这给了我序列10, 10, 8, 10, 2, 10, 9, 9, 7, 4。给定序列，我可以使用某种方法或算法来获得数字 1024？我知道那是看到的 1024 的有效序列，但我只是组成一个序列10, 1, 9, 6, 3, 9, 10, 3, 5, 2...... 有没有办法知道这是否是该算法的有效序列，如果是，种子是什么？

RNG.h：

@interface RNG : NSObject
@property (assign) unsigned long seed;
- (unsigned long)random;
- (long)randomBetween: (long)min and: (long)max;
@end

RNG.m:

#define A 16807         /* a relatively prime number -- also M div Q */
#define M 2147483647L   /* 0xFFFFFFFF / 2 */
#define Q 127773L       /* M div A */
#define R 2836          /* M mod A */

@implementation RNG
@synthesize seed = _seed;

- (id)init {
    self = [super init];
    if (self) {
        self.seed = 0;
    }
    return self;
}


- (unsigned long)random {
    self.seed = A * (self.seed % Q) - R * (self.seed / Q);
    if (self.seed > M)
        return (self.seed -= M);
    else if (self.seed)
        return (self.seed);
    else
        return (self.seed = 1L);
}


- (long)randomBetween: (long)min and: (long)max {
    return ([self random] % (max - min + 1) + min);
}


- (void)seed: (unsigned long)new_seed {
    if (new_seed == 0)
        new_seed = 1;
    while (new_seed > M)
        new_seed -= M;

    self.seed = new_seed;
}
@end
4

3 回答 3

3

您发布的代码与openbsd srandom基本相同- 它是一个线性同余生成器，用于避免舍入（这就是它包含的原因Q）。

这是一篇关于如何破解这种生成器的论文，但它希望完整的输出（而不是“中间”值）可用。

我想你应该能够扩展论文中的方法以使用算术模范围来处理“之间”（大概你需要更多样本）。

于 2012-08-16T13:19:23.770 回答
3

这看起来像一个“线性同余生成器”，参见http://en.wikipedia.org/wiki/Linear_congruential_generator？

这些没有提供良好的密码安全性，所以是的，应该可以计算产生序列的种子。

于 2012-08-16T08:57:39.603 回答
0

您最好的选择可能是创建一个数组（或磁盘文件），该数组（或磁盘文件）具有您为每个种子选择的算法返回的第一个值。然后只需通过与第一个值匹配的那些来寻找更长的匹配。事实上，数据库表会很棒——想到 gdbm 或 bsddb 或 sqlite。

在我看来，这听起来像是“它是可计算的，但是……”的问题之一。IOW，它可以做到，但它不是特别漂亮。

于 2012-08-16T19:38:21.450 回答