How To Decrypt the Runes 3: The Vigenère cipher

Introduction


This is another long post, we have many interesting things to cover. It follows on from part 1 and part 2, where we developed some useful tools and a general method for solving pages based on: looking for patterns, forming a hypothesis and scoring many possibilities. In this post we will solve Pages 3-4 and Pages 14-16 (using the page numbering from this github). Last time we noticed they had lower 1-gram and 2-gram IoC values than true Runeglish:


                          1-gram IoC     2-gram IoC                            
War & Peace          1.77              4.97

Pages 3-4               1.17              1.59

Pages 14-16           1.11              1.89


These numbers suggest that trying a simple substitution cipher won’t be useful, and that is what we find. Therefore, we must try and find a different pattern. There are many different ways to solve these pages, here we will discuss techniques that use our pre-built tools and try and exploit information that we use when trying to decrypt the unsolved pages. In particular we will use the rune-word lengths. Before we do that we should discuss another way of thinking about substitution ciphers.


Rune Addition

The substitution cipher and shifting the runes using the cipher discs are related to the arithmetic of addition. This is because we can represent the shifts with numbers. For example, consider the following:


    ᚠ [0th rune in Gematria]  =  F
    ᚢ [1st rune in Gematria]  =  U
    ᚦ [2nd rune in Gematria]  = TH …

The number of runes from ᚠ to ᚢ is 1 so:

    ᚠ + 1 [0th rune + 1] = ᚢ = U
    ᚠ + 2 [0th rune + 2] = ᚦ = TH …

(In a very real sense) we have defined what it means to add a number to rune, with the result being another rune. In general, shifting a cipher disc N steps is similar to adding N to a rune to give a new rune. The cipher disc also gives us a visual way of showing what happens when we add numbers greater than the number of runes, the disc spins back round to the start and we keep counting, just like a clock. For example:


        ᚠ + 29 [0th rune + 29] = ᚠ              ᚠ + 30[0th rune + 30] = ᚢ, ...

Of course, we don’t need to use numbers, they’re just symbols, we could use the runes themselves to represent the numbers, or the Gematria Letters, (or anything, as long as we are consistent). In general, we can seamlessly switch between using numbers, runes or letters, and from now on we will.

Encryption with Rune Addition


We can use rune-addition to encrypt a message, if we add the same number to each rune this is the same substitution cipher discussed last time:


    Message Text (MT) = ᚠ,  ᚩ,   ᚱ,   ᚪ,    ᛚ,     ᛚ,     ᛁ,    ᛋ,    ᛋ,     ᚪ,   ᚳ,   ᚱ,   ᛖ,   ᛞ

    MT(Letters)             = F,  O,   R,  A,   L,    L,    I,    S,   S,    A,   C,  R,  E,   D

    MT(numbers)          = 0,   3,   4,  24,  20,  20,  10, 15, 15,  24,  5,  4,  18,  23

    MT(numbers)+1      = 1,   4,   5,  25,  21,  21,  11, 16, 16,  25,  6,  5,  19,  24

    CipherText(CT)       = U,   R,  C,  AE, NG, NG, J,   T,    T,   AE, G,  C,  M,  A


There is no reason to add the same number to each part of MT, we could add a series of numbers, defined by a Key (in the above example we could say the key was 1). For example with a key = 0,1,2,3,4,5 = F, U, TH, O, R, C = ᚠ, ᚢ, ᚦ, ᚩ, ᚱ, ᚳ) :

    
    MT (numbers) = 0,     3,      4,       24,       20,      20,     10, 15, 15, 24, 5, 4, 18, 23
    Key                 = 0,      1,      2,      3,         4,         5,       
    CT (numbers) = 0+0,  3+1,  4+2,  24+3,   20+4,  20+5, …


When we have run out of Key numbers we can try repeating the Key, giving:


    Key = 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 0, 1

    CT (numbers) = 0, 4, 6, 27, 24, 25, 10, 16, 17, 27, 9, 9, 18, 24

    CT (runes) = ᚠ, ᚱ, ᚷ, ᛡ, ᚪ, ᚫ, ᛁ, ᛏ, ᛒ, ᛡ, ᚾ, ᚾ, ᛖ, ᚪ


This type of encryption is often known the Vigenère cipher.


Spotting the Pattern in the Vigenère Cipher


The above Key had 6 runes and then repeated. This means that every 7th MT rune was encrypted using the same key rune (+0 starting from the first rune),


    and every 7th MT rune starting from the 2nd rune was encrypted with +1,

    and every 7th MT rune starting from the 3nd rune was encrypted with +2.

    and every 7th MT rune starting from the 4th rune was encrypted with +3…

    ... 

