Using a Genetic Algorithm to Break Alberti Cipher

William Servos '06
Extended abstract submitted to the 2004 CCSCNE Conference
Keywords: Artificial Intelligence,Student Research,Genetic Algorithms

The Alberti Cipher was created by Leon Battista Alberti in 1467 and is considered in many ways to be the backbone of modern encryption. Alberti, a Renaissance Man to rival Da Vinci, created the first polyalphabetic cipher. Polyalphabetic ciphers cannot be solved by letter frequency analysis, since each consecutive letter is encrypted using a different alphabet than the one proceeding it. This differs from simple substitution ciphers, where the order of the letters in the plaintext alphabet is simply rearranged, but the new ciphertext alphabet which is produced remains constant.

The Alberti cipher also possesses rearranged alphabets, however, as the message is encrypted, with each new letter, the alphabet is rotated some arbitrary number of characters. This process eliminates consistencies in language, such as how in English e is the most common letter. To control this process, the key for an Alberti cipher is split into the cipher-alphabet, which is the permutated plaintext alphabet of the original message, and the shift key, which is some arbitrary word. The length and composition of the shift key determine how many alphabets the cipher has, with each letter in the shift key representing a shift in the cipher alphabet. Longer and more varied words create more complex ciphers. A simple substitution cipher can be simulated by any string of a single character, regardless of length. The complexity of a simple substitution cipher is, for English, twenty-six factorial (26!), while that of an Alberti cipher with a two character shift key is twice that, and increases as the length of the shift key does.

In this study the Alberti cipher is cracked using a Genetic Algorithm, designed specifically for solving the two part key, and written in Java. The data collected from the numerous experiments as well as an analytical look at the Alberti cipher will be included in the conference poster. The experimental data consists of repeated runs on varying length encrypted messages, and demonstrates the ability of a Genetic Algorithm to solve more complex forms of encryption consistently.

References