Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.3k views
in Technique[技术] by (71.8m points)

cryptography - Python: decode Vigenere cipher that was encoded with Affine cipher

How do I decode some text that has been encoded like this: affine(vigenere(text, vigenere_key), *affine_key)? I don't know keys to either of them. At first I thought I could just bruteforce it by trying out all possible combinations, but then I realised that cracking Vigenere is based on finding keyword which can be literally anything and since the decoded message wont make any sense after cracking Vigenere as it is still encoded with Affine I'm kinda confused how do I find the right key to Vigenere and crack it?

question from:https://stackoverflow.com/questions/65643521/python-decode-vigenere-cipher-that-was-encoded-with-affine-cipher

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

Well I guess this will not answer your question but I hope it can help . In your situation if you are serious about breaking this ciphertext you can try to brute force the affine cipher key (I Hope it's not very long since brute forcing has exponential time complexity) then for each decrypted ciphertext you can test if that specific decrypted ciphertext has an extra layer of vigenere encryption by exploiting the property of vignere cipher keep traces of Index of coincidence of the plaintext language which can be used to guess if that piece of decrypted ciphertext is somewhat like English (except letters are substituted) although this can only work if vigenere key is short (around 5 or 6 characters). then after a having a promising candidate you can use brute force to break the vigenere key.

This python code calculates the Index of coincidence and try to guess the key length.

def index_of_coincidence(ciphertext: str) -> float:
    alphabet = "qwertyuioplkjhgfdsazxcvbnm"
    ciphertext = ciphertext.lower()
    ciphertext_length = 0

    for char in ciphertext:
        if char in alphabet:
            ciphertext_length += 1

    lc = 0
    denomiator = (ciphertext_length * (ciphertext_length-1))
    for char in alphabet:
        letter_count = ciphertext.count(char)
        lc += (letter_count * (letter_count-1)) / denomiator
    return lc

def vigenere_key_length(ciphertext: str) -> int:

    lc_ranges = ["x", 0.0639, 0.0511, 0.0468, 0.0446, 0.0438, 0.0426]
    lc = index_of_coincidence(ciphertext)

    print(lc)
    if lc >= lc_ranges[1]:
        print("The Key length is probably {}".format(1))
        key = 1
        return key

    key = 1
    for key_length in range(1, 6):
        if key_length == 6:
            print("Cant determine Key length with accuracy")
            return None
            
        if lc_ranges[key_length] >= lc >= lc_ranges[key_length + 1]:
            key += key_length
            break

    print("The Key Length is probably {}".format(key))
    return key

Note that the expected time complexity of breaking a vigenere key will not be very large for small key lengths for example a key length of 5 characters will be 7893600 = 26*25*24*23*22 tries which can be done somewhat easily for every decrypted ciphertext but it will gets complicated if affine cipher key is large that it will be better to use above code to test if it's a possible English candidate before brute forcing.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...