# Problem of the week, 137

A former colleague Bill Wardlaw (March 3, 1936-January 2, 2013) used to create a “Problem of the Week” for his US Naval Academy students, giving a prize of a cookie if they could solve it. One of them is given below.

Chain addition is a technique employed in cryptography for extending a short sequence of digits, called the seed to a longer sequence of pseudorandom digits. Quoting David Kahn (in Kahn on Codes, MacMillan, New York, 1983, p. 154), “the first two digits of the [seed] are added together modulo 10 [which means they are added and the carry is neglected] and the result placed at the end of the [sequence], then the second and third digits are added and the sum placed at the end, and so forth, using also the newly generated digits when the [seed] is exhausted, until the desired length is obtained”. Thus, the seed 3964 yields the sequence 3964250675632195… .

Periodic pattern

a. Show that this sequence eventually repeats itself.
b. Show that the sequence begins repeating itself with “3964”.
c. EXTRA CREDIT: How many digits are there before the first repetition of “3964”?

# The Vigenère cipher and Sage

The Vigenère cipher is named after Blaise de Vigenère, a sixteenth century diplomat and cryptographer, by a historical accident. Vigenere actually invented a different and more complicated cipher. The so-called “Vigenère cipher” cipher was actually invented by Giovan Batista Belaso in 1553. In any case, it is this cipher which we shall discuss here first.

This cipher has been re-invented by several authors, such as author and mathematician Charles Lutwidge Dodgson (Lewis Carroll) who claimed his 1868 “The Alphabet Cipher” was unbreakable. Several others claimed the so-called Vigenère cipher was unbreakable (e.g., the Scientific American magazine in 1917). However, Friedrich Kasiski and Charles Babbage broke the cipher in the 1800’s [1]. This cipher was used in the 1700’s, for example, during the American Civil War. The Confederacy used a brass cipher disk to implement the Vigenère cipher (now on display in the NSA Museum in Fort Meade) [1].

The so-called Vigenère cipher is a generalization of the Cesaer shift cipher. Whereas the shift cipher shifts each letter by the same amount (that amount being the key of the shift cipher) the so-called Vigenère cipher shifts a letter by an amount determined by the key, which is a word or phrase known only to the sender and receiver).

For example, if the key was a single letter, such as “C”, then the so-called Vigenère cipher is actually a shift cipher with a shift of 2 (since “C” is the 2-nd letter of the alphabet, if you start counting at 0). If the key was a word with two letters, such as “CA”, then the so-called Vigenère cipher will shift letters in even positions by 2 and letters in odd positions are left alone (or shifted by 0, since “A” is the 0-th letter, if you start counting at 0).

REFERENCES:
[1] Wikipedia article on the Vigenere cipher.

Using Sage, let’s look at a message (a chant at football games between rivals USNA and West Point):

sage: AS = AlphabeticStrings()
sage: A = AS.alphabet()
sage: VC = VigenereCryptosystem(AS, 1) # sets the key length to be = 1
sage: m = VC.encoding("Beat Army!"); m  # trivial example
BEATARMY


Now, we choose for illustration a simple key of length 1, and encipher this message:

sage: key = AS("D")
sage: c = VC.enciphering(key, m)
sage: c  # a trivial example
EHDWDUPB


You see here that in this case the cipher boils down to the Caesar/shift cipher (shifting by 3).

Deciphering is easy:

sage: VC.deciphering(key, c)
BEATARMY


Next, we choose for illustration a simple key of length 2, and encipher the same message:

sage: VC = VigenereCryptosystem(AS, 2)
sage: key = AS("CA")
sage: m = VC.encoding("Beat Army!"); m
BEATARMY
sage: c = VC.enciphering(key, m); c
DECTCROY


Since one of the key letters is “A” (which shifts by 0), half the plaintext is unchanged in going to the ciphertext.

Here is the algorithmic description of the above (so-called) Vigenère cipher:

    ALGORITHM:
INPUT:
key - a string of upper-case letters (the secret "key")
m - string of upper-case letters (the "plaintext" message)
OUTPUT:
c - string of upper-case letters (the "ciphertext" message)

Identify the alphabet A, ..., Z with the integers 0, ..., 25.
Step 1: Compute from the string key a list L1 of corresponding
integers. Let n1 = len(L1).
Step 2: Compute from the string m a list L2 of corresponding
integers. Let n2 = len(L2).
Step 3: Break L2 up sequencially into sublists of size n1, and one sublist
at the end of size <=n1.
Step 4: For each of these sublists L of L2, compute a new list C given by
C[i] = L[i]+L1[i] (mod 26) to the i-th element in the sublist,
for each i.
Step 5: Assemble these lists C by concatenation into a new list of length n2.
Step 6: Compute from the new list a string c of corresponding letters.


Once it is known that the key is, say, n characters long, frequency analysis can be applied to every n-th letter of the ciphertext to determine the plaintext. This method is called “Kasiski examination“, or the “Kasiski attack” (although it was first discovered by Charles Babbage).

