Comenzando Con El Criptosistema SRVB

Introducción

La seguridad de la información es un fascinante campo de conocimiento que puede involucrar 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 se ocupe de la 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 te dará una introducción a los principios detrás de los criptosistemas de clave pública y te introducirá al 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, los autores del algoritmo están preparando una campaña que incluye una recompensa financiera para cualquiera que logre descifrar el código. Como 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 de interpretarlo de manera viable siempre que se proporcione una instrucción específica, que generalmente es la llamada “clave”. Si bien esta es una definición muy amplia que abarca incluso las primeras técnicas, vale la pena mencionar que esto no cubre todo lo que hay para la seguridad de la información.

Se espera que la carrera tecnológica entre los métodos de cifrado y las formas de descifrarlos nunca tenga un ganador definitivo. También, 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 de forma sistemática los mensajes cifrados, es decir, omitir la seguridad o el cifrado.

Para que los usuarios puedan considerar que un criptosistema (dada la técnica de la criptografía) es seguro, debe contar con la aprobación de la comunidad internacional de expertos y, por lo tanto, ser conocido públicamente, lo que se conoce como principio de Kerckhoffs. Sin embargo, esta misma condición expone el sistema al escrutinio de la comunidad mundial de criptoanálisis, que tratará de idear formas de romper sistemáticamente las encriptaciones.

¿Cómo se puede hacer que un determinado proceso de encriptación sea lo suficientemente secreto como para que solo los agentes intentados puedan descifrarlo, al mismo tiempo que sea lo suficientemente público como para que la comunidad mundial de criptoanálisis pueda dar fe de su robustez? La respuesta es un componente que es un elemento clave de 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 propiedades adecuadas, no será factible que los atacantes determinen los parámetros simplemente mediante inspección.

Finalmente, para que una clave funcione de manera efectiva, debe producirse fácilmente pero es casi imposible de adivinar. Con el poder computacional de las computadoras de hoy en día, una computadora necesitaría menos tiempo para descifrar una clave generada por el ser humano de lo que cualquier humano necesitaría siquiera imaginarlo, además de que no es rentable generar claves de esa manera de todos modos. Debido a eso, las claves tienden a ser generadas por un algoritmo.

Un algoritmo de generación de claves no debe crear salidas predecibles/reproducibles como resultado del 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 transforman 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 del paquete de red o incluso el hardware dedicado, dependiendo de la aplicación.

---

Criptosistemas de clave pública

Prepárate para sorprenderte una vez más, porque ahora presentaremos 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) hayan sido intercambiados de forma segura, pero el problema de intercambiar los parámetros a través de un canal público permanece. En este momento, presentaremos un concepto que resuelve un problema levemente más palpable: la creación de un canal seguro.

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

Enviar claves por correo electrónico no sería una opción, ya que su competidora Eve puede interceptar el intercambio y usar sus claves para leer todos los datos encriptados posteriormente. Si tuvieran otro canal digital a través del cual pudieran transmitir esta información sensible, entonces no necesitarían en primer lugar el cifrado y, por lo tanto, las claves. También se podría interceptar el envío de la clave a través del correo físico, ya que para empezar, es necesario intercambiar información confidencial. Enviar una clave estegangrafiada ocultándose dentro de otros datos sería inteligente, pero inútil a menos que el remitente esté seguro de que el destinatario, y el destinatario solo, están al tanto de la existencia de tal 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í misma, lo que nos lleva al punto de partida.

La solución está diseñando un criptosistema para el cual el parámetro de encriptación no es suficiente para interpretar factiblemente el mensaje original ^[1], y guardando para usted el parámetro que le permitiría interpretar el mensaje. Llamamos a ese parámetro la clave privada. Con base en la clave privada, uno puede generar de manera factible un conjunto de parámetros para una herramienta de cifrado sin hacer que esos nuevos parámetros 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 encriptar 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 llama clave pública.

