Merkle's puzzles

Crittografia

Crittografia a chiave pubblica

Idea -> lucchetto (chiave pubblica, privata)

Esempio

Merkle's puzzles

Creare un lucchetto (e una chiave)

Creare tantissimi problemi risolvibili (ma che necessitano un po' di tempo) e con come risultato due numeri: n e k in modo che n sia 1 per un problema, 2 per un altro, 3 per un alto ancora,...

Tenere a mente che k corrisponde ad ogni n (la chiave privata) Spedire tutti i problemi (ma in sequenza disordinata, casuale) (questa è la chiave pubblica)

Chiudere un lucchetto (spedire un messaggio cifrato)

scegliere un problema a caso dalla chiave pubblica risolverlo (trovando così n1 e k1 rendere illeggibile il messaggio usando k1 spedire n1 e il messaggio reso illeggibile

Aprire il lucchetto (decrittare il messaggio)

a partire da n1 (siccome si conosce la chiave private) trovare k1
Decifrare il messaggio usando k1

Un “nemico” qualcuno cioè che non conosce la chiave privata per trovare k1 (siccome non sa quale problema è stato risolto) deve risolvere circa la metà dei problemi. Questo se la chiave è veramente lunga è impraticabile.

Metodi usati

L'esempio dei Merkle's Puzzles è semplice da capire, ma perché sia sicuro la chiave deve essere incredibilmente lunga. Questo ovviamente è scomodo e impraticabile, in realtà i metodi che si usano (ad esempio RSA) si basano su problemi matematici riconosciuti difficili (ad esempio logaritmo discreto o radice in gruppi finiti e fattorizzazione). In questi problemi la difficoltà nel trovare la chiave aumenta in modo esponenziale e non lineare come per i Merkle's Puzzles. Cioè se la chiave è lunga il doppio, decrittare non è solo il doppio più difficile ma molto,molto di più (difficoltà non k*lunghzza(Chiave) ma klunghezza(Chiave)). Così che con chiavi non troppo lunghe è comunque impraticabile decrittare il messaggio.

Esempi

Comunicazione segreta

I metodi a chiave pubblica permettono ad esempio a due persone che non si sono messe d'accordo prima di parlare in modo segreto (importante per esempio per effetuare pagamenti su internet)

  1. Alice prepara una chiave pubblica (e una privata)
  2. Alice spedisce la chiave pubblica a Bob
  3. Bob usa la chiave pubblica per spedire una chiave c (crittata) a Alice
  4. Alice e Bob usano la chiave c per comunicare in modo segreto

Eve (il nemico) può spedire anche lei un messaggio a Bob, ma non può capire la chiave c e quindi quello che Alice e Bob si dicono.

Proprietà

Se uno ci pensa bene può vedere un problema del metodo a chiave pubblica: l'autentificazione non è garantita. Cioè il fatto che la chiave pubblica di Bob sia proprio di Bob deve essere garantito in qualche modo esterno. Sembra infatti che si possa trasformare l'autenticità in segretezza (e la segretezza in autenticità), ma che non sia possibile “creare” autenticità o “segretezza” dal nulla (cosa che se ci si pensa un attimo appare logica).

Dimostrazioni a conoscenza zero

Anche se sembra quasi un paradosso si può dimostrare (in maniera probabilistica) di sapere qualcosa senza fornire informazioni su quello che si sa.

Password

Ad esempio si può dimostrare di conoscere una password senza dirla (e senza fornire informazioni su di essa). Per fare questo basta che la password sia una chiave privata di un metodo a chiave pubblica.
  1. Il computer conosce la tua chiave pubblica
  2. Il computer, usando la chiave pubblica, rende illeggibile un messaggio che sceglie a caso
  3. Il computer ti spedisce il messaggio
  4. Tu (siccome conosci la chiave privata) lo decifri
  5. Spedisci poi il messaggio decifrato al computer (crittato pero con un metodo convenzionale e una chiave k)
  6. Il computer ti fornisce il messaggio decrittato
  7. Se il messaggio decifrato fornito dal computer è lo stesso di quello che tu hai decifrato dimostri al computer che lo hai saputo decifrare fornendogli la chiave k
  8. Il computer (con la chiave k) decifra il tuo messaggio. Se corrisponde a quello che ti ha spedito ricomincia dal punto 2 fino a quando è convinto che tu non hai potuto indovinare semplicemente per fortuna, ma perché conoscevi la chiave. Se no sa che sei un impostore

Commenti

Come si può vedere da questo esempio la dimostazione è probabilistica e sfrutta l''esistenza di sequenze casuali (non prevedibili). Il computer è convinto che tu sai la password perché é andato a caso, e quindi pensa che tu non possa sempre avere fortuna. Però il computer non può dimostrare ad un'altra persona (Eve) che tu sai la password facendogli vedere la registrazione della dimostrazione. Infatti Eve può sempre pensare che il computer era d'accordo con te, e che non sia andato a caso. Solo quello che fa la dimostrazione sa di essere andato a caso. Il computer non ha bisogno di conoscere la password (basta che sappia la chiave pubblica).

Che questa dimostrazione sia veramente a conoscenza zero si può dedurre dal fatto che il computer può simulare una registrazione di una dimostrazione di conoscenza della password da solo. Quindi le informazioni che impara da te può benissimo simularle e impararle da solo. Ciò significa che tu non gli hai insegnato niente di nuovo che non poteva sapere da solo.