Reversible "hash" function from 64-bit integer to 64-bit integer

Question

What I need is a reversible function that transforms a long (64-bit integer) into another long number, in a way that seems "random" for a user (but actually is deterministic), so that 3 subsequent numbers are transformed into 3 numbers completely different to each other.

It is easy to do it without being reversible, but it turns out pretty difficult when it comes to this part.

Basically it's the same question as Reversible hash function?, but I need more than 2^32 distinct values.

Any ideas?

PS: I'm going to write it in Java, but the question itself is pretty generic.

Aurea

Yes. Just do what they did for the other question, but do it for 64 bits instead of 32 bits. – Disaffection

A hash/checksum is a one-way street. They're designed to be irreversible. You're looking for a cipher. – Cabinetwork

Answer 1

These are the basic requirements for a block cipher, which is usually implemented with a Feistel structure: https://en.wikipedia.org/wiki/Feistel_cipher

1. Create a hash of the lower 32 bits and XOR it into the upper 32 bits
2. Swap the lower and upper 32 bits
3. Repeat a few times.

Sheehan

Answer 2

You can use any 64-bit block cipher (for example, DES), and use encrypt for a "hash", and decrypt for an "reverse hash".

Tricky

Answer 3

This is a really old question, but a common solution to hide sequential ids from urls is XTEA

For example, you have an old system that wants an ID that were generated sequentially, then it's easy to guess the nearby values. (e.g. If I see userid=511 in the url, then there's probably a userid=510 in the system).

XTEA will take numbers and turn them into what looks like random values. Except these random values can be turned the back into their original values on the server.

Lek

Answer 4

If security is not your concern and you just need to visually randomize the numbers, a really fast solution is using a simple XOR with a fixed key in your code. To get it back, just XOR again with this 'secret' key.

If you are interested in security, but you have no space limitations, you may use bigger keys (eg a sliding XOR) or even an OTP. Here is a Java example of OTP.

I should also highlight the following two cases where already proposed solutions using certain symmetric encryption algorithms (even the simple XOR or OTP) may not work as expected.

1. If we need to maintain the sign of the number
2. If we need to maintain the size of the number (eg I have a 5digit number and I want to show its reversible-randomized 5 digit version (or at least close to its size (4-6))

To support the above requirements, a policy-based modified XOR/OTP, that applies only on the required bits, can be a good candidate.

Ricercar

it is not "random" at all, if there are some binary relations between input numbers. – Appreciable

Yes I totally agree, you can apply a more complex strategy to increase randomness, but the level of randomness depends on what the OP wants to achieve. I am pointing out that it's just visually random, not bitwise; otherwise the answer is obvious, you need a secure encryption algorithm! – Ricercar

Answer 5

static long GMULL = 0x9E3779B97F4A7C15L;
static long GDIVL = 0xF1DE83E19937733DL;
static long GADDL = 0x0123456789ABCDEFL;
public static long golden64fwd(long key) {
    key *= GMULL;
    key += GADDL;
    return key;
}

public static long golden64rev(long key) {
    key -= GADDL;
    key *= GDIVL;
    return key;
}

static int GMULI = 0x9E3779B9;
static int GDIVI = 0x144CBC89;
static int GADDI = 0x01234567;
public static int golden32fwd(int key) {
    key *= GMULL;
    key += GADDL;
    return key;        
}

public static int golden32rev(int key) {
    key -= GADDI;
    key *= GDIVI;
    return key;        
}

So as far as hash properties are concerned it is at best average. GMUL[I,N] are the approximate golden ratio for 64 and 32 bit. GDIV[I,N] are the respective multiplicative inverses mod 2^size. GADD[I,N] is an odd number. There are numbers that are consecutive and their "hashed" values are also very close. But I doubt that there are three in a row.

Postprandial