реверсивного алгоритм шифрования, операция XOR каждого символа с другим в строке, используя соотношение для контроля смещения

Question

Я перевернул следующий алгоритм из переходящего двоичном Я расследую:

def encrypt(plain): 
    l = len(plain) 
    a = 10 
    cipher = "" 

    for i in range(0, l): 
     if i + a < l - 1: 
      cipher += chr(xor(plain[i], plain[i+a])) 
     else: 
      cipher += chr(xor(plain[i], plain[a])) 

     if ord(plain[i]) % 2 == 0: a += 1 # even 
     else: a -= 1 # odd 

    return cipher 

from binascii import hexlify 
print hexlify(encrypt("this is a test string")) 

По сути, это операция XOR каждый символа с другим символом в строке, смещенным на a. a начальное значение равно 10, поскольку функция выполняет итерацию над символами в строке, a +=1, если значение символа равно или a -= 1, если оно нечетное.

Я разработал в своей голове, как отменить этот шифр и получить простой текст, для этого потребуется использовать рекурсивную функцию, чтобы выяснить, какие смещения символов четные/нечетные в исходной строке. IE: Учитывая свойства XOR% 2, мы теперь считаем, что если cipher[0] нечетно, то либо plain[0], либо plain[10] является нечетным, но не тем и другим. Аналогично, если cipher[0] равно, то оба значения plain[0] и plain[10] являются четными или оба являются нечетными. Оттуда рекурсивный алгоритм должен уметь работать остальным.

Как только мы узнаем, какие символы в открытом тексте четные/нечетные, обратное остальное тривиально. Я потратил несколько часов на это, но теперь я теряю его реализацию.

Я использовал базовые рекурсивные алгоритмы в прошлом, но никогда ничего, что «отделяется» от решения чего-то подобного.

EDIT: Извините, только чтобы быть ясным и в ответ на комментарий, после того, как я почесываю голову на это в течение нескольких часов, я думал, что стратегия рекурсии, изложенная выше, будет единственным способом решить эту проблему. Если нет, я открыт для любых подсказок/помощи для решения титульного вопроса.

Answer 1

Вы можете решить эту проблему с помощью так называемого recursive backtracking. Сделайте предположение, затем опустите этот путь, пока вы не расшифровали строку, или вы не достигли противоречия. Когда вы достигнете противоречия, вы возвращаете отказ, и вызывающая функция попробует следующую возможность. Если вы вернете успех, верните успех вызывающему абоненту.

Извините, но я не мог удержаться от попытки решить эту проблему. Вот что я придумал:

# Define constants for even/odd/notset so we can use them in a list of 
# assumptions about parity. 
even = 0 
odd = 1 
notset = 2 

# Define success and failure so that success and failure can be passed 
# as a result. 
success = 1 
failure = 0 

def tryParity(i, cipher, a, parities, parityToSet): 
    newParities = list(parities) 
    for j, p in parityToSet: 
     try: 

      if parities[j] == notset: 
       newParities[j] = p 
      elif parities[j] != p: 
       # Failure due to contradiction. 
       return failure, [] 

     except IndexError: 
      # If we get an IndexError then this can't be a valid set of values for the parity. 
      # Error caused by a bad value for "a". 
      return failure, [] 

    # Update "a" based on parity of i 
    new_a = a+1 if newParities[i] == even else a-1 

    return findParities(i+1,cipher,new_a,newParities) 


def findParities(i, cipher, a, parities): 
    # Start returning when you've reached the end of the cipher text. 
    # This is when success start bubbling back up through the call stack. 
    if i >= len(cipher): 
     return success, [parities] # list of parities 

    # o stands for the index of the other char that would have been XORed. 
    # "o" for "other" 
    o = i+a if i + a < len(cipher)-1 else a 

    result = None 
    resultParities = [] 
    toTry = [] 

    # Determine if cipher[index] is even or odd 
    if ord(cipher[i]) % 2 == 0: 
     # Try both even and both odd 
     toTry = (((i,even),(o,even)), 
       ((i,odd),(o,odd))) 

    else: 
     # Try one or the other even, one or the other odd 
     toTry = (((i,odd),(o,even)), 
       ((i,even),(o,odd))) 


    # Try first possiblity, if success add parities it came up with to result 
    resultA, resultParA = tryParity(i, cipher, a, parities, toTry[0]) 

    if resultA == success: 
     result = success 
     resultParities.extend(resultParA) 

    # Try second possiblity, if success add parities it came up with to result 
    resultB, resultParB = tryParity(i, cipher, a, parities, toTry[1]) 

    if resultB == success: 
     result = success 
     resultParities.extend(resultParB) 

    return result, resultParities 

def decrypt(cipher): 
    a = 10 
    parities = list([notset for _ in range(len(cipher))]) 

    # When done, possible parities will contain a list of lists, 
    # where the inner lists have the parity of each character in the cipher. 
    # Comes back with mutiple results because each 
    result, possibleParities = findParities(0,cipher,a,parities) 

    # A print for me to check that the parities that come back match the real parities 
    print(possibleParities) 
    print(list(map(lambda x: 0 if ord(x) % 2 == 0 else 1, "this is a test string"))) 

    # Finally, armed with the parities, decrypt the cipher. I'll leave that to you. 
    # Maybe more recursion is needed 

# test call 
decrypt(encrypt("this is a test string")) 

Кажется, что это работает, но я не пробовал его ни на какие другие входы.

Это решение только дает вам четности, я оставил расшифровку символов до вас. Вероятно, их можно было бы сделать вместе, но я хотел сконцентрироваться на ответе на ваш вопрос, как было задано. Я использовал Python 3, потому что это то, что я установил.

Я тоже начинаю в этой области. Я рекомендую прочитать книгу Питера Норвига. Спасибо за сложный вопрос.