Primeros pasos con el criptosistema SRVB

Introducción

La seguridad de la información es un campo de conocimiento fascinante que puede involucrar cualquier cosa, desde la informática teórica hasta la ingeniería de software, e incluso observar la psicología del error humano.

La criptografía es ahora uno de los muchos héroes tecnológicos anónimos de nuestra vida diaria. Las redes sociales, la banca web, la inteligencia militar y cualquier otro sistema de información que trate con información confidencial dependen en gran medida de la criptografía. La criptografía nos permite tener privacidad, que algunos consideran el 12º derecho humano.

Este artículo le brindará una introducción a los principios detrás de los criptosistemas de clave pública y le presentará Santana Rocha-Villas Boas (SRVB), un criptosistema desarrollado por el autor del artículo y el Prof. Daniel Santana Rocha. En el momento de escribir este artículo, los autores del algoritmo están preparando una campaña que incluye una recompensa económica para cualquiera que logre descifrar el código. Dado que el artículo cubrirá la funcionalidad del algoritmo en detalle, este es el mejor lugar para comenzar la búsqueda del premio. Hay más información disponible en el sitio de SRVB.

¿Qué es un criptosistema?

La criptografía es cualquier método para obstaculizar la interpretabilidad de un mensaje, al mismo tiempo que permite una forma factible de interpretarlo siempre que se proporcione una instrucción específica, que suele ser la llamada "clave". Si bien esta es una definición muy amplia que abarca incluso las técnicas más antiguas, vale la pena mencionar que esto no cubre todo lo relacionado con la seguridad de la información.

Se espera que la carrera tecnológica entre los métodos de encriptación y las formas de descifrarlos nunca tenga un ganador definitivo. Se espera que cada nueva generación eleve los estándares de seguridad de la información y criptoanálisis, que es el conjunto de técnicas para descifrar/romper mensajes cifrados de forma sistemática, es decir, eludir la seguridad o el cifrado.

Para que un criptosistema (técnica dada de criptografía) sea considerado seguro por sus usuarios, debe recibir la aprobación de la comunidad internacional de expertos y, por lo tanto, ser conocido públicamente, lo que se conoce como el principio de Kerckhoff. Sin embargo, esta misma condición expone el sistema al escrutinio de la comunidad de criptoanálisis del mundo, que intentará idear formas de romper sistemáticamente las encriptaciones.

¿Cómo se puede hacer que un proceso de encriptación determinado sea lo suficientemente secreto para que solo los agentes previstos puedan descifrarlo, y al mismo tiempo lo suficientemente público para que la comunidad de criptoanálisis del mundo pueda dar fe de su solidez? La respuesta es un componente que es un elemento clave de la criptología: la clave. Una clave de un criptosistema es un parámetro para los algoritmos de cifrado o descifrado, o ambos. Al mantener los parámetros en secreto, en lugar de la familia de algoritmos, se pueden lograr ambos requisitos contradictorios. Siempre que la familia de parámetros sea lo suficientemente grande (posiblemente infinita) y se pueda demostrar que cada uno de sus componentes tiene las propiedades adecuadas, no será factible que los atacantes determinen los parámetros simplemente por inspección.

Finalmente, para que una clave funcione de manera efectiva, debe ser fácil de producir pero casi imposible de adivinar. Con el poder de cómputo de las computadoras de hoy, una computadora necesitaría menos tiempo para descifrar una clave generada por un humano de lo que cualquier humano necesitaría para imaginarla, además del hecho de que no es rentable generar claves de esa manera de todos modos. Por eso, las claves tienden a ser generadas por un algoritmo.

Un algoritmo de generación de claves no debe crear una salida predecible/reproducible como resultado de un uso típico. Dado que los algoritmos realizan procedimientos sin ningún proceso inteligente, la pregunta es cómo se puede hacer esto. La respuesta es convertir los algoritmos de generación de claves en mapas que transformen una gran cantidad de bits verdaderamente aleatorios en claves. Se pueden adquirir bits verdaderamente aleatorios del sistema operativo, que los genera a partir de la incertidumbre en el universo. Algunas fuentes serían el movimiento del mouse, las latencias de los paquetes de red o incluso el hardware dedicado, según la aplicación.

Criptosistemas de clave pública

Prepárate para sorprenderte una vez más, porque ahora introduciremos un concepto que aparentemente contradice lo que acabamos de decir: la clave pública.

Hasta ahora, hemos visto la creación de comunicación segura después de que los parámetros secretos (claves) se hayan intercambiado de forma segura, pero el problema de intercambiar los parámetros a través de un canal público persiste. Ahora mismo, presentaremos un concepto que resuelve un problema un poco más palpable: la creación de un canal seguro.

Supongamos que Alice está trabajando con Bob y quieren mantener seguras sus interacciones laborales mediante el cifrado. Pueden reunirse e intercambiar sus claves de cifrado entregándose una unidad flash USB con sus claves. Pero, ¿y si Alice y Bob están ubicados en diferentes continentes? ¿Cómo establecer un canal seguro donde no lo hay?

