Pfa*_*nXD 6 algorithm permutation
我有一个不寻常的问题,可能会或可能不会被问过(虽然我没有找到任何东西,但我可能只是寻找错误的流行语).
我的任务很简单:给出自然数字的"列表",直到N [0,1,2,... N - 1]我想要改变这个序列.例如,当我输入数字4时,一个可能的结果将是[3,0,1,2].随机性应该由一些种子确定(然而这对于大多数普通语言的PRNG来说是标准的).
天真的方法是实例化一个大小为N的数组,用数字填充它并使用任何改组算法.
然而问题是,这种方法的存储器复杂性是O(n),在我的特殊情况下是不易处理的.我的想法是,编写一个生成器,迭代地在结果列表中提供数字.
更确切地说,我想要一些以迭代方式提供数字的"算法".更确切地说,概念类看起来像这样:
class Generator {
// some state
int nextNumber(...) {
// some magic
}
}
并且迭代地调用nextNumber方法提供序列的编号(即[0,1,... N-1]的任何排列.当然,这个生成器实例的状态应该比O(n)具有更好的内存复杂性再一次(我什么也得不到).
有什么算法要做,我想要什么？
这是使用我在大约2年前写的平衡Feistel网络的格式保留加密的 Python 3中相当简单的实现.它可以在32位系统上执行N到2 64的索引排列,或在64位构建的Python上执行2 128.这是由于函数返回的整数的大小.请参阅查找系统的限制.使用可以返回更大位长的值的更高级的哈希函数并不难,但我不想让这段代码更复杂或更慢.hash()sys.hash_info
我对之前的版本进行了一些小改进,并在评论中添加了一些更多信息.我们使用高位来代替使用散列函数返回的低位,这通常会改善随机性,特别是对于短位长度.我还添加了另一种散列函数,xxhash由扬科莱,其中工程作品多比Python的更好的hash为这个应用程序,特别是对于较短的位长,虽然它是一个慢一点.xxhash算法比内置算法具有更高的雪崩效应hash,因此产生的排列往往更加良好.
尽管此代码适用于较小的值,stop但它更适合处理stop >= 2**16.如果您需要置换较小的范围内它可能是一个好主意,只是使用random.shuffle上list(range(stop)).它会更快,并且它不会使用那么多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
# xxhash by Yann Collet. Specialised for a 32 bit number
# See http://fastcompression.blogspot.com/2012/04/selecting-checksum-algorithm.html
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)
# The highest number in the range
self.maxn = stop - 1
# Get the number of bits in each part by rounding
# the bit length up to the nearest even number
self.shiftbits = -(-self.maxn.bit_length() // 2)
self.lowmask = (1 << self.shiftbits) - 1
self.lowshift = 32 - self.shiftbits
# Make 4 32 bit round keys from the keystring.
# Create an independent random stream so we
# don't intefere with the default stream.
stream = Random()
stream.seed(keystring)
self.keys = [stream.getrandbits(32) for _ in range(4)]
self.ikeys = self.keys[::-1]
def feistel(self, n, keys):
# Split the bits of n into 2 parts & perform the Feistel
# transformation on them.
left, right = n >> self.shiftbits, n & self.lowmask
for key in keys:
left, right = right, left ^ (xxhash_num(right, key) >> self.lowshift)
#left, right = right, left ^ (hash((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:
# Cycle walk, if necessary, to ensure n is in range.
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密钥.当然,除非你确切知道自己在做什么,否则不应该编写加密软件,因为编写易受时序攻击等影响的代码太容易了.
你正在寻找的是一个函数形式的伪随机置换,比如f,它以伪随机双射方式将1到N的数字映射到1到N的数字.然后,要以伪随机排列生成第n个数,只需返回f(n)
这基本上与加密问题相同.具有密钥的分组密码是伪随机双射函数.如果按顺序将所有可能的纯文本块精确地输入一次,它将以不同的伪随机顺序返回所有可能的密文块.
因此,为了解决像你这样的问题,你基本上做的是创建一个密码,它可以处理从1到N而不是256位块或其他数字的数字.您可以使用加密工具来执行此操作.
例如,您可以使用Feistel结构(https://en.wikipedia.org/wiki/Feistel_cipher)构建您的置换函数,如下所示:
由于该函数由许多步骤组成,每个步骤将以0和N-1的数字以双射方式将数字从0映射到N-1,整个函数也将具有此属性.如果你输入从0到N-1的数字,你将以伪随机顺序将它们退回.