Instruções
Cria uma implementação da cifra afim, um antigo sistema de encriptação criado no Médio Oriente.
A cifra afim é um tipo de cifra de substituição monoalfabética.
Cada caráter é mapeado para o seu equivalente numérico, encriptado com uma função matemática e depois convertido na letra correspondente ao seu novo valor numérico.
Embora todas as cifras monoalfabéticas sejam fracas, a cifra afim é muito mais forte do que a cifra Atbash, porque tem muito mais chaves.
Encriptação
A função de encriptação é:
E(x) = (ai + b) mod m
Onde:
-
i é o índice da letra, de 0 até ao comprimento do alfabeto - 1.
-
m é o comprimento do alfabeto.
Para o alfabeto romano, m é 26.
-
a e b são números inteiros que constituem a chave de encriptação.
Os valores a e m têm de ser coprimos (ou, primos entre si) para que a desencriptação automática seja bem-sucedida, ou seja, têm o número 1 como único fator comum (podes encontrar mais informações no artigo da Wikipédia sobre números inteiros coprimos).
Caso a não seja coprimo com m, o teu programa deve indicar que isto é um erro.
Caso contrário, deve encriptar ou desencriptar com a chave fornecida.
Para os fins deste exercício, os algarismos são uma entrada válida, mas não são encriptados.
Os espaços e os carateres de pontuação são excluídos.
O texto cifrado é escrito em grupos de comprimento fixo separados por espaço, sendo o tamanho tradicional do grupo 5 letras.
Isto serve para dificultar a adivinhação do texto encriptado com base nos limites das palavras.
Desencriptação
A função de desencriptação é:
D(y) = (a^-1)(y - b) mod m
Onde:
-
y é o valor numérico de uma letra encriptada, ou seja, y = E(x)
- é importante notar que
a^-1 é o inverso multiplicativo modular (MMI) de a mod m
- o inverso multiplicativo modular só existe se
a e m forem coprimos.
O MMI de a é x tal que o resto da divisão de ax por m é 1:
ax mod m = 1
Podes encontrar mais informações sobre como encontrar um inverso multiplicativo modular e o que significa no artigo relacionado da Wikipédia.
Exemplos gerais
- Encriptar
"test" dá "ybty" com a chave a = 5, b = 7
- Desencriptar
"ybty" dá "test" com a chave a = 5, b = 7
- Desencriptar
"ybty" dá "lqul" com a chave errada a = 11, b = 7
- Desencriptar
"kqlfd jzvgy tpaet icdhm rtwly kqlon ubstx" dá "thequickbrownfoxjumpsoverthelazydog" com a chave a = 19, b = 13
- Encriptar
"test" com a chave a = 18, b = 13 é um erro porque 18 e 26 não são coprimos
Exemplo de como encontrar um inverso multiplicativo modular (MMI)
Encontrar o MMI para a = 15:
(15 * x) mod 26 = 1-
(15 * 7) mod 26 = 1, ou seja, 105 mod 26 = 1
-
7 é o MMI de 15 mod 26
