C++ Program To Perform A Letter Frequency Attack On A Monoalphabetic Substitution Cipher Tpoint Te

Introduction:

Monoalphabetic substitution ciphers have a long history of concealing and encoding messages. In this encryption method, every letter in the original message is substituted with a corresponding letter in the cipher text. While these ciphers are straightforward to understand and implement, they are susceptible to attacks such as letter frequency analysis.

Problem Statement

The primary objective of a letter frequency analysis is to decrypt a monoalphabetic substitution cipher without the key. This is accomplished by analyzing the frequency of letters in the encrypted text and comparing it to the expected letter distribution in the specific language (such as English). Through pattern recognition and statistical analysis, educated assumptions can be made about the key, ultimately resulting in the successful decryption of the encoded message.

Approach:

In order to conduct a letter frequency attack on any ciphertext, we should take the following steps:

• ✅ First, find how often each letter occurs within this text.
• ✅ Next, measure how often each character appears by comparison with standard frequencies for this written language (e.g., English).
• ✅ Attempt an initial guess at what could be used as a key through frequency analysis.
• ✅ Decrypt using this hypothetical code or guessed key and examine the results.
• ✅ Refine this result until readable plaintext is obtained.

Code Implementation:

Implementing a basic letter frequency analysis in C++ to decipher a monoalphabetic substitution code. The ciphertext is expected to be in capital letters without any spaces or special characters.

#include <iostream>
#include <string>
#include <map>
#include <algorithm> // Include <algorithm> for std::max_element

// Function to calculate letter frequencies in a string
std::map<char, int> calculateFrequency(const std::string& text) {
    std::map<char, int> freq;
    for (char c : text) {
        if (isalpha(c)) {
            freq[toupper(c)]++;
        }
    }
    return freq;
}

// Function to perform letter frequency attack
std::string letterFrequencyAttack(const std::string& ciphertext) {
    // Calculate letter frequencies in the ciphertext
    std::map<char, int> ciphertextFreq = calculateFrequency(ciphertext);
    
    // English letter frequencies (from most to least common)
    std::string englishFreq = "ETAOINSHRDLCUMWFGYPBVKJXQZ";
    
    // Guess the key based on frequency analysis
    std::map<char, char> key;
    for (size_t i = 0; i < englishFreq.size(); i++) {
        char c = englishFreq[i];
        auto it = std::max_element(ciphertextFreq.begin(), ciphertextFreq.end(),
            [](const std::pair<const char, int>& a, const std::pair<const char, int>& b) {
                return a.second < b.second;
            });
        key[it->first] = c;
        ciphertextFreq.erase(it->first);
    }
    
    // Decrypt the ciphertext using the guessed key
    std::string plaintext;
    for (char c : ciphertext) {
        if (isalpha(c)) {
            plaintext += key[toupper(c)];
        } else {
            plaintext += c;
        }
    }
    
    return plaintext;
}

int main() {
    std::string ciphertext = "WKH TXLFN EURZQ IRA MXPSV RYHU WKH ODCB GRJ";
    std::string plaintext = letterFrequencyAttack(ciphertext);
    std::cout << "Decrypted plaintext: " << plaintext << std::endl;
    
    return 0;
}

Output:

Decrypted plaintext: IAT JNFCY LOEZV MES GNBKX EQTO IAT PDRH UEW

Explanation:

• ✅ Calculate Letter Frequencies (calculateFrequency function): In this example, the function that is used to compute the letter frequencies is calculateFrequency. This function takes a string called text (in this case, which happens to be the ciphertext). After doing this, it goes through all the characters in the text. If it is an alphabet, it converts into uppercase and increases its frequency count in the freq map. It returns a map freq containing the frequencies of each letter in the input text.
• ✅ Perform Letter Frequency Attack (letterFrequencyAttack function): It takes the ciphertext as input. Calculates the frequency of each letter in the ciphertext using the calculateFrequency function. Creates a string englishFreq, which represents the standard English letter frequencies (from most to least common).
• ✅ In this example, the function that is used to compute the letter frequencies is calculateFrequency.
• ✅ This function takes a string called text (in this case, which happens to be the ciphertext).
• ✅ After doing this, it goes through all the characters in the text.
• ✅ If it is an alphabet, it converts into uppercase and increases its frequency count in the freq map.
• ✅ It returns a map freq containing the frequencies of each letter in the input text.
• ✅ It takes the ciphertext as input.
• ✅ Calculates the frequency of each letter in the ciphertext using the calculateFrequency function.
• ✅ Creates a string englishFreq, which represents the standard English letter frequencies (from most to least common).

