Tag: CrypTool 2

A few weeks ago, I was asked by a viewer of my YouTube channel (“Cryptography for everybody”) if there was an “affine cipher component” in CrypTool 2. After taking a look at all our components, I realized that there was no component that implemented this cipher. I made a video for new CrypTool 2 developers and how they may implement the affine cipher, as an example of how to build new CrypTool 2 components. But I never added such an affine cipher component to CrypTool 2. So I sat down and created a brand new component and also made a YouTube video about the cipher (see the video at the end of this blog article). Also, in this blog article I summarize the video and how the encryption process works. You’ll also learn about the size of the key space and the unicity distance of the affine cipher. I hope you enjoy reading the article and that you understand how the cipher works afterwards.

1. Introduction to the Affine Cipher

The affine cipher is essentially a monoalphabetic substitution cipher, which means each letter of the plaintext is substituted with another letter to form the ciphertext. This method can trace its origins back to the time of the Caesar cipher, a cipher used in ancient Rome.

Over the course of history, as the mathematical domain grew, so did the complexity and strength of ciphers. The affine cipher is a one of the first testaments to this growth, combining the principles of two basic ciphers: the additive and the multiplicative cipher.

An interesting aspect of the affine cipher, and the ciphers we’ll be discussing, is that they operate on numbers. The ciphers essentially translate each letter of the used alphabet (e.g. the Latin alphabet) into a number (and back), providing a platform for mathematical operations. This translation is quite straightforward:

2. The Additive Cipher

Let’s start with the basics. The additive cipher functions by adding an offset number to each letter, shifting it to the right. This is the underlying principle behind the famous Caesar cipher.

For this cipher:

• Key: The shift value, denoted as 𝒃
• Encryption: 𝑐 = (𝑝 + 𝑏) 𝑚𝑜𝑑 26
• Decryption: 𝑝 = (𝑐 - 𝑏) 𝑚𝑜𝑑 26

For example, consider a shift value (b) of 5:

Plaintext:  HELLO WORLD = 7 4 11 11 14 22 14 17 11 3
Ciphertext: MJQQT BTWQI = 12 9 16 16 19 1 19 22 16 8

3. The Multiplicative Cipher

The multiplicative cipher involves multiplying each letter with a specific number. This process essentially “randomly selects” a letter from the alphabet, but still for each plaintext letter always the same ciphertext letter.

Key elements:

• Key: The multiplication value, denoted as 𝒂. However, there needs to be an inverse (𝑎⁻¹) of this value for decryption. For a number 𝒂 to have a multiplicative inverse modulo m (here the alphabet size, which is 26), 𝒂 and m must be coprime, which means their greatest common divisor (GCD) is 1. In mathematical terms: gcd⁡(a,m)=1.
• Encryption: 𝑐 = (𝑝 ∙ 𝑎) 𝑚𝑜𝑑 26
• Decryption: 𝑝 = (𝑐 ∙ 𝑎⁻¹) 𝑚𝑜𝑑 26

To illustrate, let’s use 𝑎 = 5 (with its inverse 𝑎⁻¹ = 21):

Plaintext: HELLO WORLD = 7 4 11 11 14 22 14 17 11 3
Ciphertext: JUDDS GSHDP = 9 20 3 3 18 6 18 7 3 15

Note: Computing the inverse of a number in modular arithmetic is crucial. Techniques like the extended Euclidean algorithm (see https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm) come in handy, and we’ll delve into this in a future discussion (and youtube video :-))!

4. The Affine Cipher

Building on the previous concepts, the affine cipher is a combination of both additive and multiplicative ciphers.

Key components:

• Key: Comprises a multiplication value 𝒂 and a shift value 𝒃.
• Encryption: 𝑐 = (𝑝 ∙ 𝑎 + 𝑏) 𝑚𝑜𝑑 26
• Decryption: 𝑝 = (𝑐 − 𝑏) ∙ 𝑎⁻¹ 𝑚𝑜𝑑 26

For a hands-on example, using 𝑎 = 5 (inverse 𝑎⁻¹ = 21) and 𝑏 = 5:

Plaintext: HELLO WORLD = 7 4 11 11 14 22 14 17 11 3
Ciphertext: OZIIX LXMIU = 14 25 8 8 23 11 23 12 8 20

5. Keyspace Size and Unicity Distance

Understanding key spaces and unicity distances is essential for appreciating the security of a cipher:

• Keyspace size: For the affine cipher, we have 25 possible values for 𝒂 and 26 for 𝒃. However, 𝒂 and 26 need to be coprime. Thus, only specific values are valid for 𝑎 as they possess an inverse (𝑎⁻¹). These values are 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, and 25. The total key space is then 12 x 26 = 312.
• Unicity distance (𝑈): This concept helps determine the number of characters required to uniquely identify plaintext from its ciphertext. For the affine cipher, using the entropy of the key space (𝐻(𝐾)) and the redundancy of the English language (𝐷), the unicity distance is approximately 3. The equation to compute the unicity distance is U = H(K)/D.

