Math for Devs - Encryption Essentials

Encryption is something that we use extensively in computer science. It's an indispensable technique in systems connected through a network or those containing sensitive data. But what most people don't know, is that cryptography is essentially math. So when you encrypt a message, you are basically using a mathematical algorithm to hide your message.

History of Encryption

While encryption as a way to secret a message is central to computer science, its roots go much deeper. Ancient civilizations utilized encryption techniques long before the advent of modern computing. The first known evidence of cryptography was found in an inscription carved around 1900 BC in Egypt. Another famous early cryptographic method was the "Caesar Cipher," used by the Roman consul Julius Caesar to transmit secret messages to his generals during military campaigns.

Cryptography assumed a more prominent role during the World Wars, especially during World War II. The Nazis developed the "Enigma" machine to encrypt radio transmissions, making communication more secure. The complexity of the Enigma encryption far surpassed that of the Caesar Cipher. It employed cipher keys for encrypting messages, and these keys were rotated daily. Polish cryptanalysts initially made significant progress in understanding how the Enigma worked. Later, Alan Turing and his team in Britain built on this work and developed a machine and algorithms to deduce the daily key settings of the Enigma.

Math concepts used in Cryptography

1. Number Theory: modular arithmetic, and prime numbers are widely used in public key cryptographic schemes.

2. Probability and Statistics: Used to evaluate the randomness of algorithms, analyze potential vulnerabilities

3. Combinatorics: Helpful in understanding the strength of cryptographic systems by determining possible combinations or permutations, especially in brute-force attacks. Permutations are also a way to ensure that the encryption algorithm is non-linear and "mixed" relative to the input.

4. Linear Algebra: Plays a role in several cryptographic protocols and systems. Classic algorithms such as "Hill Cipher" are heavily based on linear algebra, more specifically matrices operations.

5. Information Theory: Concepts like entropy are used to measure and ensure the unpredictability and randomness necessary in cryptographic systems.

Understanding some Cryptographic Algorithms

In this section we are gonna discuss some basic Cryptographic Algorithms, and how they use math in its implementations.

Caesar Cipher: A Linear Shift in Alphabets

The Caesar Cipher is one of the earliest and simplest forms of encryption. It involves shifting each letter in a message by a predetermined number of positions in the alphabet. In a way, it's a linear transformation of each letter in the text.

How it Works:

Imagine the alphabet as a linear array of characters:
A B C D ... Z

When you want to encrypt a letter using the Caesar Cipher, you simply move it down (or up) by a certain number of spaces, wrapping around when you reach the end of the alphabet. This "certain number" is known as the shift.

For instance, with a shift of 3:

• A becomes D
• B becomes E
• C becomes F ... and so on.

The formula for each letter transformation is essentially:
$C \space = \space (P + s) \space \space mod \space 26$
Where:

• $C$ is the resulting cipher text letter
• $P$ is the plaintext original letter
• $s$ is the shift case (in our case 3)
• $mod \space 26$ just ensures we wrap around if we go beyond $Z$ .

Given our example shift of 3, the message:

SCALA IS THE BEST PROGRAMMING LANGUAGE

would translate to:

VFDOD LV WKH EHVW SURJUDPPLQJ ODQJXDJH

To decrypt, you'd shift back by the same amount.

Though a Caesar Cipher is simple and easy to break today, it was innovative during its time and serves as a foundational concept in cryptography.

Hill Cipher

In classical cryptography, the Hill cipher is a substitution cipher based on linear algebra. Invented by Lester S. Hill in 1929, it is a subsitution cipher just like Caesar Cipher, but it is more powerful because it uses a public key signature to encrypt the text.

We can use this table as a base to the mod 26 alphabet mapping:

Encrypting the text

Let's suppose we have the following message that we want to encrypt:

PELE IS THE GREATEST FOOTBALL PLAYER OF ALL TIME

With the text in hands, now we define our encryption key.

1. Encryption Key

In Hill Cipher, the encryption key is a square matrix, it means that its dimensions should be 2x2 , 3x3 , 4x4 and so on. For our example, let's use a 3x3 matrix, but keep in mind that for more secure keys you should use a bigger key matrix to make brute-force attacks more challenging.

2. Splitting the text in blocks

The second step involves dividing the input text into blocks. Given that we're working with a 3x3 matrix, it's necessary to segment the text into blocks of three characters each. So, at the end of this segmentation, our blocks will look like this:

PEL EIS THE GRE ATE STP LAY ERO FAL LTI MEE

Observe that when spaces are removed, our sentence doesn't neatly divide by three. To fix this, we've duplicated the final character to ensure a complete block of three characters.

3. Convert each block into a column vector

To do this, we have to use the table above as a reference. With the table, we can map a letter to its corresponding number. Let's see how it works:

$''PEL'' \rightarrow \begin{bmatrix} 15 \\ 4 \\ 11 \\ \end{bmatrix}$

$''EIS'' \rightarrow \begin{bmatrix} 4 \\ 8 \\ 18 \\ \end{bmatrix}$

$''THE'' \rightarrow \begin{bmatrix} 19 \\ 7 \\ 4 \\ \end{bmatrix}$

$...$

$...$

$...$

$''MEE'' \rightarrow \begin{bmatrix} 12 \\ 4 \\ 4 \\ \end{bmatrix}$

Note: I hadn't showed all the substitutions, so you need to do the rest with the other blocks. I did only the first 3 ones and the last.

4. Multiply each column vector by the key matrix

Now, we multiply each column vector of the text block, by the key matrix, and then apply the $mod 26$ to the resulting matrix.

$mod 26$ is dividing a number by 26 and getting the remainder

5. Getting it all together and matching the characters

After doing all the multiplying operations, we already have the result matrices. So, the only thing left to do is to map the matrices items to the letters. For our case, the final result will be:

OUNIICULYVWSFKKETNZJBUSDDEBMWUGMBINXZPWUTN

Conclusion

In summary, while the Caesar Cipher involves a straightforward shift of letters, the Hill Cipher employs linear algebra to provide a more complex transformation. To decrypt, you essentially reverse the encryption process using the matrix's inverse.

References

https://www.dcode.fr/hill-cipher

https://cryptii.com/pipes/caesar-cipher

https://en.wikipedia.org/wiki/Hill_cipher