Brute Force - Cryptography and Computer Programming

When a cipher method does not have many keys, it may be feasible to try all possible keys and visually inspect the results for a possible plaintext. Your definition of “not many keys” may change if you were doing this by hand or with a computer. Trying all 26 possible keys of the Caesar cipher by hand would be possible but tedious for a single person to undertake. Trying all 312 possible keys for the Affine cipher less so. The process of trying all possible keys for a given system is called a Brute Force method. It’s not efficient but it is guaranteed to reveal the plaintext message eventually. This is where the computer can really take care of the tedious work for us. We’ll encounter other cipher methods later on that can thwart a brute force method.

Brute Forcing the Caesar Cipher¶

Suppose you intercepted the ciphertext:

PMOLO HKHUF AOPUN JVUMP KLUAP HSAVZ HFOLD YVALP APUJP WOLYA OHAPZ IFZVJ OHUNP UNAOL VYKLY VMAOL SLAAL YZVMA OLHSW OHILA AOHAU VAHDV YKJVB SKILT HKLVB A

We’ll use the previously written text_clean() and caesar() functions to try all 26 possible keys and generate 26 candidates for our plaintext.

def textClean( text ):
    # input: string: `text`
    # output: string
    LETTERS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    text = text.upper()
    cleaned = ''
    for char in text:
        if char in LETTERS:
            cleaned += char
            
    return cleaned

def caesarDecipher(text, key):
    # inputs: string: text, int: key
    # output: string: ciphertext
    ciphertext = textClean(text)
    LETTERS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    plaintext = ''
    
    for char in ciphertext:
        plaintext += LETTERS[ (LETTERS.find(char) - key) % 26 ]
    
    return plaintext.lower()

ciphertext = 'PMOLO HKHUF AOPUN JVUMP KLUAP HSAVZ HFOLD YVALP APUJP WOLYA OHAPZ IFZVJ OHUNP UNAOL VYKLY VMAOL SLAAL YZVMA OLHSW OHILA AOHAU VAHDV YKJVB SKILT HKLVB A'

for testkey in range(0,26):
    print( 'Key', testkey, caesar(ciphertext, testkey, encipher = False) )