In essence, the affine cipher, with its mathematical underpinnings and historical significance, offers an exciting glimpse into the world of cryptography. Whether you’re a beginner or an aficionado, diving into these ciphers can be both intriguing and rewarding. Stay tuned for more cryptographic adventures also with CrypTool 2

6. A YouTube Video About the Affine Cipher

Of course, I also made a YouTube video about the affine cipher. You may watch it here:

Some days ago, I saw a very interesting hand cipher called the “Grandpré cipher”. It is not interesting because it was very secure or original. It is interesting because the “keying process”, i.e. the search for words for usage as the key(s), was kind of tedious. In this blog article, I will explain the background of the cipher, how it works, and its keyspace size and unicity distance.

History of the Grandpré Cipher

The cipher is said to be first published by A. de Grandpré in his 1905 French book “Cryptographie pratique”. It was later named after the author. Unfortunately, I did not find any information on the author despite his (or her?) last name. So, I actually don’t know what the “A.” stands for. The description of the cipher itself can be found in the book on page 31. The chapter is named “Méthode de carre de 10×10”, which can be translated to “10×10 square method”. Grandpré defined the method for squares of 10×10, but squares with smaller sizes (9, 8, 7, 6) can also be used. We did also implement the cipher in a CrypTool 2 component. So if you want to try it by yourself, you may download CrypTool 2 to do so. Here, we show the original cover of Grandpré’s book:

Cryptographie pratique (1905) by A. de Grandpré

The American Cryptogram Association (ACA) has added the Grandpré cipher to its portfolio of “standard ciphers”. Their description of the cipher can be found here: https://www.cryptogram.org/downloads/aca.info/ciphers/Grandpre.pdf

The Grandpr´é cipher is a homophonic substitution cipher based on a keyword and several additional words. The cipher encrypts plaintext letters into two-digit ciphertext numbers. It uses a table to do so. We will discuss how this works in the next section.

Table Creation Based on Keyword and Words

First, we need to find 10 words (or less), depending on our selected table size. The table size depends on our chosen secret keyword. Let’s say our secret keyword is “VIMOUTIERS” as used by Grandpré in his book. This keyword has 10 letters, so our table has to be a 10×10-sized table.

Now, we have to find 10 more words, each starting with a letter of our secret keyword. So a word for “V”, let’s take “VOLUPTUEUX”, a word for “I”, let’s take “INQUIETUDE”, and so on. Of course, here, for the example, we used the same words which Grandpré used in his book. To create the table, we write the keyword in the first column and the additional words in the rows. Each word starts with one of the letters of the keyword. The final table looks like the one below. But besides adding only the words, we also add digit coordinates (from 1 to “keyword length”; 10 = 0) to the rows and columns:

10×10-table based on the keyword “VIMOUTIERS” as shown by Grandpré in his book

Encryption and Decryption

Now, we can use this table to encrypt a text. To encrypt a letter, we need to find it in the table. Then, we use the row R and column C to create our ciphertext symbol “RC”. Examples: E = “34”, A = “47”, E = “66”. Here, you can also see why the cipher is a homophonic substitution cipher. We have several options to choose from for most of the letters. But you can also see the drawback of the cipher. It is troublesome to find words for the table creation that contain all letters of our alphabet. Especially rarely used letters like Q and X are difficult to add to the table.

As an example, here is the encryption of the plaintext “HELLO WORLD”:

As you can see, we have several valid ciphertexts. Since the Grandpré cipher is a homophonic substitution cipher, we can use different homophones to create a variety of valid ciphertexts.

Clearly, the decryption of a given ciphertext is the inverse process. Here, you always take two digits and lookup the corresponding plaintext letter in the same table as used for encryption.

Keyspace Size and Unicity Distance

Here, we calculate the size of the keyspace and the unicity distance of the Grandpré cipher. We compute the largest possible keyspace obtained by using a 10×10 table.

For the 10 x 10 case, there are 10 ∙ 10 = 100 cells in the table. Thus, we have a total number of 26^100 = 2^470 tables. But we use English words and don’t use the complete “table space”. Thus, let’s consider English has about 2,000 10-letter words. Then, we would “only” have 2000^10 valide tables, which is about 2^110 different tables.

Now, based on the above computed keyspace, lets compute the unicitiy distance U. It is the minimum number of letters needed when cryptanalyzing a ciphertext which allows us to be able to obtain only one valid solution. Below this number, we can find multiple valid English texts. To compute the distance, we have to divide the entropy of the keyspace H(K) by the redundancy D of the English language:

We need a minimum of 35 letters to be able to obtain only a single valid solution through cryptanalysis. Clearly, a given ciphertext can be solved like any other digit-based homophonic substitution cipher :-).

