Cifra afim
Codifique e decodifique com E(x) = (ax + b) mod 26. Informe a e b, e a ferramenta verifica se a pode ser desfeito, encontra o seu inverso modular e percorre cada letra; se você não souber a chave, o modo de decodificação testa as 312 e as classifica pelo quanto os resultados parecem inglês.
Não pode ter fator em comum com 26 — escolha um dos 12 valores abaixo.
Qualquer número inteiro; ele é tomado mod 26.
Desenvolvimento para esta chave
Codificação: E(x) = (5x + 8) mod 26
Decodificação: D(y) = 21(y − 8) mod 26
21 é o inverso de 5 porque 5 × 21 = 105, que é 1 a mais do que um múltiplo de 26.
Cada a válido e o seu inverso
| a | 1 | 3 | 5 | 7 | 9 | 11 | 15 | 17 | 19 | 21 | 23 | 25 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| a⁻¹ | 1 | 9 | 21 | 15 | 3 | 19 | 7 | 23 | 11 | 5 | 17 | 25 |
Letra por letra — as primeiras 12 letras
| Letra | x | a·x + b | mod 26 | Resultado |
|---|---|---|---|---|
| A | 0 | 8 | 8 | I |
| F | 5 | 33 | 7 | H |
| F | 5 | 33 | 7 | H |
| I | 8 | 48 | 22 | W |
| N | 13 | 73 | 21 | V |
| E | 4 | 28 | 2 | C |
| C | 2 | 18 | 18 | S |
| I | 8 | 48 | 22 | W |
| P | 15 | 83 | 5 | F |
| H | 7 | 43 | 17 | R |
| E | 4 | 28 | 2 | C |
| R | 17 | 93 | 15 | P |
Como usar a cifra afim
- 1. Escolha um modo e digite o seu texto. Codificar transforma texto simples em texto cifrado; Decodificar faz o inverso.
- 2. Defina a chave. Informe a, o multiplicador, e b, o deslocamento. a deve ser um dos 12 valores listados abaixo dos campos — clique em um para usá-lo. b pode ser qualquer número inteiro; ele é reduzido mod 26.
- 3. Leia o desenvolvimento. O painel abaixo do resultado traz as duas fórmulas para a sua chave, o inverso de a e a aritmética de cada letra.
- 4. Sem a chave? Teste todas. No modo Decodificar, marque Testar as 312 chaves. Os resultados são classificados pela proximidade entre a contagem das suas letras e a do inglês, e Usar esta chave carrega qualquer uma delas.
A fórmula da cifra afim
Numere as letras a partir de zero: A = 0, B = 1 … Z = 25. Para cifrar uma letra x, multiplique-a por a, some b e fique com o resto da divisão por 26: E(x) = (a·x + b) mod 26. Para decifrar uma letra y, desfaça esses passos na ordem inversa — subtraia b e depois multiplique por a⁻¹, o inverso modular de a: D(y) = a⁻¹·(y − b) mod 26. O inverso é o número que, multiplicado por a, deixa resto 1. Para a = 5, ele é 21, porque 5 × 21 = 105 = 4 × 26 + 1.
Por que só 12 valores de a funcionam
Multiplicar por a nunca pode levar duas letras ao mesmo lugar, ou a decodificação teria duas respostas. Isso acontece sempre que a tem um fator em comum com 26 = 2 × 13. Com a = 2, por exemplo, A (0) e N (13) caem ambas em b, porque 2 × 13 = 26, que é 0 mod 26. Assim, a deve ser ímpar e diferente de 13, o que deixa os doze números abaixo — exatamente os que têm um inverso mod 26. Com 26 escolhas de b, isso dá 12 × 26 = 312 chaves, uma das quais (a = 1, b = 0) não muda nada.
| a | 1 | 3 | 5 | 7 | 9 | 11 | 15 | 17 | 19 | 21 | 23 | 25 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| a⁻¹ | 1 | 9 | 21 | 15 | 3 | 19 | 7 | 23 | 11 | 5 | 17 | 25 |
Exemplo prático: a = 5, b = 8
Com a = 5 e b = 8, AFFINE CIPHER é cifrado como IHHWVC SWFRCP — o exemplo da ferramenta. As letras de AFFINE, passo a passo:
| Letra | x | 5x + 8 | mod 26 | Resultado |
|---|---|---|---|---|
| A | 0 | 8 | 8 | I |
| F | 5 | 33 | 7 | H |
| I | 8 | 48 | 22 | W |
| N | 13 | 73 | 21 | V |
| E | 4 | 28 | 2 | C |
Para decodificar, a ferramenta multiplica por a⁻¹ = 21. O I (8) vira 21 × (8 − 8) = 0, que é A; o H (7) vira 21 × (7 − 8) = −21, que é 5 mod 26, que é F. Valores negativos são normais nesta etapa — mod 26 significa apenas somar ou subtrair 26 até o número cair entre 0 e 25.
Duas cifras conhecidas são cifras afins disfarçadas. Com a = 1, a fórmula é x + b, um deslocamento de César de b; com a = 25 e b = 25, é a cifra Atbash, o alfabeto lido de trás para a frente.
Como quebrar uma cifra afim
Com apenas 311 chaves que mudam alguma coisa, o ataque mais direto é testá-las todas, o que a opção de força bruta faz em uma fração de segundo. O difícil é reconhecer a resposta, então a ferramenta classifica cada resultado com uma comparação por qui-quadrado entre a contagem das suas letras e a de um inglês típico. Em uma frase ou mais, a chave certa aparece no topo; em uma expressão curta, talvez não — só com IHHWVC SWFRCP, a chave verdadeira (5, 8) fica em quarto lugar —, então leia a lista toda em vez de confiar na primeira linha.
Os criptoanalistas podem fazer melhor com álgebra. A cifra afim é uma substituição monoalfabética — cada letra sempre se torna a mesma letra —, então a análise de frequência sugere quais letras cifradas representam E e T, e dois palpites assim dão duas equações. Com a chave acima, E (4) vira C (2) e T (19) vira Z (25), portanto 4a + b ≡ 2 e 19a + b ≡ 25 (mod 26). Subtraindo a primeira da segunda, obtém-se 15a ≡ 23; multiplicando por 7, o inverso de 15, obtém-se a ≡ 161 ≡ 5 e, depois, b ≡ 2 − 20 ≡ 8. Duas letras de texto simples conhecido recuperam a chave inteira.
Perguntas frequentes
- O que é uma cifra afim?
- Uma cifra de substituição que transforma o número x de cada letra em (a·x + b) mod 26, de modo que cada letra é multiplicada por a e depois deslocada por b. A chave é o par (a, b). Como uma dada letra sempre se torna a mesma letra cifrada, ela é monoalfabética — uma parente de aparência mais forte da cifra de César, mas não mais difícil de quebrar.
- Por que a deve ser primo com 26?
- A decodificação multiplica pelo inverso de a módulo 26, e esse inverso só existe quando a e 26 não têm fator em comum. Se tiverem, duas letras diferentes são cifradas na mesma letra e a mensagem não pode ser lida de volta com certeza. Isso exclui todos os números pares e o 13, deixando 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 e 25.
- Como encontro o inverso modular de a?
- Encontre o número entre 1 e 25 que, multiplicado por a, deixa resto 1 quando dividido por 26. Para a = 7, é 15, porque 7 × 15 = 105 = 4 × 26 + 1. Com apenas doze casos, o mais rápido é lê-los na tabela acima; para módulos grandes, o algoritmo de Euclides estendido encontra o inverso diretamente.
- Quantas chaves a cifra afim tem?
- 312 — doze escolhas de a vezes 26 escolhas de b. Uma delas, a = 1 com b = 0, deixa o texto inalterado, então 311 de fato cifram. É pouco o bastante para testar todas as chaves à mão em uma tarde e, por computador, num instante.
- A cifra de César é um tipo de cifra afim?
- Sim. Definir a = 1 transforma a fórmula em x + b, que é um deslocamento de César de b; o ROT13 é a = 1, b = 13. O Atbash também é afim, com a = 25 e b = 25. Ambos estão entre as 312 chaves que a força bruta testa.
- A cifra afim é segura?
- Não. Ela cai diante da força bruta, da análise de frequência e de apenas duas letras de texto simples conhecido, como mostra a álgebra acima. É um excelente exercício de aritmética modular, mas tudo o que importa exige criptografia moderna.