Secret Sharing Condivisione di segreti Scenario Distribuzione del
by user
Comments
Transcript
Secret Sharing Condivisione di segreti Scenario Distribuzione del
Un dealer vuole condividere un segreto S tra n partecipanti in modo che: k o più partecipanti possano ricostruire S k-1 o meno partecipanti non hanno alcuna informazione su S !!" " " !# Stelvio Cimato DTI – Università di Milano, Polo di Crema Corso di Crittografia A.A. 2004/05 $ … … Stelvio Cimato Corso di Crittografia A.A. 2004/05 DTI – Università di Milano, Polo di Crema % Stelvio Cimato DTI – Università di Milano, Polo di Crema Corso di Crittografia A.A. 2004/05 % … Stelvio Cimato DTI – Università di Milano, Polo di Crema … … Corso di Crittografia A.A. 2004/05 Stelvio Cimato DTI – Università di Milano, Polo di Crema Corso di Crittografia A.A. 2004/05 1 &'( ← ← Vedremo: ← ← Schema (n,n) Schema (k,n) … Stelvio Cimato Corso di Crittografia A.A. 2004/05 DTI – Università di Milano, Polo di Crema Stelvio Cimato &'( ← ← ← ← $ ← ← ← ← ← ← Corso di Crittografia A.A. 2004/05 DTI – Università di Milano, Polo di Crema … ← ← … Stelvio Cimato Corso di Crittografia A.A. 2004/05 DTI – Università di Milano, Polo di Crema ) &*'*( ← ← ← ← ← ← ← ← ← ← Stelvio Cimato Corso di Crittografia A.A. 2004/05 DTI – Università di Milano, Polo di Crema % ← ← ← ← ← ← ! … !! Stelvio Cimato DTI – Università di Milano, Polo di Crema Corso di Crittografia A.A. 2004/05 Stelvio Cimato DTI – Università di Milano, Polo di Crema Corso di Crittografia A.A. 2004/05 2 % ) &*'*( P1 sa che 3 = a1 P2 sa che 2 = a2 P3 sa che 1 = a3 P5 sa che 4 = S-a1-a2-a3–a4 mod 7 … ! Stelvio Cimato Corso di Crittografia A.A. 2004/05 DTI – Università di Milano, Polo di Crema S a4 0 4 1 5 2 6 3 0 4 1 5 2 6 3 " Stelvio Cimato Corso di Crittografia A.A. 2004/05 DTI – Università di Milano, Polo di Crema &+' ( ← ← ## ← ← &+' ( $%&' $%&'← ← (( … Corso di Crittografia A.A. 2004/05 DTI – Università di Milano, Polo di Crema Stelvio Cimato && "" )) ← ←$% $%'' ← ← Corso di Crittografia A.A. 2004/05 DTI – Università di Milano, Polo di Crema $ $%&' $%&'← ← (( ## … Stelvio Cimato # ## &&# ← ← # && ## &&# "" )) ← ←$% $%'' ) ← ← ## ← ← $%&' $%&'← ← (( &,'*( ← ← ← ← && && "" )) ← ←$% $%'' ← ← ← ← # # $ # ! … Stelvio Cimato DTI – Università di Milano, Polo di Crema $ !! Corso di Crittografia A.A. 2004/05 Stelvio Cimato DTI – Università di Milano, Polo di Crema Corso di Crittografia A.A. 2004/05 3 + % k equazioni: yi = S+a1i+…+ ak-1ik-1 per i=i1, i2, … ik k incognite: S, a1,…, ak-1 Possono ricostruire il segreto! … … Stelvio Cimato DTI – Università di Milano, Polo di Crema ) Stelvio Cimato Corso di Crittografia A.A. 2004/05 &,'*( P1 sa che P2 sa che P4 sa che + Partecipanti Pi1, Pi2,…, Pik 6 = S + a1•1 + a2•12 4 = S + a1•2 + a2•22 12 = S + a1•4 + a2•42 #− #− = (% ( + ( ) ) = ) #− * * , ( Stelvio Cimato DTI – Università di Milano, Polo di Crema '% '% ' # ! ( " - , # #− )# #− ∏% = . − ' ! Corso di Crittografia A.A. 2004/05 Calcolo polinomio f(x) Formula di interpolazione di Lagrange Grado k-1 f(ij) = yij 0 Distribuisco a ciascun partecipante un punto Solo k partecipanti avranno k punti e possono ricostruire la curva # $%&' = /= $%1' ( $%1' = $%1' (, )/ # /= 2 Corso di Crittografia A.A. 2004/05 , DTI – Università di Milano, Polo di Crema Per uno schema a soglia k utilizzo un polinomio di grado k-1: yi = S+a1i+…+ ak-1ik-1 Risolvendo k equazioni in k incognite + Stelvio Cimato Corso di Crittografia A.A. 2004/05 Es. dati due punti esiste una sola retta passante DTI – Università di Milano, Polo di Crema # ≤ < ≤# Lo stesso schema può essere visto utilizzando la formula di Lagrange per l’interpolazione polinomiale: Un insieme di n punti individua univocamente una curva di ordine n-1 Stelvio Cimato Corso di Crittografia A.A. 2004/05 DTI – Università di Milano, Polo di Crema 34 5 Stelvio Cimato DTI – Università di Milano, Polo di Crema )/ &− ≤# / − ∏ ≤ ≠/ ∏ ≤ ≤# ≠/ − Posso precalcolare i valori per ogni j / Corso di Crittografia A.A. 2004/05 4 % +-. k-1 equazioni: yi = S+a1i+…+ ak-1ik-1 per i=i1, i2, … ik-1 k incognite: S, a1,…, ak-1 Non possono ricostruire il segreto Ogni segreto è equamente possibile … Stelvio Cimato ) 6 = S + a1•1 + a2•12 4 = S + a1•2 + a2•22 = * ! " Stelvio Cimato S a1 a2 0 10 15 1 18 6 2 7 16 3 15 7 4 4 17 5 12 8 6 1 18 7 9 8 17 0 9 6 10 10 14 20 11 3 11 12 11 2 13 0 12 9 14 8 3 15 16 13 16 5 4 17 13 14 ak-1ik-1 k-1 equazioni: yi = S+a1i+…+ per i=i1, i2, … ik-1 k incognite: S, a1,…, ak-1 Ipotizzando un valore per il segreto S yik = F(ik) = S+a10+…+ ak-10k-1 # # # ) #− ) #− = ) #− Stelvio Cimato + #( , 1 = ∏% − ' , . ≤ < ≤# - )# #− Corso di Crittografia A.A. 2004/05 DTI – Università di Milano, Polo di Crema % +-. #− … Stelvio Cimato Corso18di Crittografia 2 5 A.A. 2004/05 DTI – Università di Milano, Polo di Crema Corso di Crittografia A.A. 2004/05 DTI – Università di Milano, Polo di Crema % &,'*( P1 sa che P2 sa che Stelvio Cimato Corso di Crittografia A.A. 2004/05 DTI – Università di Milano, Polo di Crema &.( Nel caso (3,5) con p=17 e i punti siano assegnati scegliendo xi=i; ottenendo le tre share y1=8, y3=10, y5=11 Supponiamo che (P1, P3, P5) collaborino per ricostruire il segreto. Si sa che 3 = ∏ ≤ ≤# ≠/ ! DTI – Università di Milano, Polo di Crema Corso di Crittografia A.A. 2004/05 − Stelvio Cimato DTI – Università di Milano, Polo di Crema = / = ∏ ≤ ≤# ≠/ Corso di Crittografia A.A. 2004/05 5 % &/( Quindi si ha: & & %& − & %& − & && 3 = %& − & %& − & = = − ⋅ && %& − & %& − & = − ⋅− = 3 = 3 = = = = ⋅ + Stelvio Cimato DTI – Università di Milano, Polo di Crema ⋅ ⋅ − ⋅ + − = − ⋅ = = = Corso di Crittografia A.A. 2004/05 6