Feistel on sequences

feistel.py

import hashlib
import math
import sys

def keyed_digest(salt):
    byteorder = sys.byteorder
    m = hashlib.sha256()
    m.update(salt)
    
    def digest(r, k):
        h = m.copy()
        h.update(k.to_bytes(1, byteorder))
        h.update(r.to_bytes(max(r.bit_length(), 1), byteorder))
        return int.from_bytes(h.digest(), byteorder)

    return digest


def feistel(seq, round_fn=keyed_digest(b"salt"), rounds=8):
    sz = len(seq)
    w = math.ceil(math.sqrt(sz))

    for n in range(pow(w, 2)):
        for k in range(rounds):
            l, r = divmod(n, w)
            r, l = l + round_fn(r, k), r
            n = l * w + r % w
        if n < sz:
            yield seq[n]
            
def find_factor(x):
    m = math.floor(math.sqrt(x))
    while m > 0:
        q, r = divmod(x, m)
        if r == 0:
            return m, q
        m -= 1

def feistel_clean(seq, round_fn=keyed_digest(b"salt"), rounds=8):
    sz = len(seq)
    m, c = find_factor(sz)

    for n in range(sz):
        for k in range(rounds):
            l, r = divmod(n, m)
            r, l = (l + round_fn(r, k)) % c, r
            m, c = c, m
            n = l * m + r
        yield seq[n]

            
names = ('John', 'Jane', 'Jim', 'Julia', 'Jeff', 'Jill', 'Jacob', 'Jorgen')
elts = [
    tuple(feistel(names, round_fn=fn))
    for fn in map(keyed_digest, map(bytes, range(30)))
]
print("Unique entries: {}".format(len(set(elts))))
print(elts)