(Безопасно) Случайная строка?

Question

В Lua обычно генерируют случайные значения и / или строки, используя math.random & math.randomseed, где os.time используется для math.randomseed.

Этот метод, однако, имеет одну большую слабость; Возвращенное число всегда так же случайно, как и текущее время, И интервал для каждого случайного числа одна секунда , что слишком много, если нужно много случайных значений в очень короткое время.

На эту проблему даже указывают пользователи вики Lua: http://lua -users.org / wiki / MathLibraryTutorial и соответствующий рецепт RandomStringS: http://lua -users.org / вики / 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

---

Поскольку этот вопрос будет опущен, независимо от моих правок, я также отменил свой ранее принятый ответ - в надежде на лучший, даже если просто лучшее мнение. Я понимаю, что вопросы, связанные со случайными значениями / числами, обсуждались много раз, но я не нашел такого вопроса, который мог бы иметь отношение к Lua. Пожалуйста, имейте это в виду!

Answer 1

1. Вы не должны вызывать seed каждый раз, когда вызываете random , вы должны вызывать его только один раз при инициализации программы (если, например, вы не получили откуда-то начальное число,повторить некоторое предыдущее «случайное» поведение).

2. Стандартный генератор случайных чисел Lua имеет плохое качество в статистическом смысле (как это, фактически, стандартный генератор случайных чисел C), неиспользуйте это, если вы заботитесь об этом.Используйте, например, модуль lrandom (доступен в LuaRocks).

3. Если вам нужно более безопасное случайное чтение, прочитайте из /dev/random в Linux.(Я думаю, что в Windows должно быть что-то в том же духе, но вам, возможно, придется что-то кодировать в C, чтобы использовать это.)

4. Использование значений указателей таблиц - плохая идея.Подумайте об альтернативных реализациях Lua, например, в Java - невозможно сказать, что они вернут.(Кроме того, значения указателя могут быть предсказуемыми, и при определенных обстоятельствах они могут быть одинаковыми при каждом запуске программы.)

5. Если вы хотите более высокую точность для начального числа (ивы захотите этого, только если вы запускаете программу чаще, чем раз в секунду), вам следует использовать таймер с лучшим разрешением.Например, socket.gettime() от LuaSocket.Умножьте его на некоторое значение, поскольку math.randomseed работает только с целочисленной частью, а socket.gettime() возвращает время в секундах (с плавающей запятой).

   require 'socket'
   
   math.randomseed(socket.gettime() * 1e6)
   
   for i = 1, 1e3 do
     print(math.random())
   end
   

Answer 2

Этот метод, однако, имеет одну большую слабость;Возвращенное число всегда так же случайно, как и текущее время, И интервал для каждого случайного числа составляет одну секунду, что слишком много, если нужно очень много случайных значений за очень короткое время.

Он имеет эти недостатки только в том случае, если вы неправильно его реализуете.

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 всегда и иметь разные случайные числа каждый раз, когда вызываете его.

Единственный сценарий, который вам следует немного беспокоиться о неслучайности, - это когда ваша программа должна выполняться более чемодин раз в секунду.В этом случае, как говорят другие, самое простое решение - использовать часы с более высоким разрешением.

Другими словами:

• Вызвать math.randomseed с подходящим семенем (os.time() - это нормально, 99% случаев) в начале вашей программы
• Вызывайте math.random каждый раз, когда вам нужно случайное число.

С уважением!

Answer 3

Некоторые мысли по первой части вашего вопроса:

Итак, мой вопрос, насколько случайными являются эти числа, возвращаемые realrandom на самом деле?

Ваша функцияпытается найти адрес таблицы, используя причину ее реализации по умолчанию tostring().Я не верю, что строка, возвращаемая tostring{}, имеет указанный формат или что значение, включенное в эту строку, имеет какое-либо задокументированное значение.На практике это происходит от адреса что-то , связанного с конкретной таблицей, и поэтому разные таблицы преобразуются в разные строки.Тем не менее, следующая версия Lua может изменить это на что угодно.Хуже того, формат, который он принимает, будет сильно зависеть от платформы, поскольку он использует спецификатор формата %p для sprintf(), который указывается только как разумное представление указателя.

Существует также гораздо большийвопрос.Хотя адрес n-й таблицы, созданной в процессе, может показаться случайным на вашей платформе, tt может не быть случайным вообще.Или это может варьироваться всего в несколько бит.Например, на моем win7-боксе меняется только несколько битов, причем не очень случайно:

C:...>for /L %i in (1,1,20) do @ lua -e "print{}"
table: 0042E5D8
table: 0061E5D8
table: 0024E5D8
table: 0049E5D8
table: 0042E5D8
table: 0042E5D8
table: 0042E5D8
table: 0064E5D8
table: 0042E5D8
table: 002FE5D8
table: 0042E5D8
table: 0049E5D8
table: 0042E5D8
table: 0042E5D8
table: 0042E5D8
table: 0024E5D8
table: 0042E5D8
table: 0042E5D8
table: 0061E5D8
table: 0042E5D8

