Last active
February 18, 2022 17:09
-
-
Save zv/887071ece2c76aea104b447903663b4f to your computer and use it in GitHub Desktop.
Feistel on sequences
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment