Write a VIC cipher decoder

Question

You've received a coded message from your ally that you know is encoded with the VIC cipher. As you know that the VIC cipher is notoriously convoluted, you want to write a program that will decode the VIC cipher but is small enough to hide from the enemy if you are captured, and thus uses as few bytes as possible.

Your instructions are as follows:

The information you have

• The encoded message. For this example, we'll use the message we encrypted in the "VIC cipher encoder" challenge: 71431 14842 71192 58619 04185 22614 14745 49924 32826 13348 02189 38641 70140 40252 44820 64522 43982 47921 71283 22694 94443 80642 14521
• A keyword with the most common letters of your chosen alphabet.
• A key phrase, such a quote or song lyric
• A date (or another number that is six digits or more)
• A personal agent number

In practice, these last four should be agreed upon beforehand by the sender and the recipient, including whether the agent number of the sender or the recipient is used in encoding.

What you and your ally agreed to use in your encoding is the following: the keyword SENATORI, the key phrase "The first principle is that you must not fool yourself — and you are the easiest person to fool.", and the date 3172016, and the recipient's agent number, 9.

Summary of steps

1. Derive the intermediate keys for use in the following steps and extract the message identifier from the encoded message.
2. Construct and apply the second (disrupted) transposition table in reverse.
3. Construct and apply the first transposition table in reverse.
4. Construct and apply the straddling checkerboard in reverse.
5. Finalize the decoding removing nulls and by starting the message at the "message begin" mark.

Submechanisms

Two more things to explain before we get into the meat of the matter: the processes of chain addition and sequentializing.

Chain addition, also known as a lagged Fibonacci generator, works by taking a starting digit sequence, adding the first two digits without adding and appending the result to the end. For example:

79081
7 + 9 = 6

790816
9 + 0 = 9

7908169
0 + 8 = 8

79081698
8 + 1 = 9

790816989
1 + 6 = 7

7908169897
... and so on

Sequentializing is essentially taking a sequence of letters or digits and labeling them by their alphabetical/numerical order. Duplicates are labelled left to right. For example:

E X A M P L E
    0         A
1   0       2 Es
1   0     3 2 L
1   0 4   3 2 M
1   0 4 5 3 2 P
1 6 0 4 5 3 2 X

3  3  0  5  8  4  2  0  4  7  5  4  8  1
      1              2                    0s
      1              2                 3  1
      1           4  2                 3  2
5  6  1           4  2                 3  3s
5  6  1        7  4  2  8        9     3  4s
5  6  1 10     7  4  2  8    11  9     3  5s
5  6  1 10     7  4  2  8 12 11  9     3  7
5  6  1 10 12  7  4  2  8 12 11  9 14  3  8s

I use zero-indexing here, but index however you like.

1. Intermediate Keys

Firstly, you need to retrieve the message identifier M from the message. The last digit of the date 3172016 is 6, so you know that the message identifier was placed sixth from the last in the message.

The encoded message = 
  71431 14842 71192 58619 04185 22614 14745 49924 32826 13348 02189 38641 
  70140 40252 44820 64522 43982 47921 71283 22694 94443 80642 14521
Message id = 47921

Split the first 20 letters of the key phrase into two groups of 10 and sequentialize each individually, which we will call S1 and S2.

    THEFIRSTPR
S1: 8201357946

    INCIPLEIST
S2: 2603751489

Subtract, without borrowing, the first five digits of the key date 3172016 from M:

M      47921
date - 31720
     = 16201

Chain add the result until you have ten digits:

1620178218

Add these digits to S1, without carrying, to obtain G:

     1620178218
S1 + 8201357946
G  = 9821425154

Above S2, write the sequence 0123456789. Locate each digit of G in the sequence 0123456789 and replace it with the digit directly below it in S2. The result is T.

   0123456789
S2 2603751489

G  9821425154
T  9806705657

Use chain addition to expand T by 50 digits. These digits, in five rows of ten, form the U block.

T  9806705657
U  7863751124
   5490262369
   9392885958
   2210634430
   4316978734

The last two non-equal digits of the U block are individually added to the agent's personal number to give the widths of the two transpositions, p and q.

9 + 3 = 12  (p, first transposition width)
9 + 4 = 13  (q, second transposition width)

Sequentialize T and use this sequence to copy off the columns of the U block, from top to bottom, into a new row of digits, V.

T     9806705657
seqT  9804612537

