Newsgroup: it.hobby.enigmi
Titolo: sicurezza!

bene, oggi abbiamo risolto questo problema:
si tratta di avere un gruppo di n persone e un segreto che devono
condividere.
ma non si vuole che una sola persona possa ottenere il segreto. in
particolare, si vuole che k<n qualsiasi persone possano ottenere il
segreto ma k-1 qualsiasi no.
come possono fare?
ciao ciao!
pazqo


E' necessario innanzitutto dividere il segreto in binomiale di n su k-1 
(coefficiente binomiale ovviamente) parti. A questo punto si "associa" 
ogni parte di questo segreto ad ognuno dei possibili gruppi di k-1 
persone e si fa in modo che tutte le persone al di fuori del gruppo 
conoscano questa parte di segreto.
Esempio numerico: n = 7, k = 4. In pratica qualunque gruppo di almeno 4 
persone su 7 deve conoscere il segreto ma se sono solo 3 no.
Il binomiale di 7/3 è 35 e quindi divido il segreto in 35 parti. Associo 
ad ogni gruppo di persone (ipotizzo di chiamare le persone a, b, c, d, 
e, f, g e i gruppi relativi con la sequenza delle lettere) una delle 
parti, quindi:
gruppo abc => parte 1
gruppo abd => parte 2
gruppo abe => parte 3
gruppo abf => parte 4
gruppo abg => parte 5
gruppo acd => parte 6
gruppo ace => parte 7
gruppo acf => parte 8
gruppo acg => parte 9
gruppo ade => parte 10
gruppo adf => parte 11
gruppo adg => parte 12
gruppo aef => parte 13
gruppo aeg => parte 14
gruppo afg => parte 15
gruppo bcd => parte 16
e così via fino al 35° gruppo (efg).
Alla fine consegno la parte di segreto 1 a tutti tranne il primo gruppo 
(abc), la parte di segreto 2 a tutti tranne il secondo gruppo (abd) e 
così via.
Ogni utente conoscerà tutte le parti di segreto tranne quelle che gli 
sono state tolte per via dell'appartenenza a qualche gruppo. Ogni 
persona farà parte di binomiale n-1 su k-2 gruppi (in questo caso 15 
gruppi) e quindi conoscerà solamente 25 parti su 35 del segreto.
Ok, spero di essermi spiegato e soprattutto di avere indovinato :-)
Stefano
ps: per scrivermi inverti la c e la q

a dire il vero mi sembra molto piu' dispendioso del metodo che abbiamo
visto in classe...
tanto per fare un esempio:
metti che ci siano 1 generale, 2 colonnelli e 5 ufficiali.
il generale puo' ordinare l'attacco da solo, i due colonnelli possono
ordinare l'attacco in coppia e i 5 ufficiali possono ordinare
l'attacco tutti assieme. oppure 3 ufficiali e un colonnello possono
ordinare l'attacco. come procederesti, con il tuo metodo?
tieni conto che piu' informazioni segrete hai piu' e' facile che il
nemico venga a conoscenza di alcune di queste...
ciao ciao
pazqo
ps: essenzialmente, mi pare che con il tuo metodo sia difficile
conservare tutte le chiavi in poco spazio!

 conservare tutte le chiavi in poco spazio!
Questa cosa non era nei requisiti e poi ora non parli più di segreto ma 
di chiavi: se stiamo parlando di chiavi informatiche, beh, non mi pare 
complesso conservare dei bit. Immagina che il segreto di prima sia 
composto da 35 parti di 128bit ciascuna, otteniamo una macrochiave da 
4480bit (poco più di 500 byte, una cosa irrisoria) e solo K persone 
insieme avranno la chiave completa. La chiave completa permetterà di 
decriptare il "segreto", qualunque dimensione esso abbia.
Se manca una persona mancano comunque almeno 128 bit che non sono pochi 
se si vogliono provare tutte le combinazioni (3.4E38).
Comunque sono molto interessato a conoscere la soluzione che vi è stata 
proposta visto che sicuramente ne esistono altre oltre a quella proposta 
da me. Purtroppo non ho tempo di guardare questa variante e mi pare che 
non ci siano altri "partecipanti" a questo quesito in questo newsgroup.
Attendo con curiosità..
Stefano

 Stefano
ti do l'idea: principio di identita' dei polinomi e interpolazione...
;p
potrebbe sviare un po', ma e' la strategia giusta!
ciao ciao!
pazqo
ps: oggi ho l'esame di crittografia, quindi ti rispondero' meglio tra
qualche giorno! ciao ciao again

 potrebbe sviare un po', ma e' la strategia giusta!
Purtroppo usciamo dalle mie conoscenze, mi sa...
Quando hai tempo per darmi due link dove capire come il principio 
dell'interpolazione si applica in questo caso o addirittura riportare la 
soluzione al problema che hai postato sarebbe una cosa molto gradita!
Grazie,
Stefano

 ha scritto nel messaggio
news:ch6l0d$dfq$2...@news.ngi.it...

l'idea č questa: Abbiamo k persone e vogliamo che m possano rompere il
segreto ma m-1 no (m<k)
sia s il segreto da condividere.
sia n un numero > max(s, k)
scegliamo m-1 valori: a_1,...,a_(m-1)
allora costruiamo il polinomio f(x) = s + a_1*x + a_2*x^2 + ... +
a_m-1*x^(m-1) (mod n). ora diamo alla prima persona la coppia (1, f(1)),
alla seconda la coppia (2, f(2)) e cosě via fino alla k-esima persona. m
persone possono ricostruire il polinomio e ottenere s. m-1 non possono dire
nulla, visto che per s sono possibili tutte le scelte... :-P
nell'esempio dei colonneli, lavoro nel modo seguente:
creo un sistema a 30 chiavi, che sia possibile rompere avendone 10. poi
assegno 10 chiavi al generale, 5 a ciascun colonnello e 2 a ciascun
ufficiale.
cosě il generale da solo puň rompere il segreto, i due colonnelli assieme
possono farlo, i 5 ufficiali pure e anche un colonnello e 3 ufficiali, che
si ritrovano con 11 chiavi (5+2+2+2)
ciaooo
pazqo