Come posso consentire l'accesso ai dati crittografati se solo 2 utenti su 3 forniscono un segreto?

Si chiama crittografia della soglia (o, qui, decrittografia).

Uno schema ben noto è Condivisione segreta di Shamir . Permette di suddividere un valore segreto in condivisioni n , in modo tale che qualsiasi azione t sia sufficiente per ricostruire il segreto. n e t possono essere scelti a piacimento (anche se vorrai avere n maggiore di t nella pratica) . Per il problema della crittografia della soglia, si applica lo schema di Shamir sulla chiave di decrittografia. Quando i t detentori di quote si incontrano, possono ricostruire la chiave di decodifica e quindi decrittografare i dati.

Sebbene lo schema di Shamir sia valido (in effetti, è provabilmente sicuro anche contro gli aggressori con infinite capacità computazionali - pochissimi algoritmi crittografici possono pretendere di essere altrettanto sicuri), ha una limitazione che è la seguente: ricostruisce un < em> segreto . Questo lo rende in qualche modo "one shot": se gli shareholder ricostruiscono il segreto, allora hanno il segreto. Ognuno di loro sarà in grado di eseguire ulteriori decrittazioni da solo semplicemente ricordando il segreto ricostruito.

A seconda del contesto, questo può o non può essere un problema. Per esempio, ci sono sistemi di votazione che usano la crittografia omomorfica (ad esempio con ElGamal), dove i voti criptati vengono sommati insieme senza decrittografarli (questo è il punto dell'omomorfismo); ma il conteggio finale deve ancora essere decodificato. Vogliamo la decrittazione della soglia qui: diverse autorità devono collaborare tra loro per eseguire la decrittazione. In questo modo, le autorità si tengono sotto controllo. Tuttavia, se imparano la chiave privata stessa nel processo, allora ciascuna autorità sarà in grado di decifrare i voti individuali, il che vanifica l'intero scopo.

Se questo problema si applica al tuo contesto, allora devi fare più matematica. Esistono schemi di decodifica della soglia che consentono, ad esempio, una decifratura ElGamal di soglia, in modo tale che t titolare dell'azione debba parlare tra loro per l'istanza di decodifica ogni , scambiando "messaggi parzialmente decrittografati ". La chiave privata non viene mai realmente ricostruita, ma la sua azione (la decrittografia) viene gradualmente riprodotta.

C'è molta teoria sui crittosistemi a soglia, con varie caratteristiche (quante condivisioni, quali valori di soglia possibili, lo schema resiste bene quando alcuni detentori di azioni barano attivamente, quanti messaggi devono essere scambiati e così via). Se il tuo problema a portata di mano può essere risolto con lo schema di Shamir, allora, con tutti i mezzi, provaci. È abbastanza semplice da implementare (in particolare, la condivisione di file è facile se si eseguono tutti i calcoli in GF (2 ⁸ ) ).

Quello che stai cercando è Shamir Secret Sharing . L'obiettivo è che dato un gruppo di utenti k , qualsiasi n di loro che lavora insieme può decodificare i dati. D'altra parte un gruppo con meno di n utenti non dovrebbe essere in grado di apprendere alcuna informazione sulla chiave di decodifica.

L'idea generale di come funziona utilizza una geometria. Supponiamo di volere che due utenti siano in grado di decodificare. Immagina il piano 2D standard con un asse orizzontale e verticale. Per impostare il sistema, scegli un punto casuale sull'asse verticale tra 0 e, diciamo 2 ^ 128; questo corrisponde a una chiave a 128 bit.

Successivamente, scegli una linea casuale sul piano che interseca quel punto. Dì a ciascuno dei tuoi utenti le coordinate di un punto su quella linea (ogni utente impara un punto diverso). Ogni due utenti può combinare i loro punti per capire quale linea hai scelto --- letteralmente collegando i punti --- e da lì capire qual è la chiave.

Se vuoi che più di due utenti abbiano bisogno di lavorare insieme, puoi scegliere un polinomio di ordine superiore (come una parabola, per tre utenti) anziché una linea.

C'è un punto tecnico su cui sto parlando qui, cioè che invece di usare la moltiplicazione e l'aggiunta standard, definisci queste operazioni in un modo speciale. (Matematicamente parlando, lavori in un campo finito). In modo informale, la ragione di ciò è che è possibile assegnare i punti degli utenti da un intervallo ben definito (con le coordinate x e y tra 0 e 2 ^ 128 - 1, ad esempio) pur impedendo loro di eliminare possibili valori chiave (a meno che non lavorino insieme al numero specificato di persone).

Sono sicuro che ci sia un nome formale per questo, ma mi sfugge. Una soluzione potrebbe essere quella di generare una chiave a 256 bit con 64 caratteri esadecimali.

Fornisci i personaggi chiave di Alice 1-22 e 22-43. Consegna i personaggi chiave di Bob 22-43 e 43-64. Fornisci i caratteri chiave Carol 1-22 e 43-64.

In questo modo, chiunque può eseguire la decrittografia, ma nessuno ha la chiave completa.

Il problema qui è che ci sono solo circa 22 caratteri / 85 bit di dati mancanti per Alice, Bob o Carol alla forza bruta. Forse se cifri con qualcosa come link che ha una chiave fino a 448 bit, questo risolverebbe il problema.