Enviar claves por correo electrónico no sería una opción, ya que su competidor Eve puede interceptar el intercambio y usar sus claves para leer todos los datos cifrados después. Si tuvieran cualquier otro canal digital a través del cual pudieran transmitir estos datos confidenciales, entonces no necesitarían encriptación y, por lo tanto, claves, en primer lugar. El envío de la clave por correo físico también podría ser interceptado, ya que, para empezar, requiere el intercambio de información confidencial. Enviar una clave esteganográfica escondida dentro de otros datos sería inteligente, pero inútil a menos que el remitente esté seguro de que el destinatario, y solo el destinatario, conoce la existencia de dicho mensaje y sabe cómo extraerlo. Da la casualidad de que la conciencia de la existencia de un mensaje junto con la descripción de cómo extraer la clave de los datos es un tipo de clave en sí mismo, lo que nos lleva de vuelta al punto de partida.

La solución es idear un criptosistema para el cual el parámetro de encriptación no sea suficiente para interpretar el mensaje original de manera factible ^[1] , y guardar para usted el parámetro que permitiría interpretar el mensaje. Llamamos a ese parámetro la clave privada. Con base en la clave privada, es factible generar un conjunto de parámetros para una herramienta de encriptación sin que esos nuevos parámetros por sí mismos puedan revelar cuál es la clave privada. Ese conjunto de parámetros se puede compartir públicamente, porque no es tan importante quién puede cifrar algo, siempre que solo una persona pueda descifrarlo. Dado que este conjunto de parámetros para la herramienta de cifrado se puede hacer público, se denomina clave pública.

La criptografía en la que las claves de cifrado y descifrado difieren, y la primera no se puede utilizar de manera factible para deducir la segunda, se denomina criptografía asimétrica, mientras que la criptografía simétrica es lo que tenemos cuando esas claves son las mismas o se deducen fácilmente unas de otras.

Alice le envía a Bob su clave pública, que solo se puede usar para cifrar cosas que solo ella puede descifrar (con su clave privada, que mantiene en privado) y, a la inversa, Bob le envía a Alice su clave pública, que solo se puede usar para cifrar cosas. que solo él puede descifrar (por medio de su clave privada, que también guarda en privado). Pero, ¿cómo es posible que se publique un parámetro para un algoritmo de cifrado del que no se pueda deducir el algoritmo inverso exacto?

La respuesta se encuentra en el campo de las matemáticas que está más relacionado con la programación, la teoría de la complejidad computacional. Cualquiera que haya profundizado lo suficiente en los problemas matemáticos ha oído hablar de transformaciones que son fáciles de hacer de una manera, pero difíciles de hacer a la inversa. En cálculo, por ejemplo, encontrar una derivada de libro de texto suele ser un ejercicio sencillo, mientras que hacer lo contrario (como resolver cualquier integral ligeramente no trivial o ODE o PDE física de libro de texto, por ejemplo) requiere un proceso más investigativo de primero hipotetizar familias de funciones que están garantizados (o al menos plausibles) para contener la(s) solución(es) y resolver problemas inversos para encontrar soluciones de estas familias.

Un ejemplo que en realidad se utiliza en el criptosistema RSA es multiplicar números primos grandes en lugar de factorizar el producto resultante sin conocer los factores. Hacer la multiplicación es trivial, pero la factorización requiere que adivines al azar ^[2] los factores primos, que tienen cientos de dígitos. Una propiedad importante de la operación es la necesidad de escalar bien. Agregar unos pocos dígitos al tamaño de los números primos en RSA dará como resultado una clave que requiere miles de veces más operaciones para descifrar mientras agrega un pequeño aumento en la complejidad del proceso de cifrado. En términos muy generales, el producto de números primos se usa para cifrar, mientras que el par de factores primos se usa para descifrar.

Con todo esto en mente, echemos un vistazo a cómo funciona el criptosistema SRVB.

El algoritmo subyacente - Analizando SRVB

El problema de la suma de subconjuntos

Como cualquier otro criptosistema de clave pública, SRVB se basa en la dificultad de resolver un problema particular que es fácil de producir. En el caso de SRVB, es el problema de la suma de subconjuntos, que se puede describir de la siguiente manera:

Dados los enteros $w$ y $v_1, \cdot \cdot \cdot, v_N \in Z$, encuentre la secuencia $b_1, \cdot \cdot \cdot, b_N \in {0,1}$, tal que $ \sum_ {i = 1}^{N} v_i b_i = w $.

Claramente, este problema se puede producir seleccionando aleatoriamente N enteros, eligiendo aleatoriamente un subconjunto de ellos y sumando este subconjunto, lo cual es trivial.

Una búsqueda de fuerza bruta tendría una complejidad de $ O( N * 2^N ) $, calculando para cada combinación de valores de los $b$s. Horowitz y Sahni dieron un enfoque más eficiente en 1972, con una complejidad de $ O ( N * 2 ^ {N / 2} ) $. El problema es al menos igual de difícil si reemplazamos $b$s y $w$ con vectores enteros de $k$-dimensionales. Sin embargo, el ámbito donde se va a sostener este problema más difícil también debe tener un isomorfismo con un anillo donde se lleva a cabo una versión más fácil del mismo problema, como veremos a continuación. Por esta razón, SRVB explota el problema de la suma de subconjuntos dentro de los enteros gaussianos, donde $ k = 2 $.

Hay un caso especial en el que este problema se vuelve fácil de calcular mediante el uso de un algoritmo codicioso. Si ordenamos una secuencia con factores de escala $ v_1, \cdot \cdot \cdot, v_N $ en la que cada entero de la secuencia es mayor que la suma de todos los enteros anteriores ($ \forall i , \sum_{j= 1}^{i-1} v_j < v_i $), uno podría usar un enfoque codicioso para encontrar la secuencia b en tiempo lineal. Una sucesión con las propiedades descritas se llama sucesión supercreciente .

