Nel precedente articolo di questa categoria ci siamo lasciati con questa funzione:
C(a, b)(x) = ax + b (mod n)
che, più semplicemente, si può scrivere così:
C(x) = ax + b (mod n)
Questa funzione prende il nome di “cifrario affine“.
Cifrario affine VS codice Cesare
Il cifrario affine è molto più sicuro di un codice Cesare convenzionale, perché la chiave è data dalla coppia a e b. Quindi il numero massimo di chiavi possibili non è più 26 (nel caso prendessimo tutto l’alfabeto), bensì 26 x 26, visto che a e b possono avere entrambi un valore compreso tra 0 e 25.
26 x 26 = 656 chiavi possibili.
Inoltre, l’MCD (massimo comune divisore) tra a e n deve essere uguale a 1. Per chi non lo sapesse, l’MCD tra due numeri si calcola in questo modo:
Calcolare l’MCD
Supponiamo di voler calcolare l’MCD tra 48 e 30. Si procede in questo modo:
MCD (48, 30)
48 / 30 = 1 resto 18
30 / 18 = 1 resto 12
18 / 12 = 1 resto 6
12 / 6 = 2 resto 0
Arrivati al resto uguale a 0, si prende come MCD il denominatore dell’ultima frazione, che in questo caso è uguale a 6.
MCD tra “a” e “n” = 1… Perché???
Il motivo per il quale, nel cifrario affine, l’MCD tra a e n deve essere uguale a 1, risiede nella necessità di decifrare ogni carattere con un altro unico carattere. Se non fosse uguale a 1, uno stesso carattere cifrato può essere decifrato con un risultato di più caratteri, rendendo impossibile la procedura. Ma facciamo un esempio.
Prendiamo le prime sei lettere dell’alfabeto:
e associamogli questa funzione:
C(x) = 2x + 1 (mod 6)
quindi con un MCD tra a (2) e n (6) di 2.
Ora cifriamo tutti i caratteri:
A -> C(0) = 2 x 0 + 1 (mod 6) = 1 (mod 6) = B
B -> C(1) = 2 x 1 + 1 (mod 6) = 3 (mod 6) = D
C -> C(2) = 2 x 2 + 1 (mod 6) = 5 (mod 6) = F
D -> C(3) = 2 x 3 + 1 (mod 6) = 7 ≡ 1 (mod 6) = B
E -> C(4) = 2 x 4 + 1 (mod 6) = 9 ≡ 3 (mod 6) = D
F -> C(5) = 2 x 5 + 1 (mod 6) = 11 ≡ 5 (mod 6) = F
Il risultato è questo:
Possiamo vedere che i caratteri A B C hanno un risultato identico a quello dei caratteri D E F. Questo rende impossibile lo svolgimento di decifrazione.
Come mai è impossibile decifrare?
L’operazione matematica di decifrazione equivale a trovare l’incognita x dato un valore y (che sarebbe C(x)) nel modulo n:
C(x) = ax + b = y
quindi
ax + b = y
ora isoliamo la x
ax = y – b
Affinché l’incognita x sia completamente isolata, bisogna fare in modo che a sia uguale a 1. Quindi bisogna moltiplicare a con il suo inverso, cioè a^(-1):
a^(-1)ax = a^(-1)(y – b) —> x = a^(-1)(y – b)
Ricordiamoci sempre che dobbiamo ragionare secondo i moduli. La a avrà un inverso nel modulo n solo se l’MCD tra i due è uguale a 1. Nell’esempio precedente, l’MCD tra i due valori era uguale a 2, quindi la a uguale a 2 non ha un inverso nel modulo 6.
Provare per credere
In un modulo, l’inverso di un numero è quel numero che moltiplicato con esso, dia come risultato un valore uguale a 1:
2 x 0 = 0 (mod 6)
2 x 1 = 2 (mod 6)
2 x 2 = 4 (mod 6)
2 x 3 = 6 ≡ 0 (mod 6)
2 x 4 = 8 ≡ 2 (mod 6)
2 x 5 = 10 ≡ 4 (mod 6)
Del risultato “1 (mod 6)” nessuna traccia. Possiamo quindi costatare che nella funzione “C(x) = 2x + 1 (mod 6)”, la a, cioè il 2, non ha un inverso. Per questo il cifrario è indecifrabile.
Esempio di cifrario affine decifrabile
Prendiamo l’alfabeto spagnolo, quindi con un carattere in più (Ñ):
Supponiamo ora di voler decifrare questo messaggio:
YSFMG
cifrato con questo cifrario affine:
C(x) = 2x + 3 (mod 27) (si noti l’MCD tra a (2) e n (27) uguale a 1)
La formula di decifrazione si ricava in questo modo:
y = 2x + 3
2x = y – 3
Ora bisogna isolare la x moltiplicando la a, che in questo caso vale 2, con il suo inverso. L’inverso di 2 nel modulo 27 è 14: infatti 14 x 2 = 28 ≡ 1 (mod 27). Arriviamo dunque all’ultimo passaggio:
x = 14(y – 3)
Ora possiamo ricavare il messaggio in chiaro:
Y -> 14(25 – 3) = 308 ≡ 11 (mod 27) = L
S -> 14(19 – 3) = 224 ≡ 8 (mod 27) = I
F -> 14(5 – 3) = 28 ≡ 1 (mod 27) = B
M -> 14(12 – 3) = 126 ≡ 18 (mod 27) = R
G -> 14(6 – 3) = 42 ≡ 15 (mod 27) = O
Siamo riusciti così a decifrare il messaggio YSFMG ricavando il testo in chiaro LIBRO.
Conclusioni
L’alfabeto cifrato si può scrivere in qualsiasi ordine. Se volessi una maggiore sicurezza, potrei cambiarlo, ad esempio, ogni mese, a seconda di quale mese sia. Se fossimo nel mese di marzo, potrei far iniziare l’alfabeto con le lettere M A R Z O (figura 1); ad aprile varrebbe lo stesso ragionamento (figura 2), e così anche per tutti gli altri mesi.
Il numero massimo di chiavi possibili aumenta così a 26!, cioè il fattoriale di 26 (26 x 25 x 24 x 23 x … x 3 x 2 x 1), che è uguale a 403.291.461.126.605.635.584.000.000 (numero maggiore di 403 quadrilioni) chiavi possibili.
Ma dietro numeri così alti, si cela una grande fragilità, che vedremo nel prossimo articolo.
<— STEGANOGRAFIA, SOSTITUZIONE E TRASPOSIZIONE, MODULI, CODICE CESARE
/-/-/-/-/
ANALISI DELLE FREQUENZE E CIFRARIO POLIALFABETICO —>
