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

Question

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?

Answer 1

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.

Answer 2

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.