PKU 1449 - Enigma

Autor da análise: RicardohahnRicardohahn

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=1449

Resumo

Dados as configurações dos discos, o deslocamento inicial de cada disco, a mensagem e a mensagem cifrada, qualquer um deles com letras faltando (no máximo 3), gerar a mensagem cifrada completa.

Solução

Em linhas gerais a solução se resume a fazer um algoritmo que dados as configurações dos discos e a mensagem original COMPLETOS, gere a mensagem cifrada. Esse algoritmo está descrito no enunciado (mas será discutido um jeito de implementá-lo).
Note que o número de incógnitas é reduzido, no máximo 3, o que torna viável gerar todas as configurações para as incógnitas ($$26^3=17576$$), e depois testar se gera a mensagem cifrada coerente que a que já existia.

O algoritmo da Enigma "transforma" uma letra em outra, mudando a posição do sinal (a letra é definida pela posição do sinal em relação à frente estática da máquina). Por exemplo vamos supor que o início da chave do rotor $$\pi_0$$ é "bdc", se o deslocamento inicial desse rotor for nulo, o "a" será transformado em "b", mas agora vamos supor que o rotor tenha sido deslocado. Agora o "a" que será passado para a máquina não coincide com o "a" do rotor, entao na verdade estaremos no "b" do rotor, que transforma em "d", pelo referencial do rotor, que está deslocado em relação ao da máquina. O "d" gerado pelo rotor corresponde ao "c" da máquina. Então o "a" será transformado em "c".
Ficar pensando em referenciais pode ser um pouco confuso, então para simplificar, pensaremos no deslocamento que o rotor causa na letra. No exemplo anterior seria ("bdc") seria (1,2,0). Com isso podemos sempre trabalhar no referencial da máquina. Se tivermos a letra "a" e o rotor $$\pi_0$$ estiver deslocado de 1, basta vermos qual o deslocamento da posição 'a'+1, que é 2, então transformando "a" em "c", já pelo referencial da máquina.
Vamos agora generalizar. Já temos o vetor de deslocamento do rotor $$\pi_0$$, t0[26], e o deslocamento inicial do rotor, d0, e queremos passar a letra contida na variável ini pela transformação ('a'==0 e 'z'==25).

final=(ini+t0[(ini+d0)%26])%26;

Agora para cifrar a mensagem, basta pegar a letra inicial e submetê-la a todas as transformações (sugiro que as inversas sejam tratadas como transformações normais, mas não iguais às originais).

Tomar cuidado com a condição para girar os rotores $$\pi_1$$, $$\pi_2$$ e $$\pi_r$$!!

Testes

Entrada

Saída

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License