Creating a randomly sorted array of all 255 bytes

[white scorpion]

Well as the title already says,
i'm trying to find a good way to create an array of all 255 different bytes which are sorted randomly.
I want to use this in an encryption program i am working on, but i'm stuck on this part.

Creating the array is easy, generating something subrandomly is fairly easy, but actually sorting something randomly is something that gives me a headache.

Any pointers are appreciated!

[Ossa]

Ok... not in asm (i'll put it in C as its quite quick for me to type), but the first thing that strikes me is to do this:

Code Select Expand


int i,j,k,c;
bool a[256];
int b[256];

for(i=0;i<256;i++) a[i] = false;

for(i=256;i>0;i--) {
if(i==1) c = 1;
else c = rand(1,i);
for(j=0,k=0;k<c;j++) {
if(!a[j]) k++;
}
b[i-1] = --j;
a[j] = true;
}


where rand(min,max) pick a random integer between min and max (inclusive)... at the end, b will contain the numbers 0 to 255 sorted randomly

This is not in any way fast, but if speed is not an issue, it will get the job done (faster but more complicated ways are already coming to mind).

Ossa

[P1]

If I were coding that, generate a random byte, then generate a random position, if populated, generate another random position.  Then check for population completion. 

The random positioning will give you a random sort.

Regards,  P1  :8)

[hutch--]

Here is a technique that comes to mind from playing cards. Create the 256 member array and load it from 0 to 255 like normal.

Then start at each location from zero up, generate a random number between 0 and 255 and swap that as an index with the current byte.

[Ossa]

If I were coding that, generate a random byte, then generate a random position, if populated, generate another random position. Then check for population completion.

Just note that (if i've got what P1 is saying straight here) that this can be very slow (it will differ in computation time for each run)... consider the last number - only 1 "space" will be "free" and random numbers must be generated until it chooses this value - this algorithm is actually not certain to terminate in a finite time (but it is infinitely close in probability that it will i.e. there is a 0.9999999... chance that this will terminate... so it will - confusing, eh?)

hutch's method seems the best to me - has complexity O(N), mine has O(N ln N).

Ossa

[white scorpion]

This is not in any way fast, but if speed is not an issue, it will get the job done (faster but more complicated ways are already coming to mind).

Speed isn't really an issue. Once it has been created then speed becomes an issue with using it, but that's a whole different story.

If I were coding that, generate a random byte, then generate a random position, if populated, generate another random position.  Then check for population completion.

The random positioning will give you a random sort.

In english please  :bg
I really had to read your answer 4 times before i understood what you meant. A very good solution, but it might take a while before generating every number between 0 & 255 at random i think.

Here is a technique that comes to mind from playing cards. Create the 256 member array and load it from 0 to 255 like normal.

Then start at each location from zero up, generate a random number between 0 and 255 and swap that as an index with the current byte.

Pff, i see i was thinking way too difficult. This would be a perfect solution  :clap:

- when do i stop swapping? I would say a random number of times between 500 - 1000
- what can i use best to generate random numbers between 0 & 255?
Random() in C & GetTickCount() aren't really random, not even a combination of the 2.
And the strength of the program will partialy lie in the randomness of the array.

[P1]

I really had to read your answer 4 times before i understood what you meant. A very good solution, but it might take a while before generating every number between 0 & 255 at random i think.

I understood a need for uniqueness.  Taking a little longer will yield a better quality of number sets.

If ultra speed is all you desire, read something random from the hard drive.  With some luck, maybe you would hit a clear text password.   :dazzled:

Regards,  P1  :8)

[Ossa]

P1, the method I pointed out will produce results of equal randomness (as every possible sequence has an equal probability of occurring), but guarantees algorithm completion in finite time. (In words, my algorithm picks a random number, c, less than the number of remaining elements and then assigns the next element of the array to be the cth unused number)

Hutch's method will asymptotically approach the same randomness as the number of swaps tends to infinity.

As for random number generators... you want a uniform random number generator. The thing is that no algorithm provides completely random numbers, so you have to rely on pseudo-random number generators... a good review of them is in the Handbook of Applied Cryptography (chapter 5) that you can download the PDF of here: http://www.cacr.math.uwaterloo.ca/hac/.

Ossa

[Roger]

Hi All,

Hutch's method will asymptotically approach the same randomness as the number of swaps tends to infinity.

Why does Hutch's method need to approach infinire time? Setting the original array ensures all 0 - 255 numbers are present and after 256 swaps every one will have been changed for a randomly selected alternative. By this time there is a high probability that most will have been changed twice.

Regards Roger

[Ossa]

Why does Hutch's method need to approach infinire time? Setting the original array ensures all 0 - 255 numbers are present and after 256 swaps every one will have been changed for a randomly selected alternative. By this time there is a high probability that most will have been changed twice.

Seems I misread hutch's method... I seem to have gotten it into my head that at each swap, the current number HAD to be swapped with another and that there was no chance for it to remain the same. Just re-read it and, yes, by the time all 256 potential swaps have occurred, every combination is just as likely.

Sorry about that - thanks for setting me straight there, Roger.

Ossa

[white scorpion]

As for random number generators... you want a uniform random number generator. The thing is that no algorithm provides completely random numbers, so you have to rely on pseudo-random number generators... a good review of them is in the Handbook of Applied Cryptography (chapter 5) that you can download the PDF of here: http://www.cacr.math.uwaterloo.ca/hac/.

I agree there is no true randomness, but i would like it be as good as i can.

If i'm not mistaken there is a random function in masm as well, but i forgot the name  :(
Can someone tell me what it is?

Tx

[Ossa]

If i'm not mistaken there is a random function in masm as well, but i forgot the name  :(
Can someone tell me what it is?

I can't say that I know of one... but I doubt it would be sufficiently random for you needs - you want something cryptographically secure I assume. There are several described in the link above (albeit rather mathematically)... I thought there was a Blum-Blum-Shub implementation floating about on one of the forums somewhere, but I can't seem to find it.

Ossa

[white scorpion]

Well, yeah i want something crytographically secure, but with pseudo randomness it should also be secure.
I've read the book and i know how one would make something more random, but i don't have the technical knowledge for it to do so.

[hutch--]

The "nrandom" algo in the masm32 lib is a reasobale performer for a pure integer pseudo random generator. A couple of our members fixed it a while ago and tested it with ENT.

If you ned cryptographic quality random sequences, you will need far better than pseudo random generators on computers, you generally need real world sampling which you can then use as seeding for computer algos.

[white scorpion]

If you ned cryptographic quality random sequences, you will need far better than pseudo random generators on computers, you generally need real world sampling which you can then use as seeding for computer algos.

I agree, but i think i can manage without that by using a table and a password.
This way the table can be choosen, let's say with a specific contact, and then the password can be used to select locations in the table that are impossible to find out without the correct table. (at least that's the theory  :bg)

nrandom, i believe that was what i was searching for.