Cifrario di Merkle-Hellman

Il cifrario di Merkle-Hellman è un cifrario a chiave pubblica basato sul problema dello zaino (knapsack problem), un problema noto per la sua difficoltà computazionale in determinate condizioni.

È uno dei primi schemi di crittografia asimmetrica, introdotto da Ralph Merkle e Martin Hellman nel 1978.

L'idea chiave è trasformare una sequenza supercrescente, che permette una facile risoluzione del problema dello zaino, in una sequenza più complessa attraverso una trasformazione modulare.

La sequenza trasformata viene utilizzata come chiave pubblica, mentre la sequenza supercrescente e i parametri utilizzati nella trasformazione rimangono segreti.

Struttura del cifrario
Pro e contro del cifrario
Un esempio pratico

Struttura del cifrario

Il cifrario è costituito da tre fasi principali: generazione delle chiavi, cifratura e decifratura.

1] Generazione delle chiavi

L'utente genera una sequenza supercrescente $ a = (a_1, a_2, \ldots, a_N) $, dove ogni elemento è maggiore della somma di tutti gli elementi precedenti.

Poi sceglie un modulo $ m $ tale che $ m > 2a_N $ e un moltiplicatore $ w $, relativamente primo a $ m $.

Calcola una sequenza trasformata $ b $, detta chiave pubblica, utilizzando:

$$ b_j = wa_j \mod m, \quad \text{per } j = 1, \ldots, N $$

La sequenza $ b = (b_1, b_2, \ldots, b_N) $ viene resa pubblica, mentre $ a, m, w $ rimangono segreti.

Nota. La trasformazione $ b_j = wa_j \mod m $ rende la sequenza $ b $ non più supercrescente. Questo complica la risoluzione del problema dello zaino per chi non conosce i parametri $ m $ e $ w $.

Nel cifrario di Merkle-Hellman e in generale nei sistemi di crittografia a chiave pubblica, la chiave segreta è scelta e posseduta esclusivamente dal destinatario prima che qualsiasi messaggio venga inviato.

Quindi, il mittente non conosce $ a $, $ w $ e $ m $ ma soltanto il destinatario. Il mittente conosce solo $ b $.

2] Cifratura

Il mittente converte il messaggio in binario e lo divide in blocchi di lunghezza $ N $, dove $ N $ è il numero degli elementi scelti nella sequenza supercrescente $ a $.

Per ogni blocco binario $ x = (x_1, x_2, \ldots, x_N) $, calcola il testo cifrato $ c $ utilizzando la chiave pubblica $ b $:

$$ c = \sum_{j=1}^N b_j x_j $$

Il valore cifrato $ c $ viene inviato al destinatario.

3] Decifratura

Il destinatario usa la chiave segreta ($ m $, $ w $, e $ w^{-1} $) per calcolare:

$$ v = w^{-1}c \mod m $$

Poiché $ v $ è una combinazione lineare della sequenza supercrescente $ a $, il destinatario può risolvere facilmente il problema dello zaino per recuperare il blocco binario $ x = (x_1, x_2, \ldots, x_N) $.

