Cryptanalysis of Classical Ciphers with Multiple Encryption

Have you ever wondered how multiple encryption affects the security of the famous classical ciphers, Caesar, Substitution and Vigenère? Does encrypting plaintext multiple times improve, weaken or not affect the overall Cipher strength? The conclusion, unsurprisingly, is that multiple rounds of encryption are equivalent to encrypting the plaintext once. Here’s why.

Caesar Cipher

The Caesar Cipher is a shift cipher where letters are replaced by those k along in the alphabet. When shifting our plaintext EXAMPLE by 5 we get JCFRUQJ. Shifting this ciphertext by 3 results in MFIUXTM. With the help of lantern this ciphertext can be decrypted.

decryptions = caesar.crack("MFIUXTM", fitness.english.quadgrams)
print(decryptions[0])
print(decryptions[0].key)
EXAMPLE
8

The plaintext was successfully found by brute forcing keys between 0 and 25. The encryption key for this text was 8. Relating this back to our initial two encryption keys, 3 and 5, it is clear that 8 is the result of combining the two shifts together. No matter how many times the text is shifted it will always stay within the bounds of the alphabet and the resulting shift can be represented by a single value. Hence, multiple encryption of the Caesar Cipher is equivalent to a single encryption, meaning it can be broken using standard methods.

Substitution Cipher

The Substitution Cipher extends the Caesar Cipher by allowing arbitrary letter replacements instead of shifting. Single encryption can be easily broken using letter frequency and dependencies.

ITISALONGESTABLISHEDFACTTHATAREADERWILLBEDISTRACTEDBYTHEREADABLECONTENTOFAPAGEWHENLOOKINGATITSLAYOUTTHEPOINTOFUSINGLOREMIPSUMISTHATITHASAMOREORLESSNORMALDISTRIBUTIONOFLETTERSASOPPOSEDTOUSINGCONTENTHERECONTENTHEREMAKINGITLOOKLIKEREADABLEENGLISHMANYDESKTOPPUBLISHINGPACKAGESANDWEBPAGEEDITORSNOWUSELOREMIPSUMASTHEIRDEFAULTMODELTEXTANDASEARCHFORLOREMIPSUMWILLUNCOVERMANYWEBSITESSTILLINTHEIRINFANCYVARIOUSVERSIONSHAVEEVOLVEDOVERTHEYEARSSOMETIMESBYACCIDENTSOMETIMESONPURPOSEINJECTEDHUMOURANDTHELIKE

Encrypt using the key: VORJLFYIDUMQTNHGEWAXBCPSZK
DXDAVQHNYLAXVOQDAILJFVRXXIVXVWLVJLWPDQQOLJDAXWVRXLJOZXILWLVJVOQLRHNXLNXHFVGVYLPILNQHHMDNYVXDXAQVZHBXXILGHDNXHFBADNYQHWLTDGABTDAXIVXDXIVAVTHWLHWQLAANHWTVQJDAXWDOBXDHNHFQLXXLWAVAHGGHALJXHBADNYRHNXLNXILWLRHNXLNXILWLTVMDNYDXQHHMQDMLWLVJVOQLLNYQDAITVNZJLAMXHGGBOQDAIDNYGVRMVYLAVNJPLOGVYLLJDXHWANHPBALQHWLTDGABTVAXILDWJLFVBQXTHJLQXLSXVNJVALVWRIFHWQHWLTDGABTPDQQBNRHCLWTVNZPLOADXLAAXDQQDNXILDWDNFVNRZCVWDHBACLWADHNAIVCLLCHQCLJHCLWXILZLVWAAHTLXDTLAOZVRRDJLNXAHTLXDTLAHNGBWGHALDNULRXLJIBTHBWVNJXILQDML

Encrypt again using key: SAEYOCBPRNZKVGJQFXMILDTWUH
YWYSDFPGUKSWDJFYSRKNCDXWWRDWDTKDNKTQYFFJKNYSWTDXWKNJHWRKTKDNDJFKXPGWKGWPCDBDUKQRKGFPPVYGUDWYWSFDHPAWWRKBPYGWPCASYGUFPTKIYBSAIYSWRDWYWRDSDIPTKPTFKSSGPTIDFNYSWTYJAWYPGPCFKWWKTSDSPBBPSKNWPASYGUXPGWKGWRKTKXPGWKGWRKTKIDVYGUYWFPPVFYVKTKDNDJFKKGUFYSRIDGHNKSVWPBBAJFYSRYGUBDXVDUKSDGNQKJBDUKKNYWPTSGPQASKFPTKIYBSAIDSWRKYTNKCDAFWIPNKFWKMWDGNDSKDTXRCPTFPTKIYBSAIQYFFAGXPEKTIDGHQKJSYWKSSWYFFYGWRKYTYGCDGXHEDTYPASEKTSYPGSRDEKKEPFEKNPEKTWRKHKDTSSPIKWYIKSJHDXXYNKGWSPIKWYIKSPGBATBPSKYGLKXWKNRAIPATDGNWRKFYVK

