The challenge is to display the top five probable plain texts which could be decrypted from the supplied monoalphabetic cypher utilizing the letter frequency attack from a string Str with size K representing the given monoalphabetic cypher.
Let us see what exactly is frequency attack.
频率分析的基础是确信特定的字母和字母组合在任何给定的书面语言部分中以不同的频率出现。此外，事实上，该语言的每个样本在字母分布上都有一个共同的模式。为了更清楚地说明，
英语字母表有26个字母，但并不是所有字母在书面英语中使用频率都相同。某些字母的使用频率是不同的。例如，如果你查看一本书或报纸上的字母，你会注意到字母E、T、A和O在英语单词中出现得非常频繁。然而，英语文本很少使用字母J、X、Q或Z。这个事实可以用来解密维吉尼亚密码的信息。术语"频率分析"就是指这种方法。
Each letter found in the plaintext is substituted with a different letter in a basic substitution cypher, and any given character in its plaintext is perpetually changed to an identical letter in the text of the cypher. A ciphertext message with several repetitions of the letter Y, for instance, would imply to the cryptanalyst that Y stands in for the letter a if every instance of the letter a are converted to the letter X.
示例示例1
Let us take string T,
按照英文字母在英语字母表中的降序连接形成的字符串。
String T=ETAOINSHRDLCUMWFGYPBVKJXQZ” Given string Str = "SGHR HR SGD BNCD";
Output: THIS IS THE CODE FTUE UE FTQ OAPQ LZAK AK LZW UGVW PDEO EO PDA YKZA IWXH XH IWT RDST
问题陈述
实现一个程序，对单字母替代密码进行字母频率攻击。
Solution Approach
In Order to perform a letter frequency attack on a monoalphabetic substitution cipher, we take the following methodology.
The approach to solve this problem and to perform a letter frequency attack on a monoalphabetic substitution cipher is by applying frequency analysis.
One widely-known technique or a practice of breaking ciphertext is nothing but a frequency analysis. It is founded on research into how often and regular different letters or groupings of letters appear in ciphertexts. A variety of letters or alphabets are used at varying rates across all languages.
For example, take the word "APPLE". The frequency of the letter "A" is 1 since it is occured only one time, similarly the frequency of the letter "L" is 1 and the frequency of the letter "E" is also 1. But the frequency of the letter "P" is 2 since it is repeated two times.
这就是我们找到字母频率的方法。
考虑一下在典型的英文文本中每个字母出现的频率。最常出现的字母是E，其次是T，然后是A，依此类推，如果我们按照从高频到低频的顺序排列这些字母 −
"ETAOINSHRDLCUMWFGYPBVKJXQZ" 是按频率排序的完整字母列表。
Algorithm
在单字母替代密码上执行字母频率攻击的算法如下所示
第一步 − 开始
第二步 - 通过使用频率攻击或分析的方法定义解密单字母替代密码的函数
步骤 3 − 存储最终的 5 个可行的解密明文
第四步 − 存储密文中每个字母的频率
步骤 5 - 遍历字符串 Str
步骤 6 − 迭代一个范围为 [0, 5]
Step 7 − Iterate over a range of [0, 26]
第8步 - 定义一个临时字符串"cur"，以便逐个或在当前时间创建一个明文
Step 9 − Now create the ith plaintext by making use of the calculated shift
第10步 − 将密码的第T个字母向右移动x个位置
第11步 - 将第k个计算出的字母添加到临时字符串cur中
Step 12 − Print the output as the generated 5 possible plaintexts.
步骤 13 − 停止
Example: C Program
以下是C程序实现的上述算法，用于对单字母替换密码进行字母频率攻击。
#include <stdio.h>
#include <string.h>
// Define a function to decrypt given monoalphabetic substitution cipher by implementing the method of frequency analysis or an attack
void printTheString(char Str[], int K){
// this stores the final 5 feasible plaintext //which are deciphered
char ptext[5][K+1];
// the frequency of every letter in the
// cipher text is stored
int fre[26] = { 0 };
// The letter frequency of the cipher text is stored in the order of descendence
int freSorted[26];
// this stores the used alphabet
int Used[26] = { 0 };
// Traversing the given string named Str
for (int i = 0; i < K; i++) {
if (Str[i] != ' ') {
fre[Str[i] - 'A']++;
}
}
// Copying the array of frequency
for (int i = 0; i < 26; i++) {
freSorted[i] = fre[i];
}
//by concatenating the english letters in //decreasing frequency in the english alphabet , the string T is //obtained
char T[] = "ETAOINSHRDLCUMWFGYPBVKJXQZ";
// Sorting the array in the order of descendence
for (int i = 0; i < 26; i++) {
for (int j = i + 1; j < 26; j++) {
if (freSorted[j] > freSorted[i]) {
int temp = freSorted[i];
freSorted[i] = freSorted[j];
freSorted[j] = temp;
}
}
}
// Iterating in the range between [0, 5]
for (int i = 0; i < 5; i++) {
int ch = -1;
// Iterating in the range between [0, 26]
for (int m = 0; m < 26; m++) {
if (freSorted[i] == fre[m] && Used[m] == 0) {
Used[m] = 1;
ch = m;
break;
}
}
if (ch == -1)
break;
// here numerical equivalent of letter is stored ith index of array letter_frequency
int x = T[i] - 'A';
// now probable shift is calculated in the monoalphabetic cipher
x = x - ch;
// defining a temporary string cur to create one plaintext at a time or at the current time
char cur[K+1];
// ith plaintext is generated by making use of the shift calculated
for (int T = 0; T < K; T++) {
// whitespaces is inserted without any //change
if (Str[T] == ' ') {
cur[T] = ' ';
continue;
}
// Shifting the Tth cipher letter by x we get
int y = Str[T] - 'A';
y =y+x;
if (y < 0)
y =y+ 26;
if (y > 25)
y -=26;
// Adding the kth calculated letter to the temporary string cur
cur[T] = 'A' + y;
}
cur[K] = '\0';
// The ith feasible plaintext is printed
printf("%s\n", cur);
}
}
int main(){
char Str[] = "SGHR HR SGD BNCD";
int K = strlen(Str);
printTheString(Str, K);
return 0;
}
输出
THIS IS THE CODE FTUE UE FTQ OAPQ LZAK AK LZW UGVW PDEO EO PDA YKZA IWXH XH IWT RDST
结论
Likewise, we can obtain a solution to perform a letter frequency attack on a monoalphabetic substitution cipher.
在本文中，我们解决了获取程序来执行对单字母替换密码进行字母频率攻击的挑战。
在这里提供了C编程代码以及在单字母替换密码上执行字母频率攻击的算法。
