Какой тип PRNG будет соответствовать таким графикам рассеяния?

avatar
Paul
8 августа 2021 в 20:44
93
1
-1

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

Каждый идентификатор получается путем прохождения предыдущего через алгоритм шифрования, который я должен перепроектировать, чтобы найти начальное число. Список, данный мне, состоит из 2070 первых идентификаторов (без семени, очевидно). Идентификаторы начинаются с 4 буквенно-цифровых символов и через некоторое время меняются на 5 (например, "2xm1", "34nj", "avdfe", "2lgq9")

.

Это переключение происходит, когда алгоритм после шифрования идентификатора возвращает идентификатор, который уже был сгенерирован ранее. В этот момент он добавляет один символ к этому возвращаемому идентификатору, делая его более длинным и, следовательно, уникальным. Затем он работает как обычно, генерируя идентификаторы новой длины. Фактически это означает, что алгоритм генерации является сюръективным.

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

После выделения двух частей списка с точки зрения длины идентификатора я построил точечный график для подсписка четырехсимвольных идентификаторов и подсписка пятизначных идентификаторов, что позволило мне заметить странные узоры плотности.

После некоторого анализа я заметил две вещи:

  • Для каждого подсписка разграничение между двумя плотностями составляет 6x36^(n-1), где n — количество символов в идентификаторе. Другими словами, это 1/6 всего диапазона значений для заданной длины идентификатора. Диапазон значений: [0; (36^n)-1]
  • Перераспределение этих идентификаторов по отношению к этому пределу имеет тенденцию к 50/50, половина из них выше предела 1/6, половина из них ниже его.

Я пытался сопоставить такое поведение с другими известными диаграммами рассеяния ГПСЧ, но ни один из них не соответствовал тому, что я получаю на своих графиках.

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

Заранее спасибо за ответы.

Источник

Ответы (1)

avatar
KMG
9 августа 2021 в 00:18
0

Этот ответ может быть не очень полезным, но я думаю, что он может помочь. показанный вами график, скорее всего, не принадлежит к одному из самых известных используемых ГПСЧ и, конечно, он никогда не будет принадлежать криптографическому ГПСЧ.

enter image description here

Но у меня есть уведомление, я не знаю, может ли оно помочь. Этот PRNG, по-видимому, имеет полный период, равный полному циклу чисел, сгенерированных для фиксированных символов. Я имею в виду, что он работает с шаблоном для 4 цифр, а затем повторяет шаблон, но с более высокой величиной для 5 символов, что, вероятно, означает, что тот же шаблон распределения будет повторяться для 6 символов, но с более высокой величиной.

Таким образом, летом это может означать, что этот шаблон можно использовать, если вы знаете, каково значение этой величины, поэтому вы знаете приращения для 6-символьного графического графика, а затем вы можете просто растянуть 5-символьный график по оси Y. -Axis, чтобы получить какое-то решение (которое будет исходным для графика из 6 символов).

РЕДАКТИРОВАТЬ: Чтобы более четко прояснить ситуацию в отношении вашего комментария. я имею в виду, что этот PRNG генерирует случайные числа, но эти случайные числа не будут повторяться до бесконечности, вместо этого будет некоторый момент времени, когда одна и та же последовательность будет восстановлена. I've inadvertantly left behind a piece of information: подтверждает это, поскольку когда он сталкивается с тем же числом, сгенерированным ранее (достигнут этот момент времени, когда та же последовательность регенерируется). Это просто добавит 1 дополнительный символ к последовательности, которая не изменит распределение на графике, но вместо этого сделает график таким, как если бы он был растянут вдоль оси Y (например, если пересечение Y функции графика только что стало больше).

Paul
9 августа 2021 в 08:50
0

Я не уверен, что правильно понял то, что вы описали. Должен ли я искать одинаковые точные закономерности распределения в обеих частях графиков? Я не совсем понимаю, что вы имеете в виду, когда говорите о «величине». Более того, я непреднамеренно оставил часть информации: мы обнаружили, что алгоритм добавляет 1 символ к длине сгенерированных идентификаторов, как только он встречает идентификатор, который уже был сгенерирован ранее. Это означает, что длина подсписков заранее не определена.

KMG
9 августа 2021 в 10:36
0

@PaulROBIN Я отредактировал ответ, чтобы попытаться упростить ситуацию.

Paul
9 августа 2021 в 10:45
0

О, это многое прояснило! Спасибо, я посмотрю на это! Единственное, что мне кажется странным, это то, что в случае части списка длиной в 4 символа идентификатор, предшествующий первому появлению дубликата, не совпадает с идентификатором, предшествующим второму появлению (первые 5 символов- длинный идентификатор). Это заставляет меня думать, что это может быть не последовательность, а только сюръективная функция.

Paul
9 августа 2021 в 11:01
0

Вот скриншоты отрывков, о которых я говорю