Feistel Cipher - Simple Reversible Cipher
explanation math algo encryption cipherintro
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 hashs0
to2^(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))