Substitution in c

Question

Write an algorithm that deciphers a given text based on frequency analysis of the Portuguese language.

Example:

The above example uses substitution key. The technique that should be used to decipher the message is statistical analysis. For example, the character a is the one that appears most often in the Portuguese language. Therefore, the symbol that appears most often should be the letter a. The order of frequency of the characters in the Portuguese language is:

a e o s r d n i t m u l c v p g q b f h j x z k y w

The order above shows the frequency spectrum of the characters, starting with a with the highest frequency and w with the lowest frequency. The message to be deciphered is:

Cscmxcszfsocmfzscssjncwcgfspezgcfkjgznvcwbmcjcwesjvcncbfmxcmzsnenkcgzcnvzsncazicgfsbcsscmcxcjngccwzxgcvcbmfocnczxbzmjifsziezmmcszsrfmkcgfsxcjsgfpezbmfxzvjccrfmkchexcnczznvm

The encrypted message above has no spaces, accentuation or punctuation, and must be written without taking these questions into account. Remember that because it is a statistical method, some incorrect characters may prevail. This eventually arises in a marginal way, and it is possible with human intervention to revise this question. Therefore, with the message deciphered, there must still be room for some modification.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
main()
{
    char chave[26],texto[30],frase[30];

    int cont,i;

    printf("Digite o texto: ");
    scanf("%s",chave);

    cont=strlen(chave);
    strcpy(texto, chave);  

    for(i=0;i<cont;i++)     
    {
        if (texto[i]=='c')
            frase[i]='a';                 
        else if (texto[i]=='z')
            frase[i]='e';
        else if (texto[i]=='s')
            frase[i]='o';
        else if (texto[i]=='m')
            frase[i]='r';
            else if (texto[i]=='n')
            frase[i]='n';
            else if (texto[i]=='e')
            frase[i]='z';
            else if (texto[i]=='j')
            frase[i]='d';
            else if (texto[i]=='a')
            frase[i]='w';             
        else frase[i]=texto[i];
    } 
    printf("\n %s\nTexto Descriptografada e :\n %s\n",texto, frase);  
}

Answer 1

The best decoding attempt I could get was this. Explanations in the code:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define MAX_STR 1000
#define NUM_LETRAS 26

