Una introducción al algoritmo criptográfico para compartir secretos de Shamir

El uso compartido de secretos de Adi Shamir es un algoritmo criptográfico que permite a distintas partes compartir conjuntamente la propiedad de un único secreto mediante la tenencia de acciones . El secreto original solo se puede reconstruir utilizando un número mínimo de acciones, lo que permite que las diferentes partes cooperen sin la necesidad de confiar plenamente entre sí.

Problema de ejemplo

Para ilustrar, imaginemos que una familia de cuatro personas comparte una sola billetera Bitcoin. Esta billetera Bitcoin contiene una única clave privada que todos los miembros de la familia son copropietarios. Debido a que hay una sola clave, cualquiera de los miembros de la familia puede usar esa clave para gastar todos los Bitcoins.

La familia tiene un problema: si cada uno guarda una copia, entonces solo una de sus copias debe comprometerse para que le roben todas las monedas. Si solo uno de ellos se queda con la llave, entonces esa persona puede perderla o decidir traicionar a los demás miembros de la familia.

Afortunadamente, uno de los miembros de la familia también es criptógrafo. En lugar de compartir ingenuamente la clave original, usan SSS (intercambio secreto de Shamir). La familia crea cuatro acciones y establece un umbral de tres, con la clave de Bitcoin como secreto original. Ahora, su plan tiene las siguientes propiedades:

• No han almacenado la clave de bitcoin en un solo lugar, lo que dificulta el robo.
• Los miembros de la familia deben cooperar para gastar Bitcoin, un miembro de la familia no puede traicionar a los demás.
• Si un miembro de la familia muere o pierde su parte, los otros tres miembros aún pueden reconstruir la llave

Comprender el umbral

Cada esquema de intercambio de Shamir tiene un número total de acciones y un umbral. El umbral es el número de acciones requeridas para reconstruir el secreto original. Por ejemplo, con cinco acciones y un umbral de tres, solo necesita tres de las cinco acciones para calcular el secreto original.

Las Matemáticas - Líneas

Una de las propiedades matemáticas fundamentales utilizadas en el secreto compartido de Shamir es el hecho de que se necesitan k puntos para definir un polinomio de grado k - 1. Por ejemplo:

• Solo se puede trazar una línea entre dos puntos.
• Solo una parábola posible cruza por los mismos tres puntos
• Solo una curva cúbica pasa por los mismos cuatro puntos
• Se pueden trazar infinitas rectas por un mismo punto
• Se pueden dibujar un número infinito de parábolas a través de los mismos dos puntos

Las Matemáticas - Tutorial

Construyamos un esquema para compartir nuestro secreto 1954 ( S ) con 4 ( n ) acciones y un umbral de 3 ( k ) .

Primero, elegimos al azar k - 1 enteros positivos, por lo que en nuestro caso, 2 enteros positivos. Elegimos al azar 43 y 12.

Luego, construimos un polinomio de la forma

 y = a0 + a1*x + a2*x^2

Donde a0 es el secreto, y a1 y a2 son nuestros números enteros elegidos al azar. Nos quedamos con:

 y = 1954 + 43x + 12x^2

Luego, usamos esta fórmula para crear 4 puntos (acciones) que le damos a cada participante.

Compartir 1

(x, y) donde x = 1

y = 1954 + 43*1 + 12*1^2 = 2009

(1, 2009)

Compartir 2

(x, y) donde x = 2

y = 1954 + 43*2 + 12*2^2 = 2088

(2, 2088)

Compartir 3

(x, y) donde x = 3

y = 1954 + 43*3 + 12*3^2 = 2191

(3, 2191)

Compartir 4

(x, y) donde x = 4

y = 1954 + 43*4 + 12*4^2 = 2318

(4, 2318)

Reconstrucción

Cada participante en nuestro esquema ahora posee un punto (x,y) , que es una sola acción. Recuerda que fijamos nuestro umbral en 3 y que 3 puntos definen perfectamente una parábola (polinomio de grado 2). Eso significa que si usamos tres puntos, podemos dibujar una parábola y calcular a0 (el secreto). Supongamos que tenemos el control de las acciones 1, 2 y 4.

Paso 1 - Trazar los puntos (participaciones) que controlamos

Paso 2 - Dibuja la parábola correspondiente

Paso 3 - Encuentra el punto donde x=0 . Su valor y es el secreto

En nuestro caso, el secreto es 1954 .

En realidad no es tan simple. Necesitamos campos finitos.

Si bien el ejemplo que analizamos anteriormente es excelente para fines de demostración, en realidad no es muy seguro. Por cada acción que obtiene un atacante, en realidad obtiene más y más información sobre el secreto. Si bien dos puntos no describen perfectamente una parábola, aún filtran información crítica sobre la parábola.

La solución está en la aritmética de campos finitos . Al trazar la función en un campo finito de tamaño suficiente, el gráfico del polinomio se desarticula y se dispersa, lo que significa que el atacante no puede hacer conjeturas informadas sobre la ruta de la función subyacente.

adi shamir

Adi Shamir es un criptógrafo israelí famoso por Shamir's Secret Sharing, pero también es co-inventor del algoritmo RSA ampliamente utilizado sobre el que se basa la gran mayoría de Internet. Shamir nació en Tel Aviv y obtuvo una licenciatura en matemáticas de la universidad allí. Posteriormente obtuvo su maestría y doctorado. Licenciatura en Ciencias de la Computación del Instituto Weizmann en 1975 y 1977 respectivamente.