python - 逆向加密算法，将字符串中的每个字符与另一个字符进行异或，使用奇偶校验来控制偏移量

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"))

本质上，它将每个字符与字符串中的另一个字符进行异或运算，偏移量为a。 a 初始值为 10，因为函数遍历字符串中的字符，a +=1 如果字符的值为偶数或 a -= 1 如果是奇数。

我已经在脑海中想出如何反转这个密码并检索纯文本，这需要使用递归函数来找出原始字符串中哪些字符偏移量是偶数/奇数。 IE:鉴于 XOR % 2 的属性，我们现在如果 cipher[0] 是奇数，则 plain[0] 或 plain[10] 是奇数，但不是两者都是。类似地，如果 cipher[0] 是偶数，则 plain[0] 和 plain[10] 都是偶数，或者都是奇数。从那里递归算法应该能够完成其余的工作。

一旦我们知道明文中的哪些字符是偶数/奇数，反转其余字符就很简单了。我花了几个小时来解决这个问题，但现在我无法实现它。

我过去使用过基本的递归算法，但从来没有使用任何“分支”来解决这样的问题。

给定一个由该函数生成的密码字符串，我们如何使用递归算法确定原始纯字符串中每个字符的奇偶校验？

编辑:很抱歉只是为了清楚地回应评论，在我为此摸索了几个小时之后，我认为上面概述的递归策略是解决这个问题的唯一方法。如果不是，我愿意接受任何提示/帮助来解决标题问题。

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，因为它是我安装的。

我也是这方面的初学者。我推荐阅读 Peter Norvig 的书。感谢您提出尖锐的问题。