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