Los esquemas de Secret Sharing se utilizan en la distribución de un valor secreto entre múltiples participantes ( accionistas ) dividiendo el secreto en fragmentos ( acciones ) . Esto se hace de una manera que evita que un solo accionista tenga ningún conocimiento útil del secreto original. La única forma de recuperar el secreto original es combinar las acciones, distribuidas entre los participantes. Por lo tanto, el control del secreto está repartido . Estos esquemas son ejemplos de Threshold Cryptosystems , que involucran la división de secretos entre múltiples partes de tal manera que varias partes (más de un umbralnúmero) debe cooperar para reconstruir el secreto.
Fig. 1 : Representación del uso compartido de secretos entre n participantes
En general, un secreto se puede dividir en n acciones (para n accionistas), de las cuales se requiere un mínimo de t , (t < n) acciones para una reconstrucción exitosa. Tal esquema se denomina esquema de compartición (t, n). De los n participantes, cualquier subconjunto de accionistas, de tamaño mayor o igual a t , puede regenerar el secreto. Es importante destacar que, incluso con cualquier k (k < t) acciones, no se aprende ninguna información nueva sobre el secreto original.
Compartir el secreto de Shamir
Shamir Secret Sharing ( SSS ) es una de las implementaciones más populares de un esquema de intercambio de secretos creado por Adi Shamir , un famoso criptógrafo israelí, quien también contribuyó a la invención del algoritmo RSA. SSS permite que el secreto se divida en un número arbitrario de acciones y permite un umbral arbitrario (siempre que sea menor que el total de participantes). SSS se basa en el concepto matemático de interpolación de polinomios que establece que un polinomio de grado t-1 se puede reconstruir a partir del conocimiento de t o más puntos, que se sabe que se encuentran en la curva.
Por ejemplo, para reconstruir una curva de grado 1 (una línea recta), necesitamos al menos 2 puntos que se encuentren en la línea. Por el contrario, es matemáticamente inviable reconstruir una curva si el número de puntos únicos disponibles es menor que (grado de curva + 1). Uno puede imaginar tener infinitas líneas rectas posibles que podrían formarse como resultado de un solo punto en el espacio 2D.
Motivación detrás de SSS
El concepto de interpolación de polinomios se puede aplicar para producir un esquema de intercambio de secretos incrustando el secreto en el polinomio. Un polinomio general de grado p se puede expresar de la siguiente manera:
En la expresión de P(x), los valores a_{1}, a_{2}, a_{3}, …, a_{n} representan los coeficientes del polinomio. Por lo tanto, la construcción de un polinomio requiere la selección de estos coeficientes. Tenga en cuenta que en realidad no se sustituyen valores por x; cada término en el polinomio actúa como un «marcador de posición» para almacenar los valores de los coeficientes.
Una vez que se genera el polinomio, esencialmente podemos representar la curva con solo p+1 puntos que se encuentran en la curva. Esto se sigue del principio de interpolación polinomial. Por ejemplo, una curva de grado 4 se puede reconstruir si tenemos acceso a al menos 5 puntos únicos que se encuentran sobre ella. Para ello, podemos ejecutar la interpolación de Lagrange o cualquier otro mecanismo de interpolación similar.
Fig. 2: Ejemplo de uso de interpolación polinomial para reconstruir una curva
En consecuencia, si ocultamos el valor secreto en un polinomio de este tipo y usamos varios puntos de la curva como acciones, llegamos a un esquema de reparto secreto. Más precisamente, para establecer un esquema de intercambio secreto (t, n) , podemos construir un polinomio de grado t-1 y seleccionar n puntos en la curva como acciones, de modo que el polinomio solo se regenerará si se agrupan t o más acciones. El valor secreto ( s ) está oculto en el término constante del polinomio (coeficiente del término de 0 grados o la intersección y de la curva) que solo se puede obtener después de la reconstrucción exitosa de la curva.
Algoritmo utilizado
Shamir’s Secret Sharing utiliza el principio de interpolación polinomial para realizar el umbral de compartición en las siguientes dos fases:
Fase I: Generación de recursos compartidos
Esta fase implica la configuración del sistema, así como la generación de los recursos compartidos.
- Decida los valores para el número de participantes (n) y el umbral (t) para asegurar algún valor secreto (s)
- Construya un polinomio aleatorio, P(x) , con grado t-1 eligiendo coeficientes aleatorios del polinomio. Establezca el término constante en el polinomio (coeficiente del término de grado cero) para que sea igual al valor secreto s
- Para generar las n participaciones, elija aleatoriamente n puntos que se encuentran en el polinomio P(x)
- Distribuya las coordenadas escogidas en el paso anterior entre los participantes. Estos actúan como las acciones en el sistema.
Fase II: Reconstrucción del secreto
Para la reconstrucción del secreto, se requiere que un mínimo de t participantes pongan en común sus acciones.
- Recoger t o más acciones
- Utilice un algoritmo de interpolación para reconstruir el polinomio, P'(x) , a partir de las acciones. La interpolación de Lagrange es un ejemplo de dicho algoritmo .
- Determine el valor del polinomio reconstruido para x = 0 , es decir, calcule P'(0) . Este valor revela el término constante del polinomio que resulta ser el secreto original. Así se reconstruye el secreto.
A continuación se muestra la implementación.
Python3
import random
from math import ceil
from decimal import Decimal
FIELD_SIZE = 10**5
def reconstruct_secret(shares):
"""
Combines individual shares (points on graph)
using Lagranges interpolation.
`shares` is a list of points (x, y) belonging to a
polynomial with a constant of our key.
"""
sums = 0
prod_arr = []
for j, share_j in enumerate(shares):
xj, yj = share_j
prod = Decimal(1)
for i, share_i in enumerate(shares):
xi, _ = share_i
if i != j:
prod *= Decimal(Decimal(xi)/(xi-xj))
prod *= yj
sums += Decimal(prod)
return int(round(Decimal(sums), 0))
def polynom(x, coefficients):
"""
This generates a single point on the graph of given polynomial
in `x`. The polynomial is given by the list of `coefficients`.
"""
point = 0
# Loop through reversed list, so that indices from enumerate match the
# actual coefficient indices
for coefficient_index, coefficient_value in enumerate(coefficients[::-1]):
point += x ** coefficient_index * coefficient_value
return point
def coeff(t, secret):
"""
Randomly generate a list of coefficients for a polynomial with
degree of `t` - 1, whose constant is `secret`.
For example with a 3rd degree coefficient like this:
3x^3 + 4x^2 + 18x + 554
554 is the secret, and the polynomial degree + 1 is
how many points are needed to recover this secret.
(in this case it's 4 points).
"""
coeff = [random.randrange(0, FIELD_SIZE) for _ in range(t - 1)]
coeff.append(secret)
return coeff
def generate_shares(n, m, secret):
"""
Split given `secret` into `n` shares with minimum threshold
of `m` shares to recover this `secret`, using SSS algorithm.
"""
coefficients = coeff(m, secret)
shares = []
for i in range(1, n+1):
x = random.randrange(1, FIELD_SIZE)
shares.append((x, polynom(x, coefficients)))
return shares
# Driver code
if __name__ == '__main__':
# (3,5) sharing scheme
t, n = 3, 5
secret = 1234
print(f'Original Secret: {secret}')
# Phase I: Generation of shares
shares = generate_shares(n, t, secret)
print(f'Shares: {", ".join(str(share) for share in shares)}')
# Phase II: Secret Reconstruction
# Picking t shares randomly for
# reconstruction
pool = random.sample(shares, t)
print(f'Combining shares: {", ".join(str(share) for share in pool)}')
print(f'Reconstructed secret: {reconstruct_secret(pool)}')
Producción:
Original Secret: 1234 Shares: (79761, 4753361900938), (67842, 3439017561016), (42323, 1338629004828), (68237, 3479175081966), (32818, 804981007208) Combining shares: (32818, 804981007208), (79761, 4753361900938), (68237, 3479175081966) Reconstructed secret: 1234
Aplicaciones prácticas
Los esquemas de intercambio de secretos se utilizan ampliamente en criptosistemas donde se requiere que la confianza se distribuya en lugar de centralizarse. Los ejemplos destacados de escenarios del mundo real en los que se utiliza el uso compartido de secretos incluyen:
- Firmas basadas en umbrales para Bitcoin
- Cómputo seguro de múltiples partes
- Aprendizaje automático privado con computación multiparte
- Gestión de Contraseñas