La criptografía donde difieren las claves de cifrado y descifrado, y la primera no puede usarse para deducir lo último, se denomina criptografía asimétrica, mientras que la criptografía simétrica es lo que tenemos cuando esas claves son iguales o se deducen fácilmente entre sí. Alice le envía a Bob su clave pública, que solo puede usarse para encriptar cosas que solo ella puede descifrar (con su clave privada, que guarda en privado) y, a la inversa, Bob le envía a Alice su clave pública, que solo puede usarse para encriptar cosas que solo él puede descifrar (mediante su clave privada, que también guarda en privado). Pero, ¿cómo se puede publicar un parámetro para un algoritmo de cifrado del que no se puede deducir el algoritmo inverso exacto?

La respuesta se encuentra en el campo de las matemáticas más relacionado con la programación, la teoría de la complejidad computacional. Cualquiera que haya profundizado lo suficiente en problemas matemáticos ha escuchado acerca de transformaciones que son fáciles de hacer de una manera, pero difíciles de hacer al revés. En el cálculo, por ejemplo, encontrar un derivado de un libro de texto suele ser un ejercicio sencillo, mientras se hace el inverso (como resolver cualquier parte física o libro de texto físico no trivial ligeramente ODE o PDE, por ejemplo) requiere un proceso más investigativo de la primera hipótesis de familias de funciones que están garantizadas (o al menos plausibles) para contener la(s) solución(es) y resolver problemas inversos para encontrar soluciones de estas familias.

Un ejemplo que se utiliza realmente en el criptosistema RSA es multiplicar grandes primos en lugar de factorizar el producto resultante sin conocer los factores. Hacer la multiplicación es trivial, pero el factoring requiere que aleatoriamente ^[2] adivine los factores primos, que tienen cientos de dígitos. Una propiedad importante de la operación es la necesidad de escalar bien. Agregar algunos dígitos sobre el tamaño de los números primos en RSA dará como resultado una clave que requiere miles de operaciones más para descifrar y agregar un pequeño aumento en la complejidad del proceso de cifrado. Hablando en términos generales, el producto de números primos se usa para encriptar, mientras que el par de factores primos se usa para descifrar.

Con todo esto en mente, echemos un vistazo a cómo funciona el sistema criptográfico SRVB.

El algoritmo subyacente: examinar SRVB

El problema de la suma del subconjunto

Al igual que 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 suma de subconjuntos, que se puede describir de la siguiente manera:

Dado el entero $w$ and $v_1, \cdot \cdot \cdot, v_N \in Z$ encuentra la secuencia $b_1, \cdot \cdot \cdot, b_N \in {0,1}$, such that $ \sum_{i = 1}^{N} v_i b_i = w $.

Claramente, este problema puede producirse seleccionando al azar N enteros, eligiendo aleatoriamente un subconjunto de ellos y resumiendo 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 $ b $ s. Un enfoque más eficiente fue dado por Horowitz y Sahni en 1972, con una complejidad de $ O ( N * 2 ^ {N / 2} ) $. El problema es al menos tan difícil si reemplazamos los vectores $b$s and $w$ with $k$- dimensionales de enteros. Sin embargo, el ámbito donde se debe realizar este problema más difícil también debe tener un isomorfismo con un [anillo] (https://en.wikipedia.org /wiki/Ring_(matemáticas)) 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 suma de subconjuntos dentro de enteros gaussianos, donde $ k = 2 $..

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

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

1. Comienza con $ i = N $, el factor actualmente observado, y $ w’ = w $, lo que resta de $w$

2. Si el factor de escala actual es demasiado grande para caber en lo que queda de $w$, significa que $ v_i > w’$, set $b_i = 0$ y continúa al próximo 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 entonces ponemos $b_i = 1$.

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

4. Verifica que, ahora $w’ == 0$, de lo contrario, el problema se corrompió.

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

Vamos a configurar una anotación para el resto del artículo. Elegimos $ v_1,\cdot\cdot\cdot, v_n $ y $ w $ para que sean los factores y la suma de la secuencia de superincremento, mientras que $ u_1,\cdot\cdot\cdot, u_n $ y $ y $ serán los públicos los 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 $ elegida para que no sea superincreíble, y el número $ y $ esté a disposición del público, no se proporciona públicamente suficiente información para recuperar la secuencia $ b_1,\cdot\cdot\cdot, b_n $. Sin embargo, si hay una secuencia super increible $ 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 eso.

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 súper creciente de los enteros) en la dura (la que carece de esta propiedad) por medio de una operación lineal (el módulo) con operandos secretos. La transformación consiste en multiplicar cada $v_i$ by a $\theta$ y tomando el resto de este producto por un $\alpha$, donde $\alpha \gt \sum_{i=1}^N v_i$ and $\gcd(\alpha, \theta) = 1$ (dos restricciones que pronto se justificarán). El resultado, la secuencia $u_1, \ldots, u_N$,ya no aumenta más, y puede considerarse una mochila difícil.

