Section 3.1 Alberti's Great Idea
Objectives
- Alberti's Biography
- Alberti's Polyalphabetic
- Modern/Vigenère's Polyalphabetic
Subsection 3.1.1 Alberti's Biography
For now see his biography on the MacTutor History of Mathematics Site: Leon Battista Alberti
Subsection 3.1.2 Alberti's Polyalphabetic Cipher
Definition 3.1.1. Polyalphabetic Substitution Cipher.
A polyalphabetic substitution cipher is a cipher in which a single plaintext letter maybe replaced by several different ciphertext letters, groups of letters, or symbols and every letter, group of letters, or symbol in the ciphertext may represent more than one plain text letter.
One of Leon Battista Alberti's greatest contributions to cryptology was not his cryptanalysis skills but an entirely new kind of cipher. Many efforts had been and would be made to shore up monoalphabetic substitution ciphers. Some of these efforts worked well enough but they were never sufficiently different to make them immune to the sorts of attacks we have studied before. Alberti made something truly different he invented a polyalphabetic substitution cipher. This was a cipher that did not just replace the plain text alphabet with a single separate alphabet but instead used multiple enciphering alphabets to create greater confusion and security.
The key to Alberti's new system was a device he called a “formula” . This was a cipher disk consisting of a fixed outer disk and a mobile inner disk. In his basic description of his new cipher he would use the outer ring of upper case letters for his plain text and the inner mobile ring of lower case letters for his cipher text.
“Say for example we mutually establish k as the index of the mobile circle. Writing, the formulae are positioned at will, say such k lies under the uppercase B [Figure 3.1.2] and the next letter corresponds to the letter that comes next. In writing to you, I will first put the uppercase B under which lies the index k in the formula; this is to signal you far away, wanting to read what I have written, that you should set up the twin formula in your keeping, positioning the mobile circle so that the B sits over the index k. Then all of the rest of the lowercase letters present in the coded text will take their meaning and sound from those of the fixed circle above them.”
“After I have written three or four words I will mutate the position of the index in our formula, rotating the disk let's say, so that the index k falls below the upper case R. Then in this missive I write an uppercase R to indicate that k no longer refers to B, but to R, and the letters that will follow will assume new meanings.” - Alberti [17, p. 181]
Comprehension Check:
- If you compare the inner and outer rings of the formula (cipher disk) what difference do you notice? Why do you think Alberti might have made these choices? (For reference I made an updated version in the appendix where I made similar choices, Figure C.0.6.)
- What step in the process above stops this from simply being a shift cipher?
- How does the recipient of a message using Alberti's method know how to set their disk and when they should change it?
- Is there an obvious weakness in the way that Alberti suggests using his system?
Checkpoint 3.1.3.
If you have not done so already make a copy of Alberti's formula [Figure 3.1.2] so that you can use it for enciphering and deciphering. Now encipher “See my first message” using an index of c initially underneath the G, but shift it underneath V after the first two words.
- Remember to line up the index c with the capital letters used of the key, here G and V.
- For Alberti, uppercase letters (the outer ring) are the plaintext and lowercase letters are the ciphertext.
- Because of what was and was not included on the disk you will need to make some choices.
G vbb ke V xsdba m&bbry&
Checkpoint 3.1.4.
Suppose that B lgiq R yam V ydme was enciphered using an index of k as directed by Alberti, what does it say?
- First identify the three key letters used in this cipher.
- Remember to line up the index k with the capital letters used of the key, and to move the index when the key letter changes.
- For Alberti, uppercase letters (the outer ring) are the plaintext and lowercase letters are the ciphertext.
cats and dogs
Checkpoint 3.1.5.
Team up with a partner and agree on a lower case index. Now each of you should try enciphering a short message, only five or six words, be sure to adjust your formula after every couple of words. Then exchange messages with your partner and decipher each others messages.
Subsection 3.1.3 Vigenère's Cipher
In spite of the fact that Alberti invented the polyalphabetic cipher his is not the name associated with it, instead that honor goes to the Frenchmen Blaise de Vigenère. Vigenère made a careful study of the cryptographers who had come before him and in 1586 he published the culmination of his work in his Traicté des chiffress, ou secrètes manières d'escrire[16]. In the Traicté he described a wide variety of older ciphers and his improvements to them. Among these was his take on Alberti's polyalphabetic cipher.
One of the key advances that Vigenère made was to replace the disk with a table [Figure 3.1.7, [16, p. 50b (102)] 1 ]. This made it easier to vary between alphabets without having to move inner and outer disks to different positions.
“... set the capitals which run across the top [of the table] for the message to be conveyed & those that run perpendicularly down the left for the keys. I have put two rows of capitals here, one black and the other red, to show that alphabets of the text as, the keys, may be transposed and changed in as many ways as you want to keep knowledge of them from all others except ones correspondents. Therefore, to encipher the saying we used previously “au nom de l'eternel,” with the key “le jour obscur” proceed in this way; from a in the alphabet across the top in red, come to the row with l and the box with b: u from e will be q: n from i, n: o from o, s: m from u, a: d from r, m: e from o, i: l from b, c: e from s, o: t from c, n: e from u, q: r from r, c: n from l, o: e from e, a: l from i, l. Altogether we get bqnsamiconcoal & so on for the remainder.” [16, pp. 49b, 50, 50b (100-102)], [11, p. 110] 2
Most of this translation is due to Mendelsohn [11], I have only filled in with my own at the end which he had not translated.
Comprehension Check:
- How did the a in the saying “au nom de l'eternel” get replaced with a b in the ciphertext bqnsamiconcoal?
- How did the u in the saying “au nom de l'eternel” get replaced with a q in the ciphertext bqnsamiconcoal?
- How did the first e in the saying “au nom de l'eternel” get replaced with a i in the ciphertext bqnsamiconcoal?
- How did the second e in the saying “au nom de l'eternel” get replaced with a o in the ciphertext bqnsamiconcoal?
- All four e's in the plaintext were replaced different ciphertexts, why and how did this happen?
Checkpoint 3.1.8.
To further check your understanding try enciphering the message “vive la france” using the key aider and the black (outer) rows in Figure 3.1.7, since there are more letters in the message than the key you will need to restart at the beginning of the key when you get to the end.
Try writing the key above the message so that you can keep track of how they correspond, like this:
Key: a i d e r a i d e r a i Plaintext: v i v e l a f r a n c e Ciphertext: Q O
Also, recall that you look up the letters in the message along the top and the key along the side.
Ciphertext: QOTEASLQACVI
Checkpoint 3.1.9.
To further check your understanding try enciphering the message “escargot” using the key ail; in Figure 3.1.7 use the red (inner) labels for the message and the black (outer) column for the key, since there are more letters in the message than the key you will need to restart at the beginning of the key when you get to the end.
Try writing the key above the message so that you can keep track of how they correspond, like this:
Key: a i l a i l a i Plaintext: e s c a r g o t Ciphertext:
Also, recall that you look up the letters in the message along the top and the key along the side.
Finally, enciphering (and deciphering) goes faster if you do all the characters enciphered with a particular key letter at one time; so first do everything enciphered with a, then i, and then l.
Ciphertext: IIREHXSL
Checkpoint 3.1.10.
Try deciphering the message NSDDTIMDQRHO using the key vilo and the black (outer) labels.
- Recall that the plaintext letters run along the top and the key letters are along the left side.
- You need to look up the ciphertext letters in the interior of the table.
- Line up the ciphertext and the key in the same way you lined up the plaintext and key previously.
Key: v i l o v i l o v i l o Ciphertext: N S D D T I M D Q R H O Plaintext: t o u
Plaintext: tour de france
Checkpoint 3.1.11.
Try deciphering the message DOLSAEXS using the key manger and the red (inner) labels.
Today when we use the Vigenère Cipher we use a table Figure C.0.8 which is simpler, and makes the resulting cipher a little easier to crack. The video below explains using the more modern table and you will play with the modern version in the exercises.