Feistel Cipher - Simple Reversible Cipher

explanation math algo encryption cipher

intro

So I recently read this article which describes how this simple cipher is used for generating seemingly random series of strings. The author introduced this cipher which makes use of feistel network to produce one that is reversible (i.e. cipher(cipher(n)) = n).

The cool thing about this cipher is that it can guarantee no collision (of cos you will have to modify it, look at the bb variable in the following section). This means that you can use this as a one-to-one hash. Although the idea is simple, it can be quite useful in this aspect.

As mentioned in the blog post, this kind of cipher is also used in postgres as pseudo_encrypt(). The original implementation from postgres is as implemented in the postgres wiki.

CREATE OR REPLACE FUNCTION pseudo_encrypt(value int) returns int AS $$
DECLARE
l1 int;
l2 int;
r1 int;
r2 int;
i int:=0;
BEGIN
 l1:= (value >> 16) & 65535;
 r1:= value & 65535;
 WHILE i < 3 LOOP
   l2 := r1;
   r2 := l1 # ((((1366 * r1 + 150889) % 714025) / 714025.0) * 32767)::int;
   l1 := l2;
   r1 := r2;
   i := i + 1;
 END LOOP;
 return ((r1 << 16) + l1);
END;
$$ LANGUAGE plpgsql strict immutable;

python version

The blog post also has some sort of python implementation that makes this feistal cipher much easier to understand. The python snippet that appears on the blog has a lot of “magic numbers”, but actually a lot of these can be modified as you see fit.

This snippet below extract those parts that can be modified, and can be adapted to your needs. A brief description of those modifiable parts is as follows:

  • _key(): this acts like a hash function for the variable
  • rnds: number of rounds to encrypt the value
  • bb: number of bits to use in the cipher (bb bits uniquely hashs 0 to 2^(bb) - 1)
def feistel(value):
    # everything that can be modified
    def _key(val):
        # as long as function returns a value from 0 to 1
        return (((1366 * val + 1508) % 714025) / 714025.0)
    rnds = 5
    bb = 16

    # A simple self-inverse Feistel cipher for ID obfuscation
    vv = (1 << bb) - 1
    l1 = (value >> bb) & vv
    r1 = value & vv

    for _ in range(rnds):
        l2 = r1
        r2 = l1 ^ int(_key(r1) * int(vv/2))
        l1 = l2
        r1 = r2
    return (r1 << bb) + l1

for i in range(10):
	print(feistel(feistel(i)), feistel(i))