Aquí hay una descripción simple de la solución codiciosa para este caso:

1. Comience con $ i = N $, el factor actualmente observado, y $ w' = w $, el resto de $w$

2. Si el factor de escala actual es demasiado grande para caber en lo que queda de $w$, es decir, $ v_i > w'$, establezca $b_i = 0$ y continúe con el siguiente paso. De lo contrario, sabemos que el factor de escala debe estar en la secuencia (ya que el resto de los factores es menor que $v_i$) y establecemos $b_i = 1$.

3. $ w' \Leftarrow w' - v_i * b_i$, $i \Leftarrow i - 1$. Si $i > 0$, regrese al paso 2.

4. Verifique que, ahora, $w' == 0$, de lo contrario, el problema estaba dañado

Esto funciona porque sabemos que todos los multiplicadores más pequeños que el actualmente observado no pueden cubrir colectivamente la mayor parte de la (sub)suma $ w' $ como lo hace el multiplicador actual. Entonces, si la suma restante es mayor que el factor actual, sabemos con certeza que todos los siguientes factores juntos no lograrán sumar sin la ayuda del factor actual. Por otro lado, como todos los multiplicadores son positivos, si el factor actual $v_i$ es mayor que la suma restante $w'$, sumar cualquier otro factor haría que el resultado superara aún más a $w'$.

Configuremos una notación para el resto del artículo. Elegimos $ v_1, \cdot \cdot \cdot, v_n $ y $w$ para ser los factores y la suma de la secuencia supercreciente, mientras que $ u_1, \cdot \cdot \cdot, u_n $ y $y$ serán los públicamente parámetros disponibles que se proporcionan para recuperar $ b_1, \cdot \cdot \cdot, b_n $.

Con una secuencia $ u_1, \cdot \cdot \cdot, u_n $ seleccionada para que no supercreciente, y el número $y$ disponible públicamente, no se proporciona suficiente información públicamente para recuperar la secuencia $ b_1, \cdot \cdot \cdot , b_n $. Sin embargo, si hay una secuencia supercreciente $ v_1, \cdot \cdot \cdot, v_n $ que podría tomar el lugar de la secuencia $ u_1, \cdot \cdot \cdot, u_n $, se podría usar esta secuencia para resolver el problema con un enfoque codicioso.

A continuación, mostraremos cómo funciona.

Uso de sumas de subconjuntos en un criptosistema anterior

En 1978, Ralph Merkle y Martin Helman idearon una forma de explotar esos dos paradigmas de mochila y la linealidad de la operación del módulo para construir la conexión entre las dos secuencias descritas en la sección anterior, concibiendo así un criptosistema de clave pública. La idea era transformar la mochila fácil (la que consiste en el vector supercreciente de los números enteros) en la dura (la que carece de esta propiedad) mediante una operación lineal (el módulo) con operandos secretos. La transformación consiste en multiplicar cada $v_i$ por un $\theta$ y tomar el resto de este producto por un $\alpha$, donde $\alpha \gt \sum_{i=1}^N v_i$ y $\gcd (\alpha, \theta) = 1$ (dos restricciones que pronto serán justificadas). El resultado, la secuencia $u_1, \ldots, u_N$, ya no es supercreciente y puede considerarse una mochila dura .

Se le daría una permutación aleatoria de la secuencia $u_1, \ldots, u_N$ a la parte que quiere cifrar y enviarnos un mensaje. La permutación se realiza para que a un tercero le resulte más difícil adivinar cuál es la secuencia supercreciente original. Los bloques de bits de un mensaje se utilizan como coeficientes $b_1, \ldots, b_N$. El cifrado se realiza multiplicando la secuencia de claves con esta secuencia de coeficientes y sumando las multiplicaciones en un resultado, que etiquetaremos como $y$. Sólo el propietario de la clave privada puede transformar $y$ en los $w$ correspondientes que se obtendrían si estos mismos bloques $b_1, \ldots, b_N$ se hubieran multiplicado con los enteros fáciles (la secuencia $v_1, \ldots , v_N$). Eso se hace mediante la multiplicación de $y$ por $\theta^{-1}$, el inverso multiplicativo de $\theta$ módulo $\alpha$ (cuya existencia depende de esa condición de $\gcd(\alpha, \ theta) = 1$). En otras palabras, $(\theta * \theta^{-1}) \bmod \alpha = 1$. Después de eso, calculamos $w = (y * \theta^{-1}) \bmod a$. La razón por la que se garantiza que esto funcione es la linealidad del módulo , es decir, que la combinación lineal de los residuos es igual al resto de la combinación lineal.

Si aplicamos consecutivamente la definición de $u$, el anillo del cociente y la propiedad de linealidad del operador módulo, vemos la correspondencia:

$ \begin{align} y & = \sum_{i=1}^N b_iu_i \newline & = \sum_{i=1}^N b_i (v_i * \theta \bmod \alpha) \newline & = \sum_{ i=1}^N b_i * v_i * \theta \bmod \alpha \newline & = \left[ \sum_{i=1}^N b_i * v_i * \theta \right] \bmod \alpha \newline & = \ izquierda[ \sum_{i=1}^N b_i * v_i \right] * \theta \bmod \alpha \newline & = w * \theta \bmod \alpha \end{align} $