U     7863751124
      5490262369
      9392885958
      2210634430
      4316978734

V     69911 56837 12548 26533 30206 13947 72869 49804 84323 75924

Sequentialize the first p digits to get the key for the first transposition K1, and the following q digits for the key for the second K2.

First 12  6  9  9  1  1  5  6  8  3  7  1  2
K1        6 10 11  0  1  5  7  9  4  8  2  3

Next 13   5  4  8  2  6  5  3  3  3  0  2  0  6
K2        8  7 12  2 10  9  4  5  6  0  3  1 11

Finally, sequentialize the final row of the U block to get C, the column headers for the straddling checkerboard:

U5  4316978734
C   3105968724

2. Reverse the Second Transposition

We fill a transposition table with the message by columns in order of the column headings, K2. The message has 110 digits in 13 columns, leaves 8 full rows and six digits in a final row.

71431 14842 71192 58619 04185 22614 14745 49924 32826 13348 02189 38641 
70140 40252 44820 64522 43982 47921 71283 22694 94443 80642 14521

starts off with 

K2   8  7 12  2 10  9  4  5  6  0  3  1 11

              8                 7     4
              6                 1     2
              1                 4     7
              9                 3     1
              0                 1     1
              4                 1     9
              1                 4     2
              8                 8     5
              5

resulting in

K2   8  7 12  2 10  9  4  5  6  0  3  1 11

     0  6  0  8  2  6  4  2  8  7  2  4  9
     2  4  6  6  7  4  5  8  0  1  2  2  4
     5  1  4  1  1  5  4  2  2  4  6  7  9
     2  7  2  9  2  2  9  6  1  3  1  1  4
     4  0  1  0  8  2  9  1  8  1  4  1  4
     4  1  4  4  3  4  2  3  9  1  1  9  4
     8  4  5  1  2  3  4  3  3  4  4  2  3
     2  0  2  8  2  9  3  4  8  8  7  5  8
     0  4  1  5  6  8                 

Taking the rows one at a time, and stopping at the disrupted parts

K2   8  7 12  2 10  9  4  5  6  0  3  1 11

                                7  2  4  9  stop at 0
                                   2  2  4
                                      7  9
                                         4
                                            go all the way down until you run out of row
     4  1  4  4  3  4  2  3  9  1  1  9  4
     8  4  5  1  2  3  4  3  3  4  4  2  3
     2  0  2  8  2  9  3  4  8  8  7  5  8
     0  4  1  5  6  8

Result so far: 060826428 2466745801 51411542246 272922961311 4010829181414

The continue to avoid disrupted bits until the end...

K2   8  7 12  2 10  9  4  5  6  0  3  1 11

                                7  2  4  9  stop at 0
                                   2  2  4
                                      7  9
                                         4
                                            go all the way down until you run out of row
                                      9  4  restart until 1
                                         3

              5  6  8                       restart until 2

Result so far: 060826428 2466745801 51411542246 272922961311 4010829181414
41443423911 845123433442 2028293488758 041

Then grab the rest:

Result: 060826428 2466745801 51411542246 272922961311 4010829181414
41443423911 845123433442 2028293488758 041 7249 224 79 4 94 3 568

3. Reverse the First Transposition

As before, create the transposition table by filling in columns in order of the column headings, K1. With 110 digits and 12 columns, we have 9 full rows and 2 digits in a final row.

K1   6 10 11  0  1  5  7  9  4  8  2  3

              0
              6
              0
              8
              2
              6
              2
              4
              8

resulting in

K1   6 10 11  0  1  5  7  9  4  8  2  3

     4  0  7  0  2  0  1  2  9  3  1  2
     4  4  9  6  4  8  1  9  6  3  5  4
     1  1  4  0  6  2  8  3  1  4  1  6
     4  7  9  8  6  9  4  4  3  4  4  2
     4  2  4  2  7  1  5  8  1  2  1  7
     3  4  3  6  4  8  1  8  1  2  1  2
     4  9  5  4  5  1  2  7  4  0  5  9
     2  2  6  2  8  4  3  5  0  2  4  2
     3  2  8  8  0  1  4  8  1  8  2  2
     9  4

Reading of the rows in order, with no disruptions this time, we obtain:

407020129312 449648196354 114062831416 479869443442 424271581217 
343648181212 495451274059 226284350242 328801481822 94

4. Reversing the Straddling Checkerboard

