Newsmail #4 , Ukens nøtt #2

unknown_cipher.py

#coding: utf-8

import string
from collections import Counter
from pprint import pprint

def split_word_by_length(word, length):
    return [word[i:i+length] for i in range(0, len(word), length)]

def create_bigrams(sentence):
    bigrams = []
    words = sentence.split(' ')
    for word in words:
        if len(word) > 1 and len(word) % 2 == 0:
            bigrams += split_word_by_length(word, 2)
        else:
            words.remove(word)
    return bigrams

def translated(text, translateFrom, translateTo):
    transtable = string.maketrans(translateFrom, translateTo)
    return text.translate(transtable)

def main():
    cipher = "WZXM XM E DECMEA DXJZCA XHMXPC E ACLCAMCP EOJZEBCW DXJZCA XHMXPC E MUBMWXWUWXVH DXJZCA"

    # Først ser vi på frekvensen av bokstaver, for å se om det er et substitution cipher
    cipherFrequency = Counter(list(cipher))
    pprint(cipherFrequency)

    '''
    Vi ser at bokstavene X, C, M, E skiller seg ut noe som kan indikere at det er et substitution cipher.
    Litt meta: Vi vet at Even liker engelske tekster og vi tror neppe dette er en *hard* oppgave.
    Når vi ser på ordene i cipheret ser vi at E stikker ut som eneste 1-gram.
    De eneste bokstavene som gir mening her er enten I eller A. 
    Gitt at I brukes som 'Jeg' så er vi ganske sikre på at E = A eller E = I.

    http://en.wikipedia.org/wiki/Frequency_analysis
    http://en.wikipedia.org/wiki/Letter_frequency

    I frekvensanalyse prøver vi å se på 2-gram eller bigram som de kalles. 
    Bigrams er to sammenhengende bokstaver. Vi tar utgangspunkt i de som forekommer oftest i engelsk.
    De neste vi gjør er å se på frekvensen av bigrams i cipherteksten vår.
    '''

    bigrams = create_bigrams(cipher)
    bigramFrequencies = Counter(bigrams)
    pprint(bigramFrequencies)

    '''
    Bigramene som er mest vanlig i engelsk
    http://en.wikipedia.org/wiki/Bigram
    '''

    topBigrams = ['TH', 'HE', 'IN', 'ER', 'AN', 'RE', 'ND', 'AT', 'ON', 'NT', 'HA', 'ES', 'ST', 'EN', 
                  'ED', 'TO', 'IT', 'OU', 'EA', 'HI', 'IS', 'OR', 'TI', 'AS', 'TE', 'ET', 'NG', 'OF', 
                  'AL', 'DE', 'SE', 'LE', 'SA', 'SI', 'AR', 'VE', 'RA', 'LD', 'UR']

    '''
    Ved å se på frekvensen til alle ord som deles opp i hele bigrams ser vi de som forekommer oftest. 
    Spesielt er vi interessert i hva mønsteret: DXJZCA mapper til, den gjentas 3 ganger i cipherteksten. 
    I tillegg til XHMXPC som gjentas 2 ganger.
    Vi er også interessert i starten av beskjeden: WZXM XM. Siden de siste bigramet i ord 1 må være ord 2. 
    Vi starter med: WZXM XM

    Det som er interessant her er at XM må da være et gyldig engelsk ord, tatt fra listen under.
    Kandidater: IN, AN, AT, ON, TO, IT, IS, OR, AS, OF
    TH og HE skiller seg mest ut som start på engelske ord (se wikipedia link om bigram). 

    La oss se hva vi har:

    THIN IN, THAN AN, THAT AT, THON ON, THIT IT, THIS IS, THAS AS, THOF OF
    HEIN IN, HEAN AN, HEAT AT, HEON ON, HEIT IT, HEIS IS, HEAS AS, HEOF OF

    De som gir mening er THAT AT, THIS IS, HEAT AT

    Hvis vi antar at E = A så får vi en fin start: THIS IS A

    For syns skyld har vi mapping så langt:
    '''

    print translated(cipher, 'EWZXM', 'ATHIS')
    '''
    THIS IS A DACSAA DIJHCA IHSIPC A ACLCASCP AOJHABCT DIJHCA IHSIPC A SUBSTITUTIVH DIJHCA

    Vi kan allerede se deler av ord formes. SUBSTITUTIVH blir SUBSTITUTION. 
    Dvs MUBMWXWUWXVH = SUBSTITUTION

    Den nye oversettelsestabellen vår ser da slik ut:
    '''

    print translated(cipher, 'EWZXMUBVH', 'ATHISUBON')
    '''
    THIS IS A DACSAA DIJHCA INSIPC A ACLCASCP AOJHABCT DIJHCA INSIPC A SUBSTITUTION DIJHCA

    Hintet til nøtten var Inception. La oss prøve IHSIPC = INSIDE slik at XHMXPC = INSIDE
    '''

    print translated(cipher, 'EWZXMUBVHPC', 'ATHISUBONDE')
    '''
    THIS IS A DAESAA DIJHEA INSIDE A AELEASED AOJHABET DIJHEA INSIDE A SUBSTITUTION DIJHEA

    Da er vi nærme. Hvis ordet "DIJHEA" etter SUBSTITUTION er CIPHER så er vi nesten i mål. 
    Dvs DXJZCA = CIPHER
    '''

    print translated(cipher, 'EWZXMUBVHPCDJZCA', 'ATHISUBONDECPHER')
    '''
    THIS IS A CAESAR CIPHER INSIDE A RELERSED AOPHABET CIPHER INSIDE A SUBSTITUTION CIPHER

    RELERSED AOPHABET = REVERSED ALPHABET
    '''

    print translated(cipher, 'EWZXMUBVHPCDJZCALO', 'ATHISUBONDECPHERVL')
    '''
    THIS IS A CAESAR CIPHER INSIDE A REVERSED ALPHABET CIPHER INSIDE A SUBSTITUTION CIPHER

    Det var nok for å løse cipheret.

    Et naivt alternativ ville vært å brute force 26! versjoner av alfabetet for å treffe nøyaktig. 
    Ved å vite noen karakteristikker med språket som er enkodet i cipherteksten så kan man drastisk 
    redusere kompleksiteten som behøves for å finne hele ord og setninger. 
    Frekvensanalyse kan da brukes selv på penn og papir. Noe som er delvis gjort her.
    '''

if __name__ == '__main__':
    main()