Jarl Van Eycke and Louie Helm recently solved a bigram substitution ciphertext consisting of 1000 letters – the shortest one ever broken. Now I have created a 750-letter challenge of the same kind.
The bigram substitution is a manual encryption method with a history of over 500 years. A bigram (also known as a digraph) is a pair of letters, such as CG, HE, JS or QW. The number of bigrams in the Latin alphabet is 26×26=676, ranging from AA to ZZ. A bigram substitution replaces each letter pair with another one (or with a symbol or with a number between 1 and 676). In order to use a bigram substitution, we need a substitution table with 676 entries.
Examples
The oldest bigram substitution I am aware of is described in the book De Furtivis Literarum Notis written by 16th century cryptologist Giambattista della Porta. Porta uses a 20 letter alphabet. He therefore needs a substitution table with 400 entries.
As can be seen, Porta substituted each letter pair with a symbol. He had to be quite inventive to come up with 400 different symbols. For instance, the bigram IA is replaced with a symbol that looks like an X. The bigram VO is substituted with something resembling an O.
Blaise de Vigenère invented a bigram substitution, too:
Vigenère replaces each bigram with a single letter or a letter followed by a dot, colon or semicolon. E.g., LM is substituted with “r.”.
The following bigram substitution, which is described in David Kahn’s book The Codebreakers, was used by the Nazi authority Reichssicherheitshauptamt (RSHA):
Two challenges
As far as I can tell, hill cimbing is the best approach to attack a bigram substitution. However, this technique will only be successful if there is enough material to analyze, i.e., if the ciphertext is long enough. But how long is long enough? Not much has been published about this question in the literature. In order to take a first step to find the answer, I decided to create a challenge. I took two messages – one with 2500 and one with 5000 letters – and encrypted them with a bigram substitution. Subsequently, I published them on my blog.
Within a few days, blog reader Norbert Biermann found the solution of the 5000 letters version – still with a few mistakes – using hill climbing. Thomas Ernst published a few interesting word pattern considerations. Then Norbert provided a second, more sophisticated hill-climbing result, which was almost error-free. Finally, Armin Krauß published the correct solution.
After the solution of the 5000 letter challenge had proven quite difficult, I expected that the 2500 letter ciphertext would not be solved so soon. I was wrong. Only a few days later, Norbert Biermann published the correct solution of the 2500 letter challenge, which he had again found with his hill climber. To my knowledge, this success represented the world record in breaking bigram substitutions.
The Bigram 1346 challenge
Two years after Norbert’s record, I published another bigram challenge on this blog. This time, I took an English text constisting of 1346 letters as plaintext, calling the result Bigram 1346 challenge. Contrary to last time, I didn’t replace bigrams with numbers but with other bigrams. For this reason, the ciphertext consisted of letters, which had to be read pair-wise. Here’s the challenge:
UNGOZIHIJGSLGVWPIVGJSOKEFMAHSDBDGLUBUNZIWPIEBIUNKFVOUN
BDSLPPHELVAQBAHEBIFJMHKVFLHXQQEFSLQQBDAQRIBVBIBYGJMOSOZ
BSDUXZINXUNEQVKUGYHUNVOWPSGSMGEFLFKRUHELFPHGVUXFGHRJ
YFUHIPBMHUNVOWPSGHXVKRSSGPHPWQXPLKCXGUNFGBICJFGJGCLLC
FPNXUNTUUKKIZBKFABEQNHRFWLKCYHDJHJOPBZRLAHQVFTHETGRQRJ
TDAYDTXTVDBDKFEFZKSDHETUFVIQBIYABDEXZIKCHXRUKQRLGECJAQA
OBKZIOBTEFMFRZNZACLWDWAUNEBBISLMREQKWRJRCUGHERGJMXON
WGJHIPBEYGDZOHXIXKFOXFLKVRUDWAOBIDLSRRICSICJGKFZBBUMRFM
GQKFYBXOHETGHEOAMUEMWLAYRJWPKIGXUOSKZIHIJGSLHIGIBLFUXX
UKUQPHGEGWHIOPZIBDLVBUKQRJSMUGFPWLWPSGPHFIKVYXCJLVULK
VQSZIBDLVBUUISRRUGJAIYXXGLKQXFRPBUOJIBTGHGDTGRCICUNVOWP
SGDTLIEMTAVOUNVUQQKCRTLHBDAIUXFGOAKPBTKVFLAHVWRHWAUG
KCXGUNFGBIXAGJHEHXGLBIRNGDOEBPUQSGBDIKACVORUBLKVVLZIHIJ
GSLWPIEUNCEPHFOMKFVMHUGNOPKBGLKCGCLHEXFAYUOMKTAGDZO
HEKFLVBWKVPLGXBPHEGIXOTJWURUUNCLSOFMKVWGFMFPIKGJLLJYO
GDWFRGLFQQEYDFVCAHYZPJGKFBIRQHEBAHELFHEFSVUCLWDBWIGJG
DRAYVKFPWLZNLQFGGJQAKFBLFUWQPWGJOBSLRIVVBXBDVUMHYIZY
BZKFGQLWROZIOBMACTPHSMGECLFGVOSGUNTUJYOGBIHECERCUGW
DEMFGKPAYSQKCBWONQVGEKVDHBIDWPHEMGEAQAONOEXZIOBMA
UNTUPHFYNXXGUNFGBIFNFMMFOXJBBDCLBIBIFJMHKVFLFJMHXNHXV
KUNKFZBTFFMHMFVLVWLYHHEMFOFICOJVUYXMFZNWLLWICLVSDZIFS
EBUNNXVUFIHARCXOZKMMFPKVRUUNVOWPSGLCQWUGCECJTGHIVK
WAFLPHAQVKPHHJSGMFHMRLDDHJZUBPTDBOFGVOSGUNTUJYOGXG
UNFGBIXAFMWAAQFPAIEQQQKCFIHAQWFIBPGLUBZNNNSOWDXMXG
UNFGBIEAHAKCAHAQSGRLMSKFWDBAHEFVMHWGPHFYBIUNTUJYOG
AIYXWAZIFLYNKCRUSOKVLKBOWARIBIHJ
In August 2019, Norbert Biermann published the solution of the bigram 1346 challenge as a comment on my blog. With this success, Norbert set a new world record for the shortest bigram ciphertext ever broken.
The Bigram 1000 Challenge
After Norbert had broken the Bigram 1346 message, I decided to create a new, even shorter challenge. This time, I took a plaintext with exactly 1000 letters. I encrypted it in the same way as the Bigram 1346 plaintext, calling it Bigram 1000 Challenge. Here’s the ciphertext:
IBFWNUNFEBVGDQBVTTMHLHUDVVZYBSKCWCUJNSCQYCXNEBSVFD
IYWCKZHKCDSUQBKBBBCYSIYYWMOVDLQXSIQXUGEEKBVOEEVJXYSE
MCUURBLXOVMSEBBFIBTBYFJMMERNVBRWQBIPUGEKJNZJPEBTVWW
KVVIBMEXIVHMERZXHCWWKIPACKHJNTEHKSVBNPYSOXYQOUUQMA
GVWSVLPBFBFHHXHLFJNVJKYTUSIBVBBMEJIDLFPYFRQCGDAEQZJVUZ
TWKEDEHYOKKWRBJVWNVZJUUBBBFXHBBEQHMRSRJDVLJSVMHQXB
FMKKEVRACDXGXVIBOXAMCAIOBQLIBFWEHYOVAXHVJRBDBHKSEHEU
URNIBPVFQKEKDNXDZBSUDBFKHYYTEHKKIIPUGVWWKVVBNIBFWXHV
JRBDBHKDHBXUUSVXHEQNZEFAIKHHIWKZERXKFBQYQZMTUNXOSXA
QXHRJJRQSUIBLINXWUKCUGEKJNZJPEBTVWWKVVMEFGBBVRBTXVGB
BXGFVRCWBBWCBSBJBITDRQJIJIRVZEKBWMUGRTTOHRQEVRACIBBUQ
XXZXFXYQOUUSEJAEOZJNBXHNLACZJTUSIBVBNWRIQLFKBVIKJTDHBZ
JOOIAONWAEKKEBOUGEKJNZJPEBTVWWKVVBFMSRTDUAIBZATCYEQ
HNUGPEBFUNRJHKSVTCRQCYBBTDRJHKJNXYXHMDZJUUBBMEXYKUU
SGBWRFGWMFQPYUGVIXHCWBBZNUGJYBUVVSIVBZSUGBSBJBITDRQ
GXTUBFAGWAPQRVAMACIBGKXZXVKJBNIBPVNSGWTCSUVGORYOTDI
BGKXPQXMUGKIWVRBJQXUGEKJNZJPEBTVWWKVVCDQXKZNCACHKL
DUUIBNITJCGYCXNDLVIVOQXBXLFPEAGKBUGEHWUKBBSHKSVZEQXU
GRQCGKHQXBZYYWMTRRXIBTUBQNVNCRTJORTVSNXTUSIBVTRVVFD
BHADTEUWIWAWCERJYFHKDL
Again, the challenge was broken and a new world record reached. This time, the solution came from Jarl Van Eycke and Louie Helm. They used highly sophisticated hill climbing techniques.
The Bigram 750 Challenge
After Bigram 1000 had been solved, I couldn’t help creating a new, even tougher challenge. Here it is:
YYXFTVUJKXMYWODAWFZPSAPPVDWNEXAJXFPPRXKCMFBZIXDLTC VIBSKLZOXIUKPEMUXFEMDUOGPCRRMWZSVBNMYYSHLWCIAJJWOR CFCHKYRXYYJVUPAGJHBZAJZPCJSEWZSEWZCJLFWOFHSAEMXZZU JHLNGNNMYYIXUVNMYYIXBWAOKYJRYCHUBMNOQTXAPCRRMWPPWZ AMLLPCXFEMWFITKYPGISZEKJMOMUXAEREKWGQTEOXILBUGGNTC YOYAHUUQZNKYBJADXIAFICRWCRFPPGZIEEBZHUIWKRKERRLZWF GQNAJRJQNTPYKBPEKBDLNGDYXPVAZSSKUVHUBBDLXAWFZUPNHZ CCRXGOLFZUHUGNVWDYRRSAJHTRZUXAXPKMYYYCHRXZDUQSLFDY KJIAZIDLGQNAQXBVWRSWGXPPAJMPDUPPVWAVNAORHUUWNBLNFM BSSAPPDVGCGCWFWYDYZEWOPETHDLMUZURXKJHMKJYUBVOJWYDY UGCYZPZIDLXFLWPCFSEXZRWFERWFIXDTYYWUVJPNAJZURXTFHZ OAXALZXITHDLBSKLZOXIUKJPYYSHLWCIAJXFZURLVWUNPCHUPT XZHCAJANBWLPKMHUVCWRKXKMBVCXCTHUHMNCQXVBTCNGADRHPC KWUGRRKBRQXFPGWAMUDYIXDLKJJSDUOGQTRRKBXILBUGBBIPDL XZZUWAOSDLYYZPYAZSVBKBGCJPUJXLLHDYIAKBVBZENMVCRWFA
This ciphertext has 750 letters. I call it the Bigram 750 challenge. Can a reader break it? If so, he or she will set a new world record.
Follow @KlausSchmeh
Further reading: Can you solve this Cold War encryption challenge?
Linkedin: https://www.linkedin.com/groups/13501820
Facebook: https://www.facebook.com/groups/763282653806483/
Kommentare (7)