Prendiamo in considerazione uno scenario in cui è necessario garantire la sicurezza di una cassaforte bancaria. Essa è considerata completamente inaccessibile senza la chiave, che ti viene fornita il primo giorno di lavoro. Il tuo obiettivo è proteggere la chiave in modo sicuro.

Supponiamo che tu abbia deciso di tenere sempre la chiave con te, fornendo l'accesso alla cassaforte all'occorrenza. Ma presto ti renderai conto che questa soluzione non scala bene nella pratica, poiché ogni volta per aprire la cassaforte è necessaria la tua presenza fisica. E per quanto riguarda le ferie che ti hanno promesso? Inoltre, c'è un'altra preoccupazione: cosa succede se perdi l'unica chiave?

Pensando alle ferie, hai deciso di fare una copia della chiave e affidarla a un altro dipendente. Tuttavia, comprendi che anche questo non è ideale. Raddoppiando il numero di chiavi, hai raddoppiato anche le possibilità di furto della chiave.

Disperato, distruggi il duplicato e decidi di dividere la chiave originale a metà. Ora, pensi che due persone fidate con i frammenti delle chiavi debbano essere fisicamente presenti per assemblare la chiave e aprire il deposito. Questo significa che un ladro deve rubare due frammenti, il che è il doppio più difficile rispetto al furto di una sola chiave. Tuttavia, presto ti rendi conto che questo schema non è molto meglio di una sola 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 presto saranno necessari tanti chiavi e serrature. Decidi che in uno schema ideale la chiave dovrebbe essere divisa, affinché la sicurezza non dipenda completamente da una sola persona. Concludi anche che deve esistere una certa soglia di frammenti, in modo che nella perdita di un frammento (o se una persona è in ferie) l'intera chiave rimanga funzionale.

Come dividere un segreto

Di questo tipo di schema di gestione delle chiavi pensava Adi Shamir nel 1979, quando pubblicò il suo lavoro «Come dividere un segreto». Nell'articolo si spiega brevemente il cosiddetto schema di soglia per la segmentazione efficace di un valore segreto (ad esempio, una chiave crittografica) in parti. Quindi, quando e solo quando almeno di parti sono raccolte, è possibile ripristinare facilmente il segreto. .

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

Interpolaizone polinomiale

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

Tra due punti si può tracciare un numero illimitato di polinomi di secondo grado. Per scegliere uno di essi in modo univoco, è necessaria un terza punto. Illustrazione: Wikipedia

Consideriamo un polinomio di grado uno, . Se desideri costruire questa funzione su un grafico, quante punti ti servono? Bene, sappiamo che si tratta di una funzione lineare, quindi sono necessarie almeno due punti. Successivamente, consideriamo una funzione polinomiale di grado due, . Questa è una funzione quadratica, quindi per costruire il grafico servono almeno tre punti. E per un polinomio di grado tre? Servono almeno quattro punti. E così via.

La cosa davvero interessante di questa proprietà è che, dato il grado della funzione polinomiale e almeno punti, possiamo dedurre punti aggiuntivi per questa funzione polinomiale. Chiamiamo l'estrapolazione di questi punti aggiuntivi interpolazione polinomiale.

Costruzione del segreto

Potresti già aver capito che qui entra in gioco lo schema segreto di Shamir. Supponiamo che il nostro segreto — rappresenta . Possiamo trasformare in un punto sul grafico e inventare una funzione polinomiale di grado , che soddisfa questo punto. Ricordiamo che sarà la nostra soglia di frammenti richiesti, quindi se impostiamo la soglia a tre frammenti, dobbiamo scegliere una funzione polinomiale di grado due.

Il nostro polinomio avrà la forma , dove e — numeri interi positivi scelti casualmente. Stiamo semplicemente costruendo un polinomio di grado , dove il termine costante  — è il nostro segreto , e ogni uno dei successivi termini ha un coefficiente positivo scelto casualmente. Tornando all'esempio originale e assumendo che , otteniamo quindi la funzione .

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

Recupero del segreto

Abbiamo già discusso il concetto di interpolazione polinomiale e che essa sta alla base dello schema di soglia di Shamir . Quando tre dei quattro fiduciari vogliono ripristinare , devono solo interpolare con i loro punti unici. Per questo possono definire i loro punti e calcolare il polinomio di Lagrange usando la seguente formula. Se la programmazione ti è più chiara della matematica, allora pi è fondamentalmente un operatore per, che moltiplica tutti i risultati, e la sigma è per, che somma tutto.

Durante possiamo risolverlo nel seguente modo e restituire la nostra funzione polinomiale originale:

Poiché sappiamo che , il ripristino è semplice:

Utilizzo di aritmetica intera non sicura

