Cipher Algorithms
Hello once more, everyone! Sharing with you what I learn, research, and put in thought and effort is something I love to do, as you already know. I am convinced that these materials can be a valuable resource for me in the future, so this time, with the same purpose in mind, I chose a topic that I presented as a project assignment in an elective course I took at university.
Also, I may refer to the biographical film of the famous mathematician genius John Nash, ‘A Beautiful Mind.’ (I recommend watching it if you haven’t already.)
This article will focus on “encryption algorithms”, which are also related to account theft, which is a common issue these days.
To understand the concept of these algorithms, I think it’s necessary to have some grasp of certain terms before starting. What are they?
- Cryptography
- Cryptanalysis
- Cryptology
Cryptography: Cryptography is a branch of science used to encrypt or decrypt information using mathematical algorithms to ensure confidentiality.
Cryptanalysis: Cryptanalysis is a discipline used to analyze the security of cryptographic systems and attempt to break them.
Cryptology: Cryptology is a combination of cryptography and cryptanalysis, providing an overview of these two fields. It involves developing encryption techniques for securely transmitting and storing information, as well as testing the security of these techniques using cryptanalysis methods.
Some basic terms used in “Cryptography”:
- Plaintext: Original, plain text.
- Ciphertext: Encrypted text.
- Cipher: Algorithm that converts plaintext to ciphertext. Encryption algorithm.
- Encipher (encrypt): Process of converting plaintext to ciphertext.
- Decipher (decrypt): Process of recovering plaintext from ciphertext.
Areas of Application for Encryption Algorithms:
◼ Secure communication
◼ Data privacy
◼ Encrypted file storage
◼ Data signatures
Security and Vulnerabilities:
◼ Resilience against brute force attacks due to long key spaces.
◼ Discovery of mathematical weaknesses, meaning algorithms once considered strong may now be weak with increasing computational power.
◼ Security is compromised when weak passwords or keys are used.
Once we’ve accumulated the necessary knowledge, we can move on to the topics we’ll concentrate on…
We Will Mainly Cover These Topics:
- Vigenere Cipher
- Kasiski Analysis
- Running Key Cipher
Vigenère Cipher
The encryption known as the Vigenère Cipher was first described by Giovan Battista Bellaso in his 1553 book “La Cifra del.”
It is also known as polyalphabetic encryption. As the name suggests, polyalphabetic encryption differs from monoalphabetic methods in that when a letter is replaced, it does not always revert to the same letter. Depending on the key, each letter corresponds to multiple letters in the alphabet.
The Vigenère Cipher is an adaptation of the Trithemius Cipher, but instead of systematically progressing through the encrypted text alphabets in the Tabula Recta, it uses a keyword to select which columns to use.
The most famous example of code and cipher in history, the ENIGMA machine, is nothing more than an enhanced polyalphabetic substitution cipher.
To perform encryption, we need a few things:
- A table known as the Vigenère Table
- A key (for encrypting the message).
The table consists of the alphabet written 26 times in different rows, assuming we’re using the English alphabet. Each alphabet is cyclically shifted to the left compared to the previous alphabet, corresponding to the 26 possible Caesar Ciphers. To apply the algorithm simply: [A-Z] → [0–25].
Let’s create our cipher using an example.
- Our plaintext is “SoftwareDevelopment”
- We’ll choose our key as “Gokce”
To encrypt, we need to find the intersections of the letters we’ve written vertically with the Vigenère table.
By continuing in this manner, we obtain our encrypted text.
Ciphertext: “YCPVAGFOFIBSVQTSSXV”
We can also obtain the same result using the following method:
For centuries, the Vigenère Cipher was known as a very secure encryption method, and it was believed to be unbreakable for a long time. However, it was cracked by Friedrich Kasiski in 1863.
I assume we understand the subject now. Shall we take a look at a code example together?
- When we look at the code, we see that an empty StringBuilder object is created. The loop continues until the keyword is equal to the length of the text. Characters of the keyword are added one by one. A loop is created to reuse the characters in the keyword. It returns the extended keyword.
- An empty StringBuilder object is created. The keyword is extended to the length of the text. A loop is initiated for each character of the text. Characters of the text are taken one by one. Characters of the keyword are taken one by one. Encryption process is performed. Letters are shifted using the character of the keyword. Encrypted characters are appended to the encrypted text. It returns the encrypted text.
Kasiski Analysis
Kasiski examination is a cryptographic analytic technique used to determine the key length used in encryption systems, particularly effective against polyalphabetic encryption methods such as the Vigenère cipher.
This algorithm focuses on finding periodic recurring patterns in the text, and the distance between these patterns helps us determine the probable key length. Once the length of the key is found, the cryptanalyst divides the encrypted text into columns equal to the length of the key. Then, each column can be treated as if it were encrypted using a monoalphabetic encryption method. In this way, frequency analysis can be applied to each column.
Let’s take a look at the stages of Kasiski Analysis, where Friedrich Kasiski endured the hardship and Charles Babbage enjoyed the pleasure.
The stages are as follows:
◼Repeated character sequences are searched for in the encrypted text.
◼For a successful examination, character sequences should be at least three characters long.
◼Then, the distances between repeated character sequences tend to be multiples of the key length.
◼Finding more repeated character sequences narrows down the possible lengths of the key because the greatest common divisor of all distances can be taken.
The difficulty of Kasiski's examination lies in finding repeated words. This process is quite challenging when done manually, but computers can greatly facilitate this task. However, it should be noted that some repeated sequences may occur by chance, so the analyst must eliminate some repeat distances that may be misleading. They need to eliminate coincidences to find the correct length, and then the resulting monoalphabetic encrypted texts should be subjected to cryptanalysis.
If we’ve looked into enough technical details, let’s try to decrypt our sample text encrypted with the Vigenère cipher using Kasiski Analysis.
Our sample text is:
YAGFQNSUSAWQOISQAKLRANUPOYNMRWLZSMOQYERQTHNDOPWXAGAEAGKRLHDQRLUFHXYAWGZYAESSAKKQNLHZDMOQYTSEOXUVORCETGNFHXNMRWLZSHMNGAHGSX
It’s beneficial to go step by step…
Step 1:
The encrypted text is examined, and the distances between recurring text groups are found.
When we look at the text, we see that the recurring text groups are “AG” and “QN”. Let’s find the frequency of each. (We’ll need this for frequency analysis.)
- The distances between recurring “AG”s are 48 and 4.
- The distance between recurring “QN”s is 76.
Step 2:
We examine the factors of 4, 48, and 76.
- Factors of 4: 1, 2, 4
- Factors of 48: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48
- Factors of 76: 1, 2, 4, 19, 76
Since the common factor is 4, our estimated key length is 4. Thus, we assume that our key is 4 characters long.
Step 3:
Let’s use the coincidence sequence test to verify if the key length is indeed 4.
Given the values, it’s evident that m=4 holds true.
Step 4:
We’ve found that our key length is 4. This tells us that each group of 4 letters in our example encrypted text is encrypted with the first letter of the key.
- So, the 1st, 5th, 9th, 13th, 14th… letters of the encrypted text are encrypted with the 1st letter of the key.
- Following the same logic, the 2nd, 6th, 10th, 14th… letters are encrypted with the 2nd letter of the key.
- Similarly, the 3rd, 7th, and 11th… letters are encrypted with the 3rd letter of the key.
- The 4th, 8th, 12th, and 16th… letters are encrypted with the 4th (last) letter of the key.
Indeed:
1st letter: Y Q U Q Q R P M Z Q D X E R Q F A Y S Q Z Q E V E F M Z N G
2nd letter: A N S O A A O R S Y T O A A L R H W A A N D Y O O T H R S G S
3rd letter: G Z A I K N Y W M E H P G G H L X G E K L M T X R G X W H A X
4th letter: F S W S L U N L O R N W A K D U Y Z S K H O S U C N L M H
Result:
Using the frequency of letter occurrences, we found the key of the encrypted text to be “MATH”.
We previously mentioned how an encrypted text can be decrypted using its key (by utilizing the Vigenère Table).
As a result, the decrypted text is: “MANY ENGLISH PEOPLE ARE FOUND OF GARDENS. THEY LIKE TO GROW PLANTS AND FLOWERS IN THEIR OWN SMALL GARDENS AND THEY ALSO ENJOY VISITING THE GARDENS OF BIG HOUSES.”
Let’s code…
- This code snippet creates an empty list named
repeatedBlocks, which will contain the recurring blocks. It also creates an empty HashMap namedblockPositions, which will store the starting positions of the blocks. - Then, it starts a loop to iterate over each character of the text, ensuring that it goes up to
text.length() - minLength. This is to ensure that a block at the end of the text doesn't have a length less thanminLength. - Within the loop, a block of length
minLengthis created starting from indexiof the text. - If
blockPositionsalready contains the block, it means the block has been found before in the text. In this case, it retrieves the previous position of the block (prevPosition) and retrieves the recurring block from that position to the nextminLengthcharacters. This recurring block is then added to therepeatedBlockslist. - If
blockPositionsdoesn't contain the block, it means the block is encountered for the first time. In this case, it adds the block and its starting position (i) to theblockPositionsmap. - After the loop completes, the
repeatedBlockslist is filled with the found recurring blocks, and this list is returned.
- Using the
findRepeatedBlocksmethod, we find the recurring blocks in the ciphertext and store these blocks in an ArrayList namedrepeatedBlocks. - We calculate the distances between the recurring blocks using two nested loops.
- For each recurring block, we iterate through all other blocks and calculate the distance between the blocks.
- The
Math.abs()function calculates the absolute difference between the positions of the blocks.
Running Key Cipher
This encryption method has been used in military communication and secret correspondence in the past. In this method, a plaintext message is combined with a running key, and the length of the running key must be equal to or longer than the length of the plaintext message.
Mathematical Representation:
Application Steps:
- Key Encryption
- Letter by Letter
- Encryption Shifting and Repeating
Example Application:
Plaintext: Flee at once. We are discovered.
Running Key: errors can occur in several places
Here’s the indicator:
Since the page number is 06301, we take the first three digits as the page number, which is 063, and the last two digits as the line number, which is 01.
So, page 63, line 01 corresponds to our key phrase.
Now, to determine the indicator, we find which letters of the plaintext alphabet correspond to the values of the plaintext message.
Since the page and line number representation is 06301, we translate it as follows: 0 corresponds to A, 6 corresponds to G, 3 corresponds to D, and so on.
Thus, our indicator is AGDAB.
Finally, when writing our encrypted message, we place our indicator before the last word group.
Our final message: JCVSR LQNPS YGUIM QAWXS AGDAB MECTO
Now, let’s imagine we’re soldiers. We want to send an encrypted message to another soldier friend using the method we discussed above. After encrypting the message, our friend needs to know which book we chose to create the indicator. With this information, they can decipher the message using the indicator.
The Running Key Cipher uses a randomly chosen key text that shifts continuously during the encryption process, providing a higher level of security. However, it’s crucial to share and store the key text securely.
Lets’s code…
As a university student, I try to write by analyzing what I have learned from the lessons I have taken and what I am curious about. I believe I have acquired more knowledge. Feel free to share your comments below.
