0

我已经从我正在调查的挑战二进制文件中反转了以下算法：

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]偶数，或者都是奇数。从那里递归算法应该能够完成其余的工作。

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

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

给定一个cipher由这个函数产生的字符串，我们如何使用递归算法来确定原始纯字符串中每个字符的奇偶性？

编辑：很抱歉，为了明确并回应评论，在我对此挠了几个小时后，我认为上面概述的递归策略将是解决这个问题的唯一方法。如果不是，我愿意接受任何提示/帮助来解决标题问题。

4

1 回答 1

1

您可以使用所谓的递归回溯来解决这个问题。做一个假设，然后沿着这条路走下去，直到你解密了字符串或者你遇到了矛盾。当您遇到矛盾时，您将返回失败，调用函数将尝试下一种可能性。如果返回成功，则将成功返回给调用者。

我很抱歉，但我无法抗拒试图解决这个问题。这是我想出的：

# 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 的书。感谢您提出棘手的问题。

于 2015-10-04T01:50:29.310 回答