2
$\begingroup$

This is related to a programming problem I have, but posted here because I think I'll get a better answer.

I've got database records that have ID's 1,2,3,.... Assume I'll never have more than a couple million records. Currently you can view that data by http://mysite/000000001, http://mysite/000000002, etc. Manager would rather those numbers look more random so people don't think "oh I'm the 352nd person to sign up". Are there any quick ways to generate a 1-1 reversible mapping that looks basically random?

Ideas:

  • Deterministically scrambling the digits and adding some constant is easily reversible but not quite random-looking enough.
  • I know I can multiply by a prime factor of N (say I choose N to be a billion, I can multiply by 384720347) and then mod by N, which will give a 1-1 mapping. That's probably the lower bound on "random-looking", but doesn't seem easily reversible. (Correct me if I'm wrong).

Notes:

  • Of course I don't want to create a million-item lookup table.
  • "N" isn't restricted to anything in particular, other than being somewhere between (say) a billion and a trillion. If an algorithm only works assuming N is prime, or N is a power of 2, or N is 932483920 then that's acceptable.
$\endgroup$
  • $\begingroup$ Just use any 10 letters instead of the ten digits - nobody would guess the correspondence. $\endgroup$ – A.S. Nov 5 '15 at 5:01
  • $\begingroup$ Or create a one-to-many map from 10 digits to 10 digits + 26 letters (choose it to be injective for reverse look-up and surjective for more "random looking" and balance it so that each digits gets mapped to 3-4 elements which are a digit and 2-3 letters) and randomly pick an element out of 3-4 possibilities. Assigned alfa-numeric IDs will be random. $\endgroup$ – A.S. Nov 5 '15 at 5:12
  • 2
    $\begingroup$ "but doesn't seem easily reversible" It is fairly easy to invert it. One must solve a linear congurence equation $ax \equiv b\pmod n$ which can be done for example using Euclids algorithm and for almost all typical programming languages there already exists libraries for this. $\endgroup$ – Winther Nov 5 '15 at 5:53
  • $\begingroup$ What you want cannot be done, since very many of the N numbers, regardless of what they actually represent, have a non-random-looking structure; i.e., one of the secret codes will have to be $000001$, etc. $\endgroup$ – Lucian Nov 5 '15 at 8:25
  • 1
    $\begingroup$ This is called obfuscation, I'm sure it has been asked many times before in more programming-oriented forums. Have you checked some of the answers at stackoverflow.com/questions/8554286/obfuscating-an-id ? $\endgroup$ – Erick Wong Nov 5 '15 at 19:25
1
$\begingroup$

There are several good options listed in the StackOverflow question Erick Wong gave in the comments. Below I will flesh out a simple algorithm (based on OPs own suggestion) for generating a random looking id and how we easily can invert it.


Choose a large number $N$, any number $k$ that is co-prime to $N$ and compute the modular multiplicative inverse of $k$, i.e. solve
$$kx \equiv 1 \pmod{N}$$

This can be done using the extended Euclidian algorithm as mentioned in the comments or if $N$ is not really really large you can simply brute-force evaluate $kx\pmod{N}$ for $x=1,2,3,\ldots$ untill you find the correct solution. This is a one-time computation so it's not critical how this is done.

This is all the setup we need. You can now transform to a random looking id using

$$\text{id}_{\rm random} = \text{id}\cdot k \pmod{N}$$

and by multiplying the equation above by $x$ and reducing mod $N$ it follows that you can recover the original id from the random looking id as $$\text{id} = \text{id}_{\rm random}\cdot x \pmod{N}$$

The mapping above is one-to-one since if we have two id's id$_1$ and id$_2$ that maps to the same random-looking id then

$$(\text{id}_1-\text{id}_2)k \equiv 0 \pmod{N}$$

Now since $k$ and $N$ are coprime and as long as id$_1$,id$_2 < N$ we must have $\text{id}_1 = \text{id}_2$. Note that this requires $N$ to be larger than the maximum number of id's you will ever need.

One should also compute the first few random id's to check that they indeed look random (for example for the case $N=1000$ and $k=101$ then we get a very systematic looking sequence in the beginning where $1,2,3,4,5,\ldots$ transforms into $101,202,303,404,505,\ldots$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.