big*_*bob 38 python random numbers
好吧,这是一个比它听起来更棘手的问题,所以我转向堆栈溢出,因为我想不出一个好的答案.这就是我想要的:我需要Python以随机顺序生成一个简单的0到1,000,000,000的数字列表,用于序列号(使用随机数,这样你就无法分辨已经分配了多少或做了时间攻击很容易,即猜测下一个会出现的问题).这些数字与链接到它们的信息一起存储在数据库表(索引)中.生成它们的程序不会永远运行,因此它不能依赖于内部状态.
没什么大不了的？只需生成一个数字列表,将它们推入一个数组并使用Python"random.shuffle(big_number_array)",我们就完成了.问题是我想避免必须存储一个数字列表(从而读取文件,弹出一个顶部,保存文件并关闭它).我宁愿在飞行中生成它们.问题是我能想到的解决方案有问题:
1)生成一个随机数,然后检查它是否已被使用.如果已经使用它生成一个新的数字,检查,根据需要重复,直到找到一个未使用的数字.这里的问题是,在获得未使用的数字之前,我可能会感到不幸并生成大量使用过的数字.可能的解决方法:使用一个非常大的数字池来减少这种情况的可能性(但最后我得到了愚蠢的长数字).
2)生成一个随机数,然后检查它是否已被使用.如果已经使用了从数字中添加或减去一个并再次检查,请继续重复,直到我点击未使用的数字.问题是这不再是随机数,因为我已经引入了偏见(最终我会得到一堆数字,你可以预测下一个数字有更大的成功机会).
3)生成一个随机数,然后检查它是否已被使用.如果它已被使用添加或减去另一个随机生成的随机数并再次检查,问题是我们回到简单地生成随机数并检查解决方案1.
4)将其取出并生成随机列表并保存,让守护程序将它们放入队列中,以便有可用的数字(并避免不断打开和关闭文件,而是将其批处理).
5)生成更大的随机数并散列它们(即使用MD5)来获得更小的数值,我们应该很少得到冲突,但最终我的数字大于所需的数字.
6)在随机数(即unix时间戳)之前添加或附加基于时间的信息以减少碰撞的可能性,同样我得到的数字比我需要的数字更多.
任何人都有任何聪明的想法,可以减少"碰撞"的机会(即产生一个已经采取的随机数),但也可以让我保持这个数字"小"(即少于十亿(或十亿)你的欧洲人=)).
答案以及为什么我接受它:
因此,我将简单地选择1,并希望它不是一个问题,但是如果是的话,我会选择生成所有数字并存储它们的确定性解决方案,以便有一个获得新的随机数的保证,我可以使用"小"数字(即9位数而不是MD5 /等).
Cra*_*een 12
您可以使用格式保留加密来加密计数器.你的计数器从0开始向上,加密使用你选择的一个键将它变成你想要的任何基数和宽度的看似随机的值.
分组密码通常具有固定的块大小,例如64或128位.但格式保留加密允许您采用像AES这样的标准密码,并制作一个小宽度的密码,无论你需要什么基数和宽度(例如基数10,问题参数的宽度9),算法仍然是密码学上健壮.
保证永远不会发生冲突(因为加密算法会创建1:1映射).它也是可逆的(双向映射),因此您可以获取结果数字并返回到您开始时的计数器值.
AES-FFX是一种提出的标准方法.
我已经尝试了一些AES-FFX的基本Python代码 - 请参阅此处的Python代码(但请注意,它并不完全符合AES-FFX规范).它可以例如将计数器加密为随机查看的7位十进制数.例如:
0000000 0731134
0000001 6161064
0000002 8899846
0000003 9575678
0000004 3030773
0000005 2748859
0000006 5127539
0000007 1372978
0000008 3830458
0000009 7628602
0000010 6643859
0000011 2563651
0000012 9522955
0000013 9286113
0000014 5543492
0000015 3230955
... ...
对于Python中的另一个示例,使用另一种非AES-FFX(我认为)方法,请参阅此博客文章"如何生成帐号",该文章使用Feistel密码进行FPE.它生成从0到2 ^ 32-1的数字.
使用一些模块化的算术和素数,您可以创建0到大素数之间的所有数字,不按顺序.如果你仔细选择你的数字,下一个数字很难猜到.
modulo = 87178291199 # prime
incrementor = 17180131327 # relative prime
current = 433494437 # some start value
for i in xrange(1, 100):
print current
current = (current + incrementor) % modulo
如果它们不必是随机的,但不是明显线性的(1,2,3,4 ......),那么这是一个简单的算法:
选择两个素数.其中一个将是您可以生成的最大数字,因此它应该是大约十亿.另一个应该相当大.
max_value = 795028841
step = 360287471
previous_serial = 0
for i in xrange(0, max_value):
previous_serial += step
previous_serial %= max_value
print "Serial: %09i" % previous_serial
只需存储前一个序列,以便您知道上次停止的位置.我无法通过数学证明这是有效的(自那些特定的类以来已经太久了),但它对于较小的素数来说是明显正确的:
s = set()
with open("test.txt", "w+") as f:
previous_serial = 0
for i in xrange(0, 2711):
previous_serial += 1811
previous_serial %= 2711
assert previous_serial not in s
s.add(previous_serial)
你也可以通过9位数的素数来证明它,它只需要更多的工作(或更多的内存).
这确实意味着只要给出一些序列号,就可以弄清楚你的价值是多少 - 但只有9位数字,你不太可能会选择不合适的数字.
如果你不需要加密安全的东西,但只是"充分混淆"......
伽罗瓦菲尔兹
您可以尝试在Galois Fields中操作,例如GF(2)32,将简单的递增计数器x映射到看似随机的序列号y:
x = counter_value
y = some_galois_function(x)
其中许多操作都有反转,这意味着,根据序列号,您可以计算从中派生的原始计数器值.
至于为Galois Field寻找Python的库...好问题.如果你不需要速度(你不需要速度)那么你可以自己动手.我没试过这些:
GF中的矩阵乘法(2)
在GF(2)中选择合适的32×32可逆矩阵,并将32位输入计数器乘以它.这在概念上与LFSR有关,如S.Lott的回答中所述.
CRC
相关的可能性是使用CRC计算.基于GF(2)中的不可约多项式的长除的余数.Python代码很容易用于CRC(crcmod,pycrc),尽管您可能希望选择与通常使用的不同的不可约多项式,以用于您的目的.我对理论有点模糊,但我认为32位CRC应该为每个可能的4字节输入组合生成一个唯一值.检查一下.通过将输出反馈到输入中并检查它是否产生一个长度为2 32 -1 的完整循环(零只是映射到零),可以很容易地通过实验检查这一点.您可能需要摆脱CRC算法中的任何初始/最终XOR,以使此检查起作用.
我认为你高估了方法1)的问题.除非您有硬实时要求,否则只需通过随机选择即可快速终止.需要多次迭代的概率呈指数衰减.输出100M数字(10%fillfactor),您将有十亿次机会需要超过9次迭代.即使有50%的数字被采用,你平均需要2次迭代,并且有十分之一的机会需要超过30次检查.或者甚至是99%的数字已经被采用的极端情况可能仍然是合理的 - 你将平均100次迭代并且需要2062次迭代的十亿次更改