In altre parole, il destinatario usa il valore $ w^{-1} $ (l'inverso moltiplicativo di $ w $ modulo $ m $) per riportare il messaggio cifrato $ c $ alla forma $ v $, che può essere risolto con la sequenza supercrescente $ a $.

Nota. Si sceglie una sequenza supercrescente $ a $ perché permette di risolvere il problema dello zaino in modo semplice: dati $ v $ e $ a $, è possibile determinare i coefficienti $ x_i $ in tempo polinomiale.

Pro e contro del cifrario

Questo metodo di cifratura ha come vantaggi la semplicità di implementazione e la sicurezza basata sulla difficoltà del problema dello zaino.

Tuttavia, già negli anni '80 sono stati scoperti dei criteri per ricondurre una sequenza trasformata $ b $ a una sequenza supercrescente, rendendo vulnerabile il cifrario.

Pertanto, oggi il cifrario non è più considerato sicuro per uso pratico nella crittografia moderna.

Questo sistema rimane comunque un'importante pietra miliare nella storia della crittografia a chiave pubblica.

Un esempio pratico

Il destinatario del messaggio sceglie una sequenza supercrescente con $ N = 4 $ elementi, dove ogni elemento è maggiore della somma degli elementi precedenti. Ad esempio, 2>1, 5>2+1. 9>1+2+5

$$ a = (1, 2, 5, 9) $$

Sceglie anche come modulo un numero primo, ad esempio $ m = 71 $ che soddisfa la condizione $ m > 2a_N = 2 \cdot 9 = 18 $

$$ m = 71$$

Poi un moltiplicatore $ w $ relativamente primo con $ m $. Ad esempio il numero $ w = 11 $.

$$ w = 11 $$

A questo punto il cifrario calcola la chiave pubblica utilizzando questi dati iniziali.

$$ b_j = wa_j \mod m, \quad \text{per } j = 1, \ldots, 4 $$

Svolge le congruenze modulari per ogni cifra della sequenza supercrescente $ a $ che è composta da $ N = 4 $ elementi.

$$ b_1 = 11 \cdot 1 \mod 71 = 11 $$

$$ b_2 = 11 \cdot 2 \mod 71 = 22 $$

$$ b_3 = 11 \cdot 5 \mod 71 = 55 $$

$$ b_4 = 11 \cdot 9 \mod 71 = 99 \mod 71 = 28 $$

Quindi, la chiave pubblica è:

$$ b = (11, 22, 55, 28) $$

Tutto è pronto per cifrare i messaggi.

Messaggio da cifrare

In questo esempio il messaggio da cfrare è semplicemente "ABCD". E' banale... ma semplifica la spiegazione.

Il mittente converte ogni lettera in blocchi binari.

Per semplicità, in questo esempio utilizzo una semplice mappatura di riferimento in cui a ogni lettera associo 5 bit.

Lettera	Binario	Lettera	Binario	Lettera	Binario
A	00000	B	00001	C	00010
D	00011	E	00100	F	00101
G	00110	H	00111	I	01000
J	01001	K	01010	L	01011
M	01100	N	01101	O	01110
P	01111	Q	10000	R	10001
S	10010	T	10011	U	10100
V	10101	W	10110	X	10111
Y	11000	Z	11001

Il messaggio "ABCD" viene convertito in blocchi binari da 5 bit ciascuno.

$$ A = 00000 $$

$$ B = 00001 $$

$$ C = 00010 $$

$$ D = 00011 $$

Ecco i blocchi binari elencati come elementi di una lista:

$$ (00000, 00001, 00010, 00011) $$

Per essere elaborati dal cifrario di Merkle-Hellman, i bit devono essere suddivisi in blocchi da $ N=4 $ cifre, tante quanti sono gli elementi della sequenza supercrescente, completando eventuali spazi mancanti alla fine con degli zeri.

$$ ( 0000 , 0000 , 0100 , 0100 , 0011 )$$

Cifratura

Per ogni blocco binario $ x = (x_1, x_2, x_3, x_4) $, il mittente calcola l'equivalente valore cifrato:

$$ c = \sum_{j=1}^4 b_j x_j \mod m $$

Svolgendo i calcoli ottiene questi valori usando i blocchi di bit a quattro cifre $ ( 0000 , 0000 , 0100 , 0100 , 0011 )$

$$ c_1 = 11 \cdot 0 + 22 \cdot 0 + 55 \cdot 0 + 28 \cdot 0 = 0 \mod 71 = 0 $$

$$ c_2 = 11 \cdot 0 + 22 \cdot 0 + 55 \cdot 0 + 28 \cdot 0 = 0 \mod 71 = 0 $$

$$ c_3 = 11 \cdot 0 + 22 \cdot 1 + 55 \cdot 0 + 28 \cdot 0 = 22 \mod 71 = 22 $$

$$ c_4 = 11 \cdot 0 + 22 \cdot 1 + 55 \cdot 0 + 28 \cdot 0 = 22 \mod 71 = 22 $$

$$ c_5 = 11 \cdot 0 + 22 \cdot 0 + 55 \cdot 1 + 28 \cdot 1 = 55 + 28 = 83 \mod 71 = 12 $$

Quindi, il messaggio cifrato è

$$ c = (0, 0, 22, 22, 12) $$

A questo punto, il mittente spedisce il messaggio al destinatario.

Nota. Il mittente non conosce la sequenza supercrescente $ a $, né il modulo $ m = 71 $, né il moltiplicatore $ w = 11 $ scelti dal destinatario.

Decifratura

Il destinatario riceve il messaggio cifrato $ c $ ed essendo a conoscenza degli elementi della chiave segreta $ a $, $ m $ e $ w $, calcola l'inverso moltiplicativo di $ w = 11 \mod 71 $

$$ w^{-1} = 13 \quad (\text{poiché } 11 \cdot 13 \mod 71 = 1) $$

Poi lo utilizza per decifrare ciascun valore del messaggio:

$$ v = w^{-1}c \mod m $$

Svolge i calcoli sul messaggio cifrato $ c = (0, 0, 22, 22, 12) $:

$$ v_1 = 13 \cdot 0 \mod 71 = 0 $$

$$ v_2 = 13 \cdot 0 \mod 71 = 0 $$

$$ v_3 = 13 \cdot 22 \mod 71 = 286 \mod 71 = 2 $$

$$ v_4 = 13 \cdot 22 \mod 71 = 286 \mod 71 = 2 $$

$$ v_5 = 13 \cdot 12 \mod 71 = 156 \mod 71 = 14 $$

A questo punto il destinatario conosce:

Il valore decifrato $ v $ ottenuto durante la decifratura. $$ v_1 = 0 \ , \ v_2 = 0 \ , \ v_3 = 61 \ , \ v_4 = 61 \ , \ v_5 = 9 $$
La sequenza supercrescente $ a = (1, 2, 5, 9) $.
La relazione: $$ v = x_1 \cdot a_1 + x_2 \cdot a_2 + x_3 \cdot a_3 + x_4 \cdot a_4 $$ Dove $ x_j \in \{0, 1\} $ sono i bit da ricostruire mentre $ a_1 , a_2 , a_3 , a_4 $ sono gli elementi della sequenza supercrescernte. $$ v = x_1 \cdot 1 + x_2 \cdot 2 + x_3 \cdot 5 + x_4 \cdot 9 $$

L'obiettivo è determinare i valori $ x_1, x_2, x_3, x_4 $ che rappresentano il blocco binario.

Come si ricostruisce il messaggio?

Seguendo la sequenza supercrescente $ a = (1, 2, 5, 9) $, il destinatario verifica se ogni elemento di $ a $ può essere "usato" (cioè sottratto) per formare $ v $:

Inizia con l'ultimo elemento di $ a $ ($ a_4 = 9 $).
Se $ a_4 \leq v $, allora il corrispondente bit $ x_4 = 1 $, e aggiorna $ v $ sottraendo $ a_4 $.
Se $ a_4 > v $, allora $ x_4 = 0 $.
Ripete il processo per gli altri elementi della sequenza ($ a_3, a_2, a_1 $).

Vediamo cosa accade nel dettaglio

Per $ v_1 = 0 $:
Nessun elemento di $ a $ può essere sottratto da $ v $ perché ($ v < a_1, a_2, a_3, a_4 $). Quindi tutti i bit $ x_j = 0 $ sono nulli. Il risultato è $$ v = x_1 \cdot 1 + x_2 \cdot 2 + x_3 \cdot 5 + x_4 \cdot 9 $$ $$ v = 0 \cdot 1 + 0 \cdot 2 + 0 \cdot 5 + 0 \cdot 9 $$ Quindi, il risultato decifrato è $$ (x_1, x_2, x_3, x_4) = (0,0,0,0) $$
Per $ v_2 = 0 $:
Nessun elemento di $ a $ può essere sottratto da $ v $ perché ($ v < a_1, a_2, a_3, a_4 $). Quindi tutti i bit $ x_j = 0 $ sono nulli. Il risultato è $$ v = x_1 \cdot 1 + x_2 \cdot 2 + x_3 \cdot 5 + x_4 \cdot 9 $$ $$ v = 0 \cdot 1 + 0 \cdot 2 + 0 \cdot 5 + 0 \cdot 9 $$ Quindi, il risultato decifrato è $$ (x_1, x_2, x_3, x_4) = (0,0,0,0) $$
Per $ v_3 = 2 $:
L'ultimo elemento $ a_4 = 9 $ non può essere sottratto da $ v=2 $, quindi $ x_4 = 1 $. L'elemento $ a_3 = 5 $ non può essere sottratto da $ v=2 $, quindi $ x_3 = 1 $. L'elemento $ a_2 = 2 $ può essere sottratto da $ v=2 $, quindi $ x_2 = 1 $ e aggiorniamo $ v=v-a_2=0 $. L'elemento $ a_1 = 1 $ non può essere sottratto da $ v=0 $ quindi $ x_1 =0 $ . Il risultato è $$ v = x_1 \cdot 1 + x_2 \cdot 2 + x_3 \cdot 5 + x_4 \cdot 9 $$ $$ v = 0 \cdot 1 + 1 \cdot 2 + 0 \cdot 5 + 0 \cdot 9 $$ Quindi, il risultato decifrato è $$ v_3 = (x_1, x_2, x_3, x_4) = (0,1,0,0) $$
Per $ v_4 = 2 $:
L'ultimo elemento $ a_4 = 9 $ non può essere sottratto da $ v=2 $, quindi $ x_4 = 1 $. L'elemento $ a_3 = 5 $ non può essere sottratto da $ v=2 $, quindi $ x_3 = 1 $. L'elemento $ a_2 = 2 $ può essere sottratto da $ v=2 $, quindi $ x_2 = 1 $ e aggiorniamo $ v=v-a_2=0 $. L'elemento $ a_1 = 1 $ non può essere sottratto da $ v=0 $ quindi $ x_1 =0 $ . Il risultato è $$ v = x_1 \cdot 1 + x_2 \cdot 2 + x_3 \cdot 5 + x_4 \cdot 9 $$ $$ v = 0 \cdot 1 + 1 \cdot 2 + 0 \cdot 5 + 0 \cdot 9 $$ Quindi, il risultato decifrato è $$ v_4 = (x_1, x_2, x_3, x_4) = (0,1,0,0) $$
Per $ v_5 = 14 $:
L'ultimo elemento $ a_4 = 9 $ può essere sottratto ($ 14 - 9 = 5 $), quindi $ x_4 = 1 $ e aggiorniamo $ v = v - a_4 = 5 $. L'elemento $ a_3 = 5 $ può essere sottratto ($ 5 - 5 = 5 $), quindi $ x_3 = 1 $ e aggiorniamo $ v = v - a_3 = 0 $. Gli altri elementi ($ a_2, a_1 $) non possono essere sottratti ($ v = 0 $). Il risultato è $$ v = x_1 \cdot 1 + x_2 \cdot 2 + x_3 \cdot 5 + x_4 \cdot 9 $$ $$ v = 0 \cdot 1 + 0 \cdot 2 +1 \cdot 5 + 1 \cdot 9 $$ $$ v =14 $$ Quindi, il risultato decifrato è $$ v_5 = (x_1, x_2, x_3, x_4) = (0,0,1,1) $$

Ricapitolando, grazie alla sequenza supercrescente, $ a = (1, 2, 5, 9) $ il destinatario riesce a scomporre $ v $ nei blocchi binari della mappatura iniziale.

$$ v_1 = 0 \to (0, 0, 0, 0) $$

$$ v_2 = 0 \to (0, 0, 0, 0) $$

$$ v_3 = 0 \to (0, 1, 0, 0) $$

$$ v_4 = 0 \to (0, 1, 0, 0) $$

$$ v_5 = 0 \to (0, 0, 1, 0) $$

Mettendo in sequenza i blocchi in binario, i bit sono raggruppati in $ N=4 $ cifre ciascuno:

$$ ( 0000 , 0000 , 0100 , 0100 , 0011 )$$

Poiché la mappatura utilizzata all'inizio utilizza blocchi da 5 cifre per ciascuna lettera, il destinatario deve raggruppare i bit in 5 cifre ciascuno mantenendo la stessa sequenza.

$$ ( 00000 , 00001, 00010, 00011 )$$

A questo punto può ricostruire il messaggio. A ciascuno di questi blocchi corrisponde una lettera.

$$ 00000 = A $$

$$ 00001 = B $$

$$ 00010 = C $$

$$ 00011 = D $$

Quindi, il messaggio decifrato è: "ABCD".

In conclusione, il cifrario ha funzionato correttamente, recuperando il messaggio originale.

Nota. Una volta capito come funziona il cifrario Merkle-Hellman... posso pure scordarmelo perché negli anni '80 hanno trovato il modo per individuare la sequenza supercrescente nei messaggi cifrati, rendendolo vulnerabile. Quindi, nella pratica questo cifrario è utile quanto un ombrello bucato sotto la pioggia. In genere, oggi per cifrare i messaggi si utilizza un algoritmo RSA

E così via.