Anche se abbiamo applicato con successo l'idea principale di Shamir , abbiamo un problema che abbiamo ignorato fino ad ora. La nostra funzione polinomiale utilizza un'aritmetica intera non sicura. Tieni presente che per ogni punto in più che l'attaccante riesce a ottenere nel grafico della nostra funzione, ci sono meno opportunità per altri punti. Puoi vederlo con i tuoi occhi quando tracci un grafico aumentando il numero di punti per la funzione polinomiale utilizzando l'aritmetica intera. Questo è controproducente per il nostro obiettivo dichiarato di sicurezza, perché l'attaccante non dovrebbe scoprire assolutamente nulla finché non ha almeno frammenti.

Per dimostrare quanto sia debole lo schema con l'aritmetica intera, consideriamo uno scenario in cui un attaccante ha ottenuto due punti e sa informazioni pubbliche che . Da questa informazione può dedurre , pari a due, e connettere nella formula i valori noti e .

Poi l'attaccante può trovare , calcolando :

Poiché abbiamo definito come numeri interi positivi scelti casualmente, c'è un numero limitato di possibilità . Con queste informazioni, l'attaccante può dedurre , dato che tutto ciò che supera 5 renderà negativo. Questo si rivela vero, poiché abbiamo determinato

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

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

Risolvere il problema dell'aritmetica intera non sicura

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

Rinfreschiamo rapidamente come funziona l'aritmetica modulare. Gli orologi a lancetta sono un concetto già noto. Utilizza orari che sono . Non appena la lancetta delle ore supera le dodici, ritorna all'una. Una caratteristica interessante di questo sistema è che, semplicemente guardando l'orologio, non possiamo dedurre quante volte ha girato la lancetta delle ore. Tuttavia, se sappiamo che la lancetta delle ore ha superato 12 quattro volte, possiamo determinare esattamente il numero di ore trascorse con una semplice formula , dove  — è il nostro divisore (qui ),  — è il coefficiente (quante volte il divisore si inserisce senza resto nel numero originale, qui ), e  — è il resto, che di solito restituisce la chiamata all'operatore modulo (qui ). Conoscere tutti questi valori ci permette di risolvere l'equazione per , ma se ignoriamo il coefficiente, non saremo mai in grado di ripristinare il valore originale.

Possiamo dimostrare come questo 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 custodi delle chiavi possono riutilizzare l'interpolazione polinomiale per ripristinare la nostra funzione, solo che questa volta le operazioni di somma e moltiplicazione devono essere accompagnate dalla riduzione modulo (e.g. ).

Utilizzando questo nuovo esempio, supponiamo che un attaccante conosca due di questi nuovi punti, , mentre le informazioni pubbliche . Questa volta l'attaccante, sulla base di tutte le informazioni a sua disposizione, deduce le seguenti funzioni, dove  — è l'insieme di tutti i numeri interi positivi, e rappresenta il coefficiente modulo .

Ora il nostro attaccante trova di nuovo , calcolando :

Poi prova di nuovo a dedurre , sostituendo in :

Questa volta ha un problema serio. Mancano valori nella formula , e . Poiché esistono infinite combinazioni di queste variabili, non può ottenere ulteriori informazioni.

Considerazioni di sicurezza

Il protocollo di divisione del segreto di Shamir offre sicurezza in termini di teoria dell'informazione. Ciò significa che la matematica è robusta anche contro un attaccante con potenza di calcolo illimitata. Tuttavia, lo schema presenta ancora diversi problemi noti.

Ad esempio, il protocollo di Shamir non genera frammenti verificabili, il che significa che le persone possono presentare liberamente frammenti falsi e ostacolare il recupero del giusto segreto. Un custode ostile di frammenti con informazioni sufficienti può persino generare un altro frammento, modificando a proprio piacimento. Questo problema è risolto tramite schemi di divisione del segreto verificabili, come il protocollo di Feldman.

Un'altra problematica è che la lunghezza di qualsiasi frammento corrisponde alla lunghezza del segreto sottostante, rendendo facile determinare la lunghezza del segreto. Questo problema è risolto semplicemente con riempimento segreti con numeri arbitrari di lunghezza fissa.

Infine, è importante notare che le nostre preoccupazioni per la sicurezza possono andare oltre il mero schema. Per le applicazioni crittografiche reali, esiste spesso la minaccia di attacchi attraverso canali laterali, in cui un aggressore cerca di estrarre informazioni utili dai tempi di esecuzione dell'applicazione, dalla memorizzazione nella cache, dai guasti, ecc. Se ciò suscita preoccupazioni, è importante considerare attentamente l'uso di misure protettive durante lo sviluppo, come funzioni e ricerche con tempo di esecuzione costante, evitare la memorizzazione in memoria su disco e prendere in considerazione una serie di altre questioni che vanno oltre questo articolo.

Demo

Su questa pagina ha una dimostrazione interattiva dello schema di condivisione del segreto di Shamir. La dimostrazione è basata sulla libreria ssss-js, che è a sua volta un porting JavaScript del popolare programma ssss. Si noti che il calcolo di valori elevati , e può richiedere del tempo.

Fonte: habr.com