使用 Blum Blum Shub 算法的伪随机数生成器

Question

我们需要在伪随机数生成器中实现 Blum Blum Shub 算法。我尝试在 C# 中搜索实现来获得一个想法，但没有成功。我们需要实现的一些方法不够清晰（或者也许我没有完全理解他们的要求）。

任何人都可以提供一些有关代码或类似方式的示例的帮助吗？我很难从文本中掌握概念。任何帮助都将被极大地接受！

首先，我尝试遵循问题的逻辑。由于进展甚微，我开始在线搜索更好的解释，并可能找到更好理解的实现。最后，我尝试用我认为有意义的内容来填写一些要求的方法。

static long seed = 6367859;
static long p = 3263849;
static long q = 1302498943;
static long m = p*q;

// Generates a random bit i.e. 0 or 1 using the Blum Blum Shub Algorithm and the Least Significant Bit
private byte generateRandomBit(){ }

// Method to generate a single positive 32 bit random number using the Blum Blum Shub Algorithm.
// The generateRandomBit() method is used to generate the random bits that make up the random number
// Not complete!!
public int GenerateNextRandomNumber()
{
    int nextRandomNumber = (int)((p * seed + q) % m);

    seed = nextRandomNumber;

    return nextRandomNumber;
}

// Generates a random number between min and max.
// The GenerateNextRandomNumber() method must be used to generate the initial random number which must then be manipulated (if necessary) to be between min and max
public int GenerateNextRandomNumber(int min, int max){ }

// Uses the GenerateNextRandomNumber Method to generate a sequence of Random Numbers between the minimum and the maximum value using the Blum Blum Shub Algorithm
public int[] GenerateRadmonSequence(int n, int min, int max)
{
    int[] sequence = new int[n];

    for (int i = 0; i < n; i++)
    {
        int randNum = Math.Abs(GenerateNextRandomNumber());

        randNum = min + randNum % (max + 1 +- min);
        sequence[i] = randNum;
    }

    return sequence;
}

结果应该是生成一个从 min 到 max 的数字序列。

Answer 1

不，这种类型的 RNG 不能使用 long：它几乎需要任意精度的数学运算。您实现的实际上看起来像 Linear Congruential Generator 算法，而不是 Blum Blum Shub 算法。

以下代码可帮助您使用 .NET Core 2.2 和 Win10 x64。使用 BigInteger、我认为正确的算法以及奇偶校验来获取下一个随机位。您也可以使用最低有效位作为随机位。

using System;
using System.Numerics;

namespace BlumBlumSnub
{
    class Program
    {
        public static readonly BigInteger p = 3263849;
        public static readonly BigInteger q = 1302498943;
        public static readonly BigInteger m = p*q;

        public static BigInteger next(BigInteger prev) {
            return (prev*prev) % m;
        }

        public static int parity(BigInteger n) {
            BigInteger q = n;
            BigInteger count = 0;
            while (q != BigInteger.Zero) {
                count += q & BigInteger.One;
                q >>= 1;
            }
            return ((count & BigInteger.One) != BigInteger.Zero) ? 1 : 0; // even parity
        }

        public static int LSB(BigInteger n) {
            return ((n & BigInteger.One) != BigInteger.Zero) ? 1 : 0;
        }

        static void Main(string[] args)
        {
            BigInteger seed = 6367859;

            BigInteger xprev = seed;
            for(int k = 0; k != 100; ++k) {
                BigInteger xnext = next(xprev);
                int bit = parity(xnext); // extract random bit from generated BBS number using parity,
                // or just int bit = LSB(xnext);
                Console.WriteLine($"Bit = {bit}");
                xprev = xnext;
            }
        }
    }
}

Answer 2

这个实现怎么样：

public class BlumBlumShub
{
    private readonly ulong m;
    private ulong x;

    public BlumBlumShub(int m, int seed)
    {
        this.m = (ulong) m;
        x = (ulong)seed;
    }

    public int Next()
    {
        x = (x * x) % m;
        return (int)x;
    }
}

参考

---

编辑：如果您确实需要很大的数量，您可以轻松调整：

public class BlumBlumShub
{
    private readonly BigInteger m;
    private BigInteger x;

    public BlumBlumShub(BigInteger m, BigInteger seed)
    {
        this.m = m;
        x = seed;
    }

    public BigInteger Next()
    {
        x = (x * x) % m;
        return x;
    }
}

Answer 3

注释。我发现信息表明，神经网络可以找到 Blum-Blum-Shub 算法中的漏洞，并且它不再被认为是抗加密的。有趣的是，PRNG 可以基于神经网络构建。在这种情况下，你甚至可以不使用神经网络训练。如果使用训练，计算伪随机数的算法会变得非常复杂且非线性。但如果动态改变神经元连接的数量和方向、层数和神经元数量，那就更有趣了。这样的生成器会很慢，但其结果的可预测性将是密码分析的一个大问题。