Al aterrizar en la isla me desperté y vi que mis hermanos Diego y María seguían dormidos.
“¡Que ya llegamos!” solté. Diego ni siquiera se inmutó. María abrió un ojo y me miró a los ojos. Todavía estábamos somnolientos cuando, al salir del aeropuerto, nos interceptaron dos policías.
“Ven conmigo, por favor”, nos dijeron.
Mis padres, más despiertos que nosotros, no parecían preocupados. Los policías nos explicaron que en la isla no había monedas de curso legal y que tendríamos que adaptarnos. solo podíamos usar CRIPTOMONEDAS.
“¿Esa cosa de bitcoin?” Yo pregunté.
Ellos asintieron. Nos dieron un folleto explicativo, que leímos con atención. Allí se describió el bitcoin como moneda digital, un tipo de dinero completamente virtual. Cada bitcoin es un archivo de computadora que se almacena en una aplicación de “billetera digital” en un dispositivo, como un teléfono móvil o una computadora.
Así que esto no será demasiado complicado, les dije a mis hermanos, las personas pueden enviar bitcoins a su billetera digital, por lo que es fácil enviar bitcoins a otras personas o comerciantes. Cada una de las transacciones se registra en una lista pública denominada cadena de bloque (cadena de bloquesen inglés).
Seguí leyendo, sorprendido, que gracias a esto se puede rastrear el historial de Bitcoins para evitar que las personas gasten monedas que no les pertenecen, haciendo copias o deshaciendo transacciones.
-Los cadena de bloques— mi hermano me explicó—es una estructura de datos. Una cadena de bloques, donde cada bloque contiene un conjunto de transacciones. Una especie de libro mayor distribuido que contiene todas las transacciones cronológicamente; una red formada por muchas, muchas computadoras comparten este libro.
“Y tantas computadoras, ¿cómo llegan a un acuerdo?” preguntó mi hermana.
-Buena pregunta. A ver que dice el folleto – respondí, ya un poco impaciente
Como leemos, cuando alguien quiere hacer una transacción, digamos comprar algo, envía la solicitud a la red informática. Allí, unas computadoras especiales llamadas mineros se encargan de recolectar las solicitudes (y hacer ciertas comprobaciones, como tener suficiente dinero para realizar la compra), e incorporarlas a la cadena de bloques.
“Pero si hay tantas computadoras, ¿quién se encarga de actualizar esa cadena de bloques?”. Yo pregunté.
Bueno, se propone un rompecabezas, que en realidad es hacer un cálculo muy simple con ciertos valores, para que el resultado sea un valor que parece elegido al azar. Una versión simplificada sería, por ejemplo, pedirles que calculen, para un p primo y dado un valor x, el cubo de x, y quedarse con el cálculo de la división entera del cubo de x por p. Es decir, si x = 20 y p = 541, el resultado sería 426, o si x = 21, con el mismo p, obtendríamos 64.
“¿Entonces solo cambias un número y el resultado es completamente diferente?” María preguntó sorprendida.
“Absolutamente”, observó Diego, “diferente e impredecible si no haces cuentas, por eso se llama prueba de trabajo. Vamos, te pondré a prueba, a ver quién es el primero en encontrar un valor de x que al cubo y dividido por 541, da un resto que termina en cero.
Mi hermana y yo desenfundamos el móvil. A los pocos minutos, anunció el resultado con una gran sonrisa.
“¡El 36!”
Mi hermano y yo comprobamos que tenía razón. 36 al cubo es 46656, y cuando se divide por 541, el resto es 130.
“Y solo te he pedido que termines en un cero, un 0”, continuó mi hermano. Imagínate si el objetivo es que con el mismo procedimiento acabe en dos ceros. quieres probar?
Nuestros dedos se deslizaron por la pantalla a gran velocidad. En menos de un minuto lo tenía
“¡El 481!” Grité desde los tejados. Mi estrategia de empezar en 540 y bajar no había salido tan mal.
Nuevamente, verificarlo tomó unos segundos, calcularlo tomó un poco más de trabajo. Ahora entendí por qué se llamaba prueba de trabajo, pero aún teníamos que entender cómo la cadena de bloques mantenía el dinero disponible para todos. En el folleto había una figura.
Cada rectángulo, decidimos, representaba un bloque. En cada uno, parecían reflejarse tres transacciones; por ejemplo, en el primer bloque interpretamos que D ha dado a M 5 monedas M y D ha pagado a R 3 y 4 monedas respectivamente. La etiqueta B podría ser algún tipo de nombre de bloque y el número junto a la etiqueta BA parecía referirse al bloque anterior.
—Oye!! ¿Te has dado cuenta de que son nuestras iniciales? – dijo mi hermana – Diego, Roger, María.
“Sí, tal vez mucha coincidencia”, le dije.
Dado que 541 desempeñó el papel de divisor p en los ejemplos del folleto, intentamos dividir 82821 entre 541 y, para nuestro deleite, vimos que salía 48. Ya sabíamos la relación cómo se construyó la etiqueta BA del segundo bloque, pero ¿de dónde salió B?
“¿Te has dado cuenta de que comienza con 48 y luego se concatenan los 3 valores de transacción?” observó mi hermana.
—Mmmmmmm… bueno ahora que lo mencionas, totalmente de acuerdo— respondí. Pero, ¿cómo se calculan los otros valores? Seguimos leyendo.
Allí estaba la prueba de trabajo. Jugando con los números del folleto, encontramos el rompecabezas: teníamos que calcular un número cuyas primeras cifras fueran 48421 tal que al cubo y el entero dividido por 541, las dos últimas cifras del resto fueran 00. Y resultó solo sale 4842176!
-Pues ya lo estaría- sentenció Diego. El minero que obtiene ese valor lo anuncia; los demás mineros (como lo está haciendo María) comprueban que es correcto y, si están de acuerdo, se añade el bloque a la cadena.
Fuimos a los policías y les explicamos que ya habíamos entendido. La mujer policía sonrió misteriosamente, nos dio un papel y preguntó, ¿cuánto dinero tienen cada uno?
Conseguimos pasar la prueba, y con ello una pequeña recompensa que gastamos en una pizza, que costó nada más y nada menos que 10.000 bitcoins. Era el año 2010. ¡Y pensar que en euros esa pizza ha llegado a valer más de 500 millones de euros!
¿Tú también podrías pasar la prueba?
Los desafíos criptográficos se publicarán cada 15 días. Los lectores pueden dejar sus soluciones y discutir el problema en los comentarios de esta página, por lo que se recomienda a cualquiera que quiera resolverlo por su cuenta que no lo lea hasta que haya descifrado el rompecabezas. También puede enviar sus respuestas por correo electrónico desafioscriptograficos@gmail.com. En cada nuevo reto publicaremos la solución del anterior, acompañada de un comentario con alguna idea original o inspiradora que hayamos recibido.
Vanessa Daza Fernández es profesora e investigadora del Departamento de Tecnologías de la Información y las Comunicaciones de la Universidad Pompeu Fabra de Barcelona.
La herramienta criptográfica que aparece en este desafío es esquemas de intercambio secreto: cómo compartir un valor secreto s entre diferentes participantes, dando a cada participante Pi un fragmento fiy para que sólo aquellos subconjuntos de participantes autorizados (que definen lo que se conoce como estructura de acceso).
En los dos primeros intercambios del secreto (el código del candado), los subconjuntos autorizados fueron todos aquellos con dos (o más) participantes. Esto se conoce como estructura de acceso de umbral (en este caso, el valor de umbral es 2). El criptógrafo israelí Adi Shamir (la S de RSA) propuso un manera segura de compartir secretos para una estructura de umbral de acceso t: se elige un polinomio secreto, f(x)la licenciatura t-1 tener secreto como un término independiente sa saber
f(x) = s + a1·x + a2·x² + a3·x³ + … + at-1·x elevado a t-1
Y el punto del plano cartesiano (i,f(i)) se asigna como un fragmento de un Pi participante.
El polinomio secreto f(x) tiene t coeficientes desconocidos, s, a1,…,at-1. La intuición (y las matemáticas) nos dice que para encontrar esos valores de t necesitamos conocer al menos t datos de ese polinomio, por ejemplo su evaluación en t puntos diferentes. Si hay menos de t puntos/evaluaciones/fragmentos, cualquier polinomio de grado t-1 es posible y, por lo tanto, el valor secreto s=f(0) es completamente indeterminado.
En el caso del umbral 2, el polinomio tiene grado 1 y corresponde a una recta, f(x) = s + a1·x. En la segunda distribución de fragmentos realizada por el Mago del Bosque, también correspondiente a una recta, tenemos que la recta que pasa por los puntos (1.15) y (2.17) es la recta de ecuación y = 2x + 13. Que La línea se cruza con el eje OY en el punto (0,13), por lo que el secreto en ese caso era 13.
En el caso del umbral 3, el polinomio secreto tendrá grado 2, su gráfica será una parábola: f(x) = s + a1 x + a2 x².
Para recuperar este polinomio (o parábola) secreto, se necesitan tres evaluaciones del polinomio, es decir, tres fragmentos de tres reinos diferentes, por ejemplo tomaremos los Reinos 1, 2 y 3. Con esa información, propondríamos un sistema de tres ecuaciones con tres incógnitas; las incógnitas son s, a1 y a2:
fragmento (1,22) -> 22 = f(1) = s + a1 · 1 + a2 · 1²= s + a1 + a2
fragmento (2,29) -> 29 = f(2) = s + a1 · 2 + a2 · 2²= s + 2 a1 + 4 a2
fragmento (3,32) -> 32 = f(3) = s + a1 · 3 + a2 · 3²= s + 3 a1 + 9 a2
La solución a este sistema de ecuaciones es s=11, a1=13, a2=-2, es decir que el polinomio secreto era f(x) = 11 + 13 x – 2 x², y por tanto el secreto que abrió el el candado era s=11.
A partir de ese día, como serían necesarios t=5 fragmentos (es decir, todos los fragmentos de los cinco reinos) para recuperar el secreto, una posibilidad sería utilizar un polinomio secreto de grado 4. Pero hay otra, más sencilla y posibilidad más eficiente (y que funciona siempre que el umbral t sea igual al número total de participantes): dado un secreto s para compartir, Forest Wizard simplemente tuvo que elegir cuatro fragmentos al azar, digamos f1, f2, f3 y f4 , y define el último como f5 = s – f1 – f2 – f3 – f4. Así, la suma de los cinco fragmentos dará el secreto, pero con 4 o menos fragmentos no se obtendrá información sobre el secreto.
Cuando se usan esos esquemas para compartir secretos en la vida real, los secretos y fragmentos no tienen tamaño libre, pero por ejemplo, el secreto se elige del conjunto de números enteros. {0,1,2,3,…,q-1} por un número primo qy trabajamos con operaciones modulares módulo q, es decir, q es igual a 0, q+3 igual a 3, etc. Así se consigue que el tamaño de los fragmentos f(yo) también se controla, ya que pertenecen al mismo conjunto {0,1,2,3,…,q-1} que el secreto compartido.
Muchos de nuestros lectores (como Javier, Ramiro o Joaquín) han resuelto rápidamente este reto… así que te hacemos una pregunta adicional: otra opción que habría tenido el Mago del Bosque para hacer realidad el deseo de los Reinos 1, 3 y 4. cierto que el subconjunto {2,5} no pudo recuperar el secreto, habría sido dividir el secreto para la estructura de acceso que contiene todos los subconjuntos del cardinal 2 excepto {2,5}. ¿Te atreves a encontrar la manera de compartir el secreto en ese caso?
PD: Aún tenemos que resolver el reto criptográfico musical que nos envía Salva Fuster en los comentarios a uno de estos retos. Ya hemos recibido respuesta en nuestro correo desafioscriptograficos@gmail.com. Te animamos a que tú también lo resuelvas. En el próximo reto publicaremos la solución que nos ha enviado su autor.
Puedes seguir EL PAÍS TECNOLOGÍA en Facebook y Gorjeo o regístrate aquí para recibir nuestros boletín semanal.
Leave a Reply