Y así la suma fácil $w$ se puede recuperar multiplicando ambos lados con $\theta^{-1}$ y tomando el módulo con $\alpha$. Para hacerlo, uno tiene que saber tanto $\alpha$ como $\theta$ (que permiten calcular fácilmente $\theta^{-1}$), que deben mantenerse privados como partes de la clave privada.

Una sola restricción, $\alpha \gt \sum_{i=1}^N v_i$, se dejó sin justificar y aquí va la explicación: la igualdad entre la segunda y la tercera línea consiste en una igualdad entre las clases de residuos del cociente anillo de enteros módulo $\alpha$. En otras palabras, solo establece la igualdad del resto de los miembros cuando se divide por $\alpha$, lo que no es una condición suficiente para la igualdad de los miembros mismos . Como resultado, más de un vector de valores $b$ podría mapearse en un solo $y$, lo que se evita limitando la subsuma máxima posible (es decir, la suma de todas las parcelas $v_i$) $w_{max}$ a ser menor que $\alpha$ para cualquier combinación de valores de $b$.

Al igual que cualquier otra instancia de la vida diaria, el conocimiento completo de todas las hipótesis es a menudo imposible y nunca fácil. Como resultado, tenemos que confiar en la intuición matemática al juzgar si un criptosistema es seguro de usar, lo que no nos brinda garantías reales. Seis años después de su creación, el criptosistema MH se rompió con un ataque de A. Shamir. Hubo varios intentos más de revivir MH, muchos de los cuales también fracasaron.

Criptosistema Santana Rocha - Villas Boas (SRVB)

En 2016, después de algunas lluvias de ideas con el autor de este artículo sobre las posibilidades ^[3] de un criptosistema inspirado de manera diferente, Daniel Santana Rocha tuvo la idea de sustituir $\theta$ y $\alpha$ por enteros gaussianos. Por razones más técnicas, este enfoque conduce a la resistencia contra el mencionado ataque de Shamir.

También concibió un bloque de bits que consiste en muchos pasos de la combinación lineal descrita anteriormente de una mochila dura . En cada uno de ellos, al final de la secuencia se añadiría un nuevo entero (gaussiano), equivalente a uno, superior a la suma de todos los anteriores, mientras que se descartaría el menor actualmente.

Se aplica una restricción diferente pero elegantemente análoga a $\alpha$, que ahora es un entero gaussiano. Requerimos $w_{max} \leq \vert\alpha\vert^2$. El motivo es muy difícil de formalizar, pero afortunadamente se puede intuir fácilmente a partir de una elegante descripción:

Imagina una red cuadrada en el plano de los números complejos, cuyo lado es una hipotenusa de un triángulo rectángulo de catetos ayb, paralelo a los ejes real e imaginario. A continuación se muestra un ejemplo de dicha red. Los enteros guassianos módulo $\alpha = a + bi$ pueden representarse mediante puntos ubicados dentro de dicha red. Dentro de tal retícula hay $\vert\alpha\vert^2$ puntos distintos. Si elegimos un $\alpha$ lo suficientemente grande, podemos encajar todas las combinaciones lineales de la mochila fácil.

Esta es la representación gráfica del isomorfismo $f : Z/n \rightarrow Z[i]/(\alpha)$, donde $n = 13$ y $\alpha = a + bi = 3 + 2i$ (nótese que $ n$ y $\alpha$ de hecho satisfacen $n = \vert \alpha \vert ^ 2 = a^2 + b^2 $ según sea necesario). Los puntos representan los enteros gaussianos, es decir, los números complejos $a + bi$, donde $a$ y $b$ son números enteros. Como es habitual, el eje horizontal representa la parte real, mientras que el vertical representa la parte imaginaria. Por lo tanto, mover un punto hacia la derecha o hacia la izquierda equivale a sumar +1 o -1 a su valor actual, respectivamente. Asimismo, mover un punto hacia arriba o hacia abajo corresponde a sumar +i o -i, respectivamente.

Los puntos rojos son los equivalentes a $0 \bmod(\alpha)$. Además de estos, también coloreamos 4 pares de puntos más.

El isomorfismo $f$ está definido por la transformación del $i$ésimo elemento de la secuencia cíclica $(0,1,2,\cdot\cdot\cdot,10,11,12,0,1,2,\cdot \cdot\cdot)$ en el $i$ésimo elemento de la también cíclica secuencia de puntos de la figura, que cumple las siguientes reglas:

1. Comienza desde el punto rojo de la primera fila;
2. Sigue las flechas horizontales derechas; excepto eso
3. Cuando siguiendo las flechas lleva la secuencia fuera de la red, alcanzaría uno de los puntos no negros. En lugar de ir a ese punto, salta al punto del mismo color (es decir, el punto equivalente módulo $\alfa$) dentro del mismo cuadrado; y finalmente
4. Cuando este punto no negro pasa a ser rojo (lo que sucede después de que todos los demás colores hayan pasado), la secuencia salta al punto rojo superior, reiniciando así el ciclo;

Para mapear al menos $Y$ enteros naturales, se debe tomar un cuadrado con área $\vert\alpha\vert^2$ (donde $\vert\alpha\vert = \sqrt{a^2 + b^2} $ es, por el teorema de Pitágoras, la medida de su lado) al menos tan alto.

