Generating random sequences of bits

Go To StackoverFlow.com

0

I'm trying to generate a file containing absolutely random keys with a given length, Lets say 100bits and store them in a file. What's the best way to do it and which language offers the best libraries? Thanks in advance.

2012-04-04 22:49
by mjekov
Nothing on a computer is absolutely random. Only seemingly so - Charles Caldwell 2012-04-04 22:51
@PortableWorld: You are incorrect. It is perfectly possible to get computer-generated random bits of any level of entropy desired - Eric Lippert 2012-04-04 22:52
http://random.org - DNA 2012-04-04 22:54
No, he's correct. Computers are deterministic devices. You can possibly use peripherals like disk drives to generate entropy, but even that is rather suspect. True HRNGs are, of course, an exception - Perry 2012-04-04 22:54
@PortableWorld: They might not be absolutely random, but you can make them absolutely unpredictable, I've heard of some using their thermometers as a source of entropy, since they have those built-in now - Mooing Duck 2012-04-04 23:02
A down-voting spree? Did someone wanted his answer to be the only non-negative voted one - Alexander 2012-04-04 23:03
@MooingDuck No arguments there. However, it seems that there is some disagreement in the tech community on the issue. It would be an interesting topic to study and write a blog post on - Charles Caldwell 2012-04-04 23:10
@MooingDuck: I have no idea what the distinction between "random" and "unpredictable" may be, since randomness is generally defined formally in terms of predictability. Using external hardware is the same as invoking a hardware rng of a sort. No one uses thermometers for this purpose, FYI - Perry 2012-04-04 23:13
@Perry: I can't find anything that mentions thermometers, so maybe I was told wrong. I don't know official definitions, but I know that people are lousy for random numbers, and yet unpredictable, so in my head, the difference was the distribution - Mooing Duck 2012-04-04 23:20
@MooingDuck: this person is trying to generate cryptographic keys, a very touchy operation. It may not be safe to be giving them advice based on things you vaguely remember from past discussions - Perry 2012-04-04 23:21


13

Randomness comes in different levels of "strength"; you can get either truly random bits, or pseudo random bits. The truly random bits derive their entropy from real-world sources. The pseudo random bits produce a sequence of bits that appears random but is in fact predictable.

You should always use a randomness generator designated as having cryptography strength when generating keys. These random bit generators are carefully designed to be truly unpredictable. Never use weaker sources of randomness for generating keys.

In C# you can do so by creating an instance of the aptly named random number generator cryptographic service provider and then call GetBytes to obtain an array of random bytes of the desired length.

Needless to say: be very careful when generating your own crypto keys. Cryptography is all about leveraging the security of the key into the security of the message; if you are not very careful about how you generate, store and transmit keys, then the security system is compromised. Consider hiring an expert on cryptography if you are not one yourself rather than trying to roll your own crypto code.

I note also that depending on your application, 100 bits may be far too small a key size, or far too large. It may be too small in that your algorithm may be vulnerable to attack at a key size that small, and it may be too large in the sense that some countries restrict the usage or export of crypto software that has too high a bit count. Consider consulting a lawyer.

2012-04-04 22:56
by Eric Lippert


2

Depends on what you mean by absolutely random. If pseudo random number generators are acceptable then the C++ <random> library is a great option.

If you need stronger guarantees than that then you may still be able to use std::random_device from <random> which offers non-deterministic random numbers if your platform has that capability. It may even offer access to a cryptographic random number generator. You'll have to check your platform's documentation.

#include <random>
#include <iostream>

int main() {
    std::random_device r("/dev/random"); // Cryptographically secure RNG on Linux, OpenBSD, OSX, (using libc++)
    unsigned int completely_random_value = r();
    std::cout << completely_random_value << '\n';
}

One thing that may be relevant to you is this note from Microsoft's documentation about their implementation of random_device in VS11: "In this implementation the values produced by default are not non-deterministic." It's another unfortunate quality of implementation issue with Visual Studio's C++11 library (to go along with, at least, the low resolution of their chrono::high_resolution_clock)

2012-04-04 23:00
by bames53


-2

True random numbers cannot be generated by deterministic processes, so the choice of language is in some sense unimportant. Since you say "keys", you are probably looking for cryptographic keys, and generating these by deterministic processes is very dangerous indeed, and the cause of numerous system breaks.