The heading for the checkerboard is C = 3105968724. We fill in the first row with the keyword SENATORI and the rest of the alphabet is filled in as follows:

  3 1 0 5 9 6 8 7 2 4
  S E N A T O R I
2 B D G J L P U W Y .
4 C F H K M Q V X Z #

To decode we simply look up the each number in the checkerboard as we read them. First, 4 must be a row heading, so we move to 40 which is H. 7 is I. 0 is N. 2 is a row heading, so we move to 20 which is G. Continuing in this way, we reveal the original message:

HINGELSE.MOVETOSAFEHOUSEFOXTROT#3#..
WEAREDISCOVERED.TAKEWHATYOUCAN.BURNEVERYT?

The question mark at the end is from the final 4. As this is a row heading, there should be another number after this, but this is end of the message. Thus, we conclude that this is a null, and discard it.

HINGELSE.MOVETOSAFEHOUSEFOXTROT#3#..
WEAREDISCOVERED.TAKEWHATYOUCAN.BURNEVERYT

5. Finalize the Decryption

The program does not need to reinsert spaces and punctuation, but if there is a set convention for where the message originally began (here we used ..), cycle through the message until the message beginning is at the beginning.

The final decrypted message is:

WEAREDISCOVERED.TAKEWHATYOUCAN.
BURNEVERYTHINGELSE.MOVETOSAFEHOUSEFOXTROT#3#..

Notes for this challenge:

• You are given a minimum of five inputs: the message, the letter keyword, the key phrase, the date, and a personal number.
• You may assume all inputs are valid, with the correct number of digits and letters (5-digit message identifier, at least 20 digits for the key phrase, and so on). You may assume that the keyword and key phrase have already had all punctuation and spaces removed except for those that you allow in your version, and that numbers are denoted with number signs correctly.
• The encoded message should be either a string of space-separated five-digit groups, a list of five-digit integers, one long string without spaces, or something similar.
• I used zero-indexing and 0123456789 in my example. You may use 1-indexing and 1234567890, or some other system in your answer, as long as you specify what you used.

As always, if the problem is unclear, please let me know. Good luck and good golfing!

Answer 1

Python 3, 1446 bytes

This is even longer than my encoder. Golfing suggestions very welcome.

As this is a counter to my encoder, this also uses the uppercase Latin alphabet with additional characters . and #. The decoder also uses 0-indexing and 0123456789 when converting g to t.

I=int;L=list;E=len;R=range;B=str;J=''.join
def H(s,e):
 for i in R(e-E(s)):s+=chr(48+(ord(s[i])+ord(s[i+1]))%32%10)
 return s
def Q(s):
 r=[0]*E(s);s=L(s);a=R(E(s))
 for z in a:b=min(a,key=lambda i:s[i]);r[b]=z;s[b]="~"
 return r
def T(x,k):
 u=E(x);v=E(k);g=R(v);c=[x[i::v]for i in g];s=[0]*v
 for f in g:s[k[f]]=c[f]
 return J(s)
def U(x,k,d=0):
 c=[];w=[];u=E(x);v=E(k);g=R(v);n=u//v+1;l=u%v or v;e=0
 for j in g:c+=[[]]
 for j in g:i=k.index(j);c[i]+=L(x[e:e+n-(i>=l)]);e+=n-(i>=l)
 for z in R(n):
  w+=[[]]
  for j in c:w[z]+=j[z:z+1]
 if d:
  u=[];r=y=0;i=k.index(y)
  while r<n:
   u+=w[r][:i];w[r]=w[r][i:];i+=1;r+=1
   if i>v:y=(y+1)%v;i=k.index(y)
  for j in w:u+=j
  return J(u)
 else:return J(J(i)for i in w)
def C(m,s,w):
 t={s[-2:]:".",s[-1]*2:"#"};x=64;r='';j=z=n=0;e=-1;h=''
 while x<90:
  x+=1;v=chr(x)
  if v in w:t[s[w.index(v)]]=v
  else:t[s[z-2]+s[j]]=v;j+=z;z=(z+1)%2
 for j in R(E(m)):
  if(e>=0)*(j<e+2):continue
  else:e=-1
  if n:e=m.index(s[-1]*2,j+1);r+=m[j:e]+"#";n=0
  else:
   k=m[j]
   if h:r+=t[h+k];n=t[h+k]=="#";h=''
   elif k in s[:-2]:r+=t[k]
   else:h=k
 b=r.index("..")+2
 return r[b:]+r[:b]