Observe que cada “salto” cambia el número de fila $r$ a $r \leftarrow (r + b)(mod a + b)$ si uno cuenta las filas de arriba hacia abajo y, de manera equivalente, a $r \leftarrow (r + a)(mod a + b)$ si se cuenta de abajo hacia arriba. Por lo tanto, la condición necesaria y suficiente para que cada fila (y punto) se desplace exactamente una vez en cada ciclo es que el tamaño de los saltos sea coprimo con el número de filas o, en otras palabras, $mcd(a,a + b) = mcd(b,a + b) = 1$. Debido a las propiedades del operador del máximo común divisor, ambos son equivalentes a $mcd(a,b) = 1$.

YS Villas Boas notó la necesidad de coprimalidad de $a$ y $b$. Para preservar el supercrecimiento, cada nuevo entero $w$ agregado al final de la secuencia debe superar la suma de todos los actuales ($w > \sum_{i=1}^k v_i$). Observó que para lograr esto, sus coeficientes multiplicadores $b_i$ tendrían que ser al menos 1 y, por lo tanto, cada bit no podría mapearse en los coeficientes 0 y 1. Si los coeficientes fueran 0 y 1, solo el bloque compuesto sólo de unos satisfaría el supercrecimiento. Por esta razón, los bits 0 y 1 se mapearon respectivamente a los coeficientes multiplicadores 1 y 2.

Finalmente, y menos trivial: durante cada paso de la decodificación, se debe encontrar un nuevo entero $v_1$ como solución de la ecuación $b_1 v_1 = v_{n+1} - \sum_{i = 2}^{n} b_i v_i$, donde todos los $v_i$ y $b_i$ son conocidos por $1 < i \leq n$. Como tampoco sabemos $b_1$, terminamos con un sistema con una ecuación y dos variables, lo que nos deja con un grado de libertad. Para corregir esto, tenemos que arbitrar un valor positivo (en aras de la simplicidad, 1) para que siempre se asigne a $b_1$, eliminando así la ambigüedad. Por lo tanto, dado que el primer coeficiente está fijado en 1, para codificar $n$ bits en cada paso, nuestras secuencias de enteros deben tener una longitud de $n + 1$ elementos.

Un último tecnicismo a resolver es el caso en que el tamaño en bytes del mensaje no sea múltiplo del tamaño del bloque. Es decir, ¿qué hacer con los posibles bytes restantes del último bloque de datos para que, una vez recuperados los bloques de datos, se conserven todos los bytes del contenido original, pero no más que ellos? Lo solucionamos repitiendo el último byte del mensaje una vez. A esta copia le sigue entonces una secuencia aleatoria en la que cada componente sólo requiere que sea diferente del anterior. Así, cuando se recuperan los bloques de datos, el último de ellos o, en el peor de los casos, el anterior al último se trunca en la última repetición de bytes. ^[4]

Ahora vamos a mostrar un ejemplo del criptosistema SRVB.

Empezamos con los parámetros:

$k = 4$;

$m = 4$;

lo que produce una longitud de bloque de $l = 4 * 4 = 16$, y una secuencia supercreciente de $k + 1 = 5$ enteros naturales, que se opera, es decir, se combina linealmente, se le agrega el resultado de esta combinación lineal, y reducido a sus últimos $k + 1$ elementos —$m = 4$ veces;

En aras de la simplicidad, sea el siguiente el vector (supercreciente) de $v_i$:

$(1,2,4,8,16)$

De hecho, la secuencia de las primeras cinco potencias de 2, solo porque esta es la secuencia supercreciente con cinco elementos y los valores estrictamente positivos más pequeños posibles (evitando así un 0 en la clave pública, que trivialmente revelaría el 0 correspondiente de su contraparte ).

Como dijimos antes, para $\alpha = a + bi$, los enteros $a$ y $b$ deben ser coprimos, y de acuerdo con la nueva restricción que mencionamos, tenemos que pedir que $a^2 + b^2 = \vert\alpha\vert^2 \geq W$. Un cálculo rápido arroja $W = 1590$. Dado que $\sqrt{1590} \simeq 39.8$, un $\alpha$ muy conveniente para elegir sería $\alpha = 39 + 40i$, ya que es lo suficientemente grande como para acomodar un isomorfismo con un anillo de números enteros con al menos menos 1590 componentes, mientras que también satisface $gcd(a,b)=1$. Además, debemos elegir un $\theta$ tal que $gcd(a,\theta)=1$ ^[5] y preferiblemente que no sea demasiado bajo, de modo que $(a_1 * \theta) \% \alpha \neq v_1 * \theta$, (también para evitar dar información). $\theta = 60$ hace el trabajo, produciendo:

$-19-1i,1+38i,3-3i,6-6i,12-12i$ ^[6]

Ensuciémonos las manos, entonces. Tome el mensaje Hello Toptal! . Primero lo mapeamos en una matriz de bytes según ASCII y nuestra convención para truncar bloques de datos:

 01001000 01100101 01101100 01101100 01101111 00100000 01010100 01101111 01110000 01110100 01100001 01101100 00100001 00100001

Dado que nuestro bloque de datos tiene 16 bits = 2 bytes de largo y nuestro mensaje tiene 13 caracteres, terminamos con 7 bloques de datos de 2 bytes cada uno, donde el último contiene dos veces la representación de bits del carácter '!' . Codifiquemos el primer bloque paso a paso. Presta mucha atención porque los bits de cada byte están tomados en orden de importancia.

$m=01001000 01100101$

