Premessa

In effetti chi si occupa di crittografia sa che una possibilità di cifrare un testo, consiste in:

• convertirlo in numeri [1],
• segmentarlo in pezzetti di uguale lunghezza,
• e moltiplicarlo, pezzetto per pezzetto, per una matrice quadrata [2] della stessa dimensione dei segmenti.

Per decifrare basta invertire il processo, con l'accortezza di utilizzare l'inverso (sempre modulo m) della matrice predetta.

Avvertimento. Non utilizzate questo algoritmo per casi reali, in cui eventuali assalitori possono cercare di analizzare il processo. Infatti vi è un punto debole: se l'analista riesce ad ottenere un frammento di testo cifrato e la relativa controparte non cifrata, risalire alla chiave di cifratura per decrifrare qualunque testo è banale: basta una divisione matriciale.

Osservazioni

Data la premessa, ci è spontaneo osservare che il punto focale della cifratura di Hill è data da operazioni matriciali, in particolare il prodotto tra due matrici [3] e la capacità di invertire una matrice.

Bene. Il calcolo matriciale è uno strumento estremamente diffuso in ambito tecnico e scientifico. Esistono pletore di librerie che ci danno gli strumenti per attuarlo. Ad esempio in Python si può utilizzare Numpy oppure Sympy.

Ma le librerie indicate mancano di un tool fondamentale in questo contesto. L'inversione modulo m della matrice che ci interessa. E questo ci da' lo spunto per inventare l'acqua calda, sviluppando da zero i nostri strumenti per il calcolo matriciale.

Utilizzando Python, e tenendoci ad un livello didattico, non andiamo incontro ad uno sforzo improbo.

Per chi ha fretta, qui si trova un minimo di codice, da cui partire per sperimentare e, se si vuole, migliorare.

In pratica abbiamo la classe NMatrix (la N serve a ricordarci che ci muoviamo su un piano Naive) che istanzia un oggetto matrice a partire da una lista di righe, ognuna delle quali a sua volta rappresentata da una lista. Ad esempio, creiamo due matrici 3 x 3 e moltiplichiamole:

>>> import nmatrix as nm

>>> A = nm.NMatrix([[1,2,3], [10,11,12], [21,22,23]])
>>> print(A)
[[1, 2, 3],
 [10, 11, 12],
 [21, 22, 23]]
>>> B = nm.NMatrix([[10,20,30], [10,11,12], [21,22,23]])
>>> print(B)
[[10, 20, 30],
 [10, 11, 12],
 [21, 22, 23]]
>>> C = A * B
>>> print(C)
[[93, 108, 123],
 [462, 585, 708],
 [913, 1168, 1423]]

La maggior parte del codice è semplice. La rappresentazione interna della matrice è la stessa lista di liste che abbiamo utilizzato per crearla:

def __init__(self, lol):
    # ... <cut>...
    self.__m__ = lol
    self.shape = (lr, lc,)

E tutte le operazioni si svilupperanno su questa lista di liste. In particolare quelle per l'accesso tramite indici:

def __getitem__(self, key):
    '''access by indices

       params key   int or tuple
       return requested element

       remark use:
         - M[i]          to get a row, i starts from 0
         - M[i, j]       to pick element at row i, col j
         - you can use M[i][j] too, but this isn't homogeneous with writing by indices
    '''
    if isinstance(key, tuple):
        x, y = key
        return self.__m__[x][y]
    else:
        return self.__m__.__getitem__(key)

def __setitem__(self, key, value):
    '''write by indices

       params
         - key   int or tuple
         - value list or number
       return None

       remark use:
         - M[i] = [row]         to write a row, i starts from 0
         - M[i, j] = number     to write a number at row i, col j
    '''
    # ...<cut>...
    if isinstance(key, tuple):
        x, y = key
        self.__m__[x][y] = value
    else:
        self.__m__[key] = value

Il metodo __getitem__ viene utilizzato da Python quando tentiamo un accesso ad un oggetto tramite indice. A esempio utilizzando una lista:

>>> l = [1, 2, 3]
>>> l[0]
1

L'espressione l[0] chiede a Python un accesso all'elemento con indice 0 della lista l. Python esegue, chiamando a sua volta l.__getitem__(0).

Analogamente, __setitem__ è il metodo chiamato per scrivere il contenuto dell'elemento di indice indicato. Ad esempio:

>>> l = [1, 2, 3]
>>> l[0]
1
>>> l[0] = 10
>>> l[0]
10

In questo caso quando chiediamo l[0] = 10, chiediamo di fare in modo che l'elemento di indice 0 di l sia 10. Python esegue l.__setitem__(0, 10). Qui vi è una complicazione dovuta al fatto che noi accediamo a liste di liste, quindi potremmo dover utilizzare due indici per l'accesso: riga e colonna. Per questo dobbiamo controllare se il nostro indice è un elemento composto (una tupla). In caso affermativo bisogna spacchettarlo ed utilizzare l'espressione self.__m__[x][y] = value. Nel caso di __getitem__ questo non sarebbe necessario, ma avremmo due notazioni diverse per la lettura rispetto la scrittura. Avremmo:

>>> A  = nm.NMatrix([[1,2,3],[10,11,12]])
>>> A[1][0]
10
>>> A[1, 0] = 100
>>> A[1][0]
100

Per avere una notazione omogenea, abbiamo implementato il controllo della tupla anche in __getitem__.

Bene. Le operazioni si possono implementare utilizzando i metodi __add__ per l'addizione, __sub__ per la sottrazione, e così via. In questo modo abbiamo la possibilità di utilizzare gli operatori di Python direttamente sulle istanze della nostra classe: molto elegante.

Nel calcolo matriciale le cose si fanno complesse quando dobbiamo calcolare l'inversa di una matrice o il suo determinante. In questo caso vi sono elementi di disturbo, che ci possono complicare la vita. In particolare se dobbiamo usare l'aritmetica modulo m. Infatti, mentre per i numeri reali diversi da 0, l'inverso è una operazione che ha sempre senso, nel caso di aritmetica modulare questo non è detto.

Ad esempio, l'inverso modulo 26 del numero 12, non esiste. Infatti deve esistere un numero n tale che 12 * n = 1 (mod 26) ovvero (12 * n) % 26 deve dare resto 1. Provando i numeri interi da 1 a 25, nessun resto di questa espressione dà 1.

Per questo motivo alcuni algoritmi di calcolo si inceppano, anche se l'inversa esiste. Ragion per cui in nmatrix.py vi sono due diverse modalità di calcolo del determinante e, sopratutto, della matrice inversa modulo m: inv_mod0 e inv_mod. La prima è più elegante, ma va in errore quando trova sulla diagonale elementi per i quali non può calcolare l'inversa modulo m. Abbiamo provato a spostare questi elementi con operazioni elementari sulle righe, ma non funziona comunque quando ci si imbatte in una intera colonna siffatta (e può capitare).

Il secondo algoritmo (inv_mod) si è dimostrato più robusto, anche se personalmente lo riteniamo meno elegante.

Enjoy. ldfa