Dada una string S de tamaño N que representa un cifrado monoalfabético , la tarea es imprimir los cinco textos sin formato posibles que se pueden descifrar del cifrado monoalfabético dado mediante un ataque de frecuencia de letras .
Ejemplos:
Entrada: S = “ETAOINSHRDLCUMWFGYPBVKJXQZ”
Salida: A MENSAJE SIMPLE
B TJNQMF NFTTBHF
A MENSAJE SIMPLE
C UKORNG OGUUCIG
C UKORNG OGUUCIGEntrada: S = “ABCDEFGH”
Salida: W OEILHA IAOOWCA
J BRVYUN VNBBJPN
C UKORNG OGUUCIG
R JZDGCV DVJJRXV
Y QGKNJC KCQQYEC
Enfoque: El problema se puede resolver con base en las siguientes observaciones:
- El análisis de frecuencia es uno de los ataques de texto cifrado conocidos. Se basa en el estudio de la frecuencia de letras o grupos de letras en un texto cifrado. En todos los idiomas, se usan diferentes letras con diferentes frecuencias.
- El ataque de array de frecuencia se basa en la observación de que en un texto en inglés, no todas las letras ocurren con la misma frecuencia .
- En el problema dado, la string, T = «ETAOINSHRDLCUMWFGYPBVKJXQZ» se usa para descifrar.
- Por lo tanto, la idea es encontrar la diferencia entre la i -ésima letra máxima que aparece en la string dada y la string T y luego cambiar todas las letras de la string dada con esa diferencia. La string obtenida será una de las posibles strings descifradas.
Siga los pasos a continuación para resolver el problema:
- Inicialice una string, diga T como «ETAOINSHRDLCUMWFGYPBVKJXQZ».
- Encuentre la frecuencia de cada carácter de la string S y guárdela en una variable, digamos freq[].
- Iterar sobre el rango [0, 5] usando la variable i y realizar los siguientes pasos:
- Encuentre el i -ésimo elemento que aparece más en la string S y guárdelo en una variable, digamos ch .
- Encuentre la diferencia entre el ch y el i -ésimo carácter de la string T y guárdelo en una variable, digamos x .
- Itere sobre los caracteres de la string S, y cambie todos los caracteres por x y luego inserte la string obtenida en una array de texto plano [].
- Finalmente, luego de los pasos anteriores, imprima las strings obtenidas en el arreglo plaintext[].
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to decrypt a monoalphabetic
// substitution cipher using the letter
// frequency attack
void printString(string S, int N)
{
// Stores final 5 possible deciphered
// plaintext
string plaintext[5];
// Store the frequency of each letter in
// cipher text
int freq[26] = { 0 };
// Stores the frequency of each letter
// in cipher text in descending order
int freqSorted[26];
// Store which alphabet is used already
int Used[26] = { 0 };
// Traverse the string S
for (int i = 0; i < N; i++) {
if (S[i] != ' ') {
freq[S[i] - 'A']++;
}
}
// Copy the frequency array
for (int i = 0; i < 26; i++) {
freqSorted[i] = freq[i];
}
// Stores the string formed from concatenating
// the english letters in the decreasing frequency
// in the english language
string T = "ETAOINSHRDLCUMWFGYPBVKJXQZ";
// Sort the array in descending order
sort(freqSorted, freqSorted + 26, greater<int>());
// Iterate over the range [0, 5]
for (int i = 0; i < 5; i++) {
int ch = -1;
// Iterate over the range [0, 26]
for (int j = 0; j < 26; j++) {
if (freqSorted[i] == freq[j] && Used[j] == 0) {
Used[j] = 1;
ch = j;
break;
}
}
if (ch == -1)
break;
// Store the numerical equivalent of letter at
// ith index of array letter_frequency
int x = T[i] - 'A';
// Calculate the probable shift used
// in monoalphabetic cipher
x = x - ch;
// Temporary string to generate one
// plaintext at a time
string curr = "";
// Generate the probable ith plaintext
// string using the shift calculated above
for (int k = 0; k < N; k++) {
// Insert whitespaces as it is
if (S[k] == ' ') {
curr += ' ';
continue;
}
// Shift the kth letter of the
// cipher by x
int y = S[k] - 'A';
y += x;
if (y < 0)
y += 26;
if (y > 25)
y -= 26;
// Add the kth calculated/shifted
// letter to temporary string
curr += 'A' + y;
}
plaintext[i] = curr;
}
// Print the generated 5 possible plaintexts
for (int i = 0; i < 5; i++) {
cout << plaintext[i] << endl;
}
}
// Driver Code
int main()
{
// Given string
string S = "B TJNQMF NFTTBHF";
int N = S.length();
// Function Call
printString(S, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to decrypt a monoalphabetic
// substitution cipher using the letter
// frequency attack
static void printString(String S, int N)
{
// Stores final 5 possible deciphered
// plaintext
String []plaintext = new String[5];
// Store the frequency of each letter in
// cipher text
int freq[] = new int[26];
// Stores the frequency of each letter
// in cipher text in descending order
int freqSorted[] = new int[26];
// Store which alphabet is used already
int Used[] = new int[26];
// Traverse the String S
for (int i = 0; i < N; i++) {
if (S.charAt(i) != ' ') {
freq[S.charAt(i) - 'A']++;
}
}
// Copy the frequency array
for (int i = 0; i < 26; i++) {
freqSorted[i] = freq[i];
}
// Stores the String formed from concatenating
// the english letters in the decreasing frequency
// in the english language
String T = "ETAOINSHRDLCUMWFGYPBVKJXQZ";
// Sort the array in descending order
Arrays.sort(freqSorted);
freqSorted= reverse(freqSorted);
// Iterate over the range [0, 5]
for (int i = 0; i < 5; i++) {
int ch = -1;
// Iterate over the range [0, 26]
for (int j = 0; j < 26; j++) {
if (freqSorted[i] == freq[j] && Used[j] == 0) {
Used[j] = 1;
ch = j;
break;
}
}
if (ch == -1)
break;
// Store the numerical equivalent of letter at
// ith index of array letter_frequency
int x = T.charAt(i) - 'A';
// Calculate the probable shift used
// in monoalphabetic cipher
x = x - ch;
// Temporary String to generate one
// plaintext at a time
String curr = "";
// Generate the probable ith plaintext
// String using the shift calculated above
for (int k = 0; k < N; k++) {
// Insert whitespaces as it is
if (S.charAt(k) == ' ') {
curr += (char)' ';
continue;
}
// Shift the kth letter of the
// cipher by x
int y = S.charAt(k) - 'A';
y += x;
if (y < 0)
y += 26;
if (y > 25)
y -= 26;
// Add the kth calculated/shifted
// letter to temporary String
curr += (char)('A' + y);
}
plaintext[i] = curr;
}
// Print the generated 5 possible plaintexts
for (int i = 0; i < 5; i++) {
System.out.print(plaintext[i] +"\n");
}
}
static int[] reverse(int a[]) {
int i, n = a.length, t;
for (i = 0; i < n / 2; i++) {
t = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = t;
}
return a;
}
// Driver Code
public static void main(String[] args)
{
// Given String
String S = "B TJNQMF NFTTBHF";
int N = S.length();
// Function Call
printString(S, N);
}
}
// This code contributed by Princi Singh
Python3
# Python3 program for the above approach # Function to decrypt a monoalphabetic # substitution cipher using the letter # frequency attack def printString(S, N): # Stores final 5 possible deciphered # plaintext plaintext = [None] * 5 # Store the frequency of each letter in # cipher text freq = [0] * 26 # Stores the frequency of each letter # in cipher text in descending order freqSorted = [None] * 26 # Store which alphabet is used already used = [0] * 26 # Traverse the string S for i in range(N): if S[i] != ' ': freq[ord(S[i]) - 65] += 1 # Copy the frequency array for i in range(26): freqSorted[i] = freq[i] # Stores the string formed from # concatenating the english letters # in the decreasing frequency in the # english language T = "ETAOINSHRDLCUMWFGYPBVKJXQZ" # Sort the array in descending order freqSorted.sort(reverse = True) # Iterate over the range [0, 5] for i in range(5): ch = -1 # Iterate over the range [0, 26] for j in range(26): if freqSorted[i] == freq[j] and used[j] == 0: used[j] = 1 ch = j break if ch == -1: break # Store the numerical equivalent of letter # at ith index of array letter_frequency x = ord(T[i]) - 65 # Calculate the probable shift used # in monoalphabetic cipher x = x - ch # Temporary string to generate one # plaintext at a time curr = "" # Generate the probable ith plaintext # string using the shift calculated above for k in range(N): # Insert whitespaces as it is if S[k] == ' ': curr += " " continue # Shift the kth letter of the # cipher by x y = ord(S[k]) - 65 y += x if y < 0: y += 26 if y > 25: y -= 26 # Add the kth calculated/shifted # letter to temporary string curr += chr(y + 65) plaintext[i] = curr # Print the generated 5 possible plaintexts for i in range(5): print(plaintext[i]) # Driver code # Given string S = "B TJNQMF NFTTBHF" N = len(S) # Function Call printString(S, N) # This code is contributed by Parth Manchanda
C#
// C# program for the above approach
using System;
public class GFG{
// Function to decrypt a monoalphabetic
// substitution cipher using the letter
// frequency attack
static void printString(String S, int N)
{
// Stores readonly 5 possible deciphered
// plaintext
String []plaintext = new String[5];
// Store the frequency of each letter in
// cipher text
int []freq = new int[26];
// Stores the frequency of each letter
// in cipher text in descending order
int []freqSorted = new int[26];
// Store which alphabet is used already
int []Used = new int[26];
// Traverse the String S
for (int i = 0; i < N; i++) {
if (S[i] != ' ') {
freq[S[i] - 'A']++;
}
}
// Copy the frequency array
for (int i = 0; i < 26; i++) {
freqSorted[i] = freq[i];
}
// Stores the String formed from concatenating
// the english letters in the decreasing frequency
// in the english language
String T = "ETAOINSHRDLCUMWFGYPBVKJXQZ";
// Sort the array in descending order
Array.Sort(freqSorted);
freqSorted= reverse(freqSorted);
// Iterate over the range [0, 5]
for (int i = 0; i < 5; i++) {
int ch = -1;
// Iterate over the range [0, 26]
for (int j = 0; j < 26; j++) {
if (freqSorted[i] == freq[j] && Used[j] == 0) {
Used[j] = 1;
ch = j;
break;
}
}
if (ch == -1)
break;
// Store the numerical equivalent of letter at
// ith index of array letter_frequency
int x = T[i] - 'A';
// Calculate the probable shift used
// in monoalphabetic cipher
x = x - ch;
// Temporary String to generate one
// plaintext at a time
String curr = "";
// Generate the probable ith plaintext
// String using the shift calculated above
for (int k = 0; k < N; k++) {
// Insert whitespaces as it is
if (S[k] == ' ') {
curr += (char)' ';
continue;
}
// Shift the kth letter of the
// cipher by x
int y = S[k] - 'A';
y += x;
if (y < 0)
y += 26;
if (y > 25)
y -= 26;
// Add the kth calculated/shifted
// letter to temporary String
curr += (char)('A' + y);
}
plaintext[i] = curr;
}
// Print the generated 5 possible plaintexts
for (int i = 0; i < 5; i++) {
Console.Write(plaintext[i] +"\n");
}
}
static int[] reverse(int []a) {
int i, n = a.Length, t;
for (i = 0; i < n / 2; i++) {
t = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = t;
}
return a;
}
// Driver Code
public static void Main(String[] args)
{
// Given String
String S = "B TJNQMF NFTTBHF";
int N = S.Length;
// Function Call
printString(S, N);
}
}
// This code is contributed by shikhasingrajput
Producción
A SIMPLE MESSAGE B TJNQMF NFTTBHF A SIMPLE MESSAGE C UKORNG OGUUCIG C UKORNG OGUUCIG
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por arjunsaini9081 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA