:: Secret Sharing ::
Torna alla pagina di Crittografia
Secret Sharing è un nome generico che si applica a tecniche che permettono di distribuire parti (share) di un numero segreto a più utenti, e che permettono di ricostruire il segreto solo con la collaborazione di tutti gli utenti che hanno share oppure con una parte di essi.
Si dividono in due gruppi: schema (n,n) e schema (k,n).
Lo schema (n,n) divide il segreto tra n partecipanti, e per ricostruirlo sono necessarie le share di tutti gli n partecipanti.
Lo schema (k,n) invece divide il segreto sempre tra n partecipanti, ma bastano k < n partecipanti per ricostruirlo.
Ecco che cosa occorre fare:
Voglio uno schema (5,5), cioè divido il segreto in 5 share. Ecco tutti i passaggi
Scelgo un numero primo che più mi aggrada: p = 7.
Decido che il segreto sia S = 3.
Scelgo ora n - 1 valori casuali, per assegnarli agli share fino a '''an-1:
a1 = 4 a2 = 5 a3 = 2 a4 = 4
È possibile anche avere valori ripetuti, non è un problema.
Come dicevo sopra, per trovare an devo risolvere questo calcolo:
an = S - a1 - a2 - ... - an-1 mod p an = 3 - 4 - 5 - 2 - 4 mod 7 = 2 mod 7
Ho quindi tutte le 5 share:
a1 = 4 a2 = 5 a3 = 2 a4 = 4 a5 = 2
e le distribuisco ai miei 5 utenti.
Per ricostruire il segreto S, avendo a disposizione solo le share, devo fare:
S = a1 + a2 + ... + an-1 + an S = 4 + 5 + 2 + 4 + 2 mod 7 = 17 mod 7 = 3 mod 7
E infatti, il segreto era 3.
Questo schema è più complesso: divido il segreto in n share, ma ne bastano k < n per ricostruirlo.
Come sopra, devo scegliere
In questo caso, questi k-1 valori non sono le share. Infatti, le share le ottengo calcolando la seguente espressione:
for (i = 1; i <= n; i ++) {
yi = S + a1x + a2x2 + ... + ak-1xk-1 mod p
}
Questo vuol dire che l'i-esima share è ottenuta a partire da questa formula, in cui
Distribuisco quindi i vari yi, assieme alla i stessa: ovvero, l'utente conosce il valore della share ed il numero i della sua share.
Per ricostruire il segreto, mi bastano k share, perché mi permettono di costruire un sistema così:
y1 = S + a1x + a2x2 + ... + ak-1xk-1 mod p y2 = S + a1x + a2x2 + ... + ak-1xk-1 mod p .... yk = S + a1x + a2x2 + ... + ak-1xk-1 mod p
In questo caso:
Le incognite sono quindi S e i k-1 valori di a: k incognite, k equazioni: il sistema si può risolvere.
Voglio uno schema (3,5).
Scelgo p = 7 e S = 3 come prima.
Scelgo a caso i k-1 valori di a:
a1 = 4 a2 = 3
Calcolo le share secondo la formula
yi = S + a1x + a2x2 + ... + ak-1xk-1 mod p y1 = 3 + 4 * 1 + 3 * 12 mod 7 = 3 mod 7 y2 = 3 + 4 * 2 + 3 * 22 mod 7 = 2 mod 7 y3 = 3 + 4 * 3 + 3 * 32 mod 7 = 0 mod 7 y4 = 3 + 4 * 4 + 3 * 42 mod 7 = 4 mod 7 y5 = 3 + 4 * 5 + 3 * 52 mod 7 = 0 mod 7
Posso distribuire le share:
y1 = 3 y2 = 2 y3 = 0 y4 = 4 y5 = 0
Per ricostruire, devo impostare il sistema con k di questi valori. Ad esempio, scelgo y1, y3, y5:
y1 = S + a1 * 1 + a2 * 12 mod 7 y3 = S + a1 * 3 + a2 * 32 mod 7 y5 = S + a1 * 5 + a2 * 52 mod 7
L'uomo coraggioso si può cimentare nella risoluzione del sistema. Nei temi d'esame viene chiesto di costruire le share, ma (quasi) mai di risolvere per lo schema (k,n), mentre è richiesta anche la ricostruzione per lo schema (n,n).
Nell'appello dell'11-02-09 era prevista la ricostruzione di uno schema (k,n), quindi fate molta attenzione; se mai dovesse riaccadere, preparatevi con il citrinesco teorema cinese del resto.