Instruções
Crie uma implementação da cifra afim, um antigo sistema de criptografia criado no Oriente Médio.
A cifra afim é um tipo de cifra de substituição monoalfabética.
Cada caractere é mapeado para seu equivalente numérico, criptografado 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 que a cifra Atbash, porque tem muito mais chaves.
Criptografia
A função de criptografia é:
E(x) = (ai + b) mod m
Onde:
-
i é o índice da letra, de 0 até o comprimento do alfabeto - 1.
-
m é o comprimento do alfabeto.
Para o alfabeto romano, m é 26.
-
a e b são números inteiros que formam a chave de criptografia.
Os valores a e m precisam ser coprimos (ou primos entre si) para que a descriptografia automática funcione, ou seja, eles têm o número 1 como único fator comum (mais informações no artigo da Wikipédia sobre números inteiros coprimos).
Caso a não seja coprimo de m, seu programa deve indicar que isso é um erro.
Caso contrário, ele deve criptografar ou descriptografar com a chave fornecida.
Para os fins deste exercício, dígitos são entradas válidas, mas não são criptografados.
Espaços e caracteres 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.
Isso serve para dificultar a adivinhação do texto criptografado com base nos limites das palavras.
Descriptografia
A função de descriptografia é:
D(y) = (a^-1)(y - b) mod m
Onde:
-
y é o valor numérico de uma letra criptografada, ou seja, y = E(x)
- é importante observar 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 é o x tal que o resto da divisão de ax por m seja 1:
ax mod m = 1
Mais informações sobre como encontrar um inverso multiplicativo modular e o que ele significa podem ser encontradas no artigo relacionado da Wikipédia.
Exemplos gerais
- Criptografar
"test" dá "ybty" com a chave a = 5, b = 7
- Descriptografar
"ybty" dá "test" com a chave a = 5, b = 7
- Descriptografar
"ybty" dá "lqul" com a chave errada a = 11, b = 7
- Descriptografar
"kqlfd jzvgy tpaet icdhm rtwly kqlon ubstx" dá "thequickbrownfoxjumpsoverthelazydog" com a chave a = 19, b = 13
- Criptografar
"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)
Encontrando o MMI de 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
