VIC cipher May 31, 2010

As the story goes, in 1953 a paperboy discovered a hollowed-out nickel among his change. It contained a microfilm of lines and lines of numbers. The FBI uncovered little to nothing on the cipher used until a Russian agent (codenamed VICTOR) defected to the United States in 1957 and revealed its method.

The information in this node is adapted from the CIA's page by David Kahn and John Savard's page.

There are four pieces to the key (which both sides must know in order to communicate):

  1. a short keyword or phrase (containing the most common letters in your language)
  2. a line from a song (at least 20 characters)
  3. a date
  4. a personal number (assigned per agent)

Steps to its operation:

  1. Derive the intermediate keys for use in the following steps.
  2. Construct and apply the straddling checkerboard.
  3. Construct and apply the first transposition table.
  4. Construct and apply the second (disrupted) transposition table.
  5. Finalize the message by inserting the message indicator group.

Example Key

For this writeup I will use the following information as the key:

  1. a sin to err
  2. all the people are dead but I'm gonna keep dancing
  3. September 3, 1752 = 391752
  4. 15

Submechanism: Chain Addition

Employed at a few points below is a lagged Fibonacci generator, often called "chain addition" in the context of the VIC cipher. The procedure is simple. Given a number of starting digits, add the first two digits (without carrying) and append the result to the right side. Repeat with the second and third digits to get another, and so on. Example:

79068
^^
7 + 9 = 6

790686
 ^^
9 + 0 = 9

7906869
  ^^
0 + 6 = 6

79068696
   ^^
6 + 8 = 4

790686964
    ^^
8 + 6 = 4

7906869644
et cetera

Submechanism: Sequentialize

This process transforms N letters/digits into an N number sequence which contains all digits once (a permutation of 1, 2, ..., N). Start with 1 and label letters/numbers in alphabetical/numeric order. If there are duplicates, label them (increasing) from left to right. BOOK becomes 1342, TENLETTERS becomes 8154290367, and 33058420475481 becomes 3 4 13 8 11 5 2 14 6 10 9 7 12 1:

TENLETTERS
 1  2  3    Es
 1 42  3    L
 1542  3    N
 1542  36   R
 1542  367  S
8154290367  Ts*

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

* Here, zero is used instead of ten. This will suit our purposes better in some cases, and in others we will want to continue 10, 11, 12, ... (as in the 33058420475481 example).

1. Intermediate Keys

Split the first 20 letters of the song line into two groups of 10 and sequentialize each individually. We will call these two 10-digit groups S1 and S2.

    ALLTHEPEOP
S1: 1560428379

    LEAREDEADB
S2: 9610748253

Choose a random 5-digit message identifier, MI.

MI: 60115

Subtract, without borrowing, the first five digits of the key date (39175) from MI.

MI:      60115
date:  - 39175
       = 31040

Through chain addition, expand the resulting five digits to ten, and add these digits to S1 (without carrying) to obtain G.

       3104041444
S1:  + 1560428379
G:   = 4664469713

Below S2, write the sequence 1234567890. Locate each digit of G in the sequence 1234567890 and replace it with the digit directly above it in S2. The result is T.

S2:  9610748253
     1234567890

G:  4664469713
T:  0440045891

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

T:  0440045891
U:  4840493705
    2244320757
    4687527221
    0452799431
    4979683745

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.

15 + 4 = 19  (first transposition)
15 + 5 = 20  (second transposition)

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.

T:     0440045891
seqT:  8239045671
        w       v
U:     4840493705
       2244320757
       4687527221
       0452799431
       4979683745

Reading down from the "v", then the "w", and so on, we have: 57115 82649 44857 92298 30793 77247 05234 42404 04729 43576. Sequentialize the first 19 digits to get the key for the first transposition (K1), and the following 20 for the key for the second (K2). Of course, use the numbers you got above, which won't necessarily be 19 and 20.

First 19 digits:  5711582649448579229
K1:  9 13 1 2 10 15 3 12 6 17 7 8 16 11 14 18 4 5 19

Next 20 digits:  83079377247052344240
K2:  16 4 18 12 17 5 13 14 1 7 15 19 11 2 6 8 9 3 10 20

Sequentialize the last row of the U block to get C, the column headers for the straddling checkerboard.

U5:  4979683745
C:   2960581734

2. Straddling Checkerboard

The top line of letters in the checkerboard is given as a part of the key; here I use the Russian word СНЕГОПАД and English phrase "A SIN TO ERR". Above these letters are written the 10 digits of C (from the Intermediate Keys section above). The remaining letters of the alphabet are filled into the rows below, from top to bottom and then left to right. Each letter should be found exactly once in the whole checkerboard; skip any that would repeat.

The original cipher uses the Cyrillic alphabet, which would produce a checkerboard something like this:

  2 9 6 0 5 8 1 7 3 4
  С Н Е Г О П А
