Il primo esempio di connubio tra la Matematica e la Crittografia risale ai cifrari di Cesare.
A
B
C
D
E
F
G
H
I
L
M
N
O
P
Q
R
S
T
U
V
Z
_
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
I cifrari di Cesare consistono semplicemente nella traslazione di vettore modulo k dei valori assegnati alle lettere: così, ad esempio, assegnati al vettore modulo “1” e verso “destra”, A diventa B, B diventa C e così via…
In formule: y = x+1 (dove x è la lettera di partenza e y quella di arrivo.)
Senza volerlo siamo finiti nel mondo dell’ aritmetica modulare, che onsiste nella riduzione dell’ insieme dei numeri interi positivi e negativi (Z,per intenderci) ad un numero finito di classi di equivalenza, cioè di sottoinsiemi i cui elementi hanno come caratteristica comune il resto della divisione per un certo numero “n” (ovvero il numero di classi di equivalenza), e tale caratteristica diventa un po’ come l’ “etichetta” della classe a cui appartiene.
Ad esempio, quando ci riferiamo a Z5 stiamo indicando un insieme numerico di 5 classi di equivalenza numerate da 0 a 4: nella classe “0” abbiamo i numeri 0, 5, 10…(che hanno come resto 0 nella divisione per 5); nella classe “1” abbiamo 1, 6, 11, 16…e così via per tutte le altre classi.
La particolarità di questo sistema è che i numeri di una classe possono essere identificati più rapidamente attraverso la propria “etichetta” (così ad esempio in Z5 7, 12, 17… assumono tutti come valore 2), e che operando in Zn otteniamo uguaglianze che nell’aritmetica tradizionale non incontriamo mai.
Iniziamo allora a studiare l’addizione e la moltiplicazione algebriche in aritmetica modulare.
Cosa succede nell’addizione in Z7?
Attraverso questa tabella notiamo che i valori non superano il 6; ne deduciamo che i risultati trovati sono in realtà i resti della divisone per 7 di (a + b).
Ogni numero “a” sommato a 0 dà sempre “a”, per cui 0 è l’elemento neutro nell’ addizione in Zn.
Tra le tante curiosità della tabella, ricordiamo che i risultati sono simmetrici tra loro rispetto alla diagonale indicata (detta “principale”), e ciò è segno che l’addizione è commutativa in Zn, mentre si ripetono parallelamente alla seconda diagonale.
La situazione non cambia molto per la moltiplicazione, stavolta in Z5.
Ciascun numero “a” moltiplicato per 0 dà sempre 0, pertanto 0 è l’elemento assorbente nella moltiplicazione in Zn.
Inoltre ciascun numero “a” moltiplicato per 1 dà sempre a; ne ricaviamo che 1 è l’elemento neutro nella moltiplicazione in Zn.
Se a * b = 1, allora “a” e “b” sono invertibili in Zn, cioè “a” è l’inverso di “b” e viceversa.
Tuttavia ciò succede solamente quando “a”, o “b”, è coprimo con n in Zn (cioè MCD(a,n) = 1).
(Questa caratteristica sarà fondamentale nel sistema di cifratura RSA, che tratteremo in seguito).
Infatti osserviamo che in Z4 2 non è coprimo con “n” e non è quindi invertibile (cioè non esiste nessun numero che moltiplicato per 2 dia 1).
Ovviamente in Zn è possibile risolvere anche equazioni di primo grado:
1) 2x=3 in Z5
2) 2x=1 in Z4
Per risolvere queste equazioni bisogna ricorrere ad un metodo che inconsciamente utilizziamo anche per quelle tradizionali, e cioè annullare il coefficiente dell’ incognita:
ad es.
2x = 1 ------------> ½ * 2x = ½ * 1 ------------> x = ½
