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 = (w1, w2, ..., wn)

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 > i = 1 n w i {\displaystyle \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 = rwi (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 {\displaystyle {\boldsymbol {\in }}} {0, 1} si calcola

c = i = 1 n α i β i {\displaystyle 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 = i = 1 n α i β i . {\displaystyle 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 c s ( mod q ) . {\displaystyle c'\equiv cs{\pmod {q}}.}

Da cui

c c s i = 1 n α i β i s ( mod q ) . {\displaystyle c'\equiv cs\equiv \sum _{i=1}^{n}\alpha _{i}\beta _{i}s{\pmod {q}}.}

Siccome rs mod q = 1 e βi = rwi mod q segue

β i s w i r s w i ( mod q ) . {\displaystyle \beta _{i}s\equiv w_{i}rs\equiv w_{i}{\pmod {q}}.}

Da cui

c i = 1 n α i w i ( mod q ) . {\displaystyle c'\equiv \sum _{i=1}^{n}\alpha _{i}w_{i}{\pmod {q}}.}

La somma di tutti i valori wi è minore di q e quindi anche i = 1 n α i w i {\displaystyle \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 = i = 1 n α i w i . {\displaystyle c'=\sum _{i=1}^{n}\alpha _{i}w_{i}.}

Questo problema è facile perché w è una sequenza supercrescente. Sia wk l'elemento maggiore in w. Se wk > c' , allora αk = 0, se wkc' , allora αk = 1. Sottrarre wk×αk da c' , e ripetere questi passo fino ad ottenere α.

Esempio

Come prima cosa, creare una sequenza supercrescente w

w = {2, 7, 11, 21, 42, 89, 180, 354}

Questa è la base per la chiave privata. Da questa, calcolare la somma.

w = 706 {\displaystyle \sum w=706}

Poi, scegliere un numero q maggiore della somma.

q = 881

Inoltre, scegliere un numero r all'interno dell'intervallo [ 1 , q ) {\displaystyle [1,q)} e coprimo a q.

r = 588

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

β = {295, 592, 301, 14, 28, 353, 120, 236}

infatti

2 * 588 mod 881 = 295
7 * 588 mod 881 = 592
11 * 588 mod 881 = 301
21 * 588 mod 881 = 14
42 * 588 mod 881 = 28
89 * 588 mod 881 = 353
180 * 588 mod 881 = 120
354 * 588 mod 881 = 236

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)

01100001

Secondo, moltiplica ogni bit per il numero corrispondente in β

a = 01100001
0 * 295
+ 1 * 592
+ 1 * 301
+ 0 * 14
+ 0 * 28
+ 0 * 353
+ 0 * 120
+ 1 * 236
= 1129

Alice invia questo numero al destinatario.

Per decifrare, Bob moltiplica 1129 per r −1 mod q {\displaystyle q} (Vedere aritmetica modulare)

1129 * 442 mod 881 = 372

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 {\displaystyle 0} :

372 - 354 = 18
18 - 11 = 7
7 - 7 = 0

Gli elementi selezionati dalla chiave privata corrispondono ai bit pari a 1 nel messaggio

01100001

Se riconvertito dalla notazione binaria, il messaggio decifrato è proprio "a".

Bibliografia

  • (EN) Ralph Merkle e Martin Hellman, Hiding information and signatures in trapdoor knapsacks, in IEEE Transactions on Information Theory, vol. 24, n. 5, settembre 1978, pp. 525–530, DOI:10.1109/tit.1978.1055927. URL consultato il 7 maggio 2024.
  • (EN) Adi Shamir, A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem (PDF), Springer, 1983, pp. 279–288, DOI:10.1007/978-1-4757-0602-4_27, ISBN 978-1-4757-0604-8 (archiviato dall'url originale il 24 aprile 2005).
  Portale Crittografia
  Portale Sicurezza informatica