A YouTube Video About the Cipher

I also made a YouTube video about the Grandpré cipher. You can watch it here 🙂

This is the third cipher of Félix-Marie Delastelle, a French hobby cryptographer, which I implemented in CrypTool 2. Delastelle published the four-square cipher in his book “Traité Élémentaire de Cryptographie“. He wrote the book in 1901 but it was published after Delastelle’s death in 1902.

The four-square cipher is a bigraphic monoalphabetic substitution cipher. Bigraphic means, that it always encrypts two plaintext letters at the same time. The cipher uses four Polybius squares, two of which are created using keywords.

Key Generation – Preparing the Four Polybius Squares

First, you have to prepare the four polybius squares. Let’s assume our keywords are “secret” and “keyword”:

Here, we created the second and third polybius squares using the previously chosen keywords. To create one of these polybius squares, the corresponding keyword is first written into the square from left to right and top to bottom. Here, if a letter occurs more than once, we omit it. In our example, we do not write the second “E” of “secret” again in the square. After writing the keyword, we fill the rest of the square with the remaining alphabet letters, which we did not already use for the keyword. After we created the second and third square, we fill the first and fourth square just with the alphabet. Since all the squares have only 25 positions, our alphabet consists of only 25 letters. Delastelle used “I” = “J” and did not include a “J” in his alphabet.

How Encryption works

Now, we can encrypt a plaintext using our four polybius squares. Here, for example we want to encrypt “HELLOWORLD”. To do so, we search the letter “H” in the first square and the letter “E” in the fourth square:

We create a connected “rectangle” where “H” is the upper corner and “E” is the lower corner. Now, we find our ciphertext letters in the two other corners of the so-created rectangle. Here, we encrypt the “H” by “G” and the “E” by “Y”. We continue encrypting our plaintext using this method to obtain the complete ciphertext:

To decrypt a given ciphertext, we just reverse the process. We look up the ciphertext letters (pair-wise) in the second and third square and find our plaintext letters in the first and fourth square.

Keyspace Size and Unicity Distance Computation

We compute the keyspace size by k = 25! * 25! = 2^167.36. This is, because we have to fill two polybius squares and a single polybius square has 25! possibilities to be filled with 25 letters.

We compute the unicity distance U by

Here, H(k) is the entropy of the keyspace and D is the redundancy of the language (here English). From the English Wikipedia: “In cryptography, unicity distance is the length of an original ciphertext needed to break the cipher by reducing the number of possible spurious keys to zero in a brute force attack”. In our case, we need more than 53 letters to be able to obtain only one valid plaintext.

A YouTube Video about the Four-Square Cipher

I also created a YouTube video about the four-square cipher (and how you can use it in CrypTool 2). Watch it here:

I recently made two videos about two interesting classical ciphers invented by Félix Marie Delastelle. Delastelle wrote a book on cryptography in 1901. Unfortunately, he died before his book was published in 1902. In his book, he describes several ciphers he invented. This blog post is about two of them: the bifid cipher and the trifid cipher.

The Bifid Cipher

The bifid cipher is a cipher which combines a Polybius square with transposition, and uses fractionation:

1. First, we use a keyword to create a 25-letter Polybius square
For example: “SECRET KEYWORD”:

2. Then, we encrypt the plaintext using the square, by writing the coordinates of the square below the plaintext. Example:

3. After that, we write the digits (transposed/fractionated) in a single row:

4. Finally, we decrypt the digits using the square to obtain the ciphertext:

The decryption is the reverse process. It is also possible to not encrypt the plaintext in one go. Instead, you can encrypt the ciphertext in blocks of n (n for example being 5).

The keyspace size and unicity distance (minimal number of letters needed in a ciphertext that allows having only a single valide solution) can be computed as follows:

The Trifid Cipher

The trifid cipher was invented by Félix Marie Delastelle as an extension of the above shown bifid cipher.

1. First, we use a keyword to create three 9-letter Polybius squares. For example: “SECRET KEYWORD”

2. Then, we encrypt the plaintext using the squares, by writing the number of the used square number and the coordinates below the plaintext. Example:

3. After that, we write the digits (transposed/fractionated) in a single row

4. Finally, we decrypt the digits using the three squares:

The decryption is the reverse process. It is also possible to not encrypt the plaintext in one go. Instead, you can encrypt the ciphertext in blocks of n (n for example being 5).

The keyspace size and unicity distance (minimal number of letters needed in a ciphertext that allows having only a single valide solution) can be computed as follows:

YouTube Videos about the Bifid and Trifid Ciphers

I made a YouTube video about the Bifid cipher. Here, you can also see how to use the bifid cipher component of CrypTool 2:

I also made a YouTube video about the Trifid cipher. Here, you can also see how to use the trifid cipher component of CrypTool 2: