1 to 1 mapping from a range of numbers to the same range but seemingly randomly shuffled

Question

I need a function f(n) that takes any value n between 0 and 2^256 and returns a seemingly random other number from that range. Every output f(n) should be unique and it should be possible to find n if I know f(n). This shouldnt be hard to decipher or anything.

Answer 1

Encryption is a one-to-one mapping so one method would be to encrypt 256 bit numbers: 0, 1, 2, 3, ... 2^256 - 1. You might need to dig around to find a 256 bit cipher, the most common is probably 256 bit Rijndael. I think C# has an implementation.

Answer 2

You might consider using a full-cycle linear congruential generator (LCG). It turns out that finding the predecessor of a given value can be done using the LCG algorithm with a different set of coefficients, which can be pre-calculated as described here.

If you use a bigInteger library or a language which provides arbitrary-sized integers (such as python or ruby), there should be no problem covering your target range.

Answer 3

There are many ways to achieve this. For instance, you could do the following:

• Define a chunk size and map each chunk of bits to another chunk of bits, such that it is a bijection, i.e. reversible. If you would define your chunk size as 256 bits, then this comes down to creating a mapping for each possible 256 bit value. That would be great, but to reduce memory consumption you might prefer to choose a smaller chunk size, like ... 4 bits. So then you have a bijective function of 0..15 to 0..15

• Add the chunk sequence number (0..63) to the value that is mapped (modulo chunk range, i.e. 16) to increase the feeling of "randomness".

• Define a mapping of the bits in a chunk to other bit positions, again as a bijection. Here we could choose a simple mapping such that bits 0,1,2 and 3 (in the first chunk) map to bits 0, 64, 128, 182 (equidistant), and bits 4,5,6 and 7 (i.e. of the second chunk) map to bits 1, 65, 129, 183, ...etc.

All this is reversible, but it might still not look random enough. We could increase the effect by feeding the encoded number again in the algorithm, and repeat this a fixed number of times (like 20 times).

If the programming language of choice supports 256bit numbers or has BigInteger support, then all this can be done with bitwise arithmetic on single (big) unsigned integers.

For instance, JavaScript:

const forward  = 0x7be0c36f5249a18dn; // Bijection of nibble to nibble (0..15 <-> 0..15)
const backward = 0x8d0be341f975a62cn; // ...and back.
const recur = 20; // Number of times to repeat encode/decode algorithm.

function encodeOnce(decoded) {
    let encoded = 0n;
    for (let i = 0n; i < 64n; i++) {
        const nibble = (forward >> (((decoded + i) & 0xfn)*4n)) & 0xfn;
        decoded >>= 4n;
        encoded = (encoded << 1n) | (nibble & 1n) | ((nibble & 2n) << 63n) 
                                  | ((nibble & 4n) << 126n) | ((nibble & 8n) << 189n); 
    }
    return encoded;
}

function encode(n) {
    for (let i = 0; i < recur; i++) n = encodeOnce(n);
    return n;
}

function decodeOnce(encoded) {
    let decoded = 0n;
    for (let i = 63n; i >= 0n; i--) {
        const nibble = ((encoded >> 189n) & 8n) | ((encoded >> 126n) & 4n) 
                     | ((encoded >> 63n) & 2n) | (encoded & 1n);
        encoded >>= 1n;
        decoded = (decoded << 4n) | (((backward >> (nibble*4n)) - i) & 0xfn);
    }
    return decoded;
}

function decode(n) {
    for (let i = 0; i < recur; i++) n = decodeOnce(n);
    return n;
}

// Some results
for (let n = 0n; n < 30n; n++) {
    const encoded = encode(n);
    const decoded = decode(encoded);
    // decoded should be equal to n
    console.log(`encode(${n}) = 0x${encoded.toString(16)}, decoded again = ${decoded}`);
}

function getRandom256bit() {
    let n = 0n;
    for (let i = 0; i < 8; i++) {
        n = (n << 32n) | BigInt(Math.floor(Math.random() * 0x100000000));
    }
    return n;
}

// Perform 100 tests with random numbers (nothing should be printed)
for (let k = 0; k < 100; k++) {
    const n = getRandom256bit();
    const encoded = encode(n);
    if (decode(encoded) != n) throw `Mismatch for ${n.toString(16)}`;
}
console.log("Tests passed.");

It should be clear that this algorithm is not producing anything close to real randomness. It is not intended to encrypt or anything close. It just provides a non-obvious, but reversible mapping (bijection).