P rotocolli 1
Protocolli Crittografici
Poker Mentale
Condivisione di segreti
Lancio di una moneta
Oblivious Transfer
Blind Signature
Moneta Elettronica
Elezioni
Certified email
P rotocolli 2
Mental Poker
Poker senza carte, con giocatori
“curiosi” ma “onesti”
Tre giocatori: A nnarella, B iagio, C iro
Cifratura e decifratura commutative:
D(E(x,k
1),k
2) = E(D(x,k
2),k
1) Esempio: RSA con lo stesso modulo
[Shamir, Rivest, Adleman 1978]
P rotocolli 3
Mental Poker:
B ottiene 5 carte
x
5,…,x
2Cifro e permuto le 52 carte E(x1,kA),…,E(x52,kA)
E(x4,kA),…,E(x32,kA)
Scelgo 5 carte e le cifro E(E(x5,kA),kB),…,E(E(x2,kA),kB)
Decifro i 5 valori E(x5,kB),…,E(x2,kB)
P rotocolli 4
Mental Poker:
C ottiene 5 carte
E(x4,kA),…,E(x32,kA) Invio le 47 carte cifrate da A
Invio le 47 carte cifrate da A
47 carte 47 carte
P rotocolli 5
Mental Poker:
C ottiene 5 carte
E(x4,kA),…,E(x32,kA) Invio le 47 carte cifrate da A
Invio le 47 carte cifrate da A
Scelgo 5 carte e le cifro Scelgo 5 carte e le cifro
E(E(x31,kA),kC),…,E(E(x50,kA),kC)
5 cart e 5 cart e
P rotocolli 6
Mental Poker:
C ottiene 5 carte
E(x4,kA),…,E(x32,kA) Invio le 47 carte cifrate da A
Invio le 47 carte cifrate da A
Scelgo 5 carte e le cifro Scelgo 5 carte e le cifro
Decifro i 5 valori Decifro i 5 valori
E(E(x31,kA),kC),…,E(E(x50,kA),kC)
D(E(E(x31,kA),kC),kA),…,D(E(E(x50,kA),kC)kA)
5 cart e
5 cart e
P rotocolli 7
Mental Poker:
C ottiene 5 carte
E(x4,kA),…,E(x32,kA) Invio le 47 carte cifrate da A
Invio le 47 carte cifrate da A
Scelgo 5 carte e le cifro Scelgo 5 carte e le cifro
Decifro i 5 valori Decifro i 5 valori
E(E(x31,kA),kC),…,E(E(x50,kA),kC) E(x31,kC),…,E(x50,kC)
5 cart e 5 cart e
P rotocolli 8
Mental Poker:
C ottiene 5 carte
E(x4,kA),…,E(x32,kA) Invio le 47 carte cifrate da A
Invio le 47 carte cifrate da A
Scelgo 5 carte e le cifro Scelgo 5 carte e le cifro
Decifro i 5 valori Decifro i 5 valori
E(E(x31,kA),kC),…,E(E(x50,kA),kC) E(x31,kC),…,E(x50,kC)
Decifro i 5 valori x31, …, x50
Decifro i 5 valori x31, …, x50
P rotocolli 9
Mental Poker:
A ottiene 5 carte
E(x
11,k
A),…,E(x
45,k
A) Scelgo ed invio 5 tra le
42 carte cifrate da A Scelgo ed invio 5 tra le
42 carte cifrate da A
Decifro i 5 valori x
11,…,x
45Decifro i 5 valori x
11,…,x
455 carte 5 carte
P rotocolli 1 0
Condivisione di segreti
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
[Adi Shamir, 1979]
P rotocolli 1 1
Scenario
Dealer Dealer
P 1 P
1P 2
P
2P P
nn
…
Segreto S Segreto
S
P rotocolli 1 2
Distribuzione del segreto
Dealer Dealer
P 1 P
1P 2
P
2P P
nn
…
Segreto S Segreto
S
Share
1Share
2Share
nP rotocolli 1 3
Ricostruzione del segreto
P 1 P
1P 2
P
2P P
nn
…
Il segreto è S Il segreto
è S Share
1Share
1Share
2Share
2k partecipanti
…
P rotocolli 1 4
Ricostruzione del segreto
P 1 P
1P 2
P
2P P
nn
…
Non abbiamo alcuna informazione
sul segreto Non abbiamo
alcuna informazione
sul segreto Share
1Share
1Share
2Share
2k-1 partecipanti
P rotocolli 1 5
Inizializzazione schema (k,n)
Dealer Dealer
P 1 P
1P 2
P
2P P
nn
…
p ← numero primo a1, a2,…, ak-1←elementi in Zp p ← numero primo a1, a2,…, ak-1←elementi in Zp
P rotocolli 1 6
Calcolo share schema (k,n)
Dealer Dealer
P 1 P
1P 2
P
2P P
nn
…
Segreto S in Z
pSegreto
S in Z
pp ← numero primo a1, a2,…, ak-1←elementi in Zp p ← numero primo a1, a2,…, ak-1←elementi in Zp f(x) ← S+a1x+…+ ak-1xk-1
for i=1 to n do yi←f(i) f(x) ← S+a1x+…+ ak-1xk-1 for i=1 to n do yi←f(i)
P rotocolli 1 7
Distribuzione share
Dealer Dealer
P 1 P
1P 2
P
2P P
nn
…
Segreto S in Z
pSegreto
S in Z
pf(x) ← S+a1x+…+ ak-1xk-1 for i=1 to n do yi←f(i) f(x) ← S+a1x+…+ ak-1xk-1 for i=1 to n do yi←f(i)
p ← numero primo a1, a2,…, ak-1←elementi in Zp p ← numero primo a1, a2,…, ak-1←elementi in Zp
y
1y
2y
nP rotocolli 1 8
Esempio schema (3,5)
Dealer Dealer
P 1 P
1P 2
P
2P P
55
Segreto S ← 12 Segreto
S ←12
f(x) ← 12+11x+2x2 for i=1 to 5 do yi←f(i) f(x) ← 12+11x+2x2 for i=1 to 5 do yi←f(i)
p ← 19 a1 ←11 a2 ←2 p ← 19 a1 ←11 a2 ←2
6 4
P 4 P
4P 3
P
36
3
12
P rotocolli 1 9
Ricostruzione del segreto
P 1 P
1P 2
P
2P P
nn
…
Il segreto è S Il segreto
è S Share
1Share
1Share
2Share
2k partecipanti
…
P rotocolli 2 0
Informazioni k partecipanti
k equazioni: y
i= S+a
1i+…+ a
k-1i
k-1per i=i
1, i
2, … i
k
k incognite: S, a
1,…, a
k-1
Possono ricostruire il segreto!
P rotocolli 2 1
Esempio schema (3,5)
P
1sa che 6 = S + a
1•1 + a
2•1
2
P
2sa che 4 = S + a
1•2 + a
2•2
2
P
4sa che 12 = S + a
1•4 + a
2•4
2
=
12 4 6
a a S
16 4 1
4 2 1
1 1 1
2 1
Il sistema ha un’unica soluzione:
S=19 a
1= 11 a
2= 2
det = (1-2)(1-4)(2-4) mod 19
= 13
P rotocolli 2 2
Informazioni k partecipanti
Partecipanti P
i1, P
i2,…, P
ik
=
− −
−
−
−
k 3 2 1
i i i i
1 k
2 1
1 kk k2 k
1 3k 32 3
1 2k 22 2
1 1k 12 1
y y y y
a a a S
i i i 1
i i i 1
i i i 1
i i i 1
M M L
M M M M
L L L
Il sistema ha un’unica soluzione
∏
<≤≤
−
=
k t r
1
(i
ri
t) mod p Matrice di Vandermonde det
P rotocolli 2 3
Calcolo del Segreto
Calcolo polinomio f(x)
Formula di interpolazione di Lagrange – Grado k
– F(i
j)=y
ij∑ ∏
≠≤
≤
=
−
= −
j t tk
1 j t
k t 1
j
y
ii x i i
f(x)
j
Serve solo f(0)=S
∏
∑
≠≤
≤
=
−
=
j t tk
1 t j
k t 1
j
y
ii i i
f(0)
jP rotocolli 2 4
Ricostruzione del segreto
P 1 P
1P 2
P
2P P
nn
…
Non abbiamo alcuna informazione
sul segreto Non abbiamo
alcuna informazione
sul segreto Share
1Share
1Share
2Share
2k-1 partecipanti
P rotocolli 2 5
Informazioni k-1 partecipanti
k-1 equazioni: y
i= S+a
1i+…+ a
k-1i
k-1per i=i
1, i
2, … i
k-1
k incognite: S, a
1,…, a
k-1
Non possono ricostruire il segreto
Ogni segreto è equamente possibile
P rotocolli 2 6
Esempio schema (3,5)
P
1sa che 6 = S + a
1•1 + a
2•1
2
P
2sa che 4 = S + a
1•2 + a
2•2
2
=
4 6 a a S 4 2 1
1 1 1
2 1
Il sistema ha 19 soluzioni:
5 2 18
14 13 17
4 5 16
13 16 15
3 8 14
12 0 13
2 11 12
11 3 11
20 14 10
10 6 9
0 17 8
9 9 7
18 1 6
8 12 5
17 4 4
7 15 3
16 7 2
6 18 1
15 10 0
a2 a1 S
P rotocolli 2 7
Ricostruzione del segreto
P 1 P
1P 2
P
2P P
nn
…
Non abbiamo alcuna informazione
sul segreto Non abbiamo
alcuna informazione
sul segreto Share
1Share
1Share
2Share
2k-1 partecipanti
P rotocolli 2 8
Informazioni k-1 partecipanti
k-1 equazioni: y
i= S+a
1i+…+ a
k-1i
k-1per i=i
1, i
2, … i
k-1
k incognite: S, a
1,…, a
k-1
Ipotizzano un valore per il segreto S S = S+a
10+…+ a
k-10
k-1
=
− −
−
−
−
k 3 2 1
i i i i
1 k
2 1
1 kk k2 k
1 3k 32 3
1 2k 22 2
1 1k 12 1
y y y y
a a a S
i i i 1
i i i 1
i i i 1
i i i 1
M M L
M M M M
L L L
Il sistema ha un’unica soluzione
∏
<≤≤
−
=
k t r
1 (ir it)modp
det
Matrice di Vandermonde
i
k= 0
P rotocolli 2 9
Inizializzazione schema (n,n)
Dealer Dealer
P 1 P
1P 2
P
2P P
nn
…
p ← numero primo a1, a2,…, an-1←elementi in Zp p ← numero primo a1, a2,…, an-1←elementi in Zp
P rotocolli 3 0
Calcolo share schema (n,n)
Dealer Dealer
P 1 P
1P 2
P
2P P
nn
…
Segreto S in Z
pSegreto
S in Z
pp ← numero primo a1, a2,…, an-1←elementi in Zp p ← numero primo a1, a2,…, an-1←elementi in Zp an←S-a1-…-an-1mod p
an←S-a1-…-an-1mod p
P rotocolli 3 1
Distribuzione share
Dealer Dealer
P 1 P
1P 2
P
2P P
nn
…
Segreto S in Z
pSegreto
S in Z
pp ← numero primo a1, a2,…, an-1←elementi in Zp p ← numero primo a1, a2,…, an-1←elementi in Zp
a
1a
2a
n an←S-a1-…-an-1mod pan←S-a1-…-an-1mod p
P rotocolli 3 2
Esempio schema (5,5)
Dealer Dealer
P 1 P
1P 2
P
2P P
55
Segreto S ←5 Segreto
S ← 5
p ← 7 a1 ←3 a2 ←2 a3 ←1 a4 ←2 p ← 7 a1 ←3 a2 ←2 a3 ←1 a4 ←2
3 2
P 4 P
4P 3
P
31
4 2
a5←5-3-2-1-2 mod 7a5←5-3-2-1-2 mod 7
P rotocolli 3 3
Ricostruzione del segreto
P 1 P
1P 2 P
2P n P
n…
Il segreto è S Il segreto
è S Share
1Share
1Share
2Share
2n partecipanti Share
nShare
nS ← a1+…+an-1+anmod p S ← a1+…+an-1+anmod p
P rotocolli 3 4
Ricostruzione del segreto
P 1 P
1P i P
iP n P
n…
Non abbiamo alcuna informazione
sul segreto Non abbiamo
alcuna informazione
sul segreto Share
1Share
1Share Share
22n-1 partecipanti
P rotocolli 3 5
Esempio schema (5,5)
P
1sa che 3 = a
1
P
2sa che 2 = a
2
P
3sa che 1 = a
3
P
5sa che 4 = S-a
1-a
2-a
3–a
4mod 7
Il sistema ha 7 soluzioni:
3 6
2 5
1 4
0 3
6 2
5 1
4 0
a
4S
P rotocolli 3 6
Lancio di una moneta
… …
E’ uscito testa/croce
E’ uscito testa/croce E’ uscito testa/croce E’ uscito testa/croce
iagio
nnarella
P rotocolli 3 7
Lancio di una moneta protocollo naive
E’ uscito testa
E’ uscito testa E’ uscito testa E’ uscito testa
Lancio monetatesta
iagio nnarella
P rotocolli 3 8
Lancio di una moneta
iagio
E’ uscito b⊕b´
E’ uscito b⊕b´ E’ uscito b⊕b´ E’ uscito b⊕b´
Scegli bit b
Scegli bit b´
x←commitment(b)
b´
x
rivela b
nnarella
P rotocolli 3 9
Commitment
Equivalente digitale di una busta
“Facile” da calcolare
Dato x è “difficile” calcolare b
“Facile” mostrare che x = commitment(b)
“Difficile” mostrare che x = commitment(1-b)
x←commitment(b) x←commitment(b)
P rotocolli 4 0
Commitment
Esempio
p a rità
n,e(C) = bit meno significativo di M 0 se M < n/2
h a lf
n,e(C) =
1 se M > n/2
C = M
emod n C = M
emod n x←commitment(b) x←commitment(b) b = p red ica to_d ifficile (x)
P rotocolli 4 1
Crittografia probabilistica Testo in chiaro M = M 1 M 2 M 3 … Testo cifrato C = C 1 C 2 C 3 …
M i = p red icato_d ifficile (C i )
P rotocolli 4 2
Blind Signature
… …
F è la firma di M da parte di B F è la firma di M
da parte di B
Non so che cosa ho firmato Non so che cosa
ho firmato
iagio nnarella
Voglio avere la firma di M da parte di B Voglio avere la firma
di M da parte di B
P rotocolli 4 3
Blind Signature
protocollo con busta
iagio nnarella
Voglio avere la firma di M da parte di B Voglio avere la firma
di M da parte di B
M F’
M,F
F’
P rotocolli 4 4
Blind Signature
protocollo con RSA
iagio nnarella
Voglio avere la firma di M da parte di B Voglio avere la firma
di M da parte di B
M F’
M,F
F’
k ←valore casuale t←Mkemod n
t
F’←tdmod n
F’
F ← F’ k-1mod n
P rotocolli 4 5
Blind Signature
protocollo con RSA
iagio nnarella
Voglio avere la firma di M da parte di B Voglio avere la firma
di M da parte di B
M F’
M,F
F’
k ←valore casuale t←Mkemod n
t
F’←tdmod n
F’
F ← F’ k-1mod n
F = F’ k-1mod n
= tdk-1mod n
= (Mke)d k-1mod n
= Md kedk-1mod n
= Mdmod n F = F’ k-1mod n
= tdk-1mod n
= (Mke)d k-1mod n
= Md kedk-1mod n
= Mdmod n P rotocolli 4 6
Moneta Elettronica
nnarella … … anca
Anonimia
Moneta elettronica
egoziante Deposito
P rotocolli 4 7
Moneta Elettronica I
nnarella anca
Anonimia
Assegno $1000
F’ F’
FirmaBanca(Assegno $1000)
Problemi?
P rotocolli 4 8
Moneta Elettronica II
nnarella anca
Assegno $1000
… Assegno $1000
F’ F’
FirmaBanca(Assegno $1000)
…
Apri queste 99 buste
…
100
Busta non aperta
P rotocolli 4 9
Moneta Elettronica II
nnarella anca
Assegno $1000
… Assegno $1000
F’ F’
FirmaBanca(Assegno $1000)
…
Apri queste 99 buste
…
100
Busta non aperta
Problemi?
P rotocolli 50
Moneta Elettronica III
nnarella anca
Assegno $1000, r1
… Assegno $1000, r100
F’ F’
FirmaBanca(Assegno $1000, r)
…
Apri queste 99 buste
…
100
Busta non aperta
