Cryptology The Invention of Polyalphabetic Substitution

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

Polyalphabetic Encryption in Renaissance

• Leon Battista ALBERTI (1404 – 1472)
  • »Father of modern cryptography«.
  • 1466: Cipher disk with a fixed permuted alphabet.
  • [ALBERTI also is regarded as the father of modern architecture. In particular he invented a method of perspective drawing with the help of grid lines.]
• TRITHEMIUS (Johannes Heydenberg from Trittenheim/Mosel in Germany, 1462 – 1516)
  • Steganographia (1499—printed only 100 years later) (disk cipher with standard alphabet).
  • Polygraphiae (1508—first printed book on cryptography): tabula recta (»Vigenère Table«, but this was already described by AD-DURAIHIM, maybe also by Johannes Fontana 1430).
  • [A mixture of cryptography and other »secret sciences« such as alchemy.]
• Jacopo SILVESTRI
  • Opus Novum (1526—second printed book on cryptography).
  • Much more concrete and practical than the writings by Trithemius; disk cipher, grille, cryptanalysis.
• Giovan Battista BEL(L)ASO (1505 – after 1564)
  • Book 1553: choice of shifted alphabet according to a key word.
  • See also: Augusto Buonafalce, »Bellaso's reciprocal ciphers«, Cryptologia 30 (2006), 39-51.
  • Autokey cipher (»autoclave«).
• Giovan(ni) Battista (della) PORTA (1535 – 1615)
  • 1563: General idea of polyalphabetic cipher,
  • cipher disk + keyword.
  • [The general idea was not considered manageable; only procedures with primary + shifted secondary alphabets came into use.]
• Blaise de VIGENÈRE (1523 – 1596)
  • Traicté des Chiffres 1585: table à la TRITHEMIUS but with a permuted alphabet.
• Giovanni Battista ARGENTI (? – 1591)
  • Cryptoanalysis of the BELLASO cipher by key guessing.
• Matteo ARGENTI (1561 – 1610?)—nephew of G. B.
  • Manual of Renaissance Cryptology.

Monoalphabetic substition may have developed to polyalphabetic substitution in the following steps (speculatively):

• Monoalphabetic substitution with permutation table.
• Cipher disk with fixed position as replacement for the permutation table.
• Easy change of alphabet by turning the disk to another position.
• Alphabet change inside a single message (ALBERTI).
• Progressive alphabet change after each letter (TRITHEMIUS).
• Key dependent change of alphabet after each letter (BELLASO).
• General polyalphabetic encryption (PORTA).

ALBERTI's cipher disk may have been inspired by some similar devices already in use as »mnenomic instruments«. FONTANA in 1430 even describes a device similar to the JEFFERSON cylinder. The cryptologic significance of these devices is yet a matter of speculation. See:

• Horst Kranz, Walter Oberschelp: Mechanisches Memorieren und Chiffrieren um 1430: Johannes Fontanas Tractatus de instrumentis artis memorie. Franz Steiner Verlag, Stuttgart 2009.
• Review of this book by Gerhard F. Strasser in Cryptologia 38 (2014), 96–101.

However we should not assume that polyalphabetic encryption played a major role in Renaissance. We find evidence for sporadic use only. Far more often people used the nomenclator, and there were many more famous cryptologists in Italian Renaissance than those listed above. Noteworthy usage of polyalphabetic ciphers we find only in the 19th Century.

TRITHEMIUS table (misnamed after VIGENÈRE)

This table is used for polyalphabetic substitution with the standard alphabet and its cyclically shifted secondary alphabets. It has as many rows as the alphabet has letters. The first row consists of the original alphabet. Each of the following rows has the alphabet cyclically shifted one position further to the left. For the standard alphabet this looks like this:

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
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 A
C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
Z A B C D E F G H I J K L M N O P Q R S T U V W X Z

Trithemius used it progressively, that is, he used the alphabets from top to down one after the other for the single plaintext letters, with cyclic repetition.

Note that this procedure involves no key and therefore is not an encryption in the proper sense. Its security is only by obscurity.

Notwithstanding this weakness Trithemius's method results in a crucial improvement over the monoalphabetic substitution: Each letter is encrypted to each other the same number of times in the mean. The frequency distribution of the ciphertext is perfectly uniform.

The BELLASO cipher (misnamed after VIGENÈRE)

[Note that even Vigenère himself attributes this cipher to Bellaso.]

This encryption method uses the Trithemius table but with the alphabet choice controlled by a keyword: for each plaintext letter choose the row that begins with this letter. This method uses a key and therefore is a cipher in the proper sense.

Example: take the keyword MAINZ

Then the 1st, 6th, 11th, ... plaintext letter is encrypted with the »M row«, the 2nd, 7th, 12th, ... with the »A row« and so on.

Note that this results in a periodic Caesar addition of the keyword:

     p o l y a l p h a b e t i c
     M A I N Z M A I N Z M A I N
     ---------------------------
     B O T L Z X P P N A Q T Q P

For a more general definition of the BELLASO cipher see the Mathematical description.

The first one who gave an algebraic description of this cipher as addition apparently was was the French scholar Claude COMIERS in his 1690 book using a 18 letter alphabet. Lacking a suitable formal notation his description was quite long-winded. Source:

Joachim von zur Gathen: Claude Comiers: The first arithmetical cryptography. Cryptologia 27 (2003), 339–349.

For the history of renaissance cryptography see also

Paolo Bonavoglia: Ballaso's 1552 cipher recovered in Venice. Cryptologia 43 (2019), 459–465.

Paolo Bonavoglia: Trithemius, Ballaso, Vigenère—Origins of the polyalphabetic ciphers. HistoCrypt 2020, 46–51.

Exercise. Encrypt a text of about 200 letters (3 to 4 lines) with the BELLASO cipher using a key of at least seven letters.