Key 0 pmolohkhufaopunjvumpkluaphsavzhfoldyvalpapujpwolyaohapzifzvjohunpunaolvyklyvmaolslaalyzvmaolhswohilaaohauvahdvykjvbskilthklvba
Key 1 olnkngjgteznotmiutlojktzogrzuygenkcxuzkozotiovnkxzngzoyheyuingtmotmznkuxjkxulznkrkzzkxyulznkgrvnghkzzngztuzgcuxjiuarjhksgjkuaz
Key 2 nkmjmfifsdymnslhtsknijsynfqytxfdmjbwtyjnynshnumjwymfynxgdxthmfslnslymjtwijwtkymjqjyyjwxtkymjfqumfgjyymfystyfbtwihtzqigjrfijtzy
Key 3 mjlilehercxlmrkgsrjmhirxmepxswecliavsximxmrgmtlivxlexmwfcwsglerkmrkxlisvhivsjxlipixxivwsjxlieptlefixxlexrsxeasvhgsyphfiqehisyx
Key 4 likhkdgdqbwklqjfrqilghqwldowrvdbkhzurwhlwlqflskhuwkdwlvebvrfkdqjlqjwkhrughuriwkhohwwhuvriwkhdoskdehwwkdwqrwdzrugfrxogehpdghrxw
Key 5 khjgjcfcpavjkpieqphkfgpvkcnvqucajgytqvgkvkpekrjgtvjcvkudauqejcpikpivjgqtfgtqhvjgngvvgtuqhvjgcnrjcdgvvjcvpqvcyqtfeqwnfdgocfgqwv
Key 6 jgifibebozuijohdpogjefoujbmuptbzifxspufjujodjqifsuibujtcztpdibohjohuifpsefspguifmfuufstpguifbmqibcfuuibuopubxpsedpvmecfnbefpvu
Key 7 ifhehadanythingconfidentialtosayhewroteitincipherthatisbysochangingtheorderofthelettersofthealphabetthatnotawordcouldbemadeout
Key 8 hegdgzczmxsghmfbnmehcdmshzksnrzxgdvqnsdhshmbhogdqsgzshraxrnbgzmfhmfsgdnqcdqnesgdkdssdqrnesgdzkogzadssgzsmnszvnqcbntkcadlzcdnts
Key 9 gdfcfybylwrfgleamldgbclrgyjrmqywfcupmrcgrglagnfcprfyrgqzwqmafyleglerfcmpbcpmdrfcjcrrcpqmdrfcyjnfyzcrrfyrlmryumpbamsjbzckybcmsr
Key 10 fcebexaxkvqefkdzlkcfabkqfxiqlpxvebtolqbfqfkzfmeboqexqfpyvplzexkdfkdqebloabolcqebibqqboplcqebximexybqqexqklqxtloazlriaybjxablrq
Key 11 ebdadwzwjupdejcykjbezajpewhpkowudasnkpaepejyeldanpdwpeoxuokydwjcejcpdaknzankbpdahappanokbpdawhldwxappdwpjkpwsknzykqhzxaiwzakqp
Key 12 daczcvyvitocdibxjiadyziodvgojnvtczrmjozdodixdkczmocvodnwtnjxcvibdiboczjmyzmjaoczgzoozmnjaoczvgkcvwzoocvoijovrjmyxjpgywzhvyzjpo
Key 13 czbybuxuhsnbchawihzcxyhncufnimusbyqlinycnchwcjbylnbuncmvsmiwbuhachanbyilxyliznbyfynnylmiznbyufjbuvynnbunhinuqilxwiofxvyguxyion
Key 14 byaxatwtgrmabgzvhgybwxgmbtemhltraxpkhmxbmbgvbiaxkmatmblurlhvatgzbgzmaxhkwxkhymaxexmmxklhymaxteiatuxmmatmghmtphkwvhnewuxftwxhnm
Key 15 axzwzsvsfqlzafyugfxavwflasdlgksqzwojglwalafuahzwjlzslaktqkguzsfyafylzwgjvwjgxlzwdwllwjkgxlzwsdhzstwllzslfglsogjvugmdvtwesvwgml
Key 16 zwyvyrurepkyzextfewzuvekzrckfjrpyvnifkvzkzetzgyvikyrkzjspjftyrexzexkyvfiuvifwkyvcvkkvijfwkyvrcgyrsvkkyrkefkrnfiutflcusvdruvflk
Key 17 yvxuxqtqdojxydwsedvytudjyqbjeiqoxumhejuyjydsyfxuhjxqjyiroiesxqdwydwjxuehtuhevjxubujjuhievjxuqbfxqrujjxqjdejqmehtsekbtrucqtuekj
Key 18 xuwtwpspcniwxcvrdcuxstcixpaidhpnwtlgditxixcrxewtgiwpixhqnhdrwpcvxcviwtdgstgduiwtatiitghduiwtpaewpqtiiwpicdipldgsrdjasqtbpstdji
Key 19 wtvsvorobmhvwbuqcbtwrsbhwozhcgomvskfchswhwbqwdvsfhvohwgpmgcqvobuwbuhvscfrsfcthvszshhsfgcthvsozdvopshhvohbchokcfrqcizrpsaorscih
Key 20 vsurunqnalguvatpbasvqragvnygbfnlurjebgrvgvapvcuregungvfolfbpunatvatgurbeqrebsguryrggrefbsgurnycunorggungabgnjbeqpbhyqorznqrbhg
Key 21 urtqtmpmzkftuzsoazrupqzfumxfaemktqidafqufuzoubtqdftmfuenkeaotmzsuzsftqadpqdarftqxqffqdearftqmxbtmnqfftmfzafmiadpoagxpnqympqagf
Key 22 tqspslolyjestyrnzyqtopyetlwezdljsphczeptetyntaspcesletdmjdznslyrtyrespzcopczqespwpeepcdzqesplwaslmpeesleyzelhzconzfwompxlopzfe
Key 23 sprorknkxidrsxqmyxpsnoxdskvdyckirogbydosdsxmszrobdrkdsclicymrkxqsxqdroybnobypdrovoddobcypdrokvzrkloddrkdxydkgybnmyevnlowknoyed
Key 24 roqnqjmjwhcqrwplxwormnwcrjucxbjhqnfaxcnrcrwlryqnacqjcrbkhbxlqjwprwpcqnxamnaxocqnunccnabxocqnjuyqjknccqjcwxcjfxamlxdumknvjmnxdc
Key 25 qnpmpilivgbpqvokwvnqlmvbqitbwaigpmezwbmqbqvkqxpmzbpibqajgawkpivoqvobpmwzlmzwnbpmtmbbmzawnbpmitxpijmbbpibvwbiewzlkwctljmuilmwcb