Una permutación aleatoria de la secuencia $u_1, \ldots, u_N$ se le daría a la parte que quiere encriptar y enviarnos un mensaje. La permutación se realiza para que un tercero tenga dificultades para adivinar cuál es la secuencia de superincrecimiento original. Los bloques de bits de un mensaje se usan como coeficientes $b_1, \ldots, b_N$. La encriptación se hace multiplicando la secuencia de teclas con esta secuencia de coeficientes, y sumando las multiplicaciones en un resultado, que debemos etiquetar $y$. Solo el propietario de la clave privada puede transformar $y$ en los correspondientes $w$ que serían obtenidos si los mismos $b_1, \ldots, b_N$ bloques fuesen multiplicados con enteros fáciles (la secuencia $v_1, \ldots, v_N$). Eso se hace por medio de la multiplicación $y$ by $\theta^{-1}$, el multiplicativo inverso de $\theta$ modulus $\alpha$ (cuya existencia depende de esa condición de $\gcd(\alpha, \theta) = 1$). En otras palabras, $(\theta * \theta^{-1}) \bmod \alpha = 1$. Luego de eso, calculamos $w = (y * \theta^{-1}) \bmod a$. La razón por la que se garantiza que esto funciona 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 de cociente y la propiedad de linealidad del operador de 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 & = \left[ \sum_{i=1}^N b_i * v_i \right] * \theta \bmod \alpha \newline & = w * \theta \bmod \alpha \end{align} $

Y así el la suma fácil $w$ puede recuperarse 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 se deben mantener en privado como partes de la clave privada.

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

Al igual que cualquier otra instancia de la vida cotidiana, 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 sistema criptográfico es seguro de usar, lo que no nos proporciona garantías reales. Seis años después de su creación, el criptosistema MH se rompió con un ataque por A. Shamir. Hubo varios intentos más para revivir MH, muchos de los cuales también fallaron.

---

El Criptosistema Santana Rocha - Villas Boas (SRVB)

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

También concibió un bloque de bits que constaba de muchos pasos de la combinación lineal previamente descrita de una napa dura. En cada uno de ellos, un nuevo entero (gaussiano), equivalente a uno, más alto que la suma de todos los anteriores se agregaría al final de la secuencia, mientras que el número más pequeño se eliminaría.

Se aplica una restricción diferente pero elegantemente análoga para $ \alpha $, que ahora es un número entero gaussiano. Requerimos para $ w \leq \vert \alpha \vert ^ 2 $, donde $ w $ es, nuevamente, la combinación lineal más alta de los enteros naturales de la mochila fácil. La razón es muy difícil de formalizar, pero afortunadamente se puede intuir fácilmente a partir de una descripción elegante:

