Considera uno scenario in cui è necessario proteggere il caveau di una banca. È considerato assolutamente inespugnabile senza la chiave, che ti viene consegnata il primo giorno di lavoro. Il tuo obiettivo è conservare la chiave in modo sicuro.
Supponiamo che tu decida di tenere la chiave sempre con te, fornendo l'accesso allo spazio di archiviazione secondo necessità. Ma ti renderai presto conto che una soluzione del genere non è molto scalabile nella pratica, perché è necessaria la tua presenza fisica ogni volta che apri lo spazio di archiviazione. E la vacanza che ti era stata promessa? Inoltre, la domanda è ancora più spaventosa: cosa succederebbe se perdessi la tua unica chiave?
Pensando alle tue vacanze, decidi di fare una copia della chiave e di affidarla ad un altro dipendente. Tuttavia, capisci che neanche questo è l'ideale. Raddoppiando il numero di chiavi, raddoppierai anche le possibilità di furto delle chiavi.
In preda alla disperazione, distruggi il duplicato e decidi di dividere a metà la chiave originale. Ora, si potrebbe pensare che due persone fidate con frammenti di chiave debbano essere fisicamente presenti per ritirare la chiave e aprire il caveau. Ciò significa che un ladro deve rubare due pezzi, il che è due volte più difficile che rubare una chiave. Tuttavia, ti renderai presto conto che questo schema non è molto migliore di una sola chiave, perché se qualcuno perde mezza chiave, la chiave intera non può essere recuperata.
Il problema può essere risolto con una serie di chiavi e serrature aggiuntive, ma questo approccio richiederà rapidamente много chiavi e serrature. Decidi che la soluzione ideale sarebbe quella di condividere la chiave in modo che la sicurezza non dipenda interamente da una persona. Concludi inoltre che deve esserci una soglia per il numero di frammenti in modo che se un frammento viene perso (o se una persona va in vacanza), l'intera chiave rimane funzionante.
come condividere un segreto
Questo tipo di schema di gestione delle chiavi è stato pensato da Adi Shamir nel 1979 quando pubblicò il suo lavoro . L'articolo spiega brevemente il cosiddetto 
schema di soglia per dividere in modo efficiente un valore segreto (come una chiave crittografica). parti. Poi, quando e solo quando almeno di le parti sono assemblate, puoi facilmente ripristinare il segreto .
Dal punto di vista della sicurezza, una proprietà importante di questo schema è che l'aggressore non dovrebbe sapere assolutamente nulla a meno che non abbia almeno parti. Anche la presenza le parti non dovrebbero fornire alcuna informazione. Chiamiamo questa proprietà sicurezza semantica.
Interpolazione polinomiale
Schema della soglia di Shamir costruito attorno al concetto interpolazione polinomiale. Se non hai familiarità con questo concetto, in realtà è abbastanza semplice. Infatti, se ti è mai capitato di disegnare punti su un grafico e poi collegarli con linee o curve, l'hai già utilizzato!
Attraverso due punti puoi disegnare un numero illimitato di polinomi di grado 2. Per sceglierne uno solo, hai bisogno di un terzo punto. Illustrazione:
Consideriamo un polinomio di grado uno, . Se vuoi tracciare questa funzione su un grafico, quanti punti ti servono? Bene, sappiamo che questa è una funzione lineare che forma una linea e quindi ha bisogno di almeno due punti. Consideriamo quindi una funzione polinomiale di grado due, . Questa è una funzione quadratica, quindi sono necessari almeno tre punti per tracciare il grafico. Che ne dici di un polinomio di grado tre? Almeno quattro punti. E così via e così via.
La cosa veramente interessante di questa proprietà è che, dato il grado della funzione polinomiale e almeno punti, possiamo ricavare punti aggiuntivi per questa funzione polinomiale. Chiamiamo estrapolazione di questi punti aggiuntivi interpolazione polinomiale.
Inventare un segreto
Potresti aver già capito che è qui che entra in gioco il piano intelligente di Shamir. Diciamo il nostro segreto - E ' . Possiamo voltarci ad un punto del grafico e trovare una funzione polinomiale con grado , che soddisfa questo punto. Lascia che te lo ricordiamo sarà la nostra soglia di frammenti richiesti, quindi se impostiamo la soglia su tre frammenti, dobbiamo scegliere una funzione polinomiale di grado due.
Il nostro polinomio avrà la forma Dove и — numeri interi positivi selezionati casualmente. Stiamo semplicemente costruendo un polinomio con grado , dove il coefficiente libero - Questo è il nostro segreto , e per ciascuno di quelli successivi termini c'è un coefficiente positivo selezionato casualmente. Se torniamo all'esempio originale e lo assumiamo , quindi otteniamo la funzione .
A questo punto possiamo generare i frammenti connettendoci numeri interi univoci in Dove (perché è il nostro segreto). In questo esempio, vogliamo distribuire quattro frammenti con una soglia pari a tre, quindi generiamo punti in modo casuale e inviare un punto a ciascuna delle quattro persone fidate, i custodi della chiave. Lo facciamo sapere anche alla gente , poiché questa è considerata un'informazione pubblica ed è necessaria per il recupero .
Recuperare il segreto
Abbiamo già discusso il concetto di interpolazione polinomiale e come esso sia alla base dello schema di soglia di Shamir . Quando tre qualsiasi dei quattro amministratori vogliono ripristinare , devono solo interpolare con i suoi punti unici. Per fare ciò, possono determinare i loro punti e calcolare il polinomio di interpolazione di Lagrange utilizzando la seguente formula. Se la programmazione ti è più chiara della matematica, allora pi greco è essenzialmente un operatore for, che moltiplica tutti i risultati e sigma lo è for, che somma tutto.
A possiamo risolverlo in questo modo e restituire la nostra funzione polinomiale originale:
Perché lo sappiamo , recupero fatto semplicemente:
Utilizzo dell'aritmetica dei numeri interi non sicura
Sebbene abbiamo applicato con successo l'idea di base di Shamir , ci resta un problema che finora abbiamo ignorato. La nostra funzione polinomiale utilizza l'aritmetica dei numeri interi non sicura. Si noti che per ogni punto aggiuntivo che un utente malintenzionato ottiene sul grafico della nostra funzione, ci sono meno possibilità per altri punti. Puoi vederlo con i tuoi occhi quando disegni un numero crescente di punti per una funzione polinomiale usando l'aritmetica dei numeri interi. Ciò è controproducente per il nostro obiettivo di sicurezza dichiarato, perché l'aggressore non dovrebbe sapere assolutamente nulla finché non lo saprà almeno frammenti.
Per dimostrare quanto sia debole il circuito aritmetico degli interi, consideriamo uno scenario in cui un attaccante ottiene due punti e conosce le informazioni pubbliche che . Da queste informazioni può dedurre , uguale a due, e inserisci i valori noti nella formula и .
L'attaccante può quindi trovare , contando :
Dato che abbiamo definito come numeri interi positivi selezionati casualmente, esiste un numero limitato di possibili . Utilizzando queste informazioni, un utente malintenzionato può dedurre , poiché va bene qualsiasi cosa maggiore di 5 negativo. Ciò risulta essere vero poiché lo abbiamo determinato
L'attaccante può quindi calcolare i possibili valori sostituzione в :
Con opzioni limitate per diventa chiaro quanto sia facile selezionare e controllare i valori . Ci sono solo cinque opzioni qui.
Risolvere il problema con l'aritmetica dei numeri interi non sicura
Per eliminare questa vulnerabilità, Shamir suggerisce di utilizzare l'aritmetica modulare, sostituendola su Dove и — l'insieme di tutti i numeri primi.
Ricordiamo rapidamente come funziona l'aritmetica modulare. Un orologio con le lancette è un concetto familiare. Usa un orologio . Non appena la lancetta delle ore supera le dodici, ritorna sull'una. Una proprietà interessante di questo sistema è che semplicemente guardando l'orologio non possiamo dedurre quanti giri ha fatto la lancetta delle ore. Tuttavia, se sappiamo che la lancetta delle ore ha percorso le 12 quattro volte, possiamo determinare completamente il numero di ore trascorse utilizzando una semplice formula Dove è il nostro divisore (qui ), è il coefficiente (quante volte il divisore entra nel numero originale senza resto, qui ), e è il resto, che solitamente restituisce una chiamata dell'operatore modulo (qui ). Conoscere tutti questi valori ci permette di risolvere l'equazione per , ma se tralasciamo il coefficiente non potremo mai ripristinare il valore originale.
Possiamo dimostrare come ciò migliori la sicurezza del nostro schema applicando lo schema al nostro esempio precedente e utilizzando . La nostra nuova funzione polinomiale e i nuovi punti . Ora i detentori delle chiavi possono nuovamente utilizzare l'interpolazione polinomiale per ricostruire la nostra funzione, solo che questa volta le operazioni di addizione e moltiplicazione devono essere accompagnate dalla riduzione del modulo (per esempio ).
Usando questo nuovo esempio, supponiamo che l'attaccante abbia imparato due di questi nuovi punti, e informazioni pubbliche . Questa volta l'attaccante, sulla base di tutte le informazioni in suo possesso, restituisce le seguenti funzioni, where è l'insieme di tutti gli interi positivi e rappresenta il coefficiente del modulo .
Ora il nostro aggressore ritrova , calcolando :
Poi ci riprova sostituzione в :
Questa volta ha un problema serio. Valori mancanti nella formula , и . Poiché esiste un numero infinito di combinazioni di queste variabili, non è possibile ottenere alcuna informazione aggiuntiva.
Considerazioni sulla sicurezza
Lo suggerisce lo schema di condivisione segreta di Shamir sicurezza dal punto di vista della teoria dell’informazione. Ciò significa che la matematica è resistente anche contro un aggressore con potenza di calcolo illimitata. Tuttavia, il circuito contiene ancora diversi problemi noti.
Ad esempio, lo schema di Shamir non crea frammenti da controllare, cioè le persone possono presentare liberamente frammenti falsi e interferire con il recupero del segreto corretto. Un custode di frammenti ostile con informazioni sufficienti potrebbe persino produrre un altro frammento modificandosi a tua discrezione. Questo problema viene risolto utilizzando schemi di condivisione segreta verificabili, come lo schema di Feldman.
Un altro problema è che la lunghezza di ogni frammento è uguale alla lunghezza del segreto corrispondente, quindi la lunghezza del segreto è facile da determinare. Questo problema può essere risolto banalmente imbottitura segreto con numeri arbitrari fino a una lunghezza fissa.
Infine, è importante notare che le nostre preoccupazioni in materia di sicurezza potrebbero estendersi oltre la progettazione stessa. Per le applicazioni crittografiche del mondo reale, esiste spesso la minaccia di attacchi side-channel in cui un utente malintenzionato tenta di estrarre informazioni utili dal tempo di esecuzione dell'applicazione, dalla memorizzazione nella cache, dagli arresti anomali, ecc. Se questo è un problema, durante lo sviluppo è necessario prestare particolare attenzione all'utilizzo di misure protettive quali funzioni e ricerche a tempo costante, che impediscono il salvataggio della memoria su disco e a una serie di altre considerazioni che esulano dall'ambito di questo articolo.
Demo
Su C'è una dimostrazione interattiva dello schema di condivisione segreta di Shamir. Dimostrazione basata sulla libreria , che a sua volta è un port JavaScript del popolare programma . Si noti che il calcolo di valori di grandi dimensioni , и potrebbe richiedere del tempo.
Fonte: habr.com