Another way of thinking about this is every 7th rune in the MT (no matter which rune you start with) is encrypted with the same substitution cipher. We know that the Index of Coincidence (IoC) is invariant (doesn’t change) for simple substitution ciphers and so there should be a pattern in the IoC that shows the MT leaking through into the CT. The pattern is found by trying to guess the key length.


Guessing the Key Length of the Vigenère Cipher


We take every Nth CT rune, where N is our guess of the key length, starting from the first rune, the 2nd rune, the 3rd rune … up to the Nth rune. This gives us N sets of CT runes, and we calculate the IoC for each set and then take an average. If we have guessed the correct N then we expect the IoC will be the same as Runeglish. In effect, we have ‘sliced’ out the different substitution ciphers. For example, taking the start of Pages 14-16:


    N = 1,   
    sliced CT part 1 = ᚪ, ᛋ, ᚹ, ᚪ, ᛁ, ᛈ, ᚢ, ᛟ, ᚫ, ᛈ, ᚠ, ᛖ, ᚱ, ᛋ, ᛈ, ᛈ …
    sliced IoC part 1 = 1.130


    N = 2
    Sliced CT part 1 = ᚪ, ᚹ, ᛁ, ᚢ, ᚫ, ᚠ, ᚱ, ᛈ, ᚦ, ᚾ, ᚱ, ᚹ …
    Sliced CT part 2 = ᛋ, ᚪ, ᛈ, ᛟ, ᛈ, ᛖ, ᛋ, ᛈ, ᛗ, ᚪ, ᛚ, ᛈ, …
    sliced IoC part 1 = 1.154,  sliced IoC part 2 = 1.078,
    mean IoC = 1.116


    N = 3
    Sliced CT part 1 = ᚪ, ᚪ, ᚢ, ᛈ, ᚱ, ᛈ, ᚾ, ᛚ, ᛖ, ᚢ, ᛁ …
    Sliced CT part 2 = ᛋ, ᛁ, ᛟ, ᚠ, ᛋ, ᚦ, ᚪ, ᚹ, ᚩ, ᛠ, ᚻ…
    Sliced CT part 3 = ᚹ, ᛈ, ᚫ, ᛖ, ᛈ, ᛗ, ᚱ, ᛈ, ᛈ, ᛁ, ᛞ …
    sliced part 1 IoC = 1.079,   sliced part 2 IoC = 0.928,  sliced CT part 3 IoC = 1.282
    mean IoC = 1.096 …

We keep doing this for increasing N {N, mean IoC of slices}:

{1, 1.13036}, {2, 1.1159}, {3, 1.09617}, {4, 1.10191}, {5,1.09158}, {6, 1.0742}, {7, 1.08002}, {8, 1.13691}, {9,1.05091}, {10, 1.05788}, {11, 1.04545}, {12, 0.988974}, {13, 1.91911}, {14, 1.08386}, {15, 0.923983}, {16, 1.1193}, {17,1.04865}, {18, 0.958243}, {19, 0.976393}, {20, 1.13065}

We have found a pattern: for N = 13 the IoC values match what we might expect from Runeglish. This is very good evidence a repeating key of length 13 has been used, and so we can now try and solve the pages.

Solving a Repeating Key Vigenère Cipher Using the word lengths as clues

We have to solve 13 different substitution ciphers. There are many ways to do this, here we will outline a brute-force method that uses our n-gram log probability tables.
A very quick way to solve the repeating key Vigenère that works very well with the runes uses the fact that we know how long each word is. Knowing (or, more correctly, assuming we know) the number of characters in each word is unusual for puzzles of this type and is one of the biggest clues we have to work with for the unsolved pages. We take a short sample of CT, preserving the word lengths:

        ᚪ, ᛋᚹᚪᛁ, ᛈᚢᛟᚫ, ᛈ, ᚠᛖᚱᛋᛈᛈ, ᚦᛗ, ᚾᚪᚱᛚᚹᛈ, ᛖᚩᛈᚢᛠᛁᛁᚻᛞ, ᛚᛟ, ᛠ, ᛂᛖ, ᛠ, ᛁᚫ, ᚷᛖ, ᚦᛟᛁᛞᛟ

