这是我在两年前编写的Python 3实现
格式保留加密的相当简单的实现，使用平衡的
费斯特尔网络。它可以在32位系统上执行您想要的N个索引置换，N最大可达2
64，或在64位Python版本上达到2
128。这是由
hash()函数返回的整数大小决定的。请查看
sys.hash_info以找到您系统的限制。使用更复杂或更慢的哈希函数返回更长的比特长度的值并不困难，但我不想让这段代码变得更加复杂或更慢。
更新
我对之前的版本进行了一些小改进，并在注释中添加了更多信息。我们现在使用哈希函数返回的高位而不是低位，这通常可以提高随机性，特别是对于短位长度。我还添加了另一个哈希函数Yann Collet的xxhash，它比Python的hash在这种情况下表现得要好得多，特别是对于较短的位长度，尽管它稍微慢一些。xxhash算法的雪崩效应比内置的hash要高得多，因此得到的排列往往更加乱序。
虽然这段代码适用于小值的stop，但更适合处理stop >= 2**16。如果您需要对较小的范围进行排列，最好只使用list(range(stop))上的random.shuffle。它会更快，并且不会使用太多RAM：list(range(2**16))在32位机器上占用约1280千字节。
你会注意到我使用了一个字符串来生成随机数种子。对于这个应用程序，我们希望随机器有足够的熵，并且使用一个大字符串（或
bytes）是一个简单的方法，正如
random模块文档所述。即便如此，当
stop很大时，该程序只能产生所有可能排列的一小部分。例如，当
stop == 35时，有35！（35的阶乘）种不同的排列方式，而35! > 2
132，但我们密钥的总位数仅为128位，因此无法覆盖所有这些排列方式。我们可以增加Feistel轮数以获得更多的覆盖范围，但显然对于大的
stop值来说是不切实际的。
''' Format preserving encryption using a Feistel network
This code is *not* suitable for cryptographic use.
See https://en.wikipedia.org/wiki/Format-preserving_encryption
https://en.wikipedia.org/wiki/Feistel_cipher
http://security.stackexchange.com/questions/211/how-to-securely-hash-passwords
A Feistel network performs an invertible transformation on its input,
so each input number produces a unique output number. The netword operates
on numbers of a fixed bit width, which must be even, i.e., the numbers
a particular network operates on are in the range(4**k), and it outputs a
permutation of that range.
To permute a range of general size we use cycle walking. We set the
network size to the next higher power of 4, and when we produce a number
higher than the desired range we simply feed it back into the network,
looping until we get a number that is in range.
The worst case is when stop is of the form 4**k + 1, where we need 4
steps on average to reach a valid n. In the typical case, where stop is
roughly halfway between 2 powers of 4, we need 2 steps on average.
Written by PM 2Ring 2016.08.22
'''
from random import Random
def xxhash_num(n, seed):
n = (374761397 + seed + n * 3266489917) & 0xffffffff
n = ((n << 17 | n >> 15) * 668265263) & 0xffffffff
n ^= n >> 15
n = (n * 2246822519) & 0xffffffff
n ^= n >> 13
n = (n * 3266489917) & 0xffffffff
return n ^ (n >> 16)
class FormatPreserving:
""" Invertible permutation of integers in range(stop), 0 < stop <= 2**64
using a simple Feistel network. NOT suitable for cryptographic purposes.
"""
def __init__(self, stop, keystring):
if not 0 < stop <= 1 << 64:
raise ValueError('stop must be <=', 1 << 64)
self.maxn = stop - 1
self.shiftbits = -(-self.maxn.bit_length() // 2)
self.lowmask = (1 << self.shiftbits) - 1
self.lowshift = 32 - self.shiftbits
stream = Random()
stream.seed(keystring)
self.keys = [stream.getrandbits(32) for _ in range(4)]
self.ikeys = self.keys[::-1]
def feistel(self, n, keys):
left, right = n >> self.shiftbits, n & self.lowmask
for key in keys:
left, right = right, left ^ (xxhash_num(right, key) >> self.lowshift)
return (right << self.shiftbits) | left
def fpe(self, n, reverse=False):
keys = self.ikeys if reverse else self.keys
while True:
n = self.feistel(n, keys)
if n <= self.maxn:
return n
def test():
print('Shuffling a small number')
maxn = 10
fpe = FormatPreserving(maxn, 'secret key string')
for i in range(maxn):
a = fpe.fpe(i)
b = fpe.fpe(a, reverse=True)
print(i, a, b)
print('\nShuffling a small number, with a slightly different keystring')
fpe = FormatPreserving(maxn, 'secret key string.')
for i in range(maxn):
a = fpe.fpe(i)
b = fpe.fpe(a, reverse=True)
print(i, a, b)
print('\nHere are a few values for a large maxn')
maxn = 10000000000000000000
print('maxn =', maxn)
fpe = FormatPreserving(maxn, 'secret key string')
for i in range(10):
a = fpe.fpe(i)
b = fpe.fpe(a, reverse=True)
print('{}: {:19} {}'.format(i, a, b))
print('\nUsing a set to test that there are no collisions...')
maxn = 100000
print('maxn', maxn)
fpe = FormatPreserving(maxn, 'secret key string')
a = {fpe.fpe(i) for i in range(maxn)}
print(len(a) == maxn)
print('\nTesting that the operation is bijective...')
for i in range(maxn):
a = fpe.fpe(i)
b = fpe.fpe(a, reverse=True)
assert b == i, (i, a, b)
print('yes')
if __name__ == "__main__":
test()
输出
Shuffling a small number
0 4 0
1 2 1
2 5 2
3 9 3
4 1 4
5 3 5
6 7 6
7 0 7
8 6 8
9 8 9
Shuffling a small number, with a slightly different keystring
0 9 0
1 8 1
2 3 2
3 5 3
4 2 4
5 6 5
6 1 6
7 4 7
8 7 8
9 0 9
Here are a few values for a large maxn
maxn = 10000000000000000000
0: 7071024217413923554 0
1: 5613634032642823321 1
2: 8934202816202119857 2
3: 296042520195445535 3
4: 5965959309128333970 4
5: 8417353297972226870 5
6: 7501923606289578535 6
7: 1722818114853762596 7
8: 890028846269590060 8
9: 8787953496283620029 9
Using a set to test that there are no collisions...
maxn 100000
True
Testing that the operation is bijective...
yes
0 4
1 2
2 5
3 9
4 1
5 3
6 7
7 0
8 6
9 8
这是如何使用它来制作生成器的方法：
def ipermute(stop, keystring):
fpe = FormatPreserving(stop, keystring)
for i in range(stop):
yield fpe.fpe(i)
for i, v in enumerate(ipermute(10, 'secret key string')):
print(i, v)
输出
0 4
1 2
2 5
3 9
4 1
5 3
6 7
7 0
8 6
9 8
它在Python中速度相当快，但绝对
不适用于密码学。通过将Feistel轮数增加至至少5轮，并使用适当的加密哈希函数（例如
Blake2），可以使其达到密码级别。此外，需要使用加密方法来生成Feistel密钥。当然，除非您确切地知道自己在做什么，否则不应编写密码软件，因为编写容易受到时间攻击等漏洞的代码。