Since the frequency of symbols does not change with multiple encryption, we should be able to decrypt double enciphered text easily.

decryptions = simplesubstitution.crack(ciphertext, fitness.english.quadgrams)
print(decryptions[0])
print(decryptions[0].key)
ITISALONGESTABLISHEDFACTTHATAREADERWILLBEDISTRACTEDBYTHEREADABLECONTENTOFAPAGEWHENLOOKINGATITSLAYOUTTHEPOINTOFUSINGLOREMIPSUMISTHATITHASAMOREORLESSNORMALDISTRIBUTIONOFLETTERSASOPPOSEDTOUSINGCONTENTHERECONTENTHEREMAKINGITLOOKLIKEREADABLEENGLISHMANYDESKTOPPUBLISHINGPACKAGESANDWEBPAGEEDITORSNOWUSELOREMIPSUMASTHEIRDEFAULTMODELTEXTANDASEARCHFORLOREMIPSUMWILLUNCOVERMANYWEBSITESSTILLINTHEIRINFANCYVARIOUSVERSIONSHAVEEVOLVEDOVERTHEYEARSSOMETIMESBYACCIDENTSOMETIMESONPURPOSEINJECTEDHUMOURANDTHELIKE

DJXNKCURYLVFIGPBZTSWAEQMHO

The plaintext was found, our prediction was correct. Since only the symbols change and not their frequency, multiple rounds of encryption is equivalent to a single round with a different key. The final key can be determined by encrypting the key from the previous round using the key of the current round and continuing until completion. In our example above, VORJLFYIDUMQTNHGEWAXBCPSZK encrypted using SAEYOCBPRNZKVGJQFXMILDTWUH results in DJXNKCURYLVFIGPBOTSWAEQMHZ, our final key.

Vigenère Cipher

The Vigenère Cipher is a periodic polyalphabetic substitution cipher, or in other words, it uses p many values to shift the plaintext, the same shift repeated every p letters. Since the frequency of symbols change with encryption it makes the ciphertext slightly harder to decrypt than Substitution. Once the period is known however, it is simply a matter of solving many Caesar Ciphers. With multiple encryption there can be two variants, where all keys have the same period, and where the periods differ.

Same Period

ITISALONGESTABLISHEDFACTTHATAREADERWILLBEDISTRACTEDBYTHEREADABLECONTENTOFAPAGEWHENLOOKINGATITSLAYOUTTHEPOINTOFUSINGLOREMIPSUMISTHATITHASAMOREORLESSNORMALDISTRIBUTIONOFLETTERSASOPPOSEDTOUSINGCONTENTHERECONTENTHEREMAKINGITLOOKLIKEREADABLEENGLISHMANYDESKTOPPUBLISHINGPACKAGESANDWEBPAGEEDITORSNOWUSELOREMIPSUMASTHEIRDEFAULTMODELTEXTANDASEARCHFORLOREMIPSUMWILLUNCOVERMANYWEBSITESSTILLINTHEIRINFANCYVARIOUSVERSIONSHAVEEVOLVEDOVERTHEYEARSSOMETIMESBYACCIDENTSOMETIMESONPURPOSEINJECTEDHUMOURANDTHELIKE

Encrypt using the key: VXUH
DQCZVIIUBBMAVYFPNEYKAXWAOEUAVOYHYBLDDIFIZACZOOUJOBXITQBLMBUKVYFLXLHAZKNVAXJHBBQOZKFVJHCUBXNPOPFHTLOAOEYWJFHAJCOZDKASJOYTDMMBHFMACXNPOEUZVJIYZLLSZPMUJOGHGACZOOCIPQCVILZSZQNLMPUZJMJVNBXAJRMPIDWVIQYUOEYYZZIUOBHACBLLHXEPIDCAGLIRGFELMBUKVYFLZKASDPBTVKSKZPEAJMJBWICZCFHNKXWRVDYZVKXDZYJHBBYKDQIYNKIDPPYSJOYTDMMBHXMACBCYYBZHPINTJAYSOBRAVKXHNBUYXEZVMIIYZJCWNRGDDIFBIZICZOGHIVQLWPCAZPMADIFPIQBLDOCUAXHJTSUYDLOZQBLZDLHZCXPLZSISQBXVQBLACBSLVOMZJJYADJYZWVUJXFXLIQMVHBNPHBMVIMOYKLMLDKDLXQYKCRGVPOUUYQBLGFEL