• Primer nibble del primer byte: $(0,0,0,1)\rightarrow(1,1,1,1,2)\cdot(-19-1i,1+38i,3-3i,6-6i,12 -12i)=15+4i$
• Segundo nibble del primer byte: $(0,0,1,0)\rightarrow(1,1,1,2,1)\cdot(1+38i,3-3i,6-6i,12-12i,15+ 4)=49+9i$
• Primer nibble del segundo byte: $(0,1,0,0)\rightarrow(1,1,2,1,2)\cdot(3-3i,6-6i,12-12i,15+4i,49+ 9i)=106-10i$
• Segundo nibble del segundo byte: $(0,1,1,0)\rightarrow(1,1,2,2,1)\cdot(6-6i,12-12i,15+4i,49+9i,106- 10i)=252-2i$

Y así, acabamos de mapear

“Él” $\Flecha derecha(12-12i,15+4i,49+9i,106-10i,252-2i)$

El resto del mensaje cifrado es el siguiente:

“ll” $\Flecha derecha(12-12i,21-2i,61-3i,185-31i,367-59i)$

“o “ $\Flecha derecha(12-12i,25+33i,65+32i,111+44i,244+124i)$

“Hasta” $\Flecha derecha(12-12i,9+10i,46+12i,149+5i,277+31i)$

“pt” $\Flecha derecha(12-12i,3+16i,46+12i,73+23i,201+49i)$

“al” $\Flecha derecha(12-12i,4+54i,44+53i,117+193i,231+389i)$

”!!” $\Flecha derecha(12-12i,4+54i,32+65i,63+92i,121+247i)$

Ahora, para el descifrado, tenemos $\theta^{-1}=60^{-1}=27+i$:

$($”Él” $\Rightarrow)$ $(12-12i,15+4i,49+9i,106-10i,252-2i)*\theta^{-1}\%\alpha=(16,47 ,93,223,527)$

Ahora, viene el algoritmo codicioso:

Primero, restamos cada factor contribuyente multiplicado por uno, porque se sabe que contribuyeron al menos una vez al último, lo que da:

• Segundo nibble del segundo byte:

$T \flecha izquierda (527-233-93-47-16) = 148$

$(T \geq 223) = (148 \geq 223) = false \Rightarrow b_1=0 ; T \flecha izquierda (T - 0 * 223) = 148$

$(T \geq 93) = (148 \geq 93) = verdadero \Rightarrow b_2 = 1; T \flecha izquierda (T - 1 * 93) = 55$

$(T \geq 47) = 55 \geq 47) = verdadero \Rightarrow b_3 = 1; T \flecha izquierda (T - 1 * 47) = 8$

$(T \geq 16) = 8 \geq 16) = falso \Rightarrow b_4 = 0; T \flecha izquierda (T - 0 * 16) = 8$

Resultado: 0110;

Resto: 8 (agregado al comienzo de la secuencia como nuevo elemento más bajo);

Suelta 527 del final de la secuencia actual;

• Primer nibble del segundo byte:

$T \flecha izquierda (233-93-47-16-8) = 59$

$(T \geq 93) = (59 \geq 93) = falso \Rightarrow b_1 = 0; T \leftarrow(T - 0 * 93) = 59$

$(T \geq 47) = (59 \geq 47) = verdadero \Rightarrow b_2 = 1; T \flecha izquierda (T - 1 * 47) = 12$

$(T \geq 16) = (12 \geq 16) = falso \Rightarrow b_3 = 0; T \flecha izquierda (T - 0 8 16) = 12$

$(T \geq 8) = (12 \geq 8) = verdadero \Rightarrow b_4 = 1; T \flecha izquierda (T - 0 * 12) = 4$

Resultado: 0101;

Resto: 4 (agregado al comienzo de la secuencia como nuevo elemento más bajo);

Suelta 233 del final de la secuencia actual;

• Segundo nibble del primer byte:

$T \leftarrow (93 - 47 - 16 - 8 - 4) = 18$

$(T \geq 47) = (18 \geq 47) = falso \Rightarrow b_1 = 0; T \flecha izquierda (T - 0 * 47) = 18$

$(T \geq 16) = (18 \geq 16) = verdadero \Rightarrow b_2 = 1; T \flecha izquierda (T - 1 * 16) = 2$

$(T \geq 8) = (2 \geq 8) = false \Rightarrow b_3 = 0; T \flecha izquierda (T - 0 * 8) = 2$

$(T \geq 4) = (2 \geq 4) = false \Rightarrow b_4 = 0; T \flecha izquierda (T - 0 * 4) = 2$

Resultado: 0100;

Resto: 2 (agregado al comienzo de la secuencia como nuevo elemento más bajo);

Suelta 93 del final de la secuencia actual;

• Primer nibble del primer byte:

$T \flecha izquierda (47-16-8-4-2) = 17$

$(T \geq 16) = (17 \geq 16) = verdadero \Rightarrow b_1 = 1; T \flecha izquierda (T - 1 * 16) = 1$

$(T \geq 8) = (1 \geq 8) = false \Rightarrow b_2 = 0; T \flecha izquierda (T - 0 * 8) = 1$

$(T \geq 4) = (1 \geq 4) = falso \Rightarrow b_3 = 0; T \flecha izquierda (T - 0 * 4) = 1$

$(T \geq 2) = (1 \geq 4) = false \Rightarrow b_4 = 0; T \flecha izquierda (T - 0 * 2) = 1$

Resultado: 1000;

