Consideriamo uno scenario in cui è necessario garantire la sicurezza di un magazzino bancario. Questo è considerato assolutamente inaccessibile senza la chiave, che ti viene rilasciata il primo giorno di lavoro. Il tuo obiettivo è mantenere la chiave al sicuro.

Supponiamo che tu abbia deciso di tenere sempre la chiave con te, fornendo accesso al magazzino quando necessario. Ma presto ti renderai conto che questa soluzione non scala bene in pratica, perché ogni volta per aprire il magazzino è necessaria la tua presenza fisica. E riguardo alle vacanze che ti hanno promesso? Inoltre, c'è un'ulteriore domanda preoccupante: e se perdi l'unica chiave?

Con il pensiero alle vacanze, hai deciso di fare una copia della chiave e affidarala a un altro dipendente. Tuttavia, capisci che anche questa non è una soluzione ideale. Raddoppiando il numero di chiavi, hai anche raddoppiato le possibilità di furto della chiave.

Disperato, distruggi il duplicato e decidi di dividere la chiave originale in due parti. Ora, pensi, due persone di fiducia con frammenti di chiave devono essere fisicamente presenti per riunire la chiave e aprire il magazzino. Questo significa che il ladro deve rubare due frammenti, il che è il doppio più difficile rispetto al furto di una chiave. Tuttavia, presto ti rendi conto che questo schema non è affatto migliore di una singola chiave, perché se qualcuno perde metà della chiave, la chiave completa non può essere ripristinata.

Il problema può essere risolto con una serie di chiavi e serrature aggiuntive, ma con questo approccio ben presto serviranno molte chiavi e serrature. Decidi che in uno schema ideale bisognerebbe dividere la chiave, in modo che la sicurezza non dipenda completamente da una sola persona. Concludi anche che deve esserci una certa soglia di numero di frammenti, in modo che la perdita di un frammento (o se una persona va in vacanza) non comprometta il funzionamento dell'intera chiave.

Come dividere un segreto

Questo tipo di schema di gestione delle chiavi è stato pensato da Adi Shamir nel 1979, quando pubblicò il suo lavoro «Come dividere un segreto». Nell'articolo viene brevemente spiegato il cosiddetto schema di soglia per la divisione efficace di un valore segreto (ad esempio, una chiave crittografica) in parti. Poi, quando e solo quando almeno da parti sono raccolte, è possibile ripristinare facilmente il segreto .

Dal punto di vista della sicurezza, una proprietà importante di questo schema è che un malintenzionato non deve sapere assolutamente nulla se non ha almeno parti. Anche la presenza di parti non deve fornire alcuna informazione. Chiamiamo questa proprietà sicurezza semantica.

Interpolazione polinomiale

Lo schema di Shamir è costruito attorno al concetto di interpolazione polinomiale. Se non sei familiare con questo concetto, in realtà è piuttosto semplice. In effetti, se hai mai tracciato punti su un grafico e poi li hai uniti con linee o curve, allora l'hai già utilizzato!

Tra due punti possono passare un numero illimitato di polinomi di grado 2. Per scegliere uno di essi sarà necessaria un terza punto. Illustrazione: Wikipedia

Consideriamo un polinomio di primo grado, . Se desideri rappresentare questa funzione su un grafico, quante punti ti servono? Beh, sappiamo che si tratta di una funzione lineare, che forma una linea, quindi servono almeno due punti. Consideriamo ora una funzione polinomiale di secondo grado, . Questa è una funzione quadratica, quindi per rappresentare il grafico servono almeno tre punti. E per un polinomio di terzo grado? Almeno quattro punti. E così via.

La cosa davvero interessante di questa proprietà è che, conoscendo il grado della funzione polinomiale e almeno punti, possiamo derivare ulteriori punti per questa funzione polinomiale. L'estrazione di questi punti aggiuntivi la chiamiamo interpolazione polinomiale.

Costruzione del segreto

Forse hai già capito che qui entra in gioco il geniale schema di Shamir. Supponiamo che il nostro segreto è . Possiamo trasformare in un punto su un grafico e creare una funzione polinomiale di grado , che soddisfi questo punto. Ricordiamo che sarà la nostra soglia di frammenti richiesti, quindi se fissiamo la soglia a tre frammenti, dovremmo scegliere una funzione polinomiale di grado due.

Il nostro polinomio avrà la forma di , dove e — numeri interi positivi scelti casualmente. Stiamo semplicemente costruendo un polinomio di grado , dove il termine indipendente  è il nostro segreto , e ciascuno dei successivi un membro ha un coefficiente positivo scelto casualmente. Se torniamo all'esempio originale e supponiamo che , allora otterremo una funzione .

A questo punto possiamo generare frammenti, connettendo numeri interi unici in , dove (perché è il nostro segreto). In questo esempio vogliamo distribuire quattro frammenti con una soglia di tre, quindi generiamo punti casualmente e ne inviamo uno a ciascuna delle quattro persone fidate, i custodi della chiave. Informiamo anche le persone che , poiché si tratta di un'informazione pubblica e necessaria per il recupero .

Recupero del segreto

Abbiamo già discusso il concetto di interpolazione polinomiale e del fatto che essa è alla base dello schema di Shamir . Quando tre delle quattro persone fidate vogliono recuperare , devono solo interpolare con i loro punti unici. Per farlo, possono definire 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 è sostanzialmente un operatore per, che moltiplica tutti i risultati, e sigma è per, che somma tutto.

Durante possiamo risolvere in questo modo e restituire la nostra funzione polinomiale originale:

Poiché sappiamo che , il recupero avviene in modo semplice:

