CODEWITHSUNDEEP
crandomcryptographyprng
Maestro
Maestro

Reputation: 9508

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

Suppose I have an array of bytes from a secure PRNG, and I need to generate a number between 1 and 10 using that data, how would I do that correctly?

Upvotes: 1

Views: 1923

Answers (4)

chux
chux

Reputation: 153367

Think of the array as one big unsigned integer. Then the answer is simple:

(Big_Number % 10) + 1

So all that is needed is a method to find the modulus 10 of big integers. Using 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;
}

There will be a slight bias as 256^n is not a power of 10. With large n, this will rapidly decrease in significance.

Untested code: Detect if a biased result occurred. Calling code could repeatedly call this function with new a array values to get an unbiased result on the rare occasions when bias occurs.

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;
}

Upvotes: 1

Maarten Bodewes
Maarten Bodewes

Reputation: 93968

OK, so this answer is in Java until I get to my 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;
}

So n is the maximum value in a range [0..n), i.e. n is exclusive. For a range [1..10] simply increase the result with 1.

Upvotes: 0

Barmak Shemirani
Barmak Shemirani

Reputation: 31599

It depends on a bunch of things. Secure PRNG sometimes makes long byte arrays instead of integers, let's say it is 16 bytes long array, then extract 32 bit integer like so: buf[0]*0x1000000+buf[1]*0x10000+buf[2]*0x100+buf[3] or use shift operator. This is random so big-endian/little-endian doesn't matter. 

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];

Then use % on the integer

ps, I think that's a long answer. If you want number between 1 and 10 then just use % on first byte.

Upvotes: 0

Sourav Ghosh
Sourav Ghosh

Reputation: 134316

As per the comments follow-up, it seems what you need is modulus operator [%].

You may also need to check the related wiki.

Note: Every time we use the modulo operator on a random number, there is a probability that we'll be running into modulo bias, which ends up in disbalancing the fair distribution of random numbers. You've to take care of that.

For a detailed discussion on this, please see this question and related answers.

Upvotes: 1

Related Questions