# Merkle-Hellman

Merkle-Hellman (MH) fu uno dei primi crittosistemi a chiave pubblica creato da Ralph Merkle e Martin Hellman nel 1978. Nonostante l'idea sia elegante, e più semplice di quella dell'RSA, l'algoritmo è stato forzato. Il sistema Merkle-Hellman è basato sul problema della somma di sottoinsiemi (un caso speciale del problema dello zaino): data una lista di numeri e un altro numero, il quale è la somma di un sottoinsieme dei numeri precedenti, determinare il sottoinsieme. In generale, questo problema è conosciuto essere NP-completo; tuttavia, esistono alcuni casi 'facili' che possono essere risolti efficientemente. Lo schema Merkle-Hellman è basato sulla trasformazione di casi facili in casi difficili, e viceversa. Tuttavia, lo schema fu forzato da Adi Shamir, non attaccando il problema dello zaino, ma piuttosto forzando la trasformazione dal problema facile a quello difficile.

## Descrizione
### Generazione della chiave

Per cifrare un messaggio di n bit si sceglie una sequenza crescente
    w = (w$_1$, w$_2$, ..., w$_n$)
di n numeri naturali (tranne lo zero) tale che ogni elemento sia maggiore della somma degli elementi precedenti, per esempio {1, 2, 5, 8, 16}. Si sceglie un intero casuale q tale che
q > $\sum _{i=1}^{n}w_{i}$,
e un intero casuale r tale che MCD(r,q) = 1.
q deve essere scelto in modo tale da assicurare l'unicità del messaggio cifrato, cosa che non avviene per valori di q inferiori alla sommatoria di cui sopra. Il valore scelto per r deve essere coprimo con q altrimenti non avrà un inverso mod q. L'esistenza dell'inverso di r è necessario perché sia possibile la decifrazione.
Si calcoli la sequenza
    β = (β$_1$, β$_2$, ..., β$_n$)
dove β$_i$ = rw$_i$ (mod q). La chiave pubblica è β, mentre la chiave privata è (w, q, r).

### Cifratura

Per cifrare un messaggio di n bit
    α = (α$_1$, α$_2$, ..., α$_n$),
dove α$_i$ è l'i-esimo bit del messaggio e α$_i$ ${\boldsymbol {\in }}$ {0, 1} si calcola
    $c=\sum _{i=1}^{n}\alpha _{i}\beta _{i}$.
Il messaggio cifrato è c.

### Decifrazione

Per decifrare un testo cifrato c il ricevente deve trovare nel messaggio i bit α$_i$ tali che soddisfino:
    $c=\sum _{i=1}^{n}\alpha _{i}\beta _{i}.$
Questo sarebbe un problema difficile se i valori β$_i$ fossero casuali perché il ricevente dovrebbe risolvere un'istanza del problema della somma di sottoinsiemi, che è noto essere NP-completo. Tuttavia, i valori β$_i$ sono stati scelti in modo che la decifrazione è facile se si conosce la chiave privata (w, q, r).
Per decifrare bisogna trovare un intero s che sia l'inverso di r modulo q. Ciò significa che s soddisfa l'equazione s r mod q = 1 o equivalentemente che esiste un intero k tale che sr = kq + 1. Avendo scelto r tale che MCD(r,q)=1 è possibile trovare s e k usando l'algoritmo di Euclide esteso. Quindi il ricevente del testo cifrato c calcola
    $c'\equiv cs{\pmod {q}}.$
Da cui
    $c'\equiv cs\equiv \sum _{i=1}^{n}\alpha _{i}\beta _{i}s{\pmod {q}}.$
Siccome rs mod q = 1 e β$_i$ = rw$_i$ mod q segue
    $\beta _{i}s\equiv w_{i}rs\equiv w_{i}{\pmod {q}}.$
Da cui
    $c'\equiv \sum _{i=1}^{n}\alpha _{i}w_{i}{\pmod {q}}.$
La somma di tutti i valori w$_i$ è minore di q e quindi anche $\sum _{i=1}^{n}\alpha _{i}w_{i}$ è nell'intervallo [0,q-1]. Dopodiché il ricevente deve risolvere il problema della somma di sottoinsiemi
    $c'=\sum _{i=1}^{n}\alpha _{i}w_{i}.$
Questo problema è facile perché w è una sequenza supercrescente. Sia w$_k$ l'elemento maggiore in w. Se w$_k$ > c' , allora α$_k$ = 0, se w$_k$≤c' , allora α$_k$ = 1. Sottrarre w$_k$×α$_k$ da c' , e ripetere questi passo fino ad ottenere α.

## Esempio

Come prima cosa, creare una sequenza supercrescente w
Questa è la base per la chiave privata. Da questa, calcolare la somma.
    $\sum w=706$
Poi, scegliere un numero q maggiore della somma.
Inoltre, scegliere un numero r all'interno dell'intervallo $[1,q)$ e coprimo a q.
La chiave privata consiste di q, w e r.
Per calcolare una chiave pubblica, generare una sequenza β moltiplicando ogni elemento in w per r mod q
infatti
La sequenza β è la chiave pubblica.
Poniamo che Alice voglia cifrare "a". Primo, deve trasformare "a" in notazione binaria (in questo caso usando le codifiche ASCII o UTF-8)
Secondo, moltiplica ogni bit per il numero corrispondente in β
Alice invia questo numero al destinatario.
Per decifrare, Bob moltiplica 1129 per r $^{−1}$ mod $q$ (Vedere aritmetica modulare)
Ora Bob decompone 372 selezionando l'elemento più grande in w minore o uguale a 372. Poi selezionando il secondo elemento più grande in w minore o uguale alla differenza, fino a quando la differenza è pari a $0$:
Gli elementi selezionati dalla chiave privata corrispondono ai bit pari a 1 nel messaggio
Se riconvertito dalla notazione binaria, il messaggio decifrato è proprio "a".