Можно ли использовать нейронную сеть для прогнозирования следующего псевдослучайного числа?

17

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

Что-то подобное уже существует? Если исследование уже сделано по этому или чему-то связанному (с предсказанием псевдослучайных чисел), может ли кто-нибудь указать мне на правильные ресурсы?

В настоящее время я смотрю на эту библиотеку и связанные с ней ссылки. https://github.com/Vict0rSch/deep_learning/tree/master/keras/recurrent

AshTyson
источник

Ответы:

13

Если мы говорим о совершенном ГСЧ, то ответ - нет . Невозможно предсказать действительно случайное число, иначе оно не будет действительно случайным.

Когда мы говорим о псевдо-ГСЧ, все немного меняется. В зависимости от качества PRNG проблема варьируется от простой до почти невозможной. Очень слабый PRNG, такой как опубликованный XKCD, можно, конечно, легко предсказать с помощью нейронной сети с небольшим обучением. Но в реальном мире все выглядит иначе.

Нейронная сеть может быть обучена нахождению определенных шаблонов в истории случайных чисел, генерируемых PRNG, для предсказания следующего бита. Чем сильнее становится PRNG, тем больше требуется входных нейронов, при условии, что вы используете один нейрон для каждого бита предыдущей случайности, генерируемой PRNG. Чем менее предсказуемо получает PRNG, тем больше данных потребуется для нахождения какого-либо паттерна. Для сильных PRNG это неосуществимо.

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

Поскольку современные PRNG являются ключевым компонентом криптографии, были проведены обширные исследования, чтобы убедиться, что они «достаточно случайны», чтобы противостоять таким атакам с предсказанием. Поэтому я вполне уверен, что с имеющимися в настоящее время вычислительными ресурсами невозможно создать нейронную сеть для успешной атаки на PRNG, который считается безопасным для криптографии.

Стоит также отметить, что нет необходимости точно прогнозировать выход PRNG для взлома криптографии - может быть достаточно предсказать следующий бит с точностью чуть более 50%, чтобы значительно ослабить реализацию. Поэтому, если вы в состоянии построить нейронную сеть, которая предсказывает следующий бит PRNG (считающийся безопасным для криптографии) с вероятностью успеха 55%, вы, вероятно, довольно долго будете оставаться в заголовках новостей о безопасности.

Дементо
источник
2
Вау, спасибо за объяснение этого. Я пытаюсь проанализировать паттерн и предсказать следующий бит, и это не идеальный ГСЧ, а несколько надежный ГСЧ. Но это не современное состояние. Я думаю, что с небольшой вычислительной мощностью и правильной реализацией я мог бы прогнозировать ее на 60-70%, если не больше. Если возможно, можете ли вы указать любые ресурсы, где я могу прочитать больше об этом. Я не из исследовательской среды, а скорее из разработчика.
AshTyson
3

Будучи полным новичком в машинном обучении, я провел этот эксперимент (используя Scikit-learn):

  • Сгенерировал большое количество (N) псевдослучайных извлечений, используя функцию Python random.choices, чтобы выбрать N чисел из 90.

  • Обученный классификатор MLP с данными обучения, составленными следующим образом:

    • i-й пример: X <- lotteryResults [i: i + 100], Y <- lotteryResults [i]

    На практике я стремился к функции, которая задала N чисел, и предсказывала следующую.

  • Попросил обученного классификатора спрогнозировать оставшиеся цифры.

