Algoritmo per la generazione della chiave derivata di Hilbert

Hilbert

L’algoritmo utilizzato per la generazione della chiave derivata a partire da n attributi

numerici `e stato proposto da Jonathan Lawder in [22]. Lo scopo dell’algoritmo `e

quello di determinare un’associazione univoca tra il valore di n attributi ed un punto appartenente alla curva di Hilbert, le cui coordinate compongono la chiave derivata o Hilbert derived-key. Si effettua dunque un passaggio da un sistema n-dimensionale formato dagli n attributi ad un sistema lineare formato dalle chiavi derivate di Hilbert.

Il primo passo dell’algoritmo di generazione della chiave derivata di Hilbert prevede la creazione della generator table di dimensione n necessaria per le fasi successive ed

il suo ordinamento rispetto ai valori della colonna X1. Come descritto in seguito,

l’algoritmo effettua diversi accessi alla generator table in base ai valori contenuti nella

ai valori della colonna X1, in modo da poter effettuare un accesso diretto alla tabella

in base al valore di X1. Le strutture dati utilizzate nel corso dell’algoritmo sono una

matrice di dimensione n × n, matrSc, ad indicare la matrice di trasformazione dello

stato corrente ed un array di n posizioni, signs, utilizzato per mantenere i segni degli elementi della matrice diversi da zero negativi. La posizione i -esima di questo array

avr`a valore pari a uno, se nella i -esima colonna della matrice l’elemento non nullo ha

valore pari a -1, mentre avr`a valore pari a zero nel caso in cui tale elemento abbia

valore pari ad uno. La matrice di trasformazione dello stato corrente viene modificata ad ogni iterazione del ciclo principale dell’algoritmo ed identificher`a lo stato corrente in cui l’algoritmo si trova; ad ogni aggiornamento di questa matrice corrisponde un aggiornamento dell’array dei segni degli elementi.

Un esempio della matrice di trasformazione dello stato corrente, matrSc, e della

struttura dati che ne contiene i segni, signs, `e rappresentato in figura 4.3:

Figura 4.3 – Esempio di matrice di trasformazione dello stato corrente

Il secondo passo dell’algoritmo prevede la creazione di una variable P il cui valore `e

dato dalla concatenazione delle rappresentazioni binarie dei valori degli n attributi di input. La notazione ai_j sta ad indicare il bit j -esimo dell’attributo i -esimo.

P = {a0₀ a0₁ ... a0_k−1 a1₀ a₁1 ... a1_k−1 ... an−1₀ an−1₁ ... an−1_k−1 }

La variable P avr`a dunque una dimensione pari a n × k bits, dove k esprime il

numero di bits necessari per la rappresentazione binaria dell’attributo con valore mag-

giore e n il numero di attributi (dimensioni). La variabile k esprime pi`u precisamente

l’ordine di raffinamento della curva ovvero l’intervallo di valori [0 ; 2k_{−1], in cui il valo-}

in input verr`a espressa utilizzando k bits per ciascuna, eventualmente aggiungendo uno o pi`u bit con valore pari a zero nelle posizioni pi`u significative. Un esempio del valore assunto dalla variabile P, con n = 4 e k = 5, `e riportato nella figura 4.4.

Figura 4.4 – Esempio di costruzione della variabile P

La matrice dello stato corrente all’inizio dell’algoritmo `e inizializzata con la matrice

identit`a, mentre l’array che rappresenta i segni degli elementi non nulli della matrice

contiene il valore zero in tutte le posizioni. Le altre inizializzazioni, effettuate all’inizio

dell’algoritmo, riguardano la variabile HK che conterr`a la chiave derivata di Hilbert e

una variabile intera i utilizzata per il controllo della terminazione del ciclo principale.

La variabile i inizialmente avr`a un valore pari ad uno, mentre HK `e inizializzata con

il valore zero.

La parte principale dell’algoritmo `e composta da un ciclo che viene ripetuto per k

iterazioni, con k che esprime l’ordine della curva di Hilbert ed `e mostrata in figura 4.5.

La prima istruzione del ciclo assegna alla variabile zi un valore pari ai bit i -esimi di

ciascun attributo che forma la variabile P, quindi zi sar`a composta ad ogni iterazione

da n bits. Il valore di zi corrisponde ad un n-point.

Nella seconda istruzione la variabile zi `e aggiornata con il valore restituito dal cal-

colo della funzione f1 avente come parametri lo stesso valore corrente assunto da zi e

