viernes, 6 de julio de 2012

Secretos compartidos




No soy una persona que tenga mucho que esconder, pero hay cosas que más vale mantener en secreto. Por mi parte, lo típico: el pin del móvil y el de la tarjeta de crédito, las claves del banco, de las cuentas de correo, del ordenador, y poco más. Si alguien llegara a acceder a mi cuenta bancaria, dependiendo del día del mes, igual hasta le tocaba pagar, y en mi cuenta de correo tampoco hay ningún secreto de estado.
Sin embargo, hay secretos de los que dependen cosas mucho más importantes. A nadie se le escapa que la clave del correo de un presidente de gobierno o de un empresario importante es harina de otro costal. Con un poco de información privilegiada, ganar en la bolsa puede llegar a ser un juego de niños (está claro que no hay otra forma de acceder a esa información privilegiada que accediendo ilegalmente a sus correos, porque nadie duda de la integridad de los que manejan esa información ¿verdad?).
El caso es que aquella mañana de Lunes, durante el desayuno, alguien sacó el tema -creo que el sr. Lego- y, por supuesto, a pesar de mis intentos por desviar la conversación a ámbitos más mundanos, Sofía no podía resistir la tentación de enfrascarse en cualquier conversación que oliera a seguridad informática.
Ya, de perdidos al río -pensé- así que traté de volver a entrar en la conversación:
- ¿Os imagináis tener que mantener en secreto algo como los códigos de lanzamiento de unos misiles nucleares?
¡Vaya! Ya está Alberto con sus paranoias -pude leer en la expresión de el Sr. Lego.
Sofía, sin embargo, fue mucho más directa y menos sutil:
- ¡No digas tonterías! ¿tu te fiarías de alguien tanto como para darle las claves de lanzamiento de un misil nuclear? ¿Y si se vuelve loco y le da por desatar la tercera guerra mundial?
- Quizás se podría dividir la clave en varios fragmentos y repartirlos entre varias personas, así nadie sabe la clave completa y nadie puede lanzar los misiles por su cuenta -dije tratando de impresionar a Sofía.
- Entonces, si fuera un país enemigo sólo tendría que matar a uno de los que tienen la clave para evitar que pudiera lanzar los misiles... o bastaría esperar a que a alguno le de un infarto... ¡jaque mate!
- A ver -continuó el Sr. Lego- necesitamos una forma de repartir fragmentos de la clave entre varias personas de forma que ninguna conozca la clave completa, y además, queremos ser capaces de reconstruir la clave si falla una o más de una de las personas que tienen los fragmentos. Me parece que no es posible.
- Pues siento decir que te equivocas -sonrió Sofía.

En criptografía -continuó Sofía- para resolver este tipo de asuntos se utilizan los llamados esquemas de compartición de secretos. Para este caso concreto se utilizan los esquemas de umbral. Por ejemplo, si queremos repartir un secreto entre m personas y que el secreto pueda recuperarse con n personas, hablamos de un esquema de umbral (m,n), donde n es el umbral.
Parar a Sofía a estas alturas, estaba ya fuera del alcance de cualquier mortal, así que mi única salida fue preguntar, no sin cierta resignación:
Vale, pero ¿cómo funcionan esos esquemas?
Sofía apuró el café que le quedaba en el vaso, se detuvo unos instantes como para componer en su cabeza lo que iba a decir, y continuó:
Hay varios métodos, el más sencillo, quizás, es usar el esquema vectorial, introducido por el matemático George Blakley de la universidad A&M de Texas: Si queremos compartir un secreto con un esquema de umbral (m,n) hacemos corresponder el secreto con un punto P del espacio m-dimensional, y los fragmentos serán hiperplanos de dimensión m-1 que tienen a P como punto de intersección. De esta forma, con m hiperplanos, podemos reconstruir el secreto.
- Por la cara del Sr. Lego, hacía rato que ya no seguía a Sofía. Yo, por mi parte tampoco, pero creía que estaba controlando mejor mi expresión facial hasta que Sofía me miró y sonrió con esa sonrisa piedosa del que se sabe muy por encima de su interlocutor.
Está bien -dijo Sofía tratando de simplificar un poco el asunto- imaginemos que quiero compartir en secreto las tres siguientes cifras: 3,10,5. Y lo quiero hacer entre 4 personas, de forma que sólo con 3 pueda recuperar la clave. Como son tres cifras, podemos pensar en ellas como en un punto P(x,y,z) del espacio de 3 dimensiones. Sólo tendríamos que crear 4 ecuaciones como las siguientes.


Si damos una ecuación a cada una de las cuatro personas, ninguna de ellas podrá conocer el valor del punto P(x,y,z). Sin embargo, si cualquiera de ellas tres se reúnen y resuelven el sistema que forman sus tres ecuaciones, habrán conseguido descifrar el secreto P(3,10,5), aunque no esté una de las personas.

Bastante ingenioso -pensé- no se me hubiera ocurrido, y eso que una vez que conoces el sistema, es bastante obvio.