int main() {

    int i, j;

    char alfabeto[] = "abcdefghijklmnopqrstuvwxyz";
    char ordem[] = "aeosrdnitmulcvpgqbfhjxzkyw";
    char trocas[] = "jgmfri";
    char chave[NUM_LETRAS + 1]; // + 1 por causa do terminador da string.
    int frequencias[NUM_LETRAS];
    int frequencias2[NUM_LETRAS];
    char codificado[MAX_STR];
    char decodificado[MAX_STR];

    // Passo 1:
    // Limpa o vetor "frequencias".
    for (i = 0; i < NUM_LETRAS; i++) {
        frequencias[i] = 0;
    }

    // Passo 2:
    // Lê a string codificada do usuário.
    printf("Digite o texto criptografado: ");
    fgets(codificado, MAX_STR, stdin);

    // Passo 3:
    // Percorre a string "codificado" e conta quantas vezes cada letra aparece,
    // guardando a contagem no vetor "frequencias".
    for (i = 0; codificado[i]; i++) {
        if (codificado[i] >= 'a' && codificado[i] <= 'z') { // Se for letra minúscula.
            frequencias[codificado[i] - 'a']++;
        } else if (codificado[i] >= 'A' && codificado[i] <= 'Z') { // Se for letra maiúscula.
            frequencias[codificado[i] - 'A']++;
        }
        // Poderia ter um else para os casos onde não é nenhum dos dois,
        // mas quando isso acontece, não precisamos fazer nada.
    }

    // Passo 4 (opcional):
    // Mostra o vetor "frequencias".
    // Aproveita para copiar "frequencias" para "frequencias2".
    printf("\n\nTabela de frequências:");
    for (i = 0; i < NUM_LETRAS; i++) {
        printf(" %c=%d", i + 'a', frequencias[i]);
        frequencias2[i] = frequencias[i];
    }
    printf("\n");

    // Passo 5:
    // Percorre a tabela "frequencias" para montar a "chave", utilizando a ordem das letras
    // dada pelo vetor "ordem". Entretanto, o vetor "frequencias" acaba sendo destruído
    // por esse processo, e é por isso que temos uma cópia em "frequencias2".
    for (i = 0; i < NUM_LETRAS; i++) {
        int maior = -1;
        int maior_indice = 0;
        for (j = 0; j < NUM_LETRAS; j++) {
            if (frequencias[j] >= maior) {
                maior = frequencias[j];
                maior_indice = j;
            }
        }
        chave[maior_indice] = ordem[i];
        frequencias[maior_indice] = -1;
    }
    chave[NUM_LETRAS] = 0;

    // Passo 6 (opcional):
    // Percorre a tabela "frequencias2" para procurar por letras que ocorram um mesmo
    // número de vezes (que não seja zero) e mostrar isso ao usuário.
    // Entretanto, "frequencias2" acaba sendo destruído nesse processo.
    for (i = 0; i < NUM_LETRAS; i++) {
        if (frequencias2[i] == 0) continue;
        int p = 0;
        for (j = i + 1; j < NUM_LETRAS; j++) {
            if (frequencias2[j] != frequencias2[i]) continue;
            if (p == 0) {
                printf("Frequências iguais [%d]: %c", frequencias2[i], i + 'a');
                p = 1;
            }
            printf("%c", (j + 'a'));
            frequencias2[j] = 0;
        }
        frequencias2[i] = 0;
        if (p != 0) printf("\n");
    }

    // Passo 7 (opcional):
    // Troca algumas letras da "chave" a fim de ajeitar manualmente os casos que estiverem errados.
    // As letras das posições pares são permutadas com as das posições ímpares de "trocas".
    for (i = 0; trocas[i]; i += 2) {
        char temp = chave[trocas[i] - 'a'];
        chave[trocas[i] - 'a'] = chave[trocas[i + 1] - 'a'];
        chave[trocas[i + 1] - 'a'] = temp;
    }

    // Passo 8 (opcional):
    // Mostra a chave.
    printf("\nA chave é:\n%s\n%s\n", alfabeto, chave);

    // Passo 9:
    // Tendo o vetor "chave" montado, usa ele para formar a string "decodificado"
    // a partir de "codificado".
    for (i = 0; codificado[i]; i++) {
        if (codificado[i] >= 'a' && codificado[i] <= 'z') { // Letras minúsculas.
            decodificado[i] = chave[codificado[i] - 'a'];
        } else if (codificado[i] >= 'A' && codificado[i] <= 'Z') { // Letras maiúsculas.
            decodificado[i] = chave[codificado[i] - 'A'] - 'a' + 'A';
        } else { // Copia qualquer outra coisa diretamente.
            decodificado[i] = codificado[i];
        }
    }
    decodificado[i] = codificado[i]; // Copia o terminador nulo.

    // Passo 10:
    // Mostra o texto "decodificado".
    printf("\nO texto descriptografado é:\n%s\n", decodificado);  
}

Here’s the way out:

Digite o texto criptografado: 

Tabela de frequências: a=1 b=6 c=36 d=0 e=6 f=13 g=9 h=1 i=3 j=8 k=4 l=0 m=14 n=11 o=2 p=2 q=0 r=2 s=18 t=0 u=0 v=6 w=4 x=8 y=0 z=18
Frequências iguais [1]: ah
Frequências iguais [6]: bev
Frequências iguais [8]: jx
Frequências iguais [4]: kw
Frequências iguais [2]: opr
Frequências iguais [18]: sz

A chave é:
abcdefghijklmnopqrstuvwxyz
hlawustfgnvyrdbqkpozxmcije

O texto descriptografado é:
Aoariaoesobarseoaoondacatsoquetasvntedmaclranacuonmadalsriareodudvateadmeodahegatsolaooaraiandtaaceitamalrsbadaeilerngsoeguerraoeopsrvatsoianotsquelrsiemnaapsrvafuiadaeedmr

See here working on ideone.

Note the decrypted text:

Aoariaoesobarseoaoondacatsoquetasvntedmaclranacuonmadalsriareodudvateadmeodahegatsolaooaraiandtaacceptalrsbadaeilerngsoewaroeopsrvatsoianotsquelrsiemnaapsrvafuiadaeedmr

However, I had to force some font changes (with the array trocas). The exchanges were (in the key), J with G, M with F and R with I. I found these possible exchanges on the basis of trial and error, and kick. Without these exchanges, the text produced is this:

Aoasiaoerobasreoaootdacanroquenarvtnedmaclsatacuotmadalrsiaseodudvaneadmeodahepanrolaooasaiatdnaaceinamalsrbadaeilestproepuessaoeogrsvanroiatonrquelsriemtaagrsvafuiadaeedms

And then, you’ll have to have the inglorious task of kicking several possible switches until you find the right result.

An approach that tries several possible combinations of exchanges and looks for what forms the largest number of words in a given dictionary with tens of thousands of words would be a possibility, but this is clearly far from the proposed in your problem.

If the encrypted text had spaces, the task would be much easier.