Encriptación simetrica

Los fundamentos matemáticos de la blockchain tienen sus raíces en un
área de las matemáticas llamada criptografía. En este post examinaremos estos fundamentos matemáticos. Aunque no se va a presentar la teoría matemática en un lenguaje matematico riguroso voy a intentar presentar la teoría de una manera comprensible. La meta es proporcionar una comprensión clara de los conceptos matemáticos subyacentes y su teoría. Esta será más que suficiente para permitir desarrollar aplicaciones de blockchain y criptomonedas con seguridad.

Como funciona la encriptacion simetrica

El cifrado simétrico o de clave única existe desde hace miles de años. El cifrado simétrico funciona de la siguiente manera: un mensaje (llamado texto sin formato) se cifra con una llave secreta. El proceso de cifrado convierte el texto sin formato en un mensaje confuso llamado texto cifrado. La clave secreta es simplemente una secuencia de caracteres o símbolos. Solo la persona que tiene la clave secreta puede decodificar el texto cifrado y recuperar el texto sin formato de origen. Matemáticamente, podemos representar el proceso de cifrado como:

c = E (k, p)

Aquí, E es el algoritmo de cifrado (función), k es la clave secreta y p es el texto sin formato. c es el texto cifrado producido por el algoritmo de cifrado. El proceso de descifrado se puede representar como:

p = D (k, c)

donde D es el algoritmo de descifrado. Tenga en cuenta que se utiliza la misma clave para el cifrado y descifrado. De ahí el término clave de cifrado simétrica.

Un ejemplo clásico de cifrado simétrico es el cifrado César, presuntamente utilizado por
Legiones romanas de Julio César. En este algoritmo de cifrado, cada carácter alfabético
en el texto plano se reemplaza por un carácter que está tres posiciones a la derecha (girando el comienzo del alfabeto, si es necesario) y los espacios entre palabras se ignoran. por ejemplo, la letra p se reemplaza por la letra s y la letra z se reemplaza por la letra c.
Por lo tanto, el texto sin formato al que ha llegado la legión se cifra de la siguiente manera:

texto sin formato:  la legión ha llegado
texto cifrado:  xkhohjlrqkdvduulzhg

Para descifrar este texto cifrado, simplemente reemplazamos cada carácter en el texto cifrado con el carácter que está a tres caracteres a su izquierda.

Diseño de algoritmos de encriptacion simetrica

Como hemos visto, el algoritmo de cifrado simetrico toma texto plano y una clave secreta como entradas y produce un texto cifrado como salida. El algoritmo de cifrado debe ser independiente tanto del texto plano como de la clave secreta. Normalmente, un algoritmo de cifrado consta de un número finito de rondas donde cada ronda es una secuencia finita de sustitución y operaciones de transposición. Una operación de sustitución sustituye a algún otro carácter un carácter de entrada en el texto, y una operación de transposición reorganiza o permuta una parte del texto de entrada. Cada ronda del algoritmo de cifrado confunde el texto sin formato hasta cierto punto, y esta salida distorsionada se convierte en la entrada para la siguiente ronda del algoritmo de cifrado. Para recuperar el texto sin formato del texto cifrado, las operaciones del algoritmo de cifrado deben ser reversibles. Por tanto, algoritmo de cifrado simplemente ejecuta las rondas y operaciones del algoritmo de cifrado a la inversa. El cifrado César que discutimos anteriormente es un cifrado de sustitución simple, y no hay operaciones de transposición.
Los algoritmos de cifrado simétrico vienen en dos tipos. Los cifrados de bloque dividen el
texto sin formato en bloques de longitud fija y cifran el texto sin formato un bloque a la vez. Actualmente los cifrados cifran el texto plano un byte a la vez y están destinados a cifrar la transmisión de datos a través de una red.
Diseñar un algoritmo de cifrado simétrico sólido que pueda soportar el criptoanálisis
es un esfuerzo no trivial y bastante complicado.
Hay dos formas principales de atacar un algoritmo de cifrado y así obtener la capacidad de descifrar mensajes codificados por el algoritmo. La promera técnica se basa en un ataque de fuerza bruta al algoritmo. Esta técnica intenta todas las posibles claves secretas hasta obtener un texto llano inteligible. La técnica no es factible si el espacio de claves es muy grande. Abajo muestra la relación entre el tamaño del clave de cifrado y el tiempo necesario para descifrar un mensaje con un ataque de fuerza bruta.

Esta tabla muestra que las claves más grandes ofrecen una mayor protección contra ataques de fuerza bruta que las claves más pequeñas.
La segunda vía de ataque se basa en el análisis estadístico del texto cifrado. En el idioma inglés aparecen con mayor frecuencia determinadas letras del alfabeto
que otras letras y ciertas palabras aparecen con mayor frecuencia que otras palabras.
Por ejemplo, en un párrafo de texto, la palabra «el» normalmente aparecerá con mayor
frecuencia que la palabra «oso hormiguero». Del mismo modo, ciertas combinaciones de dos letras aparecen con mayor frecuencia que otras combinaciones. Las combinaciones de tres letras (trígrafos) aparecen con mayor frecuencia que otras combinaciones. Abajo se muestra una tabla, tomada de un análisis de 40.000 palabras. Categoriza la frecuencia con la que aparecen las letras en una gran muestra de texto:

