Limited Entropy Dot Com Not so random thoughts on security featured by Eloi Sanfèlix

Shamir’s secret sharing: Secretos digitales compartidos

Con este post voy a salirme un poco de lo que viene siendo la temática habitual para meterme en otra un poquito más freak si cabe: la criptografía. No vamos a hablar de ningún algoritmo de cifrado ni de ningún criptosistema, sino de una técnica para compartir secretos digitales.

¿Qué es eso de compartir secretos? Imaginemos que somos parte del comité ejecutivo de una compañía que ha creado un producto revolucionario y desea que sus detalles se guarden en secreto, pero nuestro comité ejecutivo desea poder acceder a dicho secreto. Sin embargo, no queremos que un único miembro de dicho comité pueda acceder al secreto, sino que haya un determinado número de miembros presentes para dicho acceso. De esta forma, si un miembro por la razón que sea intenta acceder al secreto solo, el acceso será denegado.

Cómo podemos conseguir eso? Todos sabemos que para crear una recta sólo necesitamos dos puntos, una parábola 3, etcétera. Por tanto, una forma sencilla conocida como el esquema de Shamir (en inglés) se basa en el hecho de que con k+1 puntos de un polinomio somos capaces de reconstruir el polinomio entero. Para ello, se usa la interpolación polinómica de Lagrange , y en base a un determinado número de puntos se obtiene el polinomio.

Así pues, lo que habría que hacer para un esquema de secretos compartidos con n usuarios totales y un mínimo de k para obtener el secreto es lo siguiente:

• Codificar el secreto como un entero, S.
• Elegir un polinomio de grado k-1, f(x)=S+a·x + b·x^2 + ...
• Obtener n puntos de dicho polinomio y repartirlos a los n usuarios.

Así pues, cada usuario tiene su punto, y el polinomio se mantiene en secreto. Cuando se juntan k o más usuarios, simplemente aplican la fórmula de interpolación de Lagrange sobre esos puntos, y obtienen el término independiente del polinomio: nuestro secreto.

Este esquema se puede usar por ejemplo para el acceso a un sistema, siendo el secreto el password de acceso y teniendo cada usuario su propia clave. De esta forma, se proporcionan tres claves al sistema y éste reconstruye el polinomio mediante la fórmula de interpolación de Lagrange. Si el término independiente coincide con el esperado el acceso es permitido, y si no es denegado.

Un ejemplo simple e interesante de lo que pueden dar de sí las matemáticas, aplicando cosas sencillas que la mayoría conocemos de forma inteligente 🙂