Confiar pero verificar. Esa expresión captura la tensión entre confiar en los demás y al mismo tiempo querer mantener cierto nivel de control sobre una situación. El matemático Adi Shamir debe haber pensado en este desafío cuando desarrolló lo que hoy se conoce como “el intercambio secreto de Shamir”, un algoritmo que lleva su nombre.
Para entenderlo, el siguiente enigma puede ayudar: supongamos que una anciana quiere legar el contenido de su caja fuerte, asegurada con una cerradura de combinación, a sus cinco hijos, pero sospecha de cada uno de ellos. Teme que si le revela el código a solo uno, éste se llevará el contenido. Por eso quiere darle a cada hijo una pista para que sólo los cinco que trabajan juntos puedan abrir la caja fuerte. ¿Cómo debe proceder la mujer?
La tarea puede parecer sencilla. Por ejemplo, si la cerradura de combinación requiriera un código de cinco dígitos, podría darle a cada hijo un número para que pudieran abrirla juntos. Pero en ese escenario, si tres hijos se unieran, probablemente podrían pasar por alto a sus otros dos hermanos. A tres aliados les faltan sólo dos números para completar el código, por lo que podrían probar rápidamente las posibles combinaciones de números para llegar al codiciado contenido.
Por lo tanto, la mujer busca una manera de distribuir información que sólo pueda utilizarse si los cinco trabajan juntos. Si dos, tres o cuatro de los cinco hijos se juntan, el contenido informativo combinado debe ser inútil. Y ese requisito hace que la tarea sea mucho más compleja.
Pero en 1979 este desafío no desanimó a Shamir. Dos años antes había desarrollado el llamado “algoritmo RSA” junto con Ron Rivest y Leonard Adleman. fue el primero algoritmo de cifrado asimétrico ser ampliamente adoptado y todavía se utiliza hoy en día.
El intercambio secreto de Shamir en acción
Para comprender el método de Shamir para compartir secretos, es útil observar un ejemplo numérico concreto. Supongamos que el código secreto de la mujer es 43953 y, en aras de la simplicidad, supongamos que sólo tiene dos hijos. (Más adelante llegaremos a la situación con cinco hijos).
Si la mujer le hubiera confiado a un hijo el “439” y al otro el “953”, les habría dado a ambos la misma cantidad de información. Ahora, como se explicó anteriormente, cada uno de los hijos podría intentar adivinar los dos dígitos que faltan. Sólo tendrían que probar un máximo de 100 combinaciones cada uno para abrir la caja fuerte.
Por tanto, Shamir necesitaba una solución diferente. Sería mejor si cada hijo recibiera información que a primera vista no tuviera nada que ver con la solución. Pero si junta las dos piezas de información, debería poder deducir la combinación numérica 43953. Y existe una forma elegante y sencilla de hacerlo con la ayuda de una ecuación lineal.
Cada línea recta está definida únicamente por dos puntos. Shamir se dio cuenta de que el número secreto se puede codificar en línea recta: por ejemplo, como la altura a la que se cruza con el eje y. Si les das a los dos hijos las coordenadas de un punto de cada uno en la línea recta, solo podrán determinar juntos el número 43953. Uno de los hijos no puede hacer nada con un solo punto: hay infinidad de rectas que pasan por un solo punto.
La mujer podría, por ejemplo, elegir la ecuación de la recta y = 5X + 43953 y dale al hijo mayor las coordenadas de un punto PAG1 (33503, 211468) y el otro hijo las coordenadas de un segundo punto, PAG2 (85395, 470928). Incluso si los dos hijos son malos en matemáticas, pueden simplemente marcar los dos puntos en el plano, conectarlos con una regla y luego leer el punto en el que la línea recta corta el eje y para encontrar la solución a la caja fuerte.
Entonces el problema está resuelto para dos hijos. Si la mujer tiene tres hijos, podría proceder de manera similar. En este caso, sin embargo, no elegiría una línea recta sino una parábola para ocultar el código.
Por ejemplo, la mujer puede elegir la función cuadrática. y = 5X2 + 10X + 43953 y dale a cada uno de sus hijos un punto en la parábola. Nuevamente, el punto de intersección con el eje y corresponde a la solución deseada: 43953. Dos de los hijos no pueden conspirar contra el tercero porque un número infinito de parábolas pueden pasar por dos puntos; Los dos hijos necesitan la ayuda de su hermano para encontrar el punto de intersección con el eje y y así el código de la caja fuerte.
El principio puede generalizarse para cualquier número de partes: una mujer con cuatro hijos puede resolver una ecuación del tipo y = hacha3 + bx2 + cx + 43953. (Debido a que 3 es el exponente más alto en esta ecuación, se llama ecuación polinómica de tercer grado). Una mujer con cinco hijos usa una ecuación polinómica de cuarto grado (como y = hacha4 + bx3 + cx2 + dx + 43953), y así sucesivamente. El principio se basa en la llamada interpolación polinómica: en general, norte Se requieren + 1 puntos para determinar de forma única un polinomio de la nortedécimo grado.
La mujer también puede dar acceso a la caja fuerte a sus hijos de dos en dos. En este caso, ella confía en que los hijos se controlen entre sí, de modo que dos de cada cinco personas deben estar presentes para abrir la caja fuerte. Para ello, la mujer puede volver a elegir una línea recta como base y marcar en ella cinco puntos seleccionados al azar. Al darle un punto a cada hijo, se asegura de que dos de ellos puedan determinar el código, independientemente de cuáles de los hijos coincidan.
Pero hay un problema. Volvamos al escenario de los cinco hijos. Si cuatro de ellos conspiran contra un hermano, pueden utilizar los cuatro puntos para resolver la ecuación de cuarto grado en la medida de lo posible. Por supuesto, no pueden leer el código directamente desde él. Al final les queda una ecuación con dos incógnitas: un parámetro a y el codigo C (que en nuestro ejemplo es 43953, pero los hijos no lo saben).
Los cuatro hijos saben que C Sin embargo, debe ser un número entero. Y si, por ejemplo, la mujer siempre les ha dado coordenadas enteras para los puntos de la curva, entonces pueden suponer que a Probablemente también tenga un valor entero. Esto restringe considerablemente el abanico de posibilidades. Los hermanos pueden usar un programa de computadora para probar diferentes soluciones y luego determinar el código correcto.
En un rango numérico diferente
Para evitar tal escenario, Shamir tenía otro truco bajo la manga: en lugar de calcular con los números reales habituales, se limitó a un espacio numérico más pequeño: un campo finito. En este sistema numérico, las cuatro operaciones aritméticas básicas (suma, multiplicación, resta y división) se pueden aplicar como de costumbre. Sin embargo, en lugar de un número infinito de números, este espacio numérico sólo contiene un número finito de ellos.
Aunque pueda parecer desconocido, utilizamos campos finitos todos los días (por ejemplo, cada vez que miramos el reloj). Si sólo nos fijamos en las horas, el rango numérico comprende 12 o 24 números. Pero aún así calculamos en este espacio limitado: si son las 11 de la noche y alguien dice que la panadería abre en siete horas, entonces está claro que se refiere a las seis.
En el intercambio secreto de Shamir, también se elige un rango de números restringido, pero el límite superior suele ser un número primo grande. Si se elige el espacio numérico de esta manera, la gráfica de un polinomio ya no corresponde a una curva continua sino a puntos distribuidos aleatoriamente en el plano.
Al limitar los cálculos de la mujer a ese rango numérico, es prácticamente imposible que los hermanos conspiren entre sí. Para descubrir el código numérico correcto, tienen que trabajar juntos.
Este artículo apareció originalmente en Spektrum der Wissenschaft y fue reproducido con autorización.