Un análisis de 40.000 palabras del idioma inglés también indica la frecuencia
distribución de los 12 dígrafos más comunes, como se muestra en la tabla de abajo:

El criptoanálisis aprovecha estas características estructurales del lenguaje para
descifrar el texto cifrado. Este análisis muestra que un buen algoritmo de cifrado implementa varios pasos de sustitución y transposición que alteran o enmascaran las caracteristicas del lenguaje. En el algoritmo de cifrado ideal, todos los dígrafos, trígrafos y las combinaciones de n letras deben tener la misma probabilidad de aparecer en el texto cifrado. Otras tecnicas de criptoanálisis aprovechan el orden de las palabras y las reglas gramaticales.

Otra propiedad deseable de un algoritmo de cifrado es que un pequeño cambio en
el texto sin formato debería provocar un gran cambio en el texto cifrado; esto se llama efecto avalancha. El efecto de avalancha frustra el criptoanálisis diferencial que intenta decodificar texto cifrado examinando cómo difieren los diferentes mensajes cifrados por el mismo algoritmo de cada uno de los mensajes.

Advanced Encryption Standard

El Estándar de cifrado avanzado (AES) es el algoritmo de cifrado simétrico recomendado por el Instituto Nacional de Estándares de EE. UU. En 1997, NIST anunció un algoritmo
competente para reemplazar el antiguo estándar de cifrado de datos. Cuatro años después, en 2001, AES fue elegido como el ganador entre varios diseños de cifrado competidores. AES es ampliamente utilizado por gobiernos e instituciones financieras de todo el mundo. Es de cifrado muy rapido. Debido a su pequeño tamaño, AES encuentra uso en dispositivos que van desde microcontroladores a las supercomputadoras. AES procesa bloques de texto plano de 128 bits y admite cifrado longitudes de clave de 128, 192 y 256 bits. Utiliza 10 rondas de cifrado si la clave seleccionada es 128 bits de longitud, 12 rondas si la clave es de 192 bits y 14 rondas si la clave es de 256 bits.
La Tabla de abajo enumera algunos de los algoritmos de cifrado simétrico más importantes como así como sus características.

el problema de la distribucion de claves

Para que una parte pueda descifrar un texto cifrado, debe poseer la clave secreta. El problema surge cuando una clave secreta debe distribuirse a un gran número de destinatarios. En tal caso, existe un peligro significativo de que una parte maligna pueda interceptar y apropiarse de la clave. El cifrado de clave simétrica no es una técnica adecuada cuandol la clave de cifrado debe distribuirse a un gran número de usuarios. La solución a este problema radica en una técnica criptográfica llamada cifrado de clave pública que examinaremos en otro post.

generadores de numeros pseudoaleatorios

Muchos algoritmos criptográficos requieren el uso de uno o más números aleatorios,
normalmente para inicializar un proceso con una semilla, generar claves, establecer un nonce etc. En lugar de obtener un número aleatorio muestreando algún proceso
en la naturaleza o en nuestra computadora, es una práctica común utilizar una función matemática para generar una secuencia de números pseudoaleatorios. Una función que genera tal secuencia se denomina generador de números pseudoaleatorios (PRNG). Un PRNG funciona como sigue. El PRNG se siembra con un número aleatorio que se llama semilla, y luego genera recursivamente una secuencia determinista de números. Ten en cuenta que, dada cierta semilla, el PRNG siempre generará la misma secuencia de números.

Un buen generador de números pseudoaleatorios tiene propiedades estadísticas que lo hacen muy difícil de distinguir de una secuencia de números aleatorios. En particular, en un PRNG de alta calidad, los números sucesivos no están correlacionados y el PRNG tiene una gran período antes de que los números comiencen a repetirse. El generador congruencial lineal (LCG) es un PRNG de uso común. Tiene un simple definición

Xn + 1 = (m * xn + a) mod P

P >= 2 es un número entero. P es el período del PRNG.
El coeficiente entero m se llama multiplicador; m> 0 y m <P.
El valor inicial del generador x0 es la semilla.
xn es el n-ésimo número pseudoaleatorio generado por la función.

Tenga en cuenta que LCG es una función recursiva. Es muy fácil de implementar y tiene la
ventaja de ser un generador rápido de números pseudoaleatorios. La aleatoriedad estadística de LCG es sensible al valor de módulo P y la semilla que se selecciona. La biblioteca GNU C , glibc, utiliza un período de 245, un valor multiplicador de 25214903917 y una semilla de valor de 11, en la especificación de su LCG.
El siguiente código implementa el generador de congruencia lineal en Python:

class LCG:
 def __init__(self,mult,addr,prd,seed):
    self.multiplier = mult
    self.addr = addr
    self.period = prd
    self.lastValue = seed
 def generator(self):
    self.lastValue = (self.multiplier*self.lastValue + self.addr) % self.period
    return self.lastValue
lcg = LCG(11, 37, 1000, 0)
ctr = 0
while ctr < 10:
    ret = lcg.generator()
    print(ret)
    ctr += 1

El Mersenne Twister es otro PRNG de interés de alta calidad. En su derivación más común, se siembra con el número primo de Mersenne 219937-1 y tiene un período de
219937 – 1.