Generate pseudo-random integer from another pseudo-random integer and a key

Question

Suppose that there's a given function R() that generates pseudo-random integers in range [0, 999] (which I don't have control of its internals, e.g. its seed):

r1 = R()  # r1 = 671
r2 = R()  # r2 = 983
r3 = R()  # r3 = 023
...

I want to find a mapping function M(r, key) which takes the output from R() and a my own provided fixed key, and then generates another pseudorandom integer in range [0, 999].

The requirement is that for a given key and a fixed integer r, M(r, key) is deterministic. But it should have pseudorandom characteristics, that is, uniform distribution, being hard-to-guess from r (seemingly random), etc. And whenever I change the key, a whole different pseudorandom integers in range [0, 999] are returned.

The format of key is optional; it can be string, an integer in [0, 1000), or whatever I choose.

Note that the output need NOT to be cryptographically secure. But it should be reasonably uniform pseudorandom for a scientific simulation. The later is not very strict though.

I'm thinking of using HMAC_SHA1(key: my_key, message: r). But I don't know how to convert the result to an integer in [0, 1000) such that it satisfies the mentioned requirements.

What do you propose?

Answer 1

A simple way to reduce the 160 bit output of the SHA-1 HMAC uniformly to the range [0, 999] is to take the 10 least significant bits of the SHA digest and if that number is outside the range [0, 999] simply feed it back into the HMAC, repeating if necessary until you get a number in range. Here's some pseudocode of the algorithm.

function randmap(key, r)
{
    do {
        r = hmac(key, r);
        # Get 10 least significant bits, so the result is in [0, 1023]
        r = r & 0x3ff;
    } while (r >= 1000);
    return r;
}

If you don't like the idea of throwing away 150 bits of the SHA digest, another option is to use XOR-folding: break the digest into 16 10-bit blocks and XOR them together. But that's probably overkill for this non-cryptographic application.

---

If you want M(r, key) to map each $r$ in [0, 999] to a unique $q$ in [0, 999], the simplest way is to create a permutation of [0, 999] and use $r$ to index into that list. Here's some simple Python 3 code that does that. I've set the size parameter to 20 rather than 1000 to keep the test output manageable, but this code is suitable for list sizes up into the millions.

#!/usr/bin/env python3
from random import seed, shuffle

def build_mapper(key, size):
    seed(key)
    mapper = list(range(size))
    shuffle(mapper)
    return mapper

# Test

size = 20
mapper = build_mapper('test', size)
for i in range(size):
    print(i, mapper[i])    

output

0 11
1 0
2 16
3 17
4 18
5 13
6 14
7 10
8 4
9 9
10 5
11 19
12 3
13 2
14 15
15 12
16 1
17 6
18 7
19 8

Note that the Python random.seed function accepts any hashable object as its parameter, so you can feed it an integer or a string.

If you need to work with a much larger list size there are methods to create a permutation mapping that don't require a list in RAM. Such techniques are used in Format-preserving encryption. For example, you could use a Feistel network with a simple "round function".