Imagine un enrejado cuadrado en el plano de números complejos, cuyo lado es una hipotenusa de un triángulo rectángulo de cateti ayb, paralelos a los ejes real e imaginario . Un ejemplo de tal celosía se da a continuación. Los enteros de Guassian módulo $ \alpha = a + bi $ pueden ser representados por puntos ubicados dentro de dicho enrejado. Dentro de dicha red existen $ \vert \alpha \vert ^ 2 $ puntos distintos. Si escogemos un $ \alpha $ lo suficientemente grande, podemos ajustar todas las combinaciones lineales de la mochila fácil. Así que estamos estableciendo un requisito para $ w \leftarrow \vert \alpha \vert ^ 2 $, donde w es [como se describe].

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 $ (tenga en cuenta que $ n $ y $ \alpha $ de hecho satisfacen $ n = \vert \alpha \vert ^ 2 = a ^ 2 + b ^ 2 $ según se requiera). Los puntos representan los enteros gaussianos, es decir, los números complejos $ a + bi $, donde $ a $ y $ b $ son enteros. Como de costumbre, el eje horizontal representa la parte real, mientras que la vertical representa la parte imaginaria. Por lo tanto, mover un punto hacia la derecha o hacia la izquierda equivale a agregar +1 o -1 a su valor actual, respectivamente. Del mismo modo, mover un punto hacia arriba o hacia abajo equivale a agregar + i o -i, respectivamente.

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

El isomorfismo $ f $ se define por la transformación del elemento $i$th de la secuencia cíclica $ (0,1,2, \cdot \cdot \cdot, 10,11,12,0,1,2, \cdot \cdot \cdot) $ en el elemento $i$th de la secuencia de puntos también cíclica en la figura, que se adhiere a las siguientes reglas:

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

Para mapear al menos $ Y $ enteros naturales, se debe tomar un cuadrado con el área $ \vert \alpha \vert ^ 2 $ (donde $ \vert \alpha \vert = \sqrt {a ^ 2 + b ^ 2} $ es, por 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 uno cuenta de abajo hacia arriba. Por lo tanto, la condición necesaria y suficiente para que cada fila (y punto) se recorra exactamente una vez en cada ciclo es que el tamaño de los saltos es coprime con el número de filas, o, en otras palabras, $ gcd (a, a + b) = gcd (b, a + b) = 1 $. Debido a las propiedades del mayor operador de divisor común, ambos son equivalentes a $ gcd (a, b) = 1 $.

Y. S. Villas Boas notó la necesidad de la coprimidad de $ a $ y $ b $. Para preservar el superincremento, cada nuevo entero $ w $ agregado al final de la secuencia necesita superar la suma de todos los actuales ($ w> \sum_ {i = 1} ^ k v_i $). Observó que para lograr esto, sus coeficientes de multiplicación $ 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 eran 0 y 1, solo el bloque compuesto solamente por uno satisfaría el súperincremento. Por esta razón, los bits 0 y 1 fueron mapeados respectivamente a los coeficientes de multiplicación 1 y 2.

Finalmente, y de manera menos trivial: durante cada paso de la decodificación, se encuentra 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 $ 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 se fija en 1, para codificar $ n $ bits en cada paso, nuestras secuencias de enteros deben ser $ n + 1 $ elementos de longitud.

Un tecnicismo final para resolver es el caso en el que el tamaño en bytes del mensaje no es un múltiplo del tamaño del bloque. En otras palabras, ¿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 resolvimos repitiendo el último byte del mensaje una vez. Esta copia es, luego, seguida de una secuencia aleatoria en la que cada componente se requiere solo para ser diferente del anterior. Por lo tanto, 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 sistema criptográfico SRVB.

Comenzamos con los parámetros:

$k = 4$;

$m = 4$;

que produce una longitud de bloque de $ l = 4 * 4 = 16 $ y una secuencia superincreíble de $ k + 1 = 5 $ enteros naturales, que se opera —_ es decir, combinada linealmente, junto con el resultado de esta combinación lineal, y reducida a sus últimos $ k + 1 $ elementos _— $ m = 4 $ veces;

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

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

De hecho, la secuencia de las primeras cinco potencias de 2, simplemente porque esta es la secuencia superincreíble con cinco elementos y los valores posibles estrictamente más pequeños (evitando así un 0 en la clave pública, que cedería trivialmente al corresponsal 0 de su contraparte )

Como dijimos antes, para $ \alpha = a + bi $, los enteros $ a $ y $ b $ deben ser coprime, y de acuerdo con la nueva restricción mencionada, tenemos que solicitar que $ a ^ 2 + b ^ 2 = \vert \alpha \vert ^ 2 \geq W $. Un cálculo rápido produce $ W = 1590 $. Dado que $ \sqrt {1590} \simeq 39.8 $, un $ \alpha $ muy conveniente para ser elegido sería $ \alpha = 39 + 40i $, ya que es lo suficientemente grande como para acomodar un isomorfismo con un anillo de enteros con al al menos 1590 componentes, mientras que también satisface $ gcd (a, b) = 1 $. Además, debemos elegir $ \theta $ tal que $ gcd (a, \theta) = 1 $ ^[5] y preferiblemente no es demasiado bajo, por lo 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]

