（安全的）随机字符串？

2011-2-21 5:2:57
收藏：0
阅读：281
评论：3

在 Lua 中，我们通常使用 math.random 和 math.randomseed 来生成随机值和/或随机字符串，其中 os.time 用于 math.randomseed。

然而，这种方法有一个主要的弱点：返回的数字与当前时间一样随机，并且每个随机数的间隔是一秒，如果需要在短时间内获得许多随机值，这个间隔时间就太长了。

Lua 用户 wiki 甚至指出了这个问题：http://lua-users.org/wiki/MathLibraryTutorial，以及相应的 RandomStringS receipe：http://lua-users.org/wiki/RandomStrings。

因此，我坐下来写了一个不同的算法（如果它能被称为算法），通过（误用）表的内存地址生成随机数：

math.randomseed(os.time())
function realrandom(maxlen)
    local tbl = {}
    local num = tonumber(string.sub(tostring(tbl), 8))
    if maxlen ~= nil then
        num = num % maxlen
    end
    return num
end

function string.random(length,pattern)
    local length = length or 11
    local pattern = pattern or '%a%d'
    local rand = ""
    local allchars = ""
    for loop=0, 255 do
        allchars = allchars .. string.char(loop)
    end
    local str=string.gsub(allchars, '[^'..pattern..']','')
    while string.len(rand) ~= length do
        local randidx = realrandom(string.len(str))
        local randbyte = string.byte(str, randidx)
        rand = rand .. string.char(randbyte)
    end

    return rand
end

起初，一切都看起来完全随机，而我确信它们确实是随机的...至少对于当前程序来说。

因此，我的问题是，由 realrandom 返回的这些数字到底有多随机？

或者是否有一种更好的方法来在不依赖于外部库的情况下，以完全跨平台的方式在短时间内生成随机数（这意味着不应该使用 os.time，如上所述）？

编辑：

在种子随机数生成器方面似乎存在重大误解；在生产代码中，对 math.randomseed() 的调用只会发生一次，这只是一个糟糕的例子。

我的意思是，每秒钟只有一次随机值的随机值，可以通过这个粘贴板轻松演示：http://codepad.org/4cDsTpcD

由于无论我如何编辑，这个问题都会被 downvote，因此我取消了之前接受的答案——希望有一个更好的答案，即使只是更好的意见。我理解关于随机值/数字的问题已经被讨论了很多次，但我还没有找到一个与 Lua 相关的问题——请记住这一点！

原文链接 https://stackoverflow.com/questions/5035229

点赞
stackoverflow用户439599
stackoverflow用户439599

几件重要的事情需要考虑：

  • 在大多数其他语言中，您通常只在程序开始时调用随机“种子”函数一次，或者在其执行期间有限次调用。通常不希望每次生成随机数/序列时都调用它。如果在程序启动时调用它一次，就可以绕过“每秒一次”的限制。如果每次调用它，您可能会在结果中得到更少的随机性。
  • 您的 realrandom() 函数似乎依赖于Lua的私有实现细节。如果此细节更改为始终返回相同的数字或仅返回偶数等，则下一个主要版本会发生什么……仅因为现在它能用并不足够强有力的保证，特别是在想要安全RNG的情况下。
  • 当您说“一切看起来都很随机”时，您如何衡量这种性能？我们人类很难确定一个序列是否随机，仅查看数字序列几乎不可能真正确定它们是否随机。有许多方法来量化系列的“随机性”，包括频率分布、自相关、压缩等，还有许多超出我的理解范围的方法。
  • 如果您正在编写真正的“安全PRNG”以供生产使用，请不要自行编写！调查并使用专家研究、设计和尝试攻破它的库或算法。真正安全的随机数生成很难。

如果您需要更多信息，请从维基百科的PRNG文章开始，并根据需要使用参考文献/链接。

2011-02-17 22:27:38
stackoverflow用户6236
stackoverflow用户6236

  1. 每次调用 random 时你不应该调用 seed，你应该只在程序初始化时调用一次它（除非你从其他地方获取了种子，比如为了复制之前的“随机”行为）。

  2. 标准 Lua 随机生成器在统计意义上的质量很差（事实上它就是标准的 C 随机生成器），如果你关心这一点，就不要使用它。可以使用例如 lrandom 模块（可在 LuaRocks 上找到）。

  3. 如果你需要更安全的随机数，可以从 Linux 的 /dev/random 中读取。（我想 Windows 应该也有类似的东西，但你可能需要编写一些 C 代码来使用它。）

  4. 依赖于表指针值是一个坏主意。要考虑到在其他 Lua 实现（如 Java）中会发生什么，这是不可预测的。（另外，指针值可能是可预测的，在某些情况下每次调用程序时都相同。）

  5. 如果你想要更细致的种子精度（仅在加上每秒运行程序一次以上时才需要），那么你应该使用具有更好分辨率的计时器。例如，使用 LuaSocket 中的 socket.gettime() 函数。将它乘以某个值，因为 math.randomseed 只使用整数部分，并且 socket.gettime() 返回以（浮点数）秒为单位的时间。

    require 'socket'

math.randomseed(socket.gettime() * 1e6)

for i = 1, 1e3 do
  print(math.random())
end
2011-02-17 23:14:44
stackoverflow用户312586
stackoverflow用户312586

然而，这种方法有一个主要的弱点；返回的数字总是与当前时间一样随机，而且每个随机数的间隔为一秒钟，如果需要在很短时间内产生许多随机值，这个时间太长了。

只有在错误实施时才存在上述弱点。

math.randomseed 应该谨慎调用 - 通常在程序开始时仅调用一次，并且通常使用 os.time 种子。一旦种子设置，就可以使用 math.random 多次并产生随机值。

看看下面的示例会发生什么：

> math.randomseed(1)
> return math.random(), math.random(), math.random()
0.84018771715471    0.39438292681909    0.78309922375861
> math.randomseed(2)
> return math.random(), math.random(), math.random()
0.70097636929759    0.80967634907443    0.088795455214007
> math.randomseed(1)
> return math.random(), math.random(), math.random()
0.84018771715471    0.39438292681909    0.78309922375861

当我将种子从 1 更改为 2 时，我会得到不同的随机结果。但是当我回到 1 时，“随机序列”被重置。我获得与之前相同的值。

os.time() 返回一个不断增加的数字。使用它作为种子是适当的，然后您可以随意调用 math.random 并在每次调用它时获得不同的随机数。

唯一的情况是，如果您的程序每秒执行超过一次，您可能需要担心非随机性。在这种情况下，正如其他人所说，最简单的解决方案是使用精度更高的时钟。

换句话说：

  • 在程序开始时使用适当的种子（os.time() 在 99% 的情况下可行）来调用 math.randomseed
  • 每次需要一个随机数时，请调用 math.random。

问候！

2011-02-18 12:39:15

作者:

stackoverflow用户88888888

stackoverflow用户88888888
推荐文章