7 Б Ж . К * Р Ф Ч Ы Ю
3 В З , Л # Т Х Ш Ь Я
4 Д И ? М ^ У Ц Щ Э &

?  unknown
*  No
#  number shift
^  message begin
&  repeat

For Latin alphabet messages, a checkerboard may look like:

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

Suppose our message is:

ASSIGNED OBJECTIVES INVALIDATED . REPORT IMMEDIATELY TO SAFE HOUSE . AWAIT EXTRACTION INSTRUCTIONS WITHIN WEEK

Before encoding the message, divide it in two at a random point, swap these pieces, and place the message start indicator in between them. This makes it more difficult for an attacker to use common openings or closings to solve the cipher. In the Russian version, there is a character designated for this purpose---the English checkerboard above doesn't have a message start indicator, so I will use two full stops. Both parties should be privy to the convention and it shouldn't create message-altering ambiguity. (Using "#" may be a poor choice, as this is normally used to preface encoded numerals.)

IVES INVALIDATED . REPORT IMMEDIATELY TO SAFE HOUSE . AWAIT EXTRACTION INSTRUCTIONS WITHIN WEEK .. ASSIGNED OBJECT

Encode with the checkerboard, and we have:

64119 604123563925139 34 7138875 6454513962513533 58 924914683191 34 237265 147572425680 60957314256809 37654660 371140 34 34 2996360139 832301425

If the length of the message is not divisible by 5, add 1 to 4 nulls so that it is. This is so that later we can write the final product as a big list of 5-digit groups. Our message is 130 digits, so we're okay.

3. First Transposition

Create the transposition table by writing K1 (from the Intermediate Keys section) followed by the encoded message from the previous step, in rows of the same length, below the key:

K1:  9 13 1 2 10 15 3 12 6 17 7 8 16 11 14 18 4 5 19

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

Now copy off the columns (not including the top numbers in K1) from top to bottom, beginning with column "1", then "2", and so on:

1413046 1734660 0837539 538492 193239 1786313 3621443 5444200 6929666 9152061 3415644 4852778 4351853 9547832 6333903 6597531 2595112 2162045 361579

4. Second Transposition

This is a disrupted transposition. The disruption pattern is determined by the width of the table and the key. Here is an example of width eight, with irrelevant information masked out:

key:  X X 3 X 1 2 X X

      X X X X
      X X X X X   (A)
      X X X X X X
      X X X X X X X
      X X X X X X X X
      X X X X X
      X X X X X X (B)
      X X X X X X X
      X X X X X X X X
      X X
      X X X     (C)
      X X X X

Notice the leftmost part of the first triangular blank (A) begins below "1" in the key, diminishing by one digit per line until the fifth line, which contains no blanks. The second blank (B) then begins below "2" in the key, running for four lines, and the last blank (C) begins under the "3" and runs until the end of the message. If the entire key is exhausted before the end of the message, begin again at 1.

The message is copied into the rows of such a table, where the Xs would be, skipping over the blanks. After the X spots are all filled, return to the top and copy the rest of the message into the rows of blanks.

To make this sort of disrupted table for our example, we must first calculate its height by dividing the length of the message by the length of K2: 130 / 20 = 6 with remainder 10. So we need 7 rows to accomodate the message, and the last row will contain only 10 characters. The table for our example requires only one (partial) triangular blank area:

K2:  16 4 18 12 17 5 13 14 1 7 15 19 11 2 6 8 9 3 10 20

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

Remaining: 44 4852778 4351853 9547832 6333903 6597531 2595112 2162045 361579

And filling in the blank area with the remaining digits:

K2:  16 4 18 12 17 5 13 14 1 7 15 19 11 2 6 8 9 3 10 20

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

As in the first transposition, we now read off the columns, from top to bottom, beginning with column 1.

4398365 293325 486925 4359322 4039193 759123 4126566 740216 873561 335507 533511 3692606 6081424 1847491 486346 1771145 0653261 1433300 853749 529149

And rearrange into 5-digit groups:

43983 65293 32548 69254 35932 24039 19375 91234 12656 67402 16873 56133 55075 33511 36926 06608 14241 84749 14863 46177 11450 65326 11433 30085 37495 29149

5. Finalize the Message

The only remaining step is to insert the MI chosen at the beginning (60115) into the message. The final digit of the key date (2) indicates the distance the group should be from the end.

43983 65293 32548 69254 35932 24039 19375 91234 12656 67402 16873 56133 55075 33511 36926 06608 14241 84749 14863 46177 11450 65326 11433 30085 37495 60115 29149

To decrypt, read this node backward. Please report any errors or confusing bits.


jamestomasino has written an open-source AS3 implementation of VIC here, with a Flash interface.


Linked from: straddling-checkerboard