Другие платформы, конечно, будут отличаться.Я бы даже ожидал, что будут платформы, где адрес первой выделенной таблицы будет полностью детерминированным и, следовательно, будет идентичным при каждом запуске программы.

Короче говоря, адрес произвольного объекта в образе вашего процессане очень хороший источник случайности.

Редактировать: Для полноты картины я хотел бы добавить пару других мыслей, которые пришли в голову за ночь.

Функция stock tostring() предоставляется базовой библиотекой и реализуется функцией luaB_tostring().Соответствующим битом является этот фрагмент:

switch (lua_type(L, 1)) {
  ...
  default:
    lua_pushfstring(L, "%s: %p", luaL_typename(L, 1), lua_topointer(L, 1));
    break;

Если вы действительно вызываете эту функцию, то конец строки будет адресом, представленным стандартным форматом C sprintf() %p, тесно связанным сконкретная таблица.Одно наблюдение состоит в том, что я видел несколько различных реализаций для %p.Windows MSVCR80.DLL (версия библиотеки C, используемая в текущем выпуске Lua для Windows) делает ее эквивалентной %08X.Моя коробка Ubuntu Karmic Koala, кажется, делает ее эквивалентной %#x, что заметно сбрасывает ведущие нули.Если вы собираетесь разобрать эту часть строки, то вы должны сделать это более гибким способом с учетом изменения значения %p.

Также обратите внимание, что выполнениечто-нибудь подобное в библиотечном коде может преподнести вам пару сюрпризов.

Во-первых, если таблица, переданная в tostring(), имеет метатаблицу, обеспечивающую функцию __tostring(), то эта функция будет вызвана, а приведенный выше фрагмент никогда не будет выполнен вообще.В вашем случае эта проблема не может возникнуть из-за того, что таблицы имеют отдельные метатаблицы, и вы случайно не применили метатаблицу к вашей локальной таблице.

Во-вторых, к моменту загрузки вашего модуля какой-то другой модуль или предоставленный пользователемкод мог заменить акции tostring() чем-то другим.Если замена безвредна (например, оболочка memoization ), то, вероятно, это не имеет значения для написанного кода.Тем не менее, это может быть источником атаки и полностью находится вне контроля вашего модуля.Это не очень хорошая идея, если целью является улучшение безопасности вашего случайного начального материала.

В-третьих, вы можете вообще не загружаться в стандартный интерпретатор Lua, а в более крупное приложение.(Lightroom, WoW, Wireshark, ...) могут заменить функции базовой библиотеки своими собственными реализациями.Это гораздо менее вероятная проблема для tostring(), но обратите внимание, что базовая библиотека print() является частой целью для замены или удаления в альтернативных реализациях, и существуют модули ( Lua Lanes , для одного), которыеbreak, если print не является реализацией в базовой библиотеке.

Answer 4

На ум приходит несколько важных вещей:

• В большинстве других языков вы, как правило, вызываете функцию случайного 'seed' только один раз в начале программы или, возможно, в ограниченные промежутки времени во время ее выполнения.Обычно вы не хотите вызывать его каждый раз, когда генерируете случайное число / последовательность.Если вы вызываете его один раз при запуске программы, вы можете обойти ограничение «один раз в секунду».Вызывая его каждый раз, вы можете получить меньше случайности в своих результатах.
• Ваша функция realrandom (), похоже, основана на частной реализации Lua.Что произойдет в следующем основном выпуске, если эта деталь изменится так, что она всегда будет возвращать одно и то же число или только четные числа и т. Д. Только потому, что это работает на данный момент, не является достаточно сильной гарантией, особенно в случае необходимости безопасного RNG.
• Когда вы говорите «все кажется совершенно случайным», как вы измеряете эту производительность?Мы, люди, ужасно определяем, является ли последовательность случайной или нет, и просто смотреть на последовательность чисел было бы практически невозможно действительно сказать, случайны они или нет.Существует много способов количественно оценить «случайность» ряда, включая распределение частот, автокорреляцию, сжатие и многие другие, которые выходят за рамки моего понимания.
• Если вы пишете настоящий «безопасный PRNG» для производства, не пишитетвой собственный!Исследуйте и используйте библиотеку или алгоритм специалистами, которые потратили годы / десятилетия на изучение, проектирование и попытки его сломать.Истинно безопасное генерирование случайных чисел сложно.

Если вам нужна дополнительная информация, начните со статьи PRNG в Википедии и используйте ссылки / ссылки там, где это необходимо.