整数对称密码算法/方法

Question

我正在寻找一个双射变换，我可以使用不是加密，而是混淆。其思想是采用1, 2, 3, 4这样的整数，并将它们投影到另一个轴上。其主要思想是在域B中投影时，确保两个相邻整数与域A之间的最大距离。你知道吗

我用Python编写了以下内容，但是目标语言是PHP。我不在乎实现，只在乎算法/方法。你知道吗

例如n = 8：

A     B
0 <-> 4
1 <-> 5
2 <-> 6
3 <-> 0
4 <-> 2
5 <-> 7
6 <-> 3
7 <-> 1

一个简单的实现是构建一个随机的一对一对应表，然后用作O（1）变换函数。你知道吗

a = func(0) # a = 4
b = func(a) # b = 0

最有效算法

最有效的算法是建立一个哈希表，它需要O（n）内存并在O（1）中执行。你知道吗

class Shuffle:
    def __init__(self, n, seed=42):        
        self._table = list(range(n))
        random.seed(seed)
        random.shuffle(self._table)

    def enc(self, n):
        return self._table[n]

    def dec(self, n):
        return self._table.index(n)

不幸的是，我正在寻找一个更轻也许更简单的算法。你知道吗

愚蠢的企图

有趣的部分来了，因为我试过玩一次性Pad（OTP），一些对称加密算法（Blowfish），但没有成功。最终，我尝试了一种愚蠢、有趣、天真的实现方式：

def enigma(input): # Because why not?
    a = deque([1, 3, 0, 4, 2])
    b = deque([3, 0, 4, 2, 1])
    u = [0 for i in range(len(input))]
    for i, c in enumerate(input):
        u[i] = a.index(b.index([4, 3, 2, 1, 0][b[a[c]]]))
        a.rotate(1)
        b.rotate(3)    
    return u

def shuffle(n, seed=81293): # Because enigma is not enough
    random.seed(seed)
    serie = list(range(len(n)))
    random.shuffle(serie)
    for i, j in enumerate(serie):
        n = n.copy()
        n[i], n[j] = n[j], n[i]
        return n

def int2five(decimal): # Base 10 -> Base 5
    radix = 5
    s = [0 for i in range(9)]
    i = 0
    while (decimal):
        s[i] = decimal % radix
        decimal = decimal // radix
        i += 1
    return list(reversed(s))

def five2int(five): # Base 5 -> Base 10
    return int(''.join([str(x) for x in five]), 5)

def enc(n):
    return five2int(enigma(shuffle(int2five(n))))

def dec(s):
    return five2int(shuffle(enigma(int2five(s))))

结果是：

>>> ['%d <-> %d' % (i, enc(i)) for i in range(7)]
['0 <-> 1729928',
 '1 <-> 558053',
 '2 <-> 1339303',
 '3 <-> 948678',
 '4 <-> 167428',
 '5 <-> 1729943',
 '6 <-> 558068']

我为什么选择5号基地？我选择我的工作范围是[0..2e6[，因此通过寻找最佳的基础来最大化覆盖范围（是的，下面的代码很难看）：

>>> [(d, l, s, 100 - round(s/n*100,1)) for (d, l, s) in sorted([(k, round(math.log(n, k), 3), n - k**(math.floor(math.log(n, k))) - 1)
        for k in range(2, 100)], key=lambda k: k[2])[0:10]]

[(5, 9.015, 46873, 97.7),
 (18, 5.02, 110430, 94.5),
 (37, 4.018, 125837, 93.7),
 (11, 6.051, 228437, 88.6),
 (6, 8.097, 320382, 84.0),...]

我注意到基5可以用9位数字表示，覆盖范围是我的97%。排名第二的候选人是18岁，覆盖率为94%。你知道吗

Answer 1

就像你想在这里使用Format-Preserving Encryption，一个好的是Mihir Bellare的FFX（白皮书here）。你知道吗

正如您所注意到的，您不会发现任何基于旋转的简单算法可以将输入域X映射到Y，其中Y = X用于f: X->Y和X的任何范围[x0..xn]。你知道吗

使用这种保留格式的加密，您需要将范围指定为：

range = radix ** exponent - 1

在你的例子中，你选择了基数5和9作为指数。你知道吗

使用FFX加密

对于实现，可以使用pyffx，这是基于Feistel的加密（FFX）的实现。你知道吗

class Five(pyffx.String):
    def __init__(self, ffx, length, **kwargs):
        super(Five, self).__init__(ffx, '01234', length, **kwargs)

    def pack(self, v):
        return super(Five, self).pack(str(v).zfill(self.length))

    def unpack(self, v, t):
        return int(super(Five, self).unpack(v, t))

那么

>>> import pyffx
>>> radix, exponent = 5, 9
>>> e = Five(b'secret', exponent)
>>> e.encrypt(123)
321301321

任意域加密

如前所述，FFX只对由radix ** exponent - 1指定的域中的数据进行加密。如果要在任意域上加密，可以使用名为循环行走的方法，如下所述：

 def cycle_walking (x, encipher) {
   if encipher(x) is an element of M
     return encipher(x)
   else 
     return cycle_walking(encipher(x))
 }

为此，您需要使用严格大于目标域M的域N