Otro esquema, algo más elaborado -continuó Sofía- es el esquema de Shamir, que inventó el matemático Adi Shamir. Este esquema es conceptualmente bastante simple, aunque su uso implica algo más que resolver un simple sistema de ecuaciones.
Sofía paró un momento como tratando de ordenar toda la información que tenía en la cabeza y seguidamente preguntó:
- Si dibujo dos puntos en un papel, ¿cuantas líneas rectas existen que pasen exactamente por esos dos puntos?
El Sr. Lego y yo nos miramos unos instantes antes de responder al unisono: una.
- Bien -continuó Sofía- del mismo modo que sólo necesito dos puntos para definir una recta, sólo necesito tres para definir una parábola ¿verdad?
Esto ya no era tan obvio, pero haciendo un acto de fe el Sr. Lego y yo asentimos con la cabeza.
En general, necesitamos n+1 puntos en el plano para definir una curva (polinomio) de grado n ¿os lo demuestro? -preguntó Sofía.
Me apresuré a decir que no era necesario antes de que se lanzara a hacer la demostración matemática.
En general -siguió Sofía- si quiero compartir un secreto repartiéndolos en m fragmentos y con un umbral de n fragmentos, tengo que construir un polinomio de grado n-1.
Imaginemos entonces que quiero compartir en secreto el pin de mi tarjeta de crédito que, digamos, es 3254. Y lo quiero hacer entre 4 personas con un umbral de 3. Necesito, por lo tanto, un polinomio de grado 2 (es decir n-1) que tendrá la forma siguiente:


A los términos a0, a1 y a2 los llamamos coeficientes del polinomio. A a0, que es el término independiente, le asignamos el valor del secreto: en este caso a0=3254. Al resto de coeficientes le asignamos valores aleatorios.
Por ejemplo: a1=12 y a2=25. Una vez definido nuestro polinomio, como quiero repartir el secreto entre 4 personas, necesito el valor de cuatro puntos cualesquiera de la función. Por ejemplo:


En este caso hemos escogido los puntos 1, 2, 3 y 4, pero podrían ser cualesquiera.
A cada una de las personas les damos un par con uno de los puntos y el valor que toma la función en dicho punto. Es decir tendríamos los siguientes cuatro fragmentos:
(1, 3291)
(2, 3378)
(3, 3515)
(4, 3702)

Pero según hemos dicho antes, un polinomio de grado n está definido de forma inequívoca por por n+1 puntos, así que como nuestro polinomio era de grado 2, sólo necesitamos 3 de los puntos (fragmentos) para poder reconstruirlo.

La idea está clara -respondí- pero ¿cómo se reconstruye un polinomio a partir de unos puntos?
No te preocupes, Alberto, eso lo resolvió Lagrange hace ya algunos añitos. Podemos usar el polinomio interpolador de Lagrange para obtener el polinomio original, pero ¿realmente necesitamos todo el polinomio original? -nos desafió Sofía.
No, sólo el término independiente del polinomio, que es el que contiene el secreto -respondió el Sr. Lego sorprendiendo a propios y a extraños.
Efectivamente Sr. lego. No voy a entrar en detalles matemáticos, que son un poco aburridos, pero tras jugar un poco con el polinomio de Lagrange, podemos llegar a la siguiente formulita que nos devuelve el término independiente del polinomio.


Siendo las x los puntos y las y los valores que toma la función en dichos puntos.
Como véis, la formulita de marras se puede modelar muy bien con un par de bucles así que es fácil hacer un programa para generar y develar secretos con el esquema de Shamir.
A la vuelta del desayuno, ya en la oficina, Sofía nos envió las siguientes dos funciones para generar secretos y para desvelarlos. Eso sí -nos advirtió- ningún secreto está a salvo para siempre.



  1. from math import ceil
  2. from random import random
  3.  
  4.  
  5. def gen_secret(secret, users, threshold):
  6.     out = []
  7.  
  8.     max_value=100   # valor maximo factores
  9.     n=threshold     # grado del polinomio
  10.     # generar polinomio grado n
  11.     factores=[]
  12.     fragmentos=[]
  13.     factores.append(secret)
  14.     for i in range (1,n):
  15.         t=ceil(random()*max_value)
  16.         factores.append(t)
  17.    
  18.     # generar n fragmentos
  19.     for i in range(users):
  20.         # escogemos punto t de la funcion aleatorio
  21.         t=int(ceil(random()*max_value))
  22.         # calcular valor de f(t)
  23.         v=factores[0]
  24.         for j in range(1,n):
  25.           v=v+factores[j]*(t**j)
  26.      
  27.         fragmentos.append([t, int(v)])
  28.  
  29.     out=fragmentos
  30.     return out
  31.  
  32.  
  33.  
  34.  
  35. def recover_secret(fragments, threshold):
  36.     out = 0
  37.  
  38.     if len(fragments)<threshold:
  39.         print "faltan fragmentos"
  40.     else:
  41.  
  42.         for i in range(threshold):
  43.             tmp_j=1
  44.             for j in range(threshold):
  45.                 if j!=i:
  46.                     tmp_j=tmp_j*(fragments[j][0]/float((fragments[j][0]-fragments[i][0])))
  47.             out=out+(fragments[i][1]*tmp_j)
  48.  
  49.     return int(out)
  50.  
  51.  
  52. # calculamos 4 fragmentos para secreto 1234 con umbral 3
  53. s=gen_secret(1234,4,3)
  54. # recuperamos el secreto con 3 fragmentos
  55. print recover_secret(s, 3)

5 comentarios:

  1. Relacionado con este post he encontrado un vídeo que explica el tema bastante bien. Espero que os guste:
    http://www.criptored.upm.es/intypedia/video.php?id=reparto-secretos&lang=es

    ResponderEliminar
  2. Hola Sofía, aunque diferentes en naturaleza, veo que al final ambos sistemas se pueden resolver igual, no?

    En el segundo también tendríamos 4 ecuaciones con 3 variables (con tres de ellas se resuelve)
    3291 = x + y*1 + z*1
    3378 = x + y*2 + z*4
    3515 = x + y*3 + z*9

    ResponderEliminar
    Respuestas
    1. Efectivamente Daniel. Son dos enfoques diferentes para resolver el mismo problema.

      Eliminar