The cipher Vigenère actually discovered is an “auto-key cipher” described as follows.

ALGORITHM:
INPUT:
key - a string of upper-case letters (the secret "key")
m - string of upper-case letters (the "plaintext" message)
OUTPUT:
c - string of upper-case letters (the "ciphertext" message)

Identify the alphabet A, ..., Z with the integers 0, ..., 25.
Step 1: Compute from the string m a list L2 of corresponding
integers. Let n2 = len(L2).
Step 2: Let n1 be the length of the key. Concatenate the string
key with the first n2-n1 characters of the plaintext message.
Compute from this string of length n2 a list L1 of corresponding
integers. Note n2 = len(L1).
Step 3: Compute a new list C given by C[i] = L1[i]+L2[i] (mod 26), for each i.
Note n2 = len(C).
Step 5: Compute from the new list a string c of corresponding letters.


Note how the key is mixed with the plaintext to create the enciphering of the plaintext to ciphertext in Steps 2 and 3.

A screencast describing this has been posted to vimeo.

# Bifid cipher and Sage

The Bifid cipher was invented around 1901 by Felix Delastelle. It is a “fractional substitution” cipher, where letters are replaced by pairs of symbols from a smaller alphabet. The cipher uses a 5×5 square filled with some ordering of the alphabet, except that “i”‘s and “j”‘s are identified (this is a so-called Polybius square; there is a 6×6 analog if you add back in “j” and also append onto the usual 26 letter alphabet, the digits 0, 1, …, 9). According to Helen Gaines’ book “Cryptanalysis”, this type of cipher was used in the field by the German army during World War I.

The Bifid cipher was discusses in Alasdair McAndrew’s book on Cryptography and Sage. We shall follow his discussion. As an example of a Polybius square for the Bifid cipher, pick the key to be “encrypt” (as Alasdair does). In that case, the Polybius square is $\left(\begin{array}{rrrrr} E & N & C & R & Y \\ P & T & A & B & C \\ D & E & F & G & H \\ I & K & L & M & N \\ O & P & Q & R & S \end{array}\right).$ BTW, the $6\times 6$ analog is: $\left(\begin{array}{rrrrrr} E & N & C & R & Y & P \\ T & A & B & C & D & E \\ F & G & H & I & J & K \\ L & M & N & O & P & Q \\ R & S & T & U & V & W \\ X & Y & Z & 0 & 1 & 2 \end{array}\right)$.

Here is Sage code to produce the $6\times 6$ case (the $5\times 5$ case is in Alasdair’s book):

def bifid(pt, key):
"""
INPUT:
pt - plaintext string      (digits okay)
key - short string for key (no repetitions, digits okay)

OUTPUT:
ciphertext from Bifid cipher (all caps, no spaces)

This is the version of the Bifid cipher that uses the 6x6
Polybius square.

AUTHOR:
Alasdair McAndrew

EXAMPLES:
sage: key = "encrypt"
sage: pt = "meet me on monday at 8am"
sage: bifid(pt, key)
[[2, 5], [0, 0], [0, 0], [1, 0], [2, 5], [0, 0], [3, 0],
[0, 1], [2, 5], [3, 0], [0, 1], [1, 3], [1, 1], [0, 4],
[1, 1], [1, 0], [5, 4], [1, 1], [2, 5]]
'HNHOKNTA5MEPEGNQZYG'

"""
AS = AlphabeticStrings()
A = list(AS.alphabet())+[str(x) for x in range(10)]
# first make sure the letters are capitalized
# and text has no spaces
key0 = [x.capitalize() for x in key if not(x.isspace())]
pt0 = [x.capitalize() for x in pt if not(x.isspace())]
# create long key
long_key = key0+[x for x in A if not(x in key0)]
n = len(pt0)
# the fractionalization
pairs = [[long_key.index(x)//6, long_key.index(x)%6] for x in pt0]
print pairs
tmp_cipher = flatten([x[0] for x in pairs]+[x[1] for x in pairs])
ct = join([long_key[6*tmp_cipher[2*i]+tmp_cipher[2*i+1]] for i in range(n)], sep="")
return ct

def bifid_square(key):
"""
Produced the Polybius square for the 6x6 Bifid cipher.

EXAMPLE:
sage: key = "encrypt"
sage: bifid_square(key)
[E N C R Y P]
[T A B C D E]
[F G H I J K]
[L M N O P Q]
[R S T U V W]
[X Y Z 0 1 2]

"""
AS = AlphabeticStrings()
A = list(AS.alphabet())+[str(x) for x in range(10)]
# first make sure the letters are capitalized
# and text has no spaces
key0 = [SR(x.capitalize()) for x in key if not(x.isspace())]
# create long key
long_key = key0+[SR(x) for x in A if not(x in key0)]
# the fractionalization
pairs = [[long_key.index(SR(x))//6, long_key.index(SR(x))%6] for x in A]
f = lambda i,j: long_key[6*i+j]
M = matrix(SR, 6, 6, f)
return M
`

Have fun!