Attempts to determine the encryption key by analyzing the frequency of characters in the text. Identifies the most frequently occurring character in the cipher-text as a potential substitution for each letter based on standard English frequencies. Records the estimated key in a key map for reference.

Decrypts the ciphertext using guessed key:

• ✅ Iterates through each character in ciphertext.
• ✅ If it is an alphabet, convert into uppercase and substitute with respective element from key. In case if it is not letters do nothing
• ✅ It returns decrypted plaintext.

1. Main Function (main):

• ✅ It creates the string ciphertext with the message encrypted.
• ✅ Call letterFrequencyAttack with ciphertext and store it in plaintext.
• ✅ Print decrypted plaintext to console.

Time Complexity and Space Complexity

1. Time Complexity:

Compute Letter Occurrences (calculateFrequency function):

The time complexity of the calculateFrequency function is O(n), where n represents the ciphertext's length. This is due to the fact that we traverse through each character in the text exactly once.

Perform Letter Frequency Attack (letterFrequencyAttack function):

• ✅ Find the most frequent letter in the ciphertext for each letter in English frequency string: O (26 * n), where n is the length of input text (ciphertext). Here, for every letter in English frequency string, we loop through all characters of cipher text to find the most frequent character.
• ✅ Decrypting ciphertext using guessed key: O(n), where n is length of input text (ciphertext). It happens because we loop through each character in ciphertext once to decrypt it.
• ✅ Overall time complexity: O(n), where n is the length of input text (ciphertext). Decryption step dominates.

1. Space Complexity:

• ✅ Calculating space complexity could be best explained by using an equation (n).
• ✅ Storing frequency of each letter in the ciphertext (function calculateFrequency): O(26) = O(1), because there is fixed number of letters in the alphabet.
• ✅ Storing guessed key (key map): O(26) = O(1), because there are only a fixed number of letters in the alphabet.
• ✅ Storing decrypted plaintext: O(n), where n being the length of the input text (ciphertext) because the size of plaintext is equal to that of ciphertext.
• ✅ Overall space complexity: O(n), where n is the length of the input text (ciphertext).

Advantages of Monoalphabetic Substitution Cipher in C:

• ✅ Simplicity: The concept behind letter frequency attack is simple and straightforward. It depends on basic statistical analysis regarding letter frequencies found within any given encoded message.
• ✅ Efficiency: In numerous cases, monoalphabetic substitution ciphers can be broken relatively quickly through application of a letter frequency attack. It makes it applicable for decryption purposes upon simple ciphers without demanding significant computational resources.
• ✅ No Prior Knowledge Required: No prior knowledge of the encryption process or key employed is necessary during these attacks. They only rely on how often individual alphabets occur in a given language used by plain texts.
• ✅ Applicability: The letter frequency attack is effective against monoalphabetic substitution ciphers in any language. It makes it a versatile technique for decrypting messages encrypted using such ciphers.
• ✅ Educational Value: Implementing and understanding the letter frequency attack can serve as an educational exercise for learning about cryptography, statistical analysis, and programming. It provides insight into the vulnerabilities of simple encryption techniques and the importance of stronger encryption methods.
• ✅ Basis for Further Analysis: While the letter frequency attack may not always completely decrypt a ciphertext, it can provide a starting point for more advanced cryptanalysis techniques. Cryptanalysts can refine their approach and further decrypt the message by identifying common patterns and making educated guesses about the key.

Conclusion:

In summary, the frequency analysis method is a potent technique for deciphering monoalphabetic substitution codes, contingent on familiarity with the plaintext language. Its efficacy diminishes with longer texts or intricate ciphers. Consequently, more sophisticated strategies like digraphs or trigraphs frequency analysis are preferred for enhancing encryption security.