Cifrario affine
Codifica e decodifica con E(x) = (ax + b) mod 26. Inserisci a e b, e lo strumento verifica che a si possa annullare, trova il suo inverso modulare e svolge i calcoli per ogni lettera; se non conosci la chiave, la modalità di decodifica le prova tutte e 312 e le ordina in base a quanto i risultati assomigliano all'inglese.
Non deve avere fattori in comune con 26 — scegli uno dei 12 valori qui sotto.
Qualsiasi numero intero; viene preso modulo 26.
Calcoli per questa chiave
Codifica: E(x) = (5x + 8) mod 26
Decodifica: D(y) = 21(y − 8) mod 26
21 è l'inverso di 5 perché 5 × 21 = 105, che supera di 1 un multiplo di 26.
Ogni a valido e il suo 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 |
Lettera per lettera — le prime 12 lettere
| Lettera | x | a·x + b | mod 26 | Risultato |
|---|---|---|---|---|
| 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 |
Come usare il cifrario affine
- 1. Scegli una modalità e inserisci il testo. Codifica trasforma il testo in chiaro in testo cifrato; Decodifica lo inverte.
- 2. Imposta la chiave. Inserisci a, il moltiplicatore, e b, lo scorrimento. a deve essere uno dei 12 valori elencati sotto i campi — clicca su uno per usarlo. b può essere qualsiasi numero intero; viene ridotto modulo 26.
- 3. Leggi i calcoli. Il pannello sotto il risultato mostra entrambe le formule per la tua chiave, l'inverso di a e l'aritmetica di ogni lettera.
- 4. Nessuna chiave? Provale tutte. In modalità Decodifica, spunta Prova tutte le 312 chiavi. I risultati sono ordinati in base a quanto le frequenze delle loro lettere si avvicinano a quelle dell'inglese, e Usa questa chiave carica una qualsiasi di esse.
La formula del cifrario affine
Numera le lettere partendo da zero: A = 0, B = 1 … Z = 25. Per cifrare una lettera x, moltiplicala per a, aggiungi b e tieni il resto della divisione per 26: E(x) = (a·x + b) mod 26. Per decifrare una lettera y, annulla questi passaggi in ordine inverso — sottrai b, poi moltiplica per a⁻¹, l'inverso modulare di a: D(y) = a⁻¹·(y − b) mod 26. L'inverso è il numero che, moltiplicato per a, lascia resto 1. Per a = 5 è 21, perché 5 × 21 = 105 = 4 × 26 + 1.
Perché funzionano solo 12 valori di a
Moltiplicare per a non deve mai mandare due lettere nello stesso posto, altrimenti la decodifica avrebbe due risposte. Questo accade ogni volta che a ha un fattore in comune con 26 = 2 × 13. Con a = 2, per esempio, A (0) e N (13) finiscono entrambe in b, perché 2 × 13 = 26, che è 0 modulo 26. Quindi a deve essere dispari e non può essere 13, il che lascia i dodici numeri qui sotto — esattamente quelli che hanno un inverso modulo 26. Con 26 scelte per b, si ottengono 12 × 26 = 312 chiavi, una delle quali (a = 1, b = 0) non cambia nulla.
| 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 |
Esempio svolto: a = 5, b = 8
Con a = 5 e b = 8, AFFINE CIPHER si cifra in IHHWVC SWFRCP — l'esempio dello strumento. Le lettere di AFFINE, passo dopo passo:
| Lettera | x | 5x + 8 | mod 26 | Risultato |
|---|---|---|---|---|
| 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 |
Per decodificare, lo strumento moltiplica per a⁻¹ = 21. La I (8) diventa 21 × (8 − 8) = 0, cioè A; la H (7) diventa 21 × (7 − 8) = −21, che è 5 modulo 26, cioè F. I valori negativi sono normali in questo passaggio — modulo 26 significa semplicemente aggiungere o sottrarre 26 finché il numero non cade tra 0 e 25.
Due cifrari noti sono cifrari affini sotto mentite spoglie. Con a = 1 la formula è x + b, uno scorrimento di Cesare di b; con a = 25 e b = 25 è il cifrario Atbash, l'alfabeto letto al contrario.
Come violare un cifrario affine
Con sole 311 chiavi che cambiano qualcosa, l'attacco più brutale è provarle tutte, cosa che l'opzione a forza bruta fa in una frazione di secondo. La parte difficile è riconoscere la risposta, quindi lo strumento ordina ogni risultato con un confronto chi quadrato tra le frequenze delle sue lettere e quelle di un tipico testo inglese. Su una frase o più la chiave giusta compare in cima; su una frase breve potrebbe non succedere — per IHHWVC SWFRCP da solo, la vera chiave (5, 8) si classifica quarta — quindi scorri l'elenco invece di fidarti della prima riga.
I crittoanalisti possono fare di meglio con l'algebra. Il cifrario affine è una sostituzione monoalfabetica — ogni lettera diventa sempre la stessa lettera — quindi l'analisi delle frequenze suggerisce quali lettere cifrate rappresentano E e T (in un testo inglese), e due di queste ipotesi danno due equazioni. Con la chiave qui sopra, E (4) diventa C (2) e T (19) diventa Z (25), quindi 4a + b ≡ 2 e 19a + b ≡ 25 (mod 26). Sottraendo la prima dalla seconda si ottiene 15a ≡ 23; moltiplicando per 7, l'inverso di 15, si ottiene a ≡ 161 ≡ 5, e poi b ≡ 2 − 20 ≡ 8. Due lettere di testo in chiaro noto recuperano l'intera chiave.
Domande frequenti
- Che cos'è un cifrario affine?
- Un cifrario a sostituzione che trasforma il numero x di ogni lettera in (a·x + b) mod 26, così che ogni lettera viene moltiplicata per a e poi spostata di b. La chiave è la coppia (a, b). Poiché una data lettera diventa sempre la stessa lettera cifrata, è monoalfabetico — un parente dall'aspetto più robusto del cifrario di Cesare, e non più difficile da violare.
- Perché a deve essere coprimo con 26?
- La decodifica moltiplica per l'inverso di a modulo 26, e quell'inverso esiste solo quando a e 26 non hanno fattori in comune. Se ne hanno uno, due lettere diverse si cifrano nella stessa lettera e il messaggio non può essere riletto con certezza. Questo esclude ogni numero pari e il 13, lasciando 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 e 25.
- Come trovo l'inverso modulare di a?
- Trova il numero tra 1 e 25 che, moltiplicato per a, lascia resto 1 quando diviso per 26. Per a = 7 è 15, perché 7 × 15 = 105 = 4 × 26 + 1. Con soli dodici casi, è più rapido leggerli dalla tabella qui sopra; per moduli grandi, l'algoritmo di Euclide esteso trova direttamente l'inverso.
- Quante chiavi ha il cifrario affine?
- 312 — dodici scelte di a per 26 scelte di b. Una di esse, a = 1 con b = 0, lascia il testo invariato, quindi 311 cifrano davvero. Sono abbastanza poche da provarle tutte a mano in un pomeriggio, e con un computer in un istante.
- Il cifrario di Cesare è un tipo di cifrario affine?
- Sì. Ponendo a = 1 la formula diventa x + b, che è uno scorrimento di Cesare di b; ROT13 è a = 1, b = 13. Anche Atbash è affine, con a = 25 e b = 25. Entrambi si trovano tra le 312 chiavi che la forza bruta prova.
- Il cifrario affine è sicuro?
- No. Cade di fronte alla forza bruta, all'analisi delle frequenze e a sole due lettere di testo in chiaro noto, come mostra l'algebra qui sopra. È un ottimo esercizio di aritmetica modulare, ma per qualsiasi cosa importante serve una crittografia moderna.