# Looking for a bijective, discrete function that behaves as chaotically as possible

I need to write a coupon code system but I do not want to save each coupon code in the database. (For performance and design reasons.) Rather I would like to generate codes subsequent that are watermarked with another code.

They should like kind of fancy and random. Currently they look like this:

1: AKFCU2, 2: AKFDU2, 3: AKFDW2, 4: AKHCU2, 5: AKHCW2, ..., 200: CLFSU2, 201: CLFSW2, ...

It's obvious that subsequent codes look very similar as I just converted my code ingredients (the watermark and the integer in the front) to binary base and permutated the order by a fixed scheme. But to prevent people to easily guess another valid code or even accidently enter another valid code (thus making another code invalid by using it) I would prefer something more chaotic, like this:

1: FIOJ32, 2: X9NIU2, 3: SIUUN7, 4: XTVV4S, ...

In the end the problem is to find a bijective, discrete function on the domain {0,1}^27 (or alternatively {0,1,2,3,4, ..., [10^(8.5)]}) that is far away from being continuous. Also it should be as simple as possible to implement. (EDIT: I also need to implement the reverse function.)

Any suggestions for such a function?

-
Generally people do this kind of stuff with a hash function. Are you sure you need to implement the inverse? You could just have a lookup table of the hashes of all the coupons you've used so far. – Qiaochu Yuan Nov 9 '10 at 9:25
@Qiaochu You need there to be no collisions, so any one-way permutation would do (with a lookup table as you described). – Yuval Filmus Nov 9 '10 at 23:28

Take any odd $a$ and calculate $x \mapsto ax + b \pmod{2^{27}}$.

EDIT: Here's a more sophisticated suggestion. The following functions are all invertible and easy to implement:

• Multiplication by an odd number modulo $2^{27}$.
• Addition of an arbitrary number modulo $2^{27}$.
• XOR of an arbitrary 27-bit number.
• Rotation of the bits (can be implemented using two shifts).

If you compose them repeatedly they become harder to break (but probably still easy for someone who already knows the general form of your cipher).

By composing, I mean you apply several of them in succession (you can apply a given mapping more than once with same or different parameters).

Another suggestion is to use a random permutation. It's not difficult to generate a random permutation, and given a permutation to calculate its inverse. You can store both permutations in a file and load them to memory (if you have enough - it's 1GB for both) each time your main program starts.

-
Thanks for your answer! But can you please tell me the inverse function? – Philip Nov 9 '10 at 0:59
The inverse is $x \mapsto a^{-1}(x-b) \pmod{2^{27}}$. – Yuval Filmus Nov 9 '10 at 1:17
You can compute $a^{-1} \pmod{2^{27}}$ using (say) Wolfram Alpha, or conversely, just try all odd $b$s until you hit upon one such that $ab \equiv 1 \pmod{2^{27}}$. (The real way to calculate an inverse is the extended GCD algorithm.) – Yuval Filmus Nov 9 '10 at 1:18
The disadvantage to this suggestion is that if you feed serial x values in and somebody collects several coupons, they may well be able to find a and b by subtracting the codes. This presumes they know what your algorithm is. You could also use RSA encryption, but 27 bits is very few. – Ross Millikan Nov 9 '10 at 2:13
@Ross That's quite a complicated attacker! Anyhow, I added some more naive-yet-good-enough suggestions. – Yuval Filmus Nov 9 '10 at 7:37

you could make sth inspired by RSA, where you do not need two keys. like this:

calculate everything modulo $p$, where $p$ is prim. that will then be the GF[$p$] (GaloisField). now instead of finding a generator $g$ for that GF[$p$] and calculating anything in powers of $g$, you could use any large numbers for multiplication and addition. this allone will then be very unsafe, but it will be very chaotic in combination with some bit-operations.

the encoding and decoding functions can be combined out of simple unsafe functions. the combination makes them more unpredictable, especially with the bit-operations.

(calculate once the reciprocal ($m^{-1}\equiv m^{p-2}$) of every $m$, that you use to multiply; you'll need it for decryption.)

let's define functions enc1 and dec1 based on multiplication:

$enc1_m(x)=x·m$ (mod p)

$dec1_m(y)=y·m^{-1}$ (mod p)

..................................................

and another pair based on addition:

$enc2_a(x)=x+a$ (mod p)

$dec2_a(y)=y-a$ (mod p)

..................................................

and another pair based on bit-shuffling, but that need to be invertible and never generate a value $\geq p$:

let $(\odot,\oplus,\otimes,\neg)$ be the bitwise (and,or,xor,not) operations

let $permutateAndXorLowestNBits_{s}(x,n)$ change the lowest n bits of x so that it is invertible. in other words, this condition holds: $$\forall x,s,n: permutateAndXorLowestNBits_{s}^{-1}(permutateAndXorLowestNBits_{s}(x,n),n)=x$$

let N(x) be the number of lowest bits of x that can be "safely" changed so that after changing those bits, N will result in the same number and the value never exceeds p. in other words, these two conditions hold: $$x \oplus (2^{N(x)}-1) < p$$ $$\forall y. x \odot \neg(2^{N(x)}-1) \leq y \leq x \oplus (2^{N(x)}-1) \Rightarrow N(y)=N(x)$$

$enc3_s(x) = permutateAndXorLowestNBits_{s}(x,N(x))$

$dec3_s(y) = permutateAndXorLowestNBits_{s}^{-1}(y,N(y))$

..................................................

now, the resulting key will be (m,a,s) and the functions:

$enc_{m,a,s}(x)=enc1_m(enc2_a(enc3_s(x)))$

$dec_{m,a,s}(y)=dec3_s(dec2_a(dec1_m(y)))$

but any other more complec combination would be valid, too. remember, that any combination of several enc1s and enc2s can be expressed as one single combination of enc1 and enc2; so, alternate it with enc3.

i do not know, how hard it will be to break this if only p is known. without the bit-operations, a linear equation would break this, but with those bit-operations it will be very chaotic. does anyone know that?

otherwise, you could still make sth like a Feistel cipher, but i do not know wether it would be more secure or how to measure that.

-
It can be broken from two plaintext/ciphertext pairs by solving a system of linear equations. – Yuval Filmus Nov 9 '10 at 23:27
Jep, did think about that last night. I'll fix this... – comonad Nov 10 '10 at 1:05