Secret Sharing

 :: Secret Sharing ::

Torna alla pagina di Crittografia

Che cos'è

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.

Schema (n,n)

Ecco che cosa occorre fare:

• scegliere un numero primo p
• scegliere il numero segreto S, con S < p
• scegliere casualmente n-1 valori minori di p, e assegnarli alle a_n-1 share: a₁, a₂ ... a_n-1
• lo share a_n lo ottengo così: a_n = S - a₁ - a₂ - ... - a_n-1 mod p
• distribuisco gli a ai miei n utenti
• per ricostruire, tutti gli utenti devono condividere i loro share: S = a₁ + a₂ + ... + a_n-1 + a_n mod p

Esempio numerico

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 '''a_n-1:

 a1 = 4
 a2 = 5
 a3 = 2
 a4 = 4

È possibile anche avere valori ripetuti, non è un problema.

Come dicevo sopra, per trovare a_n 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.

Schema (k,n)

Questo schema è più complesso: divido il segreto in n share, ma ne bastano k < n per ricostruirlo.

Come sopra, devo scegliere

• il primo p
• il segreto S < p
• k - 1 valori: a₁, a₂ ... a_k-1, tutti minori di p

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

• i valori a_k li ho, perché li ho scelti a caso sopra
• al posto delle x sostituisco il valore di i
  • nella share numero 1, x = 1
  • nella share numero 2, x = 2
• e così via per tutte le n share

Distribuisco quindi i vari y_i, 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 varie y_i_' sono note
• le x le sostituisco come prima, con il valore di i

Le incognite sono quindi S e i k-1 valori di a: k incognite, k equazioni: il sistema si può risolvere.

Esempio

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 y₁, y₃, y₅:

 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.

Torna alla pagina di Crittografia