ℐl
cifrario che andiamo a vedere è una semplice evoluzione del
cifrario di Cesare
che si basa sui concetti di algebra lineare e
cioè sul calcolo matriciale. Ho tratto l'idea da un articolo
di Hacker
Journal ma
probabilmente queste idee fanno parte
dell'introduzione dei testi universitari che parlano di crittografia.
Per cifrare il messaggio che supponiamo in caratteri ascii, lo dividiamo in blocchi di N*N caratteri e lo moltiplichiamo per la matrice A che supponiamo quadrata di ordine N (matrice N*N). Per la decifratura è sufficiente moltiplicare il messaggio cifrato diviso in blocchi di N*N caratteri, per la chiave A-1.
Un teorema ci dice che A è invertibile sse (se e solo se) ha determinante non nullo, un altro teorema ci dice che deve avere determinante pari a ±1 sse vogliamo che A-1 abbia valori interi (cioè matrice a elementi in Z), cosa molto comoda.
Con OCTAVE possiamo fare tutti i calcoli del caso, riporto immediatamente di seguito i comandi direttamente inseribili in Octave per seguire l'esempio. Se scegliamo:
"; ?>
A=[1,2;3,5]
il determinante è:
det(A)
l'inversa ha quindi valori in Z:
inv(A)
supponiamo che il messaggio sia:
M=[1,2,3,4,5,6,7,8,9]
dove per facilità di comprensione del problema possiamo fare corrispondere al numero 1 la lettera a, al numero 2 la lettera b, ecc, quindi M sarà anche:
M=[a,b,c,d,e,f,g,h,i,l]
dividiamolo in vettori di dimensione 2:
m1=[1;2]
m2=[3;4]
m3=[5;6]
m4=[7;8]
m5=[9;0]
il messaggio cifrato C sarà:
C=[A*m1;A*m2;A*m3;A*m4;A*m5]
che avrà questo codice numerico:
ovvero mettendolo in una unica riga:
C = [5 13 11 29 17 45 23 61 9 27]
L'operazione di decifratura è del tutto simmetrica, si scompone il messaggio cifrato C in 5 sotto-messaggi:
c1=[05;13]
c2=[11;29]
c3=[17;45]
c4=[23;61]
c5=[09;27]
e si riottiene il messaggio:
a=inv(A)
M=[a*c1;a*c2;a*c3;a*c4;a*c5]
e cioè:
M=[1,2,3,4,5,6,7,8,9]
M=[a,b,c,d,e,f,g,h,i,l]
Esistono dei piccoli problemi pratici come ad esempio il caso di messaggi a lunghezza non multipla dell'ordine della matrice scelta, come nel caso mostrato e poi il problema di riportare in codifica ASCII il messaggio cifrato.
Il primo si può risolvere riportando a inizio messaggio la lunghezza del messaggio stesso e aggiungendo nei posti liberi in coda dei caratteri casuali, il secondo si può risolvere esprimendo in base 127 (o quanti sono i caratteri ASCII stampabili) il messaggio oppure utilizzando una compressione che dia una uscita ASCII.
Per quanto riguarda la determinazione di una matrice N*N che abbia determinante unitario si ricade nella teoria delle matrici di SL(N,Z). Se qualcuno è interessato mi posso informare riguardo questa teoria che però a prima vista pare complessa e inoltre non ho trovato funzioni di Octave che le generino. Mi pare di avere capito che vengano anche chiamate matrici monodrome.
Se il problema fosse difficile si può ricorrere alla matematica delle frazioni visto che l'inversa di una matrice a elementi interi è una matrice a elementi frazionari.
Nota: Il cifrario di Cesare ottiene il testo cifrato aumentando di tre il codice ASCII di ogni lettera del messaggio in chiaro, per esempio "cesare" diventa "fhvduh". Corrisponde in pratica a un ROT-3.
Per cifrare il messaggio che supponiamo in caratteri ascii, lo dividiamo in blocchi di N*N caratteri e lo moltiplichiamo per la matrice A che supponiamo quadrata di ordine N (matrice N*N). Per la decifratura è sufficiente moltiplicare il messaggio cifrato diviso in blocchi di N*N caratteri, per la chiave A-1.
Un teorema ci dice che A è invertibile sse (se e solo se) ha determinante non nullo, un altro teorema ci dice che deve avere determinante pari a ±1 sse vogliamo che A-1 abbia valori interi (cioè matrice a elementi in Z), cosa molto comoda.
Con OCTAVE possiamo fare tutti i calcoli del caso, riporto immediatamente di seguito i comandi direttamente inseribili in Octave per seguire l'esempio. Se scegliamo:
"; ?>
A=[1,2;3,5]
il determinante è:
det(A)
l'inversa ha quindi valori in Z:
inv(A)
supponiamo che il messaggio sia:
M=[1,2,3,4,5,6,7,8,9]
dove per facilità di comprensione del problema possiamo fare corrispondere al numero 1 la lettera a, al numero 2 la lettera b, ecc, quindi M sarà anche:
M=[a,b,c,d,e,f,g,h,i,l]
dividiamolo in vettori di dimensione 2:
m1=[1;2]
m2=[3;4]
m3=[5;6]
m4=[7;8]
m5=[9;0]
il messaggio cifrato C sarà:
C=[A*m1;A*m2;A*m3;A*m4;A*m5]
che avrà questo codice numerico:
ovvero mettendolo in una unica riga:
C = [5 13 11 29 17 45 23 61 9 27]
L'operazione di decifratura è del tutto simmetrica, si scompone il messaggio cifrato C in 5 sotto-messaggi:
c1=[05;13]
c2=[11;29]
c3=[17;45]
c4=[23;61]
c5=[09;27]
e si riottiene il messaggio:
a=inv(A)
M=[a*c1;a*c2;a*c3;a*c4;a*c5]
e cioè:
M=[1,2,3,4,5,6,7,8,9]
M=[a,b,c,d,e,f,g,h,i,l]
Esistono dei piccoli problemi pratici come ad esempio il caso di messaggi a lunghezza non multipla dell'ordine della matrice scelta, come nel caso mostrato e poi il problema di riportare in codifica ASCII il messaggio cifrato.
Il primo si può risolvere riportando a inizio messaggio la lunghezza del messaggio stesso e aggiungendo nei posti liberi in coda dei caratteri casuali, il secondo si può risolvere esprimendo in base 127 (o quanti sono i caratteri ASCII stampabili) il messaggio oppure utilizzando una compressione che dia una uscita ASCII.
Per quanto riguarda la determinazione di una matrice N*N che abbia determinante unitario si ricade nella teoria delle matrici di SL(N,Z). Se qualcuno è interessato mi posso informare riguardo questa teoria che però a prima vista pare complessa e inoltre non ho trovato funzioni di Octave che le generino. Mi pare di avere capito che vengano anche chiamate matrici monodrome.
Se il problema fosse difficile si può ricorrere alla matematica delle frazioni visto che l'inversa di una matrice a elementi interi è una matrice a elementi frazionari.
Nota: Il cifrario di Cesare ottiene il testo cifrato aumentando di tre il codice ASCII di ogni lettera del messaggio in chiaro, per esempio "cesare" diventa "fhvduh". Corrisponde in pratica a un ROT-3.
