CODEWITHSUNDEEP
algorithmcombinations
Arsen
Arsen

Reputation: 664

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

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.

Upvotes: 9

Views: 3506

Answers (5)

TrophyGeek
TrophyGeek

Reputation: 6099

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.

Upvotes: 1

lkreinitz
lkreinitz

Reputation: 310

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.

Upvotes: 0

Kostas Kryptos
Kostas Kryptos

Reputation: 4111

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.

Upvotes: 0

olegarch
olegarch

Reputation: 3891

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

Upvotes: 3

Matt Timmermans
Matt Timmermans

Reputation: 59184

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.

Upvotes: 8

Related Questions