Encrypt again using key: VTPM
YJRLQBXGWUBMQRUBIXNWVQLMJXJMQHNTTUAPYBUUUTRLJHJVJUMUOJQXHUJWQRUXSEWMUDCHVQYTWUFAUDUHEARGWQCBJIUTOEDMJXNIEYWMEVDLYDPEEHNFYFBNCYBMXQCBJXJLQCXKUEAEUIBGEHVTBTRLJHRUKJRHDEOEUJCXHIJLEFYHIUMMEKBBDWLHDJNGJXNKUSXGJUWMXUAXCQTBDWRMBEXDBYTXHUJWQRUXUDPEYIQFQDHWUITMEFYNRBRLXYWZFQLDQWNLQDMPURYTWUNWYJXKIDXPKINEEHNFYFBNCQBMXURKTUOTKBCFETNEJUGMQDMTIUJKSXOHHBXKUCRIIKVPYBUNDSXOUHVTDOFXRIRMUIBMYBUBDJQXYHRGVQWVOLJKYEDLLUALYEWLXQEXULXELUMHLUAMXUHXQHBLECNMYCNLROJVSYMXDJBHCUCBCUBHDFDKFEBXYDSXSJNWXKVHKHJGTJQXBYTX
decryptions = vigenere.crack(ciphertext, fitness.ChiSquared(frequency.english.unigrams), fitness.english.quadgrams)
print(decryptions[0])
print(decryptions[0].key)
ITISALONGESTABLISHEDFACTTHATAREADERWILLBEDISTRACTEDBYTHEREADABLECONTENTOFAPAGEWHENLOOKINGATITSLAYOUTTHEPOINTOFUSINGLOREMIPSUMISTHATITHASAMOREORLESSNORMALDISTRIBUTIONOFLETTERSASOPPOSEDTOUSINGCONTENTHERECONTENTHEREMAKINGITLOOKLIKEREADABLEENGLISHMANYDESKTOPPUBLISHINGPACKAGESANDWEBPAGEEDITORSNOWUSELOREMIPSUMASTHEIRDEFAULTMODELTEXTANDASEARCHFORLOREMIPSUMWILLUNCOVERMANYWEBSITESSTILLINTHEIRINFANCYVARIOUSVERSIONSHAVEEVOLVEDOVERTHEYEARSSOMETIMESBYACCIDENTSOMETIMESONPURPOSEINJECTEDHUMOURANDTHELIKE

BLSO

lantern successfully decrypted the multiple encrypted ciphertext with two keys of the same period. The period was found using standard methods and the entire text could be decrypted by solving p many Caesar Shifts. The final shift, represented by BLSOis the result of combing the shifts of VXUHand VTPM. This is intuitive to see using our understanding of how multiple encryption affects the key of a Caesar Cipher.

Different Periods

As with the same period, different period multiple encryption is equivalent to encrypting the plaintext once. The keys are combined in the same way, the period of the final key however will vary.

The periods of the keys can have common factors or they can be Relatively prime (numbers where the only positive common factor is 1). Either way, the resulting period of the final encryption key is determined by the least common multiple of all the key periods.

When encrypting using DMZU then XG results in the key AWSA. This is easy to see as XG can become XGXG without changing the encryption, we then have a multiple encryption with the same period. The least common multiple of 4 and 2 is 4, which is the length of our final key. AWSA can be determined by encrypting DMZU with the key XGXG.

When encrypting with HJC then SLOZ the final key is ZUQGBNVIUSXB. The least common multiple of 3 and 4 is 12. This can be understood visually if you imagine the keys HJC and SLOZ overlapping as they encrypt a piece of text. SLOZ is not a multiple of 3, hence multiple repetitions of the key are needed until we reach a length where both keys start again from the same letter. When they start again, we have a repeating pattern that represents the key that can express the multiple encryption as a single encryption.

| H   J   C | H   J   C | H   J   C | H   J   C |
| S   L   O   Z | S   L   O   Z | S   L   O   Z |

This pattern will repeat every 12 letters, hence the encryption from plaintext to final ciphertext can be represented by a single encryption using a key of period 12. The resultant key ZUQGBNVIUSXB is found by encrypting HJCHJCHJCHJC with the key SLOZSLOZSLOZ.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

WordPress.com.

Up ↑