Utilizzo di aritmetica intera non sicura

Anche se abbiamo applicato con successo l'idea di base di Shamir , rimane un problema che abbiamo ignorato fino ad ora. La nostra funzione polinomiale utilizza aritmetica intera non sicura. Tieni presente che per ogni punto aggiuntivo che un aggressore ottiene sul grafico della nostra funzione, ci sono meno possibilità per altri punti. Puoi vederlo con i tuoi occhi quando costruisci un grafico aumentando il numero di punti per la funzione polinomiale utilizzando aritmetica intera. Questo è controproducente per il nostro obiettivo dichiarato di sicurezza, perché un malevolo non deve assolutamente sapere nulla finché non ha almeno frammenti.

Per dimostrare quanto sia debole lo schema con aritmetica intera, consideriamo uno scenario in cui un aggressore ha ottenuto due punti e conosce l'informazione pubblica che . Questa informazione può portare , pari a due, e collegare nella formula valori noti e .

Successivamente, l'attaccante può trovare , calcolando :

Poiché abbiamo definito come numeri interi positivi scelti casualmente, ci sono un numero limitato di possibili . Con queste informazioni, l'attaccante può dedurre , poiché tutto ciò che è maggiore di 5 renderà negativo. Questo risulta essere vero, poiché abbiamo definito

Successivamente, l'attaccante può calcolare i valori possibili , sostituendo in :

Con un insieme limitato di opzioni per diventa chiaro quanto sia facile scegliere e verificare i valori . Qui ci sono solo cinque opzioni.

Risolvere il problema dell'aritmetica intera insicura

Per rimuovere questa vulnerabilità, Shamir suggerisce di utilizzare l'aritmetica modulare, sostituendo in , dove e — l'insieme di tutti i numeri primi.

Ricordiamo rapidamente come funziona l'aritmetica modulare. L'orologio con lancette è un concetto già noto. Utilizza un orologio che è . Non appena la lancetta dell'ora passa oltre le dodici, torna a uno. Una proprietà interessante di questo sistema è che guardando semplicemente l'orologio, non possiamo dedurre quante volte ha ruotato la lancetta dell'ora. Tuttavia, se sappiamo che la lancetta ha passato 12 quattro volte, possiamo determinare completamente il numero di ore passate utilizzando una semplice formula , dove  — questo è il nostro divisore (qui ),  — è il coefficiente (quante volte il divisore si inserisce nell’originale senza resto, qui ), e  — è il resto, che generalmente restituisce la chiamata dell'operatore modulo (qui ). Conoscere tutti questi valori ci consente di risolvere l'equazione per , ma se saltiamo il coefficiente, non saremo mai in grado di ripristinare il valore originale.

Si può dimostrare come questo miglioramenti 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 custodi della chiave possono utilizzare di nuovo l'interpolazione polinomiale per ripristinare la nostra funzione, solo questa volta le operazioni di somma e moltiplicazione devono essere accompagnate dalla riduzione modulo (e.g. ).

Supponiamo che in questo nuovo esempio, l'attaccante abbia scoperto due di questi nuovi punti, , e le informazioni pubbliche . In questa occasione, l'attaccante, basandosi su tutte le informazioni in suo possesso, deduce le seguenti funzioni, dove  — l'insieme di tutti i numeri interi positivi, e rappresenta il coefficiente del modulo .

Ora il nostro aggressore trova di nuovo , calcolando :

Poi cerca di nuovo di dedurre , sostituendo in :

Questa volta ha un problema serio. La formula manca di valori , e . Poiché ci sono infinite combinazioni di queste variabili, non può ottenere ulteriori informazioni.

Ragioni di sicurezza

Lo schema di divisione del segreto di Shamir offre sicurezza dal punto di vista della teoria dell'informazione. Questo significa che la matematica è robusta anche contro un aggressore con potenza di calcolo illimitata. Tuttavia, lo schema presenta ancora alcuni problemi noti.

Ad esempio, lo schema di Shamir non crea frammenti verificabili, cioè le persone possono liberamente presentare frammenti falsi e ostacolare il recupero del segreto corretto. Un custode ostile dei frammenti con informazioni sufficienti può persino generare un altro frammento, modificando a proprio piacimento. Questo problema viene risolto tramite schemi di divisione del segreto verificabili, come lo schema di Feldman.

Un altro problema è che la lunghezza di ogni frammento corrisponde alla lunghezza del segreto corrispondente, quindi la lunghezza del segreto è facilmente determinabile. Questo problema viene risolto con una semplice riempimento del segreto con numeri arbitrari fino a una lunghezza fissa.

Infine, è importante notare che le nostre preoccupazioni per la sicurezza possono andare oltre lo schema stesso. Per le applicazioni crittografiche reali, esiste spesso la minaccia di attacchi tramite canali laterali, in cui un aggressore cerca di estrarre informazioni utili dal tempo di esecuzione dell'applicazione, dalla memorizzazione nella cache, dai crash, ecc. Se questo è motivo di preoccupazione, durante lo sviluppo dovrebbe essere attentamente considerato l'uso di misure protettive, come funzioni e ricerca con tempo di esecuzione costante, per evitare di salvare la memoria su disco, e riflettere su una serie di altre questioni che vanno oltre questo articolo.

Demo

A su questa pagina c'è una dimostrazione interattiva dello schema di divisione del segreto di Shamir. La dimostrazione è realizzata sulla base della libreria ssss-js, che è essa stessa un porting JavaScript del popolare programma ssss. Si prega di notare che il calcolo di valori elevati , e può richiedere del tempo.

Fonte: habr.com