Esquema de Shamir

Archiu:Adi Shamir 2009 crop.jpg

Adi Shamir, desenrollador del sistema de compartición de secrets que du el seu nom.

El sistema de compartición de secrets de Shamir és un algoritme criptográfico. És una forma de compartición de secrets a on un secret es dividix en parts i es dona a cada participant una sola: totes o part d'elles són necessàries per a reconstruir el secret.

L'algoritme basa el seu funcionament en una propietat dels polinomis interpoladores i va ser desenrollat pel criptógrafo israelí Adi Shamir, que ho va presentar en 1979.

Definició matemàtica

Formalment, el nostre objectiu és dividir un conjunt de senyes $D$ (per eixemple, una clau) en $n$ parts $D_1,\cdots ,D_n$ de manera que:

1. El coneiximent de $k$ o més $D_i$ parts fa que $D$ siga fàcilment computable.
2. El coneiximent de $k-1$ o menys $D_i$ parts fa que $D$ estiga indeterminat, en el sentit de que tots els seus valors possibles tenen la mateixa provabilitat de ser verdaders.

Esta combinació es denomina combinació o esquema de llindar $(k,n)$. Si $k=n$ es requerix la concurrència de tots els participants per a reconstruir el secret.

Sistema de compartición de secrets de Shamir

Archiu:3 polynomials of degree 2 through 2 points.svg

Es poden dibuixar infinits polinomis de grau 2 que passen per 2 punts. Es necessiten 3 punts per a definir un polinomi únic de grau 2. Esta image només té fins ilustrativos - L'esquema de Shamir utilisa polinómios en un conjunt finito, no representable en un pla bidimensional.

L'idea essencial de la combinació de llindar de Shamir és que dos punts són suficients per a definir una llínea recta, tres punts ho són per a definir una paràbola, quatre per a definir una curva cúbica i aixina successivament. És dir, són necessaris $n+1$ punts per a definir un polinomi de grau $n$.

Supongam que volem treballar en un llindar de $(k,n)$ per a compartir un secret $S$ (qualsevol número, sense pèrdua de generalitat) sent $k<n$. L'elecció dels valors de $k$ i $n$ determina la fortalea del sistema.

Elegint a l'encert $(k-1)$ coeficients $a_1,\cdots ,a_{k-1}$, i sent $a_0=S$, es construïx el polinomi $f\left(x\right)=a_0+a_{1}x+a_2{x}^2+a_3{x}^3+\cdots +a_{k-1}{x}^{k-1}$. Calculem qualssevol $n$ punts a partir del mateix, per eixemple determinem que $i=1,\cdots ,n$ de lo que es deriva $(i,f\left(i\right))$. A tot participant en el secret se li dona un punt (un parell de valors, el d'entrada i el d'eixida per al polinomi)

Donat qualsevol subconjunt de $k$ entre estos parells, podem calcular els coeficients del polinomi per mig d'interpolació i després rebujar $a_0$, que és el secret.

Referències

• , pp. 612-613