Déjennos ensuciarnos las manos, entonces. Tome el mensaje Hola Toptal!. Primero lo mapeamos en una matriz de bytes de acuerdo con [ASCII] (https://en.wikipedia.org/wiki/ASCII#8-bit_codes) 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 longitud, 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 ‘!’ . Vamos a encriptar el primer bloque paso a paso. Preste mucha atención porque los bits de cada byte se toman en orden de su importancia.

$m=01001000 01100101$

• Primer mordisco 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 mordisco del primer 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 primer 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

“He” $\Rightarrow(12-12i,15+4i,49+9i,106-10i,252-2i)$

El resto del mensaje cifrado es el siguiente:

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

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

“To” $\Rightarrow(12-12i,9+10i,46+12i,149+5i,277+31i)$

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

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

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

Now, for the decryption, we have $\theta^{-1}=60^{-1}=27+i$:

$($”He” $\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 arrojó:

• Segundo nibble del segundo byte:

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

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

$(T \geq 93) = (148 \geq 93) = true \Rightarrow b_2 = 1; T \leftarrow (T - 1 * 93) = 55$

$(T \geq 47) = 55 \geq 47) = true \Rightarrow b_3 = 1; T \leftarrow (T - 1 * 47) = 8$

$(T \geq 16) = 8 \geq 16) = false \Rightarrow b_4 = 0; T \leftarrow (T - 0 * 16) = 8$

Resultado: 0110;

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

Eliminar el 527 del final de la secuencia actual;

• Primer mordisco del segundo byte:

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

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

$(T \geq 47) = (59 \geq 47) = true \Rightarrow b_2 = 1; T \leftarrow (T - 1 * 47) = 12$

$(T \geq 16) = (12 \geq 16) = false \Rightarrow b_3 = 0; T \leftarrow (T - 0 8 16) = 12$

$(T \geq 8) = (12 \geq 8) = true \Rightarrow b_4 = 1; T \leftarrow (T - 0 * 12) = 4$

Resultado: 0101;

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

Deja 233 desde la final de la secuencia actual;

• Segundo nibble del primer byte:

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

$(T \geq 47) = (18 \geq 47) = false \Rightarrow b_1 = 0; T \leftarrow (T - 0 * 47) = 18$

$(T \geq 16) = (18 \geq 16) = true \Rightarrow b_2 = 1; T \leftarrow (T - 1 * 16) = 2$

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

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

Resultado: 0100;

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

Dejar caer 93 desde la final de la secuencia actual;

• Primer mordisco del primer byte:

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

$(T \geq 16) = (17 \geq 16) = true \Rightarrow b_1 = 1; T \leftarrow (T - 1 * 16) = 1$

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

$(T \geq 4) = (1 \geq 4) = false \Rightarrow b_3 = 0; T \leftarrow (T - 0 * 4) = 1$

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

Resultado: 1000;

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