Looking through the output, there’s a lot of junk text but your eye may be drawn to the line for key value of 7 since it contains some words that are clearly English. After some spacing it wouldn’t be hard to see it states,

“If he had anything confidential to say, he wrote it in cipher, that is, by so changing the order of the letters of the alphabet, that not a word could be made out.”

Let’s attempt the same strategy with the Affine cipher.

Brute Forcing the Affine Cipher¶

Suppose you intercept the following ciphertext and you suspect it was enciphered using the Affine cipher:

GJLKT FJKXN AOTXU XAVXN KTNPJ JLKGN CYXKT WKJLP YCGJK CYJAC YHTFJ ACHAX ACNAX DANCH JA

We can import text_clean() and affine() to try all possible keys:

def affineDecipher(text, akey, mkey):
    ciphertext = textClean(text)
    LETTERS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    plaintext = ''
    minverse = -1
    
    for testinverse in range(0,26):
        if (testinverse * mkey) % 26 == 1:
            minverse = testinverse
    
    for char in ciphertext:
        plaintext += LETTERS[ minverse * (LETTERS.find(char) - akey) % 26 ]
    
    return plaintext.lower()

ciphertext = 'GJLKT FJKXN AOTXU XAVXN KTNPJ JLKGN CYXKT WKJLP YCGJK CYJAC YHTFJ ACHAX ACNAX DANCH JA'

for test_akey in range(0, 26):
    for test_mkey in [1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25]:
        print( 'akey:',testakey,' mkey:', testmkey, affine(ciphertext, test_akey, test_mkey, encipher=False))

Fetching long content....

Wow, that’s a lot. The eagle eyed among you may have noticed:

akey: 13  mkey: 9 fourscoreandsevenyearsagoourfathersbroughtforthonthiscontinentanewnation

somewhere in the long stream of the output. This process worked, but is still very labor intensive to look through the long list of potential plaintexts. The following code attempts to reduce the amount of output by only showing potential plaintexts that contain the string 'the' or 'and' since those are common words in the English language.

ciphertext = 'GJLKT FJKXN AOTXU XAVXN KTNPJ JLKGN CYXKT WKJLP YCGJK CYJAC YHTFJ ACHAX ACNAX DANCH JA'

for test_akey in range(0, 26):
    for test_mkey in [1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25]:
        candidate_plaintext = affine(ciphertext, test_mkey, test_akey, False)
        if ('the' in candidate_plaintext) or ('and' in candidate_plaintext):
            print( 'akey:',testakey,' mkey:', testmkey, candidate_plaintext)

akey: 10  mkey: 1 wzbajvzandqejnknqlndajdfzzbawdsonajmazbfoswzasozqsoxjvzqsxqnqsdqntqdsxzq
akey: 13  mkey: 9 fourscoreandsevenyearsagoourfathersbroughtforthonthiscontinentanewnation
akey: 20  mkey: 17 qhbedthervisdrarixrvedvphhbeqvcoreduehbpocqhecohicondthicniricvirzivcnhi

This only returns 3 possibilities: akey: 10 mkey: 1 contains 'and', akey: 20 mkey: 17 contains 'the' and akey: 13 mkey: 9 which is the correct plaintext.

It’s easy to see that this definitely reduces the possibilities, but it relies on being able to guess some words in the plaintext. It would be better if we could write a function crack_affine() that takes in the ciphertext and returns the plaintext automatically without the need for any guess and check or visual inspection. By the end of this chapter, you’ll be able to do that! But first you’ll need to learn some statistical analysis.