Симметричный шифр для целочисленного алгоритма / метода - PullRequest
Новая
       7

Симметричный шифр для целочисленного алгоритма / метода

1 голос
/ 19 июня 2019

Я ищу биективное преобразование, которое я могу использовать НЕ для шифрования , но для запутывания. Идея состоит в том, чтобы взять целые числа, такие как 1, 2, 3, 4, и спроецировать их на другую ось. Основная идея заключается в том, чтобы обеспечить максимальное расстояние между двумя соседними целыми числами от домена A при проецировании в домен B.

Я написал следующее на 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)

К сожалению, я ищу более простой, возможно, более простой алгоритм.

тупая попытка

Здесь начинается самое интересное, потому что я попытался поиграть с One-Time-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% охвата.

1 Ответ

0 голосов
/ 21 июня 2019

Это похоже на то, что вы хотите использовать Форматно-сохраняющее шифрование здесь, а хорошим является FFX от Михира Беллара (белая бумага здесь ).

Каквы заметили, что вы не найдете ни одного простого алгоритма, основанного на поворотах, который может сопоставить входной домен X с Y с Y = X для f: X->Y и X в любом диапазоне [x0..xn],

При таком типе шифрования, сохраняющем формат, вам нужно будет указать свой диапазон следующим образом: 

range = radix ** exponent - 1

В вашем случае вы выбрали основание 5 и 9 для показателя степени.

Шифрование с использованием FFX

Для реализации вы можете использовать pyffx , реализацию шифрования на основе Фейстеля (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.Если вы хотите зашифровать в произвольном домене, вы можете использовать метод с именем Cycle Walking , описанный как: 

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

Для этого вам нужно использовать домен N, строго больший, чем ваша цельдомен М.

...