Esquema de cifrado compartido de Shamir

El Esquema de Cifrado Compartido de Shamir(Shamir's Secret Sharing) es un algoritmo criptográfico creado por Adi Shamir, uno de los creadores del popular algoritmo RSA. El algoritmo es del tipo secreto compartido, donde cada participante es dueño de una única parte que se obtiene al dividir el secreto. 

Lo interesante está en la reconstrucción, puesto que se requiere un número mínimo $k$ de participantes, también llamado umbral, para obtener el secreto. 

Modelo matemático

Se requiere dividir el secreto $S$ (e.g una clave compartida para acceder a una caja fuerte) en $n$ partes $S_1, S_2, ... , S_n$ de tal manera que $S$ puede ser reconstruida por cualquier combinación de $\textbf{k}\leq n$ o más partes, sin embargo si tenemos menos de $k$ partes, $S$ es completamente indeterminado. 
Este esquema es llamado un $(k,n)$ esquema de umbral, además si $k=n$ requerimos todas las partes para la reconstrucción del secreto. 

La idea esencial de Adi Shamir se basa en la interpolación polinómica de Lagrange, que teniendo $k$ puntos en $\mathbb{R}^2$ de la forma $(x,y)$ podemos definir un polinomio en una variable $L(x)$ de grado $k-1$

Supongamos que queremos trabajar con el esquema umbral $(k,n)$ para compartir un secreto $S$ (sin perdida de generalidad consideramos a $S$ un número-código ASCII) siendo $k<n$. La elección de los valores de $k$ y $n$, tal que $k<n$ determina la fortaleza del sistema.

Algoritmo para cifrar - $(k,n)$ esquema de umbral 
  1. Elegimos de forma aleatoria(cuasi en realidad) $k-1$ enteros positivos $a_1, ... , a_{k-1}$ con $a_0 = S$ y $a_i < S$.
  2. Construimos el polinomio $L(x) = a_0  + a_1x + a_2x^2 + ... + a_{k-1}x^{k-1} $
  3. Calculamos $n$ puntos cualesquiera a partir de $L(x)$, por ejemplo $(1,L(1)),(2,L(2)), .... , (n,L(n)) $ 
  4. Repartirmos cada uno de estos puntos a cada participante, que será dueño de una única parte del secreto. 
Algoritmo para descifrar - $(k,n)$ esquema de umbral 
  1. Se tiene cualquier subconjunto de $k$ puntos.
  2. Buscamos los coeficientes del polinomio $L(x)$ usando la interpolación polinómica de Lagrange.
  3. Luego evaluamos el polinomio en 0, esto es $L(0) = a_0 = S$.
  4. Mostramos el secreto $S$.

Comentarios

Publicar un comentario

Entradas populares de este blog

Teoría de la información > Entropía y Criptografía

Imagen
Veamos: Fig1 - Idea intuitiva de la entropía La entropía es una medida de aleatoriedad en la información, esto es importante en los procesos criptográficos . En seguridad de la información, requerimos algoritmos de seguridad para producir una alta aleatoriedad en el mensaje cifrado, de modo que haya menos o ninguna dependencia entre la clave y el texto cifrado. Con una alta aleatoriedad, la relación entre la clave y el texto cifrado se vuelve compleja. Esta propiedad también se llama confusión . Se desea que un alto grado de confusión sea difícil de adivinar para un atacante. La entropía refleja el rendimiento del algoritmo criptográfico. [1, 3] Calculemos la entropía en la información usando la fórmula de Shannon.  Consideremos un mensaje $X$(variable aleatoria) la entropía de $X$, denotado por $H(X)$, es el valor medio ponderado de la cantidad de información de los diversos estados del mensaje $x_i$. $$H(X) = - \sum_{i=1}^{n}p_i \log_2(p_i)$$ Donde $p_i = p(x_i)=p(X=x_i)$ es la ...
Leer más

Linear Q-Learning - Doble Péndulo Invertido

Imagen
Fig1: Doble péndulo invertido sobre un móvil. Se ha implementado los algoritmos de aprendizaje por refuerzo Linear Q-Learning y Deep Q-Learning para lograr la convergencia del movimiento de un doble péndulo invertido a su estado de equilibrio. Los resultados indican que para una perturbación uniformemente aleatoria de la posición de equilibrio en un pequeño intervalo, los algoritmos realizan entre 100 y 300 iteraciones de promedio para lograr la convergencia. Esta aplicación del Aprendizaje Automático al control de sistemas complejos y caóticos refuerzan el enfoque de los algoritmos de aprendizaje en muchas campos donde se requiere lograr la autonomía del agente o sistema, frente a los controladores clásicos usados usualmente. Artículo completo aquí.
Leer más