We will apply partial keys spaced by 13 runes and try all possible 2-grams of the key. After we have applied the key we calculate the 2-gram log-probability score based on the position of the 2-gram in the word. For example (where DT is Decrypted Text):

    Key = F,F,_ ,_ ,_ ,_ ,_ ,_ ,_ ,_ ,_ ,_ ,_

    DT   = {A}, {S, _, _, _}, {_, _, _, _}, {_}, {_, _, _, S, P, _}, {_, _}, {_, _, _, _, _, _}, {_, _, P, U, _, _, _, _, _}, {_, _}, {_}, {_, _}, {_}, {I, AE}, {_, _}, {_, _, _, _, _}

    Key = F,U,_ ,_ ,_ ,_ ,_ ,_ ,_ ,_ ,_ ,_ ,_

    DT   = {A}, {X, _, _, _}, {_, _, _, _}, {_}, {_, _, _, S, EO, _}, {_, _}, {_, _, _, _, _, _}, {_, _, P, F, _, _, _, _, _}, {_, _}, {_}, {_, _}, {_}, {I, A}, {_, _}, {_, _, _, _, _}

    Key = F,TH,_ ,_ ,_ ,_ ,_ ,_ ,_ ,_ ,_ ,_ ,_

    DT   = {A}, {P, _, _, _}, {_, _, _, _}, {_}, {_, _, _, S, J, _}, {_, _}, {_, _, _, _, _, _}, {_, _, P, EA, _, _, _, _, _}, {_,_}, {_}, {_, _}, {_}, {I, D}, {_, _}, {_, _, _, _, _}
    …

We then try the 2nd, 3rd, 4th etc.  bi-gram of the key:

    Key = _,F,F,_ ,_ ,_ ,_ ,_ ,_ ,_ ,_ ,_ ,_

    DT   = {_}, {S, W, _, _}, {_, _, _, _}, {_}, {_, _, _, _, P, P}, {_, _}, {_, _, _, _, _, _}, {_, _, _, U, EA, _, _, _, _}, {_,_}, {_}, {_, _}, {_}, {_, AE}, {G, _}, {_, _, _, _, _}

    ... The final iteration will be ...  

    Key = _,_, _ ,_ ,_ ,_ ,_ ,_ ,_ ,_ ,_ ,EA,EA

    DT  = {_}, {_, _, _, _}, {_, _, _, _}, {_}, {_, E, R, _, _, _}, {_, _}, {_, _, _, _, _, _}, {E, O, _, _, _, _, _, _, _}, {_,_}, {_}, {_, E}, {EA}, {_, _}, {_, _}, {_, _, _, _, _}


We have 12 bigrams in the key and have tried each possibility from a set of 29^2 = 841 giving 10,092 different DT. We then look up the log-probability scores for the DT bigrams, where we know their position in the words (as indicated by the {} above). We choose the key values that give the highest scores to give:

    Key = F, I, R, F, U, O, S, E, R, E, N, S, O

    DT   = A, COAN, ISR(I)NG, A, LOUSON, THE, GNSTER, OFPLAINCH, THE, I, THO, AE, IS, THE, UMACE

Not exactly the right answer, but close enough to fill in the gaps by hand. Perhaps more interesting is that we have (basically) found the solution in a few seconds using a very short sample of the CT. A few tweaks gives:

    Key = F, I, R, F, U, M, F, E, R, E, N, F, E     

DT = A, COAN, DUR(I)NG, A, LESSON, THE, MASTER, EXPLAINED, THE, I, THE, I, IS, THE, UOICE, OL, JF, DFINFUFMFERDN, HY, JCPR, HNXN, MRAEETH, PW, IO, AEBTHMERC, WO, YIDDCJI, OHMC, OEAA, SNEOY, OM, SAICNR, DLLY, LB, JJ, A, AE(I)NGUCY, GMELAM, OEOAEOE, EAEATH, G, RGMB, NLUP, P, (I)NGOEUEA, PM, LIO, REAE, LDUXRY, CEA, TBYDPIOW, ABM, E(I)NG, XAEJJEE, YUS, TLMY, YR, BXLS, LN, MOJY(I)NGX, OM, SAICNR, DEOPTDMA, IOE, IC(I)NGDYCY, IOMA, TLIE, LN, UJGS(I)NG, EOAEB, WUIC, GAEM, WGJ, NAEYE, R(I)NG, (I)NGOEUEA, PM, IORYR, OBX, ID, IOEA, P, CIA, IOE, IC(I)NGDYCYE, BMCX, ERNUGTEOEAEOEAA

Something has gone wrong, around the text UOICE, OL, JF, DFINFUFMFERDN clearly we have more solving to do. We must find some more clues, and this problem requires some lateral thinking.

The Interrupter

What has happened is that the letter F in the plaintext message has not been encrypted, it has been used as an interrupter. An interrupter is a well-known technique in classical ciphers, for example, they are discussed in this classic text:


The interrupter causes the encryption algorithm to be skipped (or interrupted) when the algorithm sees that character. Here F is used, so each F in the plaintext is not encrypted and the algorithm passes over the F and encrypts the next letter. When we try F as in interrupter we can use the positions of F in the CT as possible places of F in the plaintext. The result can now be found, either by intelligent guessing, or by brute-forcing every possibility:

Interrupter positions = 49, 56
A, COAN, DUR(I)NG, A, LESSON, THE, MASTER, EXPLAINED, THE, I, THE, I, IS, THE, UOICE, OF, THE, CIRCUMFERENCE, HE, SAID, WHEN, ASCED, BY, A, STUDENT, TO, EXPLAIN, WHAT, THAT, MEANT, THE, MASTER, SAID, IT, IS, A, UOICE, INSIDE, YOUR, HEAD, I, DONT, HAUE, A, UOICE, IN, MY, HEAD, THOUGHT, THE, STUDENT, AND, HE, RAISED, HIS, HAND, TO, TELL, THE, MASTER, THE, MASTER, STOPPED, THE, STUDENT, AND, SAID, THE, UOICE, THAT, JUST, SAID, YOU, HAUE, NO, UOICE, IN, YOUR, HEAD, IS, THE, I, AND, THE, STUDENTS, WERE, ENLIGHTENED

Interestingly, we note that page 16 is not encrypted, even though it has the same images as the previous pages :

AN, INSTRUCTION, CWESTION, ALL, TH(I)NGS, DISCOUER, TRUTH, INSIDE, YOURSELF, FOLLOW, YOUR, TRUTH, IMPOSE, NOTH(I)NG, ON, OTHERS, CNOW, THIS

Solving Pages 3-4

Exactly the same procedure can be used to solve the remaining pages. Again, F is an interrupter, and the number of F’s in the plaintext make things a little more tricky, for example, guessing the key length using the above method is not as clear, but the signature is still there. Exploiting the word lengths and brute-forcing 2-grams is also useful, giving us a great start in a matter of seconds:

    Key = J, S, U, I, N, I, T, Y

    DT   = MPLCOME, WUSCOME, PIOURIM, TO, THU, UREAT, JOUTREY, TOWATE, THE, END

Some good guessing (or trying every possibility for the interrupter F) helps us arrive at:

    Key = D, I, V, I, N, I, T, Y       Interrupter positions = 48, 74, 84, 132, 159, 160, 250, 421, 443, 465, 514
    DT   = WELCOME, WELCOME, PILGRIM, TO, THE, GREAT, JOURNEY, TOWARD, THE, END, OF, ALL, TH(I)NGS, IT, IS, NOT, AN, EASY, TRIP, BUT, FOR, THOSE, WHO, FIND, THEIR, WAY, HERE, IT, IS, A, NECESSARY, ONE, ALO(I)NG, THE, WAY, YOU, WILL, FIND, AN, END, TO, ALL, STRUGGLE, AND, SUFFER(I)NG, YOUR, INNOCENCE, YOUR, ILLUSIONS, YOUR, CERTAINTY, AND, YOUR, REALITY, ULTIMATELY, YOU, WILL, DISCOUER, AN, END, TO, SELF, IT, IS, THROUGH, THIS, PILGRIMAGE, THAT, WE, SHAPE, OURSELUES, AND, OUR, REALITIES, JOURNEY, DEEP, WITHIN, AND, YOU, WILL, ARRIUE, OUTSIDE, LICE, THE, INSTAR, IT, IS, ONLY, THROUGH, GO(I)NG, WITHIN, THAT, WE, MAY, EMERGE, WIDSOM, YOU, ARE, A, BE(I)NG, UNTO, YOURSELF, YOU, ARE, A, LAW, UNTO, YOURSELF, EACH, INTELLIGENCE, IS, HOLY, FOR, ALL, THAT, LIUES, IS, HOLY, AN, INSTRUCTION, COMMAND, YOUR, OWN, SELF

Conclusions

We have covered much in this post. Again, the general method is based on looking for patterns, brute-forcing different possibilities and choosing results with high scores to investigate further.

• We have introduced the concept of addition with runes, based on our understanding of shifting runes with the cipher disc
  
• Rune addition can be expressed in terms of numbers, runes, or letters (it doesn’t really matter they are just symbols representing how many shifts you apply to the cipher disc)
  
• Each separate rune in MT can be encrypted with a different shift, resulting in the Vigenère Cipher
  
• A key is used to represent the different shifts
  
• If the key repeats then information on the key length leaks through to the CT and can be found with the IoC
  
• Assuming we know the word lengths of the CT gives us a very strong start to decrypting with little effort
  
• The letter F has been used by the puzzle makers as an interrupter. These can be bruteforced, because we know a CT F may be a plaintext F, or we can use some intelligence

*Comments, questions, suggestions, omissions etc ? please try #cicadasolvers

MSGA