ENTRADAS

31 ago 2016

Por qué necesitas matemáticas para guardar secretos

/
Publicado por
/
Comentarios0
/

Las decisiones económicas de una empresa las toma la Junta Directiva. Imaginemos que en una empresa la Junta Directiva está formada por seis personas. No resulta ágil para el buen funcionamiento de la empresa que cualquier decisión económica tenga que ser aceptada por los seis directivos por lo que se decide que cualquier decisión deba ser aceptada por un mínimo de tres de ellos.

Para la realización de cualquier decisión de carácter económico se requiere de una clave que es la que permite la realización de la transacción. Ahora bien, ¿qué clave damos a cada uno de los directivos?

clave, contraseña

clave, contraseña

En principio podemos pensar que cada uno de ellos disponga de una llave o clave para poder ejecutar una compra, pero si todos tienen clave entonces pueden comprar sin necesidad de llegar al consentimiento de ninguno más y recordemos que queremos incluir la condición de que, al menos tres directivos, den su consentimiento cada vez.

La idea de establecer un documento de compra que necesite ser firmado por tres de ellos no parece una buena opción ya que las firmas se pueden falsificar además de que, como cada uno tiene la clave, podrían sucumbir a la tentación de saltarse el protocolo.  Debemos por lo tanto establecer algún sistema que no permita el acceso al dinero de ningún directivo pero que al juntarse tres cualesquiera de ellos les permita acceder a él. ¿Cómo establecemos dicho sistema?

Este problema es conocido como el sistema de repartición de secretos y fue resuelto por el criptógrafo israelí Adi Shamir en 1979. Consiste en un algoritmo criptográfico basado en las propiedades de los polinomios interpoladores.

Antes de explicar el funcionamiento del algoritmo de Shamir para compartir secretos conviene recordar que cualquier clave puede expresarse de forma numérica. Es decir, todas las claves pueden ser reducidas a códigos numéricos.

Supongamos que la clave a compartir fuera VERDE, podemos de una forma fácil asignar a cada letra un código numérico de la siguiente forma:

A la letra A le asignamos el valor 00, a la letra B el valor 01, el 02 para la letra C y así sucesivamente. De forma que nuestra clave VERDE se transforma en 2104170304.

Una vez hecho este inciso procedemos a explicar el algoritmo de Shamir. Si queremos que sean necesarias n personas para poder descifrar la clave entonces el algoritmo consiste en crear un polinomio de grado n-1, donde el término independiente será la clave y los demás coeficientes serán números escogidos por la persona que quiere distribuir la clave. Estos valores son arbitrarios y no influyen en el desarrollo del algoritmo. A continuación se generan tantos valores de la forma (k, p(k)) como personas tengan acceso a la información. De esta forma basándonos en que todo polinomio de grado n-1 se puede construir utilizando n valores cualesquiera de dicho polinomio (todos ellos distintos) podremos reconstruir el polinomio y por lo tanto conseguir la clave.

Veámoslo con un ejemplo:

Supongamos que la clave secreta es s=2016. Queremos que tres personas cualesquiera de la junta directiva de entre los seis que hay puedan juntos realizar una compra y por lo tanto conocer la clave pero que menos de tres personas no puedan realizarlo. Si pensamos un poco en las técnicas interpolatorias, con tres datos distintos podemos construir un polinomio de interpolación de grado 2, por lo tanto la persona que distribuya el secreto deberá escoger dos números cualesquiera, que denotaremos por a y b, con los que construiremos el polinomio de segundo grado:

p(x)=s+ax+bx^2

Para continuar con el ejemplo, consideremos los valores a=234, b=198. En este caso el polinomio construido será:

p(x)=2016+234x+198x^2

A continuación calculamos tantos puntos del polinomio como personas haya en la junta directiva, es decir seis  puntos, por ejemplo:

(1,2448),  (3,4500),  (10,24156),  (12,33336),   (15,50076),   (20,85896)

No olvidemos que la clave que pretendemos guardar es el valor asignado a p(0), por lo que el valor (0,p(0)) no podemos asignárselo a ningún directivo puesto que en tal caso le estaríamos dando la clave completa.

Cuando tres de ellos se junten  podrán construir el polinomio p(x) utilizando las técnicas interpolatorias, y por lo tanto podrán descifrar la clave que será s=p(0).

Por ejemplo, si los directivos que se unen son los relacionados con las claves:

(1,2448),   (3,4500),   (10,24156)

Entonces el polinomio buscado será  donde s, a, b son desconocidas. Para calcularlas bastará con considerar:

\left.  \begin{array}{c}  p(1)=2448 \\  p(3)=4500 \\  p(10)=24156 \\  \end{array}  \right\}

Es decir habrá que resolver el sistema:

\left.  \begin{array}{c}  s+a+b=2448 \\  s+3a+9b=4500 \\  s+10a+100b=24156 \\  \end{array}  \right\}

Resolviendo el sistema de ecuaciones se tiene que s=2016, a=234, b=198 por lo que el polinomio viene dado por

p(x)=2016+234x+198x^2

Y por lo tanto calculando p(0)=2016 tenemos la clave que queríamos guardar.

El algoritmo de Shamir nos presenta una utilidad muy importante de los polinomios y de la interpolación polinómica, ya que nos permite compartir claves de una forma sencilla y eficaz.

AUTOR: FRANCISCO MORANTE QUIRANTES @fdetsocial

Más entradas del autor para FdeT

Si quieres participar en el blog como colaborador en alguna de las secciones, envíanos un mail a info@fdet.es 

Grupo FdeT

Compartir:
Facebooktwittergoogle_pluslinkedin

Leave a Reply

A %d blogueros les gusta esto: