如何根据字节数组生成随机数？

Question

假设我有一个来自安全 PRNG 的字节数组，我需要使用该数据生成一个 1 到 10 之间的数字，我该如何正确地做到这一点？

Answer 1

根据后续的评论，看来你需要的是modulus operator [%].

您可能还需要查看相关的wiki。

注意：每次我们对随机数使用模运算符时，我们都有可能运行变成 modulo bias，这最终会破坏随机数的公平分布数字。你必须照顾好它。

有关此的详细讨论，请参阅此question和相关答案。

Answer 2

这取决于很多事情。 Secure PRNG 有时会生成长字节数组而不是整数，假设它是 16 字节长的数组，然后像这样提取 32 位整数：buf[0]*0x1000000+buf[1]*0x10000+buf[2]*0x100+buf[3] 或使用移位运算符。这是随机的，所以 big-endian/little-endian 无关紧要。

char randbytes[16];
//...

const char *p = randbytes;

//assumes size of int is 4
unsigned int rand1 = p[0] << 24 + p[1] << 16 + p[2] << 8 + p[3]; p += 4;
unsigned int rand2 = p[0] << 24 + p[1] << 16 + p[2] << 8 + p[3]; p += 4;
unsigned int rand3 = p[0] << 24 + p[1] << 16 + p[2] << 8 + p[3]; p += 4;
unsigned int rand4 = p[0] << 24 + p[1] << 16 + p[2] << 8 + p[3];

然后对整数

使用%

ps，我认为这是一个很长的答案。如果你想要 1 到 10 之间的数字，那么只需在第一个字节上使用 %。

Answer 3

好的，所以这个答案在 Java 中，直到我进入我的 Eclipse C/C++ IDE:

public final static int simpleBound(Random rbg, int n) {

    final int BYTE_VALUES = 256;

    // sanity check, only return positive numbers
    if (n <= 0) {
        throw new IllegalArgumentException("Oops");
    }

    // sanity check: choice of value 0 or 0...
    if (n == 1) {
        return 0;
    }

    // sanity check: does not fit in byte
    if (n > BYTE_VALUES) {
        throw new IllegalArgumentException("Oops");
    }

    // optimization for n = 2^y
    if (Integer.bitCount(n) == 1) {
        final int mask = n - 1;
        return retrieveRandomByte(rbg) & mask;
    }

    // you can skip to this if you are sure n = 10

    // z is upper bound, and contains floor(z / n) blocks of n values
    final int z = (BYTE_VALUES / n) * n;
    int x;
    do {
        x = retrieveRandomByte(rbg);
    } while (x >= z);
    return x % n;
}

所以n是[0..n)范围内的最大值，即n是唯一的。对于范围 [1..10] 只需将结果增加 1.

Answer 4

将数组想象成一个大的无符号整数。那么答案就简单了：

(Big_Number % 10) + 1

因此，所需要的只是找到大整数的模数 10 的方法。使用 modular exponentiation:

#include <limits.h>
#include <stdlib.h>

int ArrayMod10(const unsigned char *a, size_t n) {
  int mod10 = 0;
  int base = (UCHAR_MAX + 1) % 10;
  for (size_t i = n; i-- > 0;  ) {
    mod10 = (base*mod10 + a[i]) % 10;
    base = (base * base) % 10;
  }
  return mod10;
}

void test10(size_t n) {
  unsigned char a[n];

  // fill array with your secure PRNG
  for (size_t i = 0; i<n; i++) a[i] = rand();

  return ArrayMod10(a, n) + 1;
}

由于 256^n 不是 10 的幂，因此会有轻微的偏差。对于大 n，这将迅速降低重要性。

未经测试的代码：检测是否出现有偏差的结果。调用代码可以使用新的 a 数组值重复调用此函数，以便在出现偏差的极少数情况下获得无偏差的结果。

int ArrayMod10BiasDetect(const unsigned char *a, size_t n, bool *biasptr) {
  bool bias = true;
  int mod10 = 0;
  int base = (UCHAR_MAX + 1) % 10;  // Note base is usually 6: 256%10, 65536%10, etc.
  for (size_t i = n; i-- > 0;  ) {
    mod10 = (base*mod10 + a[i]) % 10;
    if (n > 0) {
      if (a[i] < UCHAR_MAX) bias = false;
    } else {
      if (a[i] < UCHAR_MAX + 1 - base) bias = false;
    }
    base = (base * base) % 10;
  }
  *biaseptr = bias;
  return mod10;
}

如何根据字节数组生成随机数？

How to generate a random number based on a byte array?

c

random

cryptography

prng