Resto: 1 (agregado al comienzo de la secuencia como nuevo elemento más bajo);

Caída de 47 de la final de la secuencia actual;

Como resultado, hemos recuperado el bloque de datos: “01001000 01100101” que contiene los dos primeros caracteres “Él”, de nuestro mensaje. No solo eso, también hemos recuperado correctamente nuestra secuencia supercreciente de clave privada $(1,2,4,8,16)$.

Los otros mapas de bloques de datos van de la misma manera.

Comparación con los principales criptosistemas de clave pública

SRVB es:

1. Totalmente gratuito y público;

2. Considerablemente más simple y más fácil de entender e implementar que ECC ^[7] ;

3. Abundante en claves y, por lo tanto, virtualmente sin costo, contrario, por ejemplo, a RSA, que se basa en números primos, que son costosos.

Ya podemos resumir las vulnerabilidades más probables. Dado que SRVB desciende de MH, es fácil sospechar que sería vulnerable a una generalización del ataque Shamir, o algún otro que lo rompa. Aunque el autor tenía razones para creer que este no sería el caso, aún no se ha hecho ninguna confirmación (lo cual es muy típico cuando se trata de criptosistemas).

¿Que sigue?

Rocha observó algunas generalizaciones para el uso de los anillos de cociente, que posiblemente pueden conducir a un aumento en la complejidad del criptoanálisis. También investigaremos estas posibilidades.

El oscurecimiento algebraico lineal

Da la casualidad de que durante el desarrollo y la documentación de SRVB, Villas Boas ideó otro enfoque para mejorar el concepto de criptosistema de clave pública de mochila que no se explicará en detalle en este documento, para que este artículo no sea demasiado largo. y aburrido, pero aquí hay un vistazo. Si no logra comprenderlo, no se preocupe, solo permanezca atento a la publicación de nuestro próximo artículo, en el que entraremos en detalles más a fondo: vea el subconjunto sum $y$, de, digamos, $N$ elementos de anillo de cociente $u_i$ (que son isomórficamente correspondientes a los enteros positivos $v_i$ de la secuencia supercreciente, como antes) como una multiplicación de un vector de fila de estos $u_i$ por un vector de columna $B$ ( para binario) de ceros y unos ^[8] .

$y = \sum_{i=1}^n u_i b_i = (u_1,\cdot\cdot\cdot,u_n)^T\cdot(b_1,\cdot\cdot\cdot,b_n)$=UB,

donde $b_i \in {0,1}$

Ahora, imagina que, en lugar de este vector de $u_i$, tienes, a la izquierda, una matriz V de $n$ por $N$ (con $n < N$), que tiene los $v_i$ (los enteros de la supercreciente secuencia) vector como (sin pérdida de generalidad) su primera fila y todas las demás entradas se llenaron de ruido. Observe que, ahora, al multiplicar V por el mismo vector de bits B, obtiene un vector de columna W que tiene $w$ como su primera entrada y ruido en las demás. Ahora, tome esta matriz V y multiplíquela por una matriz aleatoria ^[9] n por n R a la izquierda, definiendo la matriz n por N P:

P = VD

La idea es que Bob use P como su nueva clave pública. Debido a la aleatoriedad de R, el vector

$Y = PB = RV B = RW$

tiene la información $w$ oscurecida por el ruido en otras filas de V. Bob también calcula de antemano y almacena el vector fila S que satisface:

$R^TS^T = e_1$

Cuando Alice envía Y a Bob, él simplemente encuentra SY, porque:

$SY=S(PB)=S((RV)B)=SRVB= {e_1}^TR^{-1}((RV)B)=$

(hasta ahora solo definiciones)

${e_1}^T (VB)={e_1}^TW = w$

(Ahora, explotando la asociatividad para cancelar las Rs)

and then proceeds as before to extract the vector of $b_i$ from $w$ by means of the greedy algorithm.

So, in one word, the Linear Algebraic Obscuring exploits the associativity of matricial multiplication (the fact that we could expand the terms and then operate their components in a new order provided we that preserved the sequence of all the operands in the sequence) to 'linearly' scramble and then filter (in the encryption and in the decryption respectively) noise to/from $w$. And in limit case $n = 1$, the system elegantly goes back to original to Rocha's approach.

The SRVB Campaign – a prize challenge

As explained before, in accordance to Kerckhoffs' principle, experience shows that antiquity of a publicly known unbroken cryptosystem is the main source of reliability of it, far more than any theoretical argumentation by the own authors, apart from anything else, because definitive proof of efficacy of the algorithms usually are not available.

And here it is our great chance to put these concepts to practice to earn a big money prize: Aware of this fact, we launched the aforementioned campaign, which is basically a crowdfunding for a prize automatically awarded to the first one that manages to break a message. The money is going to be converted to bitcoins in a given wallet whose private key will be SRVB encrypted and published so that anyone able to decipher it can simply take the money anonymously, no questions asked.

Expresiones de gratitud

This article in particular and the whole SRVB Crypto project in general have been greatly helped by Prof. Charles F. de Barros, assistant professor at the Federal University of Sao Joao Del Rei. Prof. Barros provided us a technical review of the SRVB cryptosystem itself. I judged it necessary to submit to before daring to publish, and that I would certainly take much longer to do by myself.

In addition, I also would like to extend my deep gratitude to professor Adnan Ademovic for his extraordinarily insightful, attentive, and patient work as the editor of this article.

Glosario

