# Generating random non-repeating numbers from a small group

I read this Q&A which gave a clever solution: feed an incrementing index into a block key cipher as a way of producing non-repeating random numbers. The problem is the block size of all the good algorithms is often way too big. What if I just want to iterate through all 16-bit numbers, or all N-bit numbers where N is determined by the problem at hand? Nobody in their right mind would make a 16-bit block cipher, but that's what I would need.

One idea I had to iterate pseudo-randomly through all n-bit numbers was to use a binary field. Randomise the modulus polynomial, $Q$, ensuring it's irreducible. Then take a random starting point, $a$, and multiply repeatedly by a random primitive element, $r$, to generate the pseudorandom series.

$n_i = a r^i \pmod Q$

Something tells me this isn't good enough. Predicting the next elements can be interpreted as a discrete logarithm problem if $i$ is the plaintext which must be found from $n_i$. The discrete logarithm is difficult, but when $n_i$ are all given in order, can the problem of finding $r$ and $Q$ from the sequence still be interpreted as the discrete logarithm problem? Does the problem have a name? How hard is it?

If this method of iteration is no good, I had an idea to make it a lot harder: pad the index $i$ with some random bits before encryption, so if the index is a 16 bit number, encrypt it to 20 bits with four random bits. Would that be enough to ensure an unpredictable pattern? What method of iteration would ensure sufficient difficulty in finding a solution? One downside to this modification is that although the sequence generated is non-repeating, it doesn't cover the entire output domain. Is there a way to cover the entire output domain?

• Did you have a look at Format Preserving Encryption?
– SEJPM
Apr 18 '16 at 20:11
• Check out feistel networks, they are good for crafting arbitrary sized ciphers. Use a hash function as the round function (: Apr 19 '16 at 19:30
• @SEJPM No, I'll have to check it out. Apr 20 '16 at 15:58
• @AlanWolfe sounds like a good idea. You should add this as an answer. Apr 20 '16 at 15:59

If you are going to generate ALL the numbers in the output domain, an attacker's job of guessing the next number becomes easier the more numbers you use, once you pass the halfway point. I would suggest with whatever method you choose, to never exceed $N/2$ values used, where $N$ is the total number of elements that can be generated using that method, $N=2^{16}$ in your example.

I actually see no problem with using a finite field, but you would need to make it difficult for the attacker to guess the values used to generate it, even if the method was known.

My solution would be to use the same finite field inversion method as was used to generate the AES S-box, but in $GF(2^{16})$ with the APA method. It is a highly nonlinear sequence, and there are simply too many combinations of generator values and reduction polynomials to brute force every option like there are in $GF(2^{8})$.

Essentially, you perform an affine transformation on the input, then find the inverse in the field, and then perform the affine transformation again, with an irreducible polynomial chosen at random from the list of possible polynomials. There are specific combinations of affine generators and vectors within each finite field that generate high quality results useful for S-boxes, but you would not be constrained by the same conditions, giving you more flexibility. The mathematical description of the algorithm would be very simple.

The format preserving option easily allows you to build a Feistel cipher of whatever block size you want since your domain size is an even power of 2, in your case 16-bit, by using another block cipher or PRF as the F-function. You can drop in AES, use the 8-bit block half plus a round counter as an input, and truncate the output to 8-bits. This would be very easy to code and very quick to generate numbers, at the expense of a complex description of the final algorithm. You can also generate 128-bit subkeys in CTR mode, then use these as independent AES keys for each round, at the expense of additional computation.

• The number of primitive polynomials of degree 16 over $GF(2)$ is $\phi(2^16-1)/16=2048.$ Now, each primitive generator corresponds to one of these polynomials, so you can really range over only the generators or the polynomials but not both. The pre- and post- affine multiplications don't contribute any extra security as far as I can see, just a linear change of basis, effectively. I don't know enough about format-preserving encryption to comment, but that may well be the safer route. Apr 19 '16 at 1:55
• @kodlu the polynomial does not have to be primitive, just irreducible, and there are 4080 of those. When I was talking about generators, I was referring to the affine operation, which will not change the nonlinearity, but will change the output of the algorithm Apr 19 '16 at 2:30

Check out Swap or Not (pdf). Unlike some Feistel-network based solutions, this will provide you with near-ideal security (the adversary would have to query close to the entire space to have non-negligible advantage).

Alternatively, enumerating and shuffling a list of 2^16 16-bit numbers would require only ~128KB of RAM. If you needed to reproduce the ordering, use a key as PRNG seed.

• Sometimes-Recurse Shuffle "will provide you with" much-closer-to-ideal security. ​ ​
– user991
Apr 19 '16 at 8:11
• For only 16 bits, yeah you can just store a completely random permutation since 2*2**16 = 2**17 = 128KiB, but for bigger spaces like 32-bit this becomes impractical. I hadn't made it clear when I first wrote the question, but this is for N-bit integers. The region of 30 to 63 bits is big enough for storing the complete permutation to be usually impractical but small enough that there are no suitable standard block ciphers. Apr 20 '16 at 16:06

As SEJPM mentions, what you are doing is called "format preserving encryption" and there is a lot of information out there on that, in case you want to go deeper than the answers here give you.

The problem of creating a custom sized cipher is a difficult one, especially if you want to be sure it's crypto secure, but one nice way to approach the problem is to use Feistel Networks.

They work this way:

1. Break your data into a left and right half
2. put the right half of your data through some "round function"
3. Take that result and xor the left half by that value
4. The result of that xor is the right half of the output
5. The left half of the output is the unmodified right half from step 1

A feistel network does $N$ rounds of the above, where $N$ is tunable where in general higher values of $N$ means a slower more secure cipher, and smaller values of $N$ means a faster less secure cipher.

To decrypt something encrypted with a feistel network, it's a similar process but done in reverse, using the same number of rounds.

The other tunable portion of the feistel network is what you use for the round function.

The round function is just a function where you pass in data, and it does some operations, most likely based on the data passed in, to ideally output a cryptographically secure random number.

The round function is able to destructive operations even, which might be counter intuitive, since it's overall a reversible operation. Took me a while to think through how that is possible personally.

If you have lower quality and security needs, your round function could be something like a pseudo random number generator (like those you might find in games), where you use the input of the function as the seed for the PRNG.

If you have higher quality and security needs, you could use a hash function as the round function. Note there are both cryptographic and non cryptographic hash functions, so you'd have to make a call there, again based on your needs.

The only other challenge remaining is that if your input set is not a full power of 2, your are not going to be able to get a perfectly sized cipher.

The way to handle this is to round up to the next power of 2 (you might have to round up to the next power of 4 actually, if you want your left and right side of your data to be the same size), and iterate through that full possible range of values.

You will get some output values which are "out of range" (larger than your input set), and for these you just throw them out.

For some deeper details and some simple working C++ code without external dependencies, check out my blog post on the subject: Fast & Lightweight Random “Shuffle” Functionality – FIXED!