Eliminar 47 desde la final de la secuencia actual;

Como resultado, hemos recuperado el bloque de datos: “01001000 01100101” que contiene los dos primeros caracteres “He”, de nuestro mensaje. No solo eso, también hemos recuperado correctamente nuestra secuencia superincreible 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 gratis y público;

2. Considerablemente más simple y 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 caros.

Ya podemos resumir las vulnerabilidades más probables. Como SRVB desciende de MH, es fácil sospechar que sería vulnerable a una generalización del [ataque de Shamir] (https://en.wikipedia.org/wiki/Merkle-Hellman_knapsack_cryptosystem#cite_note-2), o alguna otra que lo rompe Aunque el autor tenía razones para creer que este no sería el caso, aún no se ha confirmado (lo que es muy típico cuando se trata de criptosistemas).

---

¿Que sigue?

Rocha observó algunas generalizaciones para los anillos del cociente que se utilizarán, 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 llave pública para mochila que no se explicará en detalle en este documento, para que este artículo no sea demasiado largo. y tedioso, pero aquí hay un roce de él. Si no logra comprenderlo, no se preocupe, simplemente manténgase al tanto de la publicación de nuestro próximo artículo, en el que abordaremos los detalles con mayor precisión: vea el subconjunto suma $ y $, del, por ejemplo, $ N $ elementos de anillo de cociente $ u_i $ (que son isomórficamente correspondientes a los enteros positivos $ v_i $ de la secuencia súper creciente, 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,

where $b_i \in {0,1}$

Ahora imagine que, en lugar de este vector de $ u_i $, tiene, a la izquierda, una matriz V de $ n $ por $ N $ (con $ n <N $), que tiene $ v_i $ (los enteros del superincremento secuencia) vector como (sin pérdida de generalidad) su primera fila y todas las demás entradas llenas de ruido. Observa que, ahora, al multiplicar V por el mismo vector de bits B, obtienes un vector de columna W que tiene $ w $ como primera entrada y ruido en los demás. Ahora, toma esta matriz V y multiplícala de forma aleatoria ^[9] n por n matriz R a la izquierda, definiendo la n por N matriz P:

P = RV

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 de fila S que satisface:

$R^T S^T = e_1$

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

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

(hasta ahora solo definiciones)

${e_1}^T (V B)={e_1}^T W = w$

(Ahora, explotando la asociatividad para cancelar el Rs)

y luego procede como antes para extraer el vector de $ b_i $ de $ w $ por medio del algoritmo codicioso.

Entonces, en una palabra, el Obscurecimiento Algebraico Lineal explota la asociatividad de la multiplicación matricial (el hecho de que podríamos expandir los términos y luego operar sus componentes en un nuevo orden, siempre que nosotros conservemos la secuencia de todos los operandos en la secuencia) a ‘ linealmente ‘mezclar y luego filtrar (en el cifrado y en el desencriptado, respectivamente) el ruido a / desde $ w $. Y en el caso límite $ n = 1 $, el sistema vuelve elegantemente al original según el enfoque de Rocha.

La Campaña SRVB: un reto de premio

Como se explicó anteriormente, de acuerdo con el principio de Kerckhoff, la experiencia muestra que la antigüedad de un criptosistema ininterrumpido conocido públicamente es la principal fuente de confiabilidad de la misma, mucho más que cualquier argumentación teórica de los propios autores, aparte de cualquier otra cosa, porque la prueba definitiva de la eficacia de los algoritmos generalmente no está disponible.

Y aquí tenemos la gran oportunidad de poner en práctica estos conceptos para ganar un gran premio: conscientes de este hecho, lanzamos la campaña mencionada, que es básicamente un crowdfunding. por un premio otorgado automáticamente al primero que logra romper un mensaje. El dinero se convertirá en bitcoins en una billetera determinada cuya clave privada será encriptada y publicada en SRVB para que cualquiera que pueda descifrarla simplemente pueda tomar el dinero de forma anónima, sin preguntas.

Agradecimientos

Este artículo en particular y todo el proyecto SRVB Crypto en general han recibido una gran ayuda del Prof. Charles F. de Barros, profesor asistente en la [Universidad Federal de São João Del Rei] (http://www.ufsj.edu.br/). El Prof. Barros nos brindó una revisión técnica del propio criptosistema SRVB. Creí que era necesario someterme antes de atreverme a publicar, y que definitivamente me tomaría mucho más tiempo hacerlo por mi cuenta.

Además, también me gustaría expresar mi profunda gratitud al profesor Adnan Ademovic por su extraordinariamente perspicaz, atento y paciente trabajo como editor de esta publicación. artículo.

---

Glosario

1. Criptología/Criptografía:La ciencia / práctica de hacer que un mensaje sea casi imposible de interpretar sin un conjunto específico de instrucciones (en este contexto, la llamada "clave"), lo que permite a los agentes que comparten estas instrucciones comunicarse de forma segura incluso si son interceptados por terceros;
2. Esteganografía: La ciencia / práctica de ocultar un mensaje dentro de otro mediante la adición de modificaciones aparentemente inocuas a este último;
3. Generación de clave: el mapeo de entradas (esperadas) al azar en claves válidas (al azar);
4. Cifrado/Codificación: El mapeo fácilmente computable de un mensaje fácilmente interpretable en otro que es difícil o imposible de interpretar, mediante un elemento (como se especifica al azar) el correspondiente a la clave de a (según el principio de Kerckhoffs) , conocida y validada públicamente) familia de algoritmos;
5. Descifrado/Descodificación: El mapeo fácilmente computable que consiste en el inverso del anterior, también se puede definir por un elemento (como se especifica al azar, y por lo tanto, desconocido y difícil de adivinar por terceros) _una vez, el correspondiente a la clave_ de a (por el mismo principio, generalmente conocido) familia de algoritmos, que de este modo emite el mensaje original cuando se ingresa con el encriptado;
6. Criptosistema: Una tríada de la familia de algoritmos de codificación, la familia de algoritmos de descifrado correspondientes y un algoritmo de generación de claves;
7. Aliados: Los agentes a los que se destina la comunicación y quienes se espera que actúen de acuerdo con las reglas del protocolo;
8. Enemigos/Terceros: Los agentes con los que no se pretende la comunicación, pero intentan, sin embargo, espiar la comunicación y eludir la seguridad mejorada por el criptosistema;
9. Canal Seguro:Cualquier protocolo (procedimiento) para la comunicación que sea fácil de usar y que a la vez impida a terceros interpretar de manera viable lo que significan sus usuarios.
10. Canal No Seguro: cualquier canal (es decir, protocolo o procedimiento) que, como su nombre lo sugiere, no es un canal seguro;
11. Rompiendo una Clave: El proceso de descubrir una clave mediante información pública (como un mensaje encriptado o clave pública) que no sea la clave en sí misma para ser descubierta y que no se esperaba que permitiera el descubrimiento de la clave. Como la información que resulta de este proceso concede el descifrado de los mensajes, este es un caso particular de ...
12. Romper/descifrar un mensaje:Cualquier forma de deducir el contenido original de un mensaje encriptado solo por medio del mensaje encriptado en sí mismo y otras piezas de información que no se esperaban sean suficientes para la deducción del contenido original;
13. Rompiendo un Criptosistema: Descubrimiento de una forma sistemática de romper de manera factible cualquier mensaje cifrado por este método bajo cualquier parámetro;
14. Principio / Desideratum / Axioma / Ley de Kerckhoffs: Principio criptológico que lleva el nombre del criptógrafo holandés. Auguste Kerckhoffs, según el cual, para que un criptosistema se considere seguro, todo lo relacionado con él, excepto por sus claves (privadas), debe ser de conocimiento público;
15. Clave: Parametrización secreta de un criptosistema que le permite ser inadvertido (y consecuentemente interrumpido) por terceros mientras también es validado por la comunidad de criptoanalistas (de acuerdo con el principio de Kerckhoff);
16. Criptosistema simétrico: Cualquier criptosistema en el que cualquier parámetro para la codificación sea suficiente para deducir fácilmente el parámetro para la decodificación, y, por esta razón, debe mantenerse en privado. Uno puede reformularlo diciendo que los parámetros de cifrado y descifrado son ambos equivalentes a la clave;
17. Simetríco/Clave Pública del Criptosistema: Cualquier criptosistema para el que exista una forma de expresar los parámetros para la codificación que no sea suficiente para deducir factiblemente el parámetro correspondiente para la decodificación, lo que permite enviarlo a los aliados a través de un canal inseguro, o incluso hacerse público, y así crear un entorno seguro canal donde no había ninguno;
18. Clave Pública: Un componente de un criptosistema asimétrico que es suficiente para parametrizar el cifrado pero no es suficiente para deducir de manera factible el parámetro de descifrado, es decir, el ...
19. Llave Privada: Un componente de un criptosistema asimétrico que es suficiente para parametrizar el descifrado y, por lo tanto, debe mantenerse en privado y, por lo general, también es suficiente para parametrizar el cifrado;

---

^[1] Tenga en cuenta que, aquí, las frases decifrar o descifrar no se aplican, porque antes de que un criptosistema dado (con todos sus componentes, incluidas sus claves) esté bien definido, uno no puede clasificar un método dado de interpretación del mensaje original del encriptado como el comunicación intencionada (descifrado) o un ataque (descifrado).

^[2] Aunque existen técnicas para mejorar este trabajo de adivinación, todavía es mucho más difícil descubrir que multiplicarlas.

^[3] La primera inspiración fue mirar el árbol de la conjetura tau, un árbol infinito enraizado en el número 1, cuyos otros nodos consisten en enteros que resultan en una operación binaria de suma, resta, o multiplicación entre nodos previos, posiblemente un nodo operado consigo mismo. El objetivo de la teoría se relaciona con la profundidad, en este árbol, en la que cada entero aparece por primera vez. Aparentemente es difícil encontrar números grandes en ramas bajas (incluso si relajamos la necesidad), pero es inmediato verificar si una secuencia dada de operaciones efectivamente produce un resultado dado.

^[4] Este seguramente no es el enfoque más natural, pero al adoptar esto, uno se asegura de que este relleno de bytes (llamado relleno)…

1. Oculta el tamaño del relleno (de manera diferente, por ejemplo, de robo de texto cifrado) y oscurece el final del mensaje, lo que representa ataques de texto plano elegidos más difícil;
2. Mejora la distribución de bits tan cerca del uniforme como sea posible;

Si se sabía que los últimos bloques de cada mensaje estaban sistemáticamente predispuestos en una distribución que distaba de ser uniforme, un atacante podría aprovechar este hecho para realizar un criptoanálisis estadístico, ya que cualquier muestra de mensajes dada sería estadísticamente más representativa que lo contrario. En otras palabras, los últimos bloques son estadísticamente menos diversos, se convierten en los enlaces más débiles del mensaje.

^[5] No se equivoquen: este máximo divisor común es gaussiano, mientras que el anterior es real.

^[6]… que no es perfecto, porque fácilmente revela el hecho de que los últimos tres componentes son proporcionales a 1, 2 y 4. Pero, de nuevo, en aras de la simplicidad, ignoraremos este detalle.

^[7] … que es tan complejo que hay algunos casos notorios de falla al implementar y mantener protocolos basados en él.

^[8] Aquí, no adoptaremos el enfoque de Rocha de un bloque de combinaciones lineales múltiples, que también nos permite permutar aleatoriamente el bis para oscurecerlos aún más.

^[9] Aunque no totalmente al azar. Su transposición debe abarcar el subespacio generado por el vector $ e_1 = (1,0,…,0) $.