How to create a random char string of size 64k w/o using rand() or /dev/random in C?

Question

I am searching for way to create a somewhat random string of 64k size.
But I want this to be fast as well. I have tried the following ways:

a) read from /dev/random -- This is too slow
b) call rand() or a similar function of my own -- a soln with few(<10) calls should be ok.
c) malloc() -- On my Linux, the memory region is all zeroes always,
instead of some random data.
d) Get some randomness from stack variable addresses/ timestamp etc. to init initial few bytes.
Followed by copying over these values to the remaining array in different variations.

Would like to know if there is a better way to approach this.

Take at look at this question http://stackoverflow.com/questions/1640258/need-a-fast-random-generator-for-c. It would work for c as well. — Dervall, Feb 07 '12 at 07:13

score 1 · Accepted Answer · answered Feb 07 '12 at 07:13

1

/dev/random blocks after its pool of random data has been emptied until it gathered new random data. You should try /dev/urandom instead.

answered Feb 07 '12 at 07:13

flyx

35,506
7
89
126

score 1 · Answer 2 · answered Feb 07 '12 at 07:16

rand() should be fairly fast in your c runtime implementation. If you can relax your "random" requirement a bit (accepting lower quality random numbers), you can generate a sequence of numbers using a tailored implementaton of a linear congruential generator. Be sure to choose your parameters wisely (see the wikipedia entry) to allow additional optimizations.

To generate such a long set of random numbers faster, you could use SSE/AVX and generate four/eight 32 random bits in parallel.

Alex Reynolds · Answer 3 · 2012-02-07T08:13:39.473

Perhaps calling OpenSSL routines, something like the programmatic equivalent of:

openssl rand NUM_BYTES | head -c NUM_BYTES > /dev/null

which should run faster than /dev/random and /dev/urandom.

Here's some test code:

/* randombytes.c */

#include <stdlib.h>
#include <stdio.h>
#include <openssl/rand.h>

/*                                                                                                                                                                                                                                            
   compile with:
        gcc -Wall -lcrypto randombytes.c -o randombytes
*/

int main (int argc, char **argv)
{
    unsigned char *random_bytes = NULL;
    int length = 0;

    if (argc == 2)
        length = atoi(argv[1]);
    else {
        fprintf(stderr, "usage: randombytes number_of_bytes\n");
        return EXIT_FAILURE;
    }

    random_bytes = malloc((size_t)length + 1);
    if (! random_bytes) {
        fprintf(stderr, "could not allocate space for random_bytes...\n");
        return EXIT_FAILURE;
    }

    if (! RAND_bytes(random_bytes, length)) {
        fprintf(stderr, "could not get random bytes...\n");
        return EXIT_FAILURE;
    }

    *(random_bytes + length) = '\0';
    fprintf(stdout, "bytes: %s\n", random_bytes);
    free(random_bytes);

    return EXIT_SUCCESS;
}

Here's how it performs on a Mac OS X 10.7.3 system (1.7 GHz i5, 4 GB), relative to /dev/urandom and OpenSSL's openssl binary:

$ time ./randombytes 100000000 > /dev/null
real    0m6.902s
user    0m6.842s
sys     0m0.059s

$ time cat /dev/urandom | head -c 100000000 > /dev/null    
real    0m9.391s
user    0m0.050s
sys     0m9.326s

$ time openssl rand 100000000 | head -c 100000000 > /dev/null
real    0m7.060s
user    0m7.050s
sys     0m0.118s

The randombytes binary is 27% faster than reading bytes from /dev/urandom and about 2% faster than openssl rand.

You could profile other approaches in a similar fashion.

score 1 · Answer 4 · answered Feb 07 '12 at 07:28

You say "somewhat random" so I assume you do not need high quality random numbers.

You should probably use a "linear congruential generator" (LGC). See wikipedia for details:

http://en.wikipedia.org/wiki/Linear_congruential_generator

That will require one addition, one multiplication and one mod function per element.

Your options: a) /dev/random is not intended to be called frequently. See "man 4 random" for details. b) rand etc. are like the LGC above but some use a more sophisticated algorithm that gives better random numbers at a higher computational cost. See "man 3 random" and "man 3 rand" for details. c) The OS deliberately zeros the memory for security reasons. It stops leakage of data from other processes. Google "demand zero paging" for details. d) Not a good idea. Use /dev/random or /dev/urandom once, that's what they're for.

score 0 · Answer 5 · answered Feb 07 '12 at 07:56

0

Don't over think it. dd if=/dev/urandom bs=64k count=1 > random-bytes.bin.

answered Feb 07 '12 at 07:56

jmkeyes

3,751
17
20

This is trivial to implement in C. If `/dev/urandom` isn't fast enough, you're doing something really, really wrong. – jmkeyes Feb 07 '12 at 07:58

How to create a random char string of size 64k w/o using rand() or /dev/random in C?

5 Answers5