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

基本的に、各文字を文字列内の別の文字と XOR でオフセットしaます。文字の値が偶数または奇数の場合、関数は文字列内の文字を反復処理するため、a初期値はです。10a +=1a -= 1

この暗号を逆にしてプレーンテキストを取得する方法を頭の中で考えました。元の文字列で偶数/奇数の文字オフセットを見つけるには、再帰関数を使用する必要があります。IE: XOR % 2 のプロパティを考えると、ifcipher[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を使用しました。

この分野も初心者です。ピーター・ノーヴィグの本を読むことをお勧めします。難しい質問をありがとう。

于 2015-10-04T01:50:29.310 に答える