la matrice di trasformazione dello stato corrente. La funzione f1 `e composta di due

step successivi: il primo prevede il calcolo dell’or esclusivo (XOR) tra il valore corrente

della variabile zi e l’array signs che contiene i segni della matrice di trasformazione

dello stato corrente, mentre nel secondo si effettua una permutazione dei bit del valore ottenuto come risultato del primo passo a seconda del valore degli elementi della ma-

trice matrSc corrente. Per ciascuna riga m della matrice, se esiste un valore non nullo

nella colonna j-esima e nella posizione j -esima del risultato dell’or esclusivo vi `e un bit diverso da zero, allora si pone il bit nella posizione m-esima pari al valore di quello presente nella posizione j -esima e il bit nella posizione j -esima a zero. Nel caso in cui il bit in posizione j -esima sia gi`a stato modificato in un’iterazione precedente, il suo valore rimane immutato. Il confronto tra gli elementi della matrice di trasformazione dello stato corrente ed il valore dei bit del risultato dell’or esclusivo avviene sempre sul valore ottenuto dal calcolo dopo il primo passo della funzione f1, senza tener conto

delle modifiche che possono essere state effettuate sui bit nelle iterazioni precedenti del secondo step.

Esempio 4.1.4. Un esempio del valore di zi ottenuto dal calcolo della funzione f1

avente come parametri la matrice di trasformazione dello stato corrente in figura 4.3 ed un valore di zi = 0110, `e il seguente: Primo passo: zi =signs L zi zi = 1010L 0110 = 1100 Secondo passo: m = 0, j = 1 : matrSc(0, 0) 6= 0 ∧ zi[1] 6= 0 → zi = 1000 m = 1, j = 0 : matrSc(1, 0) 6= 0 ∧ zi[0] 6= 0 → zi = 1100

m = 2, j = 2 : matrSc(2, 2) 6= 0 ∧ zi[2] = 0 nessuna trasformazione

Valore finale di zi = 1100

Il valore di zi calcolato serve per accedere alla generator table e ricavare una parte

della chiave derivata.

Nella terza istruzione si memorizza nella variabile hi il valore della k -esima parte

della chiave derivata di Hilbert, ricavato dal valore contenuto nella colonna Y della riga zi-esima della generator table creata inizialmente.

Sempre mediante la generator table si ricava nella quarta istruzione, dalla mede-

sima riga precedente indirizzata dalla variabile zi, la matrice di trasformazione per

lo stato successivo che coincide con la matrice di trasformazione contenuta nella co- lonna T(Y). L’aggiornamento della matrice dello stato corrente avviene nella quinta

istruzione del codice tramite l’esecuzione di una funzione f2, avente come parametri

la matrice di trasformazione dello stato corrente e la matrice di trasformazione per lo stato successivo ricavata dalla generator table. Il risultato restituito dal calcolo

della funzione f2 con questi parametri costituisce la nuova matrice di trasformazione

dello stato corrente. La funzione f2, come la funzione f1 `e definita mediante due step

successivi.

Il primo passo prevede il calcolo della nuova matrice di trasformazione per lo stato corrente (matrice A), come permutazione delle righe della matrice di trasformazione per lo stato successivo ricavata dalla generator table al passo precedente (matrice C - matrice di trasformazione per zi nello stato S0) in base al valore degli elementi della

matrice di trasformazione dello stato corrente attuale (matrice B). La matrice A viene calcolata in base alle seguente regola: se nella riga i-esima della matrice B esiste un bit non nullo nella colonna j-esima, allora la la riga i-esima della matrice A assume il valore degli elementi della riga j-esima della matrice C.

Il secondo step della funzione f2 modifica i segni degli elementi della matrice A a

seconda del valore degli elementi delle matrici B e C in maniera differente a seconda dei seguenti casi:

• se il segno dell’elemento non nullo nella riga m-esima della matrice B `e negativo e il segno dell’elemento non nullo nella riga j -esima della matrice C `e positivo, allora il segno dell’elemento diverso da zero nella riga m-esima della matrice A diventa negativo.

• se il segno dell’elemento non nullo nella riga m-esima della matrice B `e positivo e il segno dell’elemento non nullo nella riga j -esima della matrice C `e negativo, allora il segno dell’elemento diverso da zero nella riga m-esima della matrice A rimane immutato.

• se i segni dell’elemento non nullo nella riga m-esima della matrice B e di quello non nullo nella riga j -esima della matrice C sono entrambi positivi, allora il segno dell’elemento diverso da zero nella riga m-esima della matrice A rimane immutato.

• se i segni dell’elemento non nullo nella riga m-esima della matrice B e di quello non nullo nella riga j -esima della matrice C sono entrambi negativi, allora il segno dell’elemento diverso da zero nella riga m-esima della matrice A diventa positivo.

Una volta terminato il calcolo della funzione f2 ed ottenuta la matrice di trasfor-

mazione per il prossimo stato, si aggiorna la matrice di trasformazione dello stato corrente con questa e l’array signs con i nuovi valori.

Nella sesta e settima istruzione del corpo del ciclo dell’algoritmo si effettua rispet- tivamente uno shift verso sinistra di n bits del valore della variabile HK, che contiene

la chiave derivata di Hilbert gi`a calcolata e si somma a questa la k -esima parte della

chiave, calcolata nella terza istruzione. Al termine dell’algoritmo la variabile HK con-

terr`a la chiave derivata di Hilbert, di dimensione n × k bits, generata a partire dal

valore degli n attributi di input.