Результаты:

  • конечно, классификатор получил выигрышную оценку, сопоставимую с оценкой случайных догадок или других методов, не основанных на нейронных сетях (я сравнил результаты с несколькими классификаторами, доступными в библиотеках scikit-learn)

  • однако, если я сгенерирую псевдослучайные извлечения из лотереи с определенной функцией распределения, то числа, предсказанные нейронной сетью, будут примерно сгенерированы с одной и той же кривой распределения (если вы строите график случайных чисел и предсказаний нейронной сети, Вы можете видеть, что эти два имеют одинаковую тенденцию, даже если на кривой предикций есть много всплесков.Так что, возможно, нейронная сеть может узнать о распределении псевдослучайных чисел?

  • Если я уменьшу размер обучающего набора до определенного предела, я вижу, что классификатор начинает предсказывать всегда одни и те же несколько чисел, которые являются одними из самых частых в псевдослучайном поколении. Как ни странно (а может и нет) такое поведение, кажется, немного увеличивает выигрышный счет.

Франческо Боккио
источник
3

Старый вопрос, но я подумал, что стоит один практический ответ. Я случайно наткнулся на это сразу после того, как посмотрел руководство по созданию такой нейронной сети, продемонстрировав эхо randint Python в качестве примера . Вот окончательный код без подробного объяснения, все еще довольно простой и полезный в случае, если ссылка отключается:

from random import randint
from numpy import array
from numpy import argmax
from pandas import concat
from pandas import DataFrame
from keras.models import Sequential
from keras.layers import LSTM
from keras.layers import Dense

# generate a sequence of random numbers in [0, 99]
def generate_sequence(length=25):
    return [randint(0, 99) for _ in range(length)]

# one hot encode sequence
def one_hot_encode(sequence, n_unique=100):
    encoding = list()
    for value in sequence:
        vector = [0 for _ in range(n_unique)]
        vector[value] = 1
        encoding.append(vector)
    return array(encoding)

# decode a one hot encoded string
def one_hot_decode(encoded_seq):
    return [argmax(vector) for vector in encoded_seq]

# generate data for the lstm
def generate_data():
    # generate sequence
    sequence = generate_sequence()
    # one hot encode
    encoded = one_hot_encode(sequence)
    # create lag inputs
    df = DataFrame(encoded)
    df = concat([df.shift(4), df.shift(3), df.shift(2), df.shift(1), df], axis=1)
    # remove non-viable rows
    values = df.values
    values = values[5:,:]
    # convert to 3d for input
    X = values.reshape(len(values), 5, 100)
    # drop last value from y
    y = encoded[4:-1,:]
    return X, y

# define model
model = Sequential()
model.add(LSTM(50, batch_input_shape=(5, 5, 100), stateful=True))
model.add(Dense(100, activation='softmax'))
model.compile(loss='categorical_crossentropy', optimizer='adam', metrics=['acc'])
# fit model
for i in range(2000):
    X, y = generate_data()
    model.fit(X, y, epochs=1, batch_size=5, verbose=2, shuffle=False)
    model.reset_states()
# evaluate model on new data
X, y = generate_data()
yhat = model.predict(X, batch_size=5)
print('Expected:  %s' % one_hot_decode(y))
print('Predicted: %s' % one_hot_decode(yhat))

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

...
 - 0s - loss: 0.2545 - acc: 1.0000
Epoch 1/1
 - 0s - loss: 0.1845 - acc: 1.0000
Epoch 1/1
 - 0s - loss: 0.3113 - acc: 0.9500
Expected:  [14, 37, 0, 65, 30, 7, 11, 6, 16, 19, 68, 4, 25, 2, 79, 45, 95, 92, 32, 33]
Predicted: [14, 37, 0, 65, 30, 7, 11, 6, 16, 19, 68, 4, 25, 2, 95, 45, 95, 92, 32, 33]
ИСП-ZAX
источник
Это не учится предсказывать случайную последовательность - это учится отражать ее. Конкретно, обучающие выборки X состоят из 5 случайных целых чисел, а выходные данные y являются четвертыми целыми числами из 5. Например, если X = [15, 33, 44, 30, 3], y = 30. LSTM учится повторять 4-й образец.
Thinkski
Да, хорошая мысль. Я все еще нахожу это очень интересным практическим примером использования LSTM. Если вы знаете, как узнать что-то вроде Мерсенна Твистера из семян, приведенных только в качестве входных данных, пожалуйста, опубликуйте это здесь, так как мне было бы очень интересно это увидеть. Кажется возможным с достаточным количеством образцов, но я могу быть совершенно не прав.
ИСП-ZAX
2

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

Bobs
источник
1
Правда. Впрочем, философский. Ожидается что-то вроде технического ответа. В любом случае, спасибо :)
AshTyson
2

В добавление к тому, что сказал Дементо, степень случайности в алгоритме генерации случайных чисел является ключевым вопросом. Ниже приведены некоторые конструкции, которые могут сделать ГСЧ слабым:
Скрытые последовательности.
Предположим, что это несколько предыдущих сгенерированных последовательностей символов: (используется только пример, для практического использования больший диапазон)

lwjVJA
Ls3Ajg
xpKr+A
XleXYg
9hyCzA
jeFuNg
JaZZoA

Изначально вы не можете наблюдать какой-либо шаблон в поколениях, но изменив их на кодировку Base64, а затем на шестнадцатеричный код, мы получим следующее:

9708D524
2ECDC08E
C692ABF8
5E579762
F61C82CC
8DE16E36
25A659A0

Теперь, если мы вычтем каждое число из предыдущего, мы получим это:

FF97C4EB6A
97C4EB6A
FF97C4EB6A
97C4EB6A
FF97C4EB6A
FF97C4EB6A

Это указывает на то, что алгоритм просто добавляет 0x97C4EB6A к предыдущему значению, усекает результат до 32-разрядного числа и Base64 кодирует данные.
Выше приведен основной пример. Современные алгоритмы и системы ML достаточно способны изучать и предсказывать более сложные паттерны.

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

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

Ugnes
источник
Вы только что продемонстрировали мне концепцию между количеством и его связью, являющуюся методом определения модели, которую я знал, что я далек от своей интуиции :)
Бобс
Но все же напрашивается неразрывный вопрос о случайности, являющейся «продуктом», оторванным от рациональности, когда мы пытаемся описать его с помощью функции языка, который мы используем, который вытекает из смирения в сохранении эволюционного процесса и восприятия метода поддержания здравомыслия человека лол.
Боб
Является ли случайность или ее восприятие дизъюнкцией между реальностью и человеческим восприятием, и из-за ее непересекаемости только остаток чувственного восприятия решает картину каждого из нас, которую мы все наблюдаем, и складывается в общедоступную случайность из-за интеллектуального непересекаемости в людях, являющегося концентрированным фактором в концептуальном распределении.
Боб
Как вы можете когда-либо анализировать что-то без основания, чтобы начать свой анализ, если вы пытаетесь анализировать случайность, тогда, конечно, это основано на определенности эго-энтеросолюбильно
Бобс
Псевдослучайность - это свойство пластичных людей, маскирующихся под настоящие приземленные качества, к которым у них есть излишнее пренебрежение и нечестивая или человеческая озабоченность. Определение ведет к вере и определенности занятия и полезного общения о продукте хорошей жизни, не выдерживая проблем баланса трудностей.
Боб