|
Wiki
UniCrema
Materie per semestre
Materie per anno
Materie per laurea
Help
|
|
Uni.CrittoSecret History
Hide minor edits - Show changes to output
Changed lines 116-119 from:
L'uomo coraggioso si può cimentare nella risoluzione del sistema. Nei temi d'esame viene chiesto di costruire le share, ma mai di risolvere per lo schema (k,n), mentre è richiesta anche la ricostruzione per lo schema (n,n). to:
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).
''[[http://ananke.crema.unimi.it/Crittografia/Appello-090211.pdf|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.''
Changed line 112 from:
y'_1_' = S + a'_1_' * 1 + a'_2_' * 1 mod 7 to:
y'_1_' = S + a'_1_' * 1 + a'_2_' * 1'^2^' mod 7
Changed lines 11-12 from:
Lo '''schema (k,n)''' invece divide il segretos sempre tra '''n''' partecipanti, ma bastano '''k < n''' partecipanti per ricostruirlo. to:
Lo '''schema (k,n)''' invece divide il segreto sempre tra '''n''' partecipanti, ma bastano '''k < n''' partecipanti per ricostruirlo. Changed line 64 from:
y'_i_' = S + a'_1_'x + a'_2_'x'^2^' + ... + a'_k-1_'x'^k-1^' to:
y'_i_' = S + a'_1_'x + a'_2_'x'^2^' + ... + a'_k-1_'x'^k-1^' mod p Changed lines 76-77 from:
y'_1_' = S + a'_1_'x + a'_2_'x'^2^' + ... + a'_k-1_'x'^k-1^'
to:
y'_1_' = S + a'_1_'x + a'_2_'x'^2^' + ... + a'_k-1_'x'^k-1^' mod p
y'_2_' = S + a'_1_'x + a'_2_'x'^2^' + ... + a'_k-1_'x'^k-1^' mod p Changed lines 79-80 from:
y'_k_' = S + a'_1_'x + a'_2_'x'^2^' + ... + a'_k-1_'x'^k-1^' to:
y'_k_' = S + a'_1_'x + a'_2_'x'^2^' + ... + a'_k-1_'x'^k-1^' mod p Added lines 85-116:
!!!Esempio
Voglio uno schema (3,5).\\
Scelgo '''p''' = '''7''' e '''S''' = '''3''' come prima.
Scelgo a caso i '''k-1''' valori di '''a''':
a'_1_' = 4
a'_2_' = 3
Calcolo le share secondo la formula
y'_i_' = S + a'_1_'x + a'_2_'x'^2^' + ... + a'_k-1_'x'^k-1^' mod p
y'_1_' = 3 + 4 * 1 + 3 * 1'^2^' mod 7 = 3 mod 7
y'_2_' = 3 + 4 * 2 + 3 * 2'^2^' mod 7 = 2 mod 7
y'_3_' = 3 + 4 * 3 + 3 * 3'^2^' mod 7 = 0 mod 7
y'_4_' = 3 + 4 * 4 + 3 * 4'^2^' mod 7 = 4 mod 7
y'_5_' = 3 + 4 * 5 + 3 * 5'^2^' mod 7 = 0 mod 7
Posso distribuire le share:
y'_1_' = 3
y'_2_' = 2
y'_3_' = 0
y'_4_' = 4
y'_5_' = 0
Per ricostruire, devo impostare il sistema con '''k''' di questi valori. Ad esempio, scelgo y'_1_', y'_3_', y'_5_':
y'_1_' = S + a'_1_' * 1 + a'_2_' * 1 mod 7
y'_3_' = S + a'_1_' * 3 + a'_2_' * 3'^2^' mod 7
y'_5_' = S + a'_1_' * 5 + a'_2_' * 5'^2^' mod 7
L'uomo coraggioso si può cimentare nella risoluzione del sistema. Nei temi d'esame viene chiesto di costruire le share, ma mai di risolvere per lo schema (k,n), mentre è richiesta anche la ricostruzione per lo schema (n,n).
Added lines 1-86:
(:title Secret Sharing:)
%titolo%''':: Secret Sharing ::'''
[[Torna alla pagina di Crittografia -> 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 segretos 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'_1_', a'_2_' ... a'_n-1_'
* lo share '''a'_n_'''' lo ottengo così: a'_n_' = S - a'_1_' - a'_2_' - ... - a'_n-1_' mod p
* distribuisco gli '''a''' ai miei n utenti
* per ricostruire, tutti gli utenti devono condividere i loro share: '''S''' = a'_1_' + a'_2_' + ... + 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_':
a'_1_' = 4
a'_2_' = 5
a'_3_' = 2
a'_4_' = 4
È possibile anche avere valori ripetuti, non è un problema.
Come dicevo sopra, per trovare '''a'_n_'''' devo risolvere questo calcolo:
a'_n_' = S - a'_1_' - a'_2_' - ... - a'_n-1_' mod p
a'_n_' = 3 - 4 - 5 - 2 - 4 mod 7 = 2 mod 7
Ho quindi tutte le 5 share:
a'_1_' = 4
a'_2_' = 5
a'_3_' = 2
a'_4_' = 4
a'_5_' = 2
e le distribuisco ai miei 5 utenti.
Per '''ricostruire''' il segreto '''S''', avendo a disposizione solo le share, devo fare:
'''S''' = a'_1_' + a'_2_' + ... + a'_n-1_' + a'_n_'
'''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'_1_', a'_2_' ... 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 ++) {
y'_i_' = S + a'_1_'x + a'_2_'x'^2^' + ... + a'_k-1_'x'^k-1^'
}
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ì:
y'_1_' = S + a'_1_'x + a'_2_'x'^2^' + ... + a'_k-1_'x'^k-1^'
y'_2_' = S + a'_1_'x + a'_2_'x'^2^' + ... + a'_k-1_'x'^k-1^'
....
y'_k_' = S + a'_1_'x + a'_2_'x'^2^' + ... + a'_k-1_'x'^k-1^'
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.
[[Torna alla pagina di Crittografia -> Crittografia]]
|
|