I would rethink the entire thing -- and if you're generating cryptographic keys on your own, you absolutely should rethink the whole thing. Amateurs, no matter how skilled at programming, should not write cryptographic code. That's caused more system bugs than I can count.

2012-04-04 22:51
by Perry
It looks like someone went on a troll-spree through all the answers.. - Richard J. Ross III 2012-04-04 22:57
@Perry: Computers can't generate truely random numbers, but they can generate non-deterministic numbers - Mooing Duck 2012-04-04 23:04
By what means may you create "non-deterministic" numbers using purely deterministic hardware - Perry 2012-04-04 23:11
@Perry: You're trolling. Said deterministic hardware can take input from a non-deterministic source. Now give up - jason 2012-04-05 02:51
And what would this "non-deterministic source" be on the average computer? Stuff like Ted T'so's /dev/random is just barely on the respectable side of black magic. I'm not "trolling" -- I am a domain expert, and just about no one else here is. The number of times people get RNGs wrong is just astonishing -- for a good example in only the last few months, see http://eprint.iacr.org/2012/064.pdf -- None of you seem to understand what you're talking about, and yet, we've got people giving ridiculously bad advice to someone doing key generation - Perry 2012-04-05 03:29
Quoting John von Neumann: "Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin. - Perry 2012-04-05 03:36
@RichardJ.RossIII: I doubt it was a troll. This answer is likely downvoted as there are means of generating cryptographically secure random numbers (and yes, C# has functions to do so). Your answer was likely downvoted because you are using a means of generating random numbers that is not cryptographically secure - Brian 2012-04-05 13:18
@Perry: Quoting Ralph Waldo Emerson: "I hate quotations. Tell me what you know." By the way, the second half of Von Neumann's quote is "For, as has been pointed out several times, there is no such thing as a random number — there are only methods to produce random numbers, and a strict arithmetic procedure of course is not such a method." Clearly he is merely cautioning us to understand the distinction between random and pseudo-random. Leaving off the second half of this quote leads to a misunderstanding of the first half - jason 2012-04-05 13:19
@Perry "Stuff like Ted T'so's /dev/random ..." Are you saying that /dev/random isn't, or is just barely, a cryptographically secure rng? Are you saying this is true for all the implementations in use or just specific implementations - bames53 2012-04-05 20:56
I'm saying that Ted's /dev/random is, at best, a pretty reasonable hack. I trust it a bit, but not so much that I'm willing to assume there are no flaws, since testing an RNG for proper function is exceptionally difficult, and since the ability to measure the entropy of the putative hardware sources is damn hard. I can't speak to "all implementations" as I can't have possibly examined "all implementations" - Perry 2012-04-05 23:31
@Perry I'm trying to determine what your criticism applies to. The general approach? In which case it applies to Yarrow, Fortuna, CryptGenRandom and most other things that are not specialized hardware random number generators. But then your comment about the difficulty in testing also applies to hardware RNGs as well. I don't see any reason to assume those don't have flaws either - bames53 2012-04-09 03:22


-2

It's relatively easy in C/C++, assuming that you understand that there are no such things as random numbers, but merely pseudo-random numbers:

uint8_t *randomBytes(int length)
{
    uint8_t buffer = malloc(length);

    for (int i = 0; i < length; i++)
    {
        buffer[i] = arc4random_uniform(256); // or similar random function
    }

    return buffer; // don't forget to free buffer when done!
}

In Java, you would return a byte array, like this:

byte[] randomBytes(int length)
{
    Random rand = new Random();
    byte[] buffer = new byte[length];

    for (int i = 0; i < length; i++)
    { 
        buffer[i] = (byte) rand.nextInt(256);
    }

    return buffer;
}

In C#, it's mostly the same as Java, but with a few differences:

byte[] randomBytes(int length)
{
    Random rand = new Random();
    byte[] buffer = new byte[length];

    for (int i = 0; i < length; i++)
    { 
        buffer[i] = (byte) rand.Next(256);
    }

    return buffer;
}
2012-04-04 22:51
by Richard J. Ross III
Those are not even crypto strength PRNGs - CodesInChaos 2012-04-07 15:00
@CodeInChaos I answered long before cryptography was in the question, so please remove your down vote - Richard J. Ross III 2012-04-07 15:37
Ads