def D(m,w,P,d,A):j=-I(d[-1]);m=m.split();M=m[j];m=J(m[:j]+m[j+1:]);t=J(B(Q(P[10:20])[I(J(B((I(H(J(B((I(M[i])-I(d[i]))%10)for i in R(5)),10)[i])+Q(P[:10])[i])%10)for i in R(10))[i])])for i in R(10));u=H(t,60)[10:];p=A+I(u[-2]);v=T(u,Q(t));return C(U(U(m,Q(v[p:p+A+I(u[-1])]),1),Q(v[:p])),J(B(i)for i in Q(u[40:])),w)

Ungolfing:

def chain_add(seq, end):
    for i in range(end - len(seq)):
        seq += chr(48+(ord(seq[i])+ord(seq[i+1]))%32%10)
    return seq

def sequent(seq):
    res = [0]*len(seq);seq=list(seq)
    for z in range(len(seq)):
        b = min(range(len(seq)),key=lambda i:seq[i])
        res[b] = z
        seq[b] = "~"
    return res

def transpose(text, keys):
    columns = ['']*len(keys)
    for t in range(len(text)):
        columns[t%len(keys)] += text[t]
    res = [0]*len(keys)
    for index in range(len(keys)):
        res[keys[index]] = columns[index]
    return''.join(res)

def untranspose(text, keys, disrupt=False):
    columns = []
    for j in range(len(keys)):
        columns += [[]]
    num_rows, len_last = divmod(len(text),len(keys))
    num_rows += 1
    if len_last == 0:
        len_last = len(keys)
    text_index = 0
    for j in range(len(keys)):
        ind = keys.index(j)
        columns[ind] += list(text[text_index:text_index+num_rows-(ind>=len_last)])
        text_index += num_rows-(ind>=len_last)
    rows = []
    for k in range(num_rows):
        rows += [[]]
        for j in columns:
            rows[k] += j[k:k+1]
    if disrupt:
        undisrupt = []
        current_row = 0
        stop_key = 0
        stop_index = keys.index(stop_key)
        while current_row < num_rows:
            undisrupt += rows[current_row][:stop_index]
            rows[current_row] = rows[current_row][stop_index:]
            stop_index += 1
            current_row += 1
            if stop_index > len(keys):
                stop_key = (stop_key + 1) % len(keys)
                stop_index = keys.index(stop_key)
        for i in rows:
            undisrupt += i
        return ''.join(undisrupt)
    else:
        return ''.join(''.join(i) for i in rows)

def uncheckerboard(message, seq, word):
    trans = {seq[-2:]:".", seq[-1]*2:"#"};x=64;res='';j=z=0
    while x<90:
        x += 1
        v = chr(x)
        if v in word:
            trans[seq[word.index(v)]] = v
        else:
            trans[seq[z-2] + seq[j]] = v
            j += z
            z = (z+1) % 2
    num = False
    end = -1
    h = ''
    for j in range(len(message)):
        if end>=0 and j<end+2:
            continue
        else:
            end = -1
        if num:
            end = message.index(seq[-1]*2,j+1)
            res += message[j:end]+"#"
            num = 0
        else:
            k = message[j]
            if h:
                res += trans[h+k]
                if trans[h+k] == "#":
                    num = 1
                h = ''
            elif k in seq[:-2]:
                res += trans[k]
            else:
                h = k
    begin = res.index("..") + 2
    return res[begin:] + res[:begin]

def decode(message, keyword, phrase, date, agent):
    mkey = -int(date[-1])
    message = message.split()
    m_id = message[mkey]
    message = ''.join(message[:mkey] + message[mkey+1:])

    s1 = sequent(phrase[:10])
    s2 = sequent(phrase[10:20])
    b = ''.join(str((int(m_id[i])-int(date[i]))%10) for i in range(5))
    a = chain_add(b, 10)
    g = ''.join(str((int(a[i])+int(s1[i]))%10) for i in range(10))
    t = ''.join(str(s2[int(g[i])]) for i in range(10))
    u = chain_add(t,60)[10:]
    p = agent+int(u[-2])
    q = agent+int(u[-1])
    seqT = sequent(t)
    v = transpose(u,seqT)
    k1 = sequent(v[:p])
    k2 = sequent(v[p:p+q])
    c = ''.join(str(i)for i in sequent(u[40:]))
    z = untranspose(message,k2,1)
    y = untranspose(z,k1)
    x = uncheckerboard(y,c,keyword)
    return x