Criptografía (CLXXV): Esquema de compartición de secretos de Shamir

Aunque habitualmente no las relacionamos con el esquema de compartición de secretos ideado por el criptógrafo israelí Adi Shamir (en inglés: "Shamir's secret sharing scheme") o esquemas similares, todos hemos visto películas en las que un secreto se divide en partes y cada una de ellas se entrega a una persona, con la finalidad de que ninguna de ellas por separado pueda recuperar el secreto original y se precise que varias, un número mínimo y previamente establecido de éstas, se pongan de acuerdo y cooperen, aportando su parte, para que el secreto se revele.

Así, por ejemplo, todo recordamos películas en las que para activar el lanzamiento de misiles balísticos intercontinentales, para iniciar la tercera guerra mundial o responder a un ataque del enemigo, se reparte el código de activación (el secreto) entre diferentes participantes (a cada uno de ellos se le entrega una clave. Para el caso que pondré más adelante, consideremos cinco personas: presidente, vicepresidente y tres generales), de manera que para lanzar los misiles se requiere que un número de ellos (supongamos que tres) aporten su parte del secreto (la clave que ha recibido cada uno de ellos), y, sólo si es así, puedan obtener el código de activación.

Para implementar esto, en criptografía se utilizan los llamados esquemas de compartición de secretos, y en el caso concreto del esquema objeto de este post se  parte de lo que se denomina esquema de umbral (k, n), donde 'k' es el número de personas entre las que se divide o fracciona el secreto ('S') y 'n' es el número de ellas que deben cooperar para recuperar u obtener éste (en nuestro ejemplo, k = 5 y n = 3). Por tanto, 'n' es el umbral y, lógicamente, será menor o igual que 'k' (si 'n' = 'k' se requiere la concurrencia de todos los participantes para reconstruir el secreto).

Tal y como nos cuente wikipedia, "La idea esencial de la combinación de umbral de Shamir es que dos puntos son suficientes para definir una línea recta, tres puntos lo son para definir una parábola, cuatro para definir una curva cúbica y así sucesivamente. Es decir, basta con n + 1 puntos para definir un polinomio de grado n".

Pongamos un ejemplo: supongamos que, como he dicho antes, el código de activación de los misiles, el secreto ('S'), es 1234 y lo vamos a dividir en 5 partes, cada una de las cuales la entregaremos a uno de los participantes (presidente, vicepresidente y tres generales), y sólo si tres cualesquiera de ellos se ponen de acuerdo e introducen en el sistema sus correspondientes claves reconstruirán el secreto ('S'), es decir, obtendrán el código de activación para lanzar los misiles.

En este caso, para implementar el esquema de compartición de secretos de Shamir, necesitamos un polinomio de grado 2 (en general, de grado n -1):

Donde: a₀ o término independiente es el secreto a compartir (en nuestro caso: S = a₀ = 1234), y al resto de coeficientes (a₁...a_n-1) les asignamos valores aleatorios (en nuestro caso, supongamos que: a₁ = 24 y a₂ = 57). Por tanto, en nuestro ejemplo tendríamos el siguiente polinomio:

A cada uno de los participantes le damos un punto de este polinomio (cada uno de ellos definido por x y f(x)):

f(1) =1234 + 24 + 57 = 1315, es decir, al presidente le damos el par de valores (1, 1315).
f(2) =1234 + 48 + 228 = 1510, es decir, al vicepresidente le damos (2, 1510).
f(3) =1234 + 72 + 513 = 1819, es decir, al primer general le damos (3, 1819).
f(4) =1234 + 96 + 912 = 2242, es decir, al segundo general le damos (4, 2242).
f(5) =1234 + 120 + 1425 = 2779, y, finalmente, al tercer general le damos (5, 2779).

Sin entrar en la demostración matemática, para lo que además no tengo ni capacidad ni talento, basándome en el polinomio interpolador de Lagrange, si no estoy equivocado, puedo obtener el polinomio original y, por tanto, reconstruir el secreto ('S') con sólo tres de los puntos anteriores (claves), no con menos, de la siguiente manera (supongamos que el primer general fallece en un atentado terrorista y nadie puede proporcionar su clave, el segundo general no está de acuerdo con el lanzamiento de los misiles en ese momento, porque duda de que estén siendo atacados, y que sólo el presidente, el vicepresidente y el tercer general están de acuerdo en el lanzamiento porque creen que, a su vez, están siendo atacados por misiles enemigos y que no pueden demorar más tiempo una respuesta contundente):

Como se ve en la figura anterior, con sólo tres puntos (claves) hemos reconstruido el secreto original, que es el término independiente del polinomio (S = a₀ = 1234), y ya estaríamos en disposición de lanzar los misiles :).