1. Cryptology/Cryptography: The science/practice of making a message nearly impossible to interpret without a specific set of instructions (in this context, the so-called "key"), thus allowing agents who share these instructions to communicate securely even if tapped by third parties;
2. Steganography: The science/practice of hiding a message within another by means of adding apparently innocuous modifications to the latter;
3. Key generation: the mapping of (expectedly) random inputs into (as random) valid keys;
4. Encryption/Encoding: The easily computable mapping of an easily interpretable message into another that is either hard or impossible to construe, by means of an (as randomly specified) element the one correspondent to the key of a (by Kerckhoffs' principle, publicly known and validated) family of algorithms;
5. Decryption/Decoding: The easily computable mapping that consists of the inverse of the previous, also being definable by an (as randomly specified, and therefore, unknown and hard to be guessed by third parties) element _again, the one correspondent to the key_ of a (by the same principle, usually known) family of algorithms, that thus outputs the original message when input with the encrypted one;
6. Cryptosystem: A triad of the family of encoding algorithms, the family of corresponding decrypting algorithms, and a key generating algorithm;
7. Allies: The agents with whom the communication is intended, and who are expected to act according to the protocol's rules;
8. Enemies/Third Parties: The agents with whom the communication is not intended, but try, nevertheless, to eavesdrop the communication and bypass the security enhanced by the cryptosystem;
9. Secure Channel: Any protocol (procedure) for communication that is easy to use while also effectively preventing third parties to feasibly construe what is meant by its users;
10. Insecure Channel: any channel (ie, protocol or procedure) that, as the name suggests, is not a secure channel;
11. Breaking a Key: The process of discovering a key by means of public pieces of information (like an encrypted message or public key) other than the key itself to be discovered and that was not expected to feasibly allow the discovery of the key. Since the information that results from this process grants the decryption of the messages, this is a particular case of…
12. Breaking/Deciphering a message: Any way to deduce the original content of an encrypted message only by means of the encrypted message itself and other pieces of information that were not expected to suffice for the deduction of the original content;
13. Breaking a Cryptosystem: Discovery of a systematic way to feasibly break whatever message is encrypted by this method under whatever parameter;
14. Kerckhoffs' Principle/Desideratum/Axiom/Law: A cryptologic principle named after the dutch cryptographer Auguste Kerckhoffs, according to which, in order for a cryptosystem to be deemed secure, everything about it except by its (private) keys must be of public knowledge;
15. Key: Secret parametrization of a cryptosystem allowing it to be infeasible to be guessed (and consequently broken) by third parties while also being validated by the community of cryptanalysts (in accordance to Kerckhoffs' principle);
16. Symmetric Cryptosystem: Any cryptosystem on which any parameter for the encoding suffices for easily deducing the parameter for decoding, and, for this reason, must be kept private. One can rephrase it by saying that the encryption and decryption parameters are both equivalent to the key;
17. Asymmetric/Public Key Cryptosystem: Any cryptosystem for which there is a way to express the parameters for the encoding that does not suffice to feasibly deduce the correspondent parameter for decoding, allowing it to be sent to allies through an insecure channel, or even made public, and thus creating a secure channel where there was none;
18. Public Key: A component of an asymmetric cryptosystem that suffices for parameterizing the encryption but does not suffice for feasibly deducing the decryption parameter, ie, the…
19. Private Key: A component of an asymmetric cryptosystem that suffices for parameterizing the decryption and thus must be kept privately and usually also suffices for parameterizing the encryption;

^[1] Note that, here, the phrases decipher or decrypt do not apply, because before a given cryptosystem (with all its components, including its keys) is well defined, one cannot classify a given method of construing the original message from the encrypted one as the intended communication (decryption) or an attack (deciphering).

^[2] Though there are techniques to improve this guessing work, it still remains far more difficult discovering than multiplying them.

^[3] The first inspiration was to look at the tree of the tau conjecture, an infinite tree rooted in the number 1, whose other nodes consist of integers resulting in one binary operation of sum, subtraction, or multiplication between previous nodes, possibly one node operated with itself. The theory's goal relates to the depth, in this tree, in which each integer first appears. It is apparently hard to find large numbers in low branches (even if we relax the need for it), but is it immediate to check if a given sequence of operations indeed produces a given result.

^[4] This is surely not the most natural approach, but by adopting this, one ensures that this byte filling (called padding)…

1. Conceals the size of the padding (differently, for example of ciphertext stealing) and obscures the end of the message, thus rendering chosen-plaintext attacks more difficult;
2. Enhances a distribution of bits as close to uniform as possible;

If the last blocks of every message were known to be systematically biased in a far from uniform distribution, an attacker could exploit this fact to do a statistical cryptanalysis, for any given sample of messages would be statistically more representative than otherwise. In other words, the last blocks being statistically less diverse, they become they become the weakest links of the message.

^[5] Make no mistake: this greatest common divisor is Gaussian, while the previous is real.

^[6] …which is not perfect, because it easily gives away the fact that the last three components are proportional to 1, 2, and 4. But, again, for the sake of simplicity, we will ignore this detail.

^[7] …which is so complex that there are a few notorious cases of failure to implement and maintain protocols based on it.

^[8] Here, we will not adopt Rocha's approach of a multiple linear combinations block, which also allows us to randomly permute the bis to obscure them even more.

^[9] Though not totally random. Its transpose must span the subspace generated by the vector $ e_1 = (1,0,…,0) $.