Istruzioni
Crea un'implementazione del cifrario affine, un antico sistema di crittografia nato in Medio Oriente.
Il cifrario affine è un tipo di cifrario a sostituzione monoalfabetica.
Ogni carattere viene mappato al suo equivalente numerico, cifrato con una funzione matematica e poi convertito nella lettera corrispondente al suo nuovo valore numerico.
Sebbene tutti i cifrari monoalfabetici siano deboli, il cifrario affine è molto più forte del cifrario Atbash, perché ha molte più chiavi.
Cifratura
La funzione di cifratura è:
E(x) = (ai + b) mod m
Dove:
-
i è l'indice della lettera, da 0 alla lunghezza dell'alfabeto meno 1.
-
m è la lunghezza dell'alfabeto.
Per l'alfabeto romano m è 26.
-
a e b sono numeri interi che costituiscono la chiave di cifratura.
I valori a e m devono essere coprimi (o, primi tra loro) perché la decifratura automatica riesca, cioè hanno il numero 1 come loro unico fattore comune (maggiori informazioni si trovano nell'articolo di Wikipedia sugli interi coprimi).
Se a non è coprimo con m, il programma dovrebbe indicare che si tratta di un errore.
Altrimenti dovrebbe cifrare o decifrare con la chiave fornita.
Ai fini di questo esercizio, le cifre sono input validi ma non vengono cifrate.
Gli spazi e i caratteri di punteggiatura sono esclusi.
Il testo cifrato viene scritto in gruppi di lunghezza fissa separati da uno spazio, e la dimensione tradizionale del gruppo è di 5 lettere.
Questo serve a rendere più difficile indovinare il testo cifrato basandosi sui confini tra le parole.
Decifratura
La funzione di decifratura è:
D(y) = (a^-1)(y - b) mod m
Dove:
-
y è il valore numerico di una lettera cifrata, cioè y = E(x)
- è importante notare che
a^-1 è l'inverso moltiplicativo modulare (MMI) di a mod m
- l'inverso moltiplicativo modulare esiste solo se
a e m sono coprimi.
L'MMI di a è x tale che il resto della divisione di ax per m è 1:
ax mod m = 1
Maggiori informazioni su come trovare un inverso moltiplicativo modulare e su cosa significhi si trovano nella relativa voce di Wikipedia.
Esempi generali
- Cifrando
"test" si ottiene "ybty" con la chiave a = 5, b = 7
- Decifrando
"ybty" si ottiene "test" con la chiave a = 5, b = 7
- Decifrando
"ybty" si ottiene "lqul" con la chiave sbagliata a = 11, b = 7
- Decifrando
"kqlfd jzvgy tpaet icdhm rtwly kqlon ubstx" si ottiene "thequickbrownfoxjumpsoverthelazydog" con la chiave a = 19, b = 13
- Cifrare
"test" con la chiave a = 18, b = 13 è un errore perché 18 e 26 non sono coprimi
Esempio di ricerca di un inverso moltiplicativo modulare (MMI)
Trovare l'MMI di a = 15:
(15 * x) mod 26 = 1-
(15 * 7) mod 26 = 1, cioè 105 mod 26 = 1
-
7 è l'MMI di 15 mod 26
