神经网络可以用来预测下一个伪随机数吗?

人工智能 神经网络 机器学习 深度学习 预言 随机性
2021-11-11 19:50:09

是否可以将随机数生成器的输出提供给神经网络并期望它学习散列(或生成器)函数,以便它可以预测下一个生成的伪随机数是什么?

这样的东西已经存在了吗?如果已经对此或相关的研究(与预测伪随机数)进行了研究,谁能指出我正确的资源?

目前,我正在查看这个库及其相关链接。 https://github.com/Vict0rSch/deep_learning/tree/master/keras/recurrent

4个回答

如果我们谈论的是一个完美的 RNG,答案是肯定预测一个真正的随机数是不可能的,否则它就不是真正的随机数。

当我们谈论伪 RNG 时,情况会发生一些变化。根据 PRNG 的质量,问题的范围从容易到几乎不可能。一个非常弱的 PRNG,比如XKCD发布的那个,当然可以很容易地通过一个几乎没有训练的神经网络来预测。但在现实世界中,事情看起来不同。

可以训练神经网络在 PRNG 生成的随机数历史中找到某些模式,以预测下一位。PRNG 越强,需要的输入神经元就越多,假设您为 PRNG 生成的每一位先验随机性使用一个神经元。PRNG 的可预测性越低,找到某种模式所需的数据就越多。对于强大的 PRNG,这是不可行的。

积极的一面是,假设您可以控制 PRNG 并且可以生成任意数量的随机数,那么您可以为神经网络生成任意数量的训练模式是有帮助的。

由于现代 PRNG 是密码学的关键组成部分,因此已经进行了广泛的研究以验证它们“足够随机”以承受此类预测攻击。因此,我很确定,使用当前可用的计算资源来构建神经网络来成功攻击被认为对密码学安全的 PRNG 是不可能的。

还值得注意的是,没有必要准确预测 PRNG 的输出来破解密码学 - 以略高于 50% 的确定性预测下一位可能足以显着削弱实现。因此,如果您能够构建一个神经网络,以 55% 的成功率预测 PRNG(被认为对密码学来说是安全的)的下一位,您可能会成为安全新闻的头条新闻很长一段时间。

老问题,但我认为值得一个实际的答案。在查看如何构建这种神经网络的指南后,我碰巧偶然发现了它,以 python randint 的回声为例这是最终代码,没有详细解释,在链接离线的情况下仍然非常简单和有用:

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]

作为机器学习的新手,我做了这个实验(使用 Scikit-learn ):

  • 生成大量(N)个伪随机提取,使用 python random.choices 函数从 90 个中选择 N 个。

  • 训练了一个 MLP 分类器,训练数据组成如下:

    • 第 i 个样本:X <- lotteryResults[i:i+100], Y <- lotteryResults[i]

    在实践中,我的目标是一个给定 N 个数字的函数,可以预测下一个数字。

  • 要求训练有素的分类器预测剩余的数字。

结果:

  • 当然,分类器获得了与随机猜测或其他不基于神经网络的技术相当的获胜分数(我将结果与 scikit-learn 库中可用的几个分类器进行了比较)

  • 但是,如果我生成具有特定分布函数的伪随机彩票提取,则神经网络预测的数字大致生成具有相同的分布曲线(如果您绘制随机数和神经网络预测的出现,你可以看到两者具有相同的趋势,即使在预测曲线中有很多尖峰。所以也许神经网络能够学习伪随机数分布?

  • 如果我将训练集的大小减小到某个限制以下,我会看到分类器开始总是预测相同的少数数字,这些数字在伪随机生成中是最常见的。奇怪的是(或者可能不是)这种行为似乎略微增加了获胜分数。

除了 Demento 所说,随机数生成算法中的随机性程度是关键问题。下面是一些可以让RNG变弱的
设计

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 编码。
以上是一个基本的例子。今天的机器学习算法和系统足以学习和预测更复杂的模式。

时间依赖性
一些 RNG 算法使用时间作为生成随机数的主要输入,尤其是那些由开发人员自己创建并在其应用程序中使用的随机数。

每当实现看似随机的弱 RNG 算法时,如果有足够的数据集可用,它们可以以完美的准确度向前或向后推断。