Criptografía

La criptografía estudia las técnicas para hacer que la información en un mensaje se codifique y que sea más “difícil” de entender para el destinatario que no tiene una clave secreta para el descifrado de la información y así tener acceso a ella.

Cifrado por sustitución.

En un cifrado por sustitución, cada letra o grupo de letras se reemplazan por otra letra o grupo de letras para “disfrazarla”. Uno de los cifrados más viejos conocidos es el cifrado del César, atribuido a Julio César. En este cifrado, el alfabeto se desplaza un número igual a 3 utilizando mayúsculas. Es decir “a” se vuelve “D”, “b” se vuelve “E”…..y “z” se vuelve “C”. Por ejemplo “ataque” se convierte en “DWDTXH”.

Cifrado por transposición.

A diferencia de los algoritmos de sustitución en donde los caracteres que conforman el mensaje en claro son sustituidos por otros, los algoritmos de transposición los cambian de posición dentro del mismo mensaje dando lugar al criptograma el cual no puede ser comprendido a simple vista.

Criptosistemas de Clave Secreta.

Generalidades sobre sistemas de clave secreta.

Denominamos criptosistema de clave secreta (de clave privada, de clave única o simétrico) a aquel criptosistema en el que la clave de cifrado, , puede ser calculada a partir de la de descifrado, , y viceversa. En la mayoría de estos sistemas, ambas claves coinciden, y por supuesto han de mantenerse como un secreto entre emisor y receptor: si un atacante descubre la clave utilizada en la comunicación, ha roto el criptosistema. 

Hasta la década de los setenta, la invulnerabilidad de todos los sistemas dependía de este mantenimiento en secreto de la clave de cifrado. Este hecho presentaba una gran desventaja: había que enviar, aparte del criptograma, la clave de cifrado del emisor al receptor, para que éste fuera capaz de descifrar el mensaje. Por tanto, se incurría en los mismos peligros al enviar la clave, por un sistema que había de ser supuestamente seguro, que al enviar el texto plano. De todos los sistemas de clave secreta, el único que se utiliza en la actualidad es DES (Data Encryption Standard, que veremos más adelante); otros algoritmos de clave privada, como el cifrado Caesar o el criptosistema de Vigenère (serán también brevemente comentados más adelante) han sido criptoanalizados con éxito, lo cual da una idea del porqué del desuso en que han caído estos sistemas (con la excepción de DES, que es seguramente el algoritmo de cifra más utilizado en la actualidad). Por si esto no fuera suficiente, el hecho de que exista al menos una clave de cifrado/descifrado entre cada dos usuarios de un sistema haría inviable la existencia de criptosistemas simétricos en las grandes redes de computadores de hoy en día: para un sistema de computación con usuarios, se precisarían claves diferentes, lo cual es obviamente imposible en grandes sistemas. Todos estos motivos han propiciado que el estudio de los cifradores simétricos (excepto DES) quede relegado a un papel histórico. 

Los sistemas de cifrado de clave única se dividen a su vez en dos grandes grupos de criptosistemas: por una parte tenemos los cifradores de flujo, que son aquellos que pueden cifrar un sólo bit de texto claro al mismo tiempo, y por tanto su cifrado se produce bit a bit, y por otro lado tenemos los cifradores de bloque, que cifran un bloque de bits (habitualmente, cada bloque es de 64 bits) como una única unidad

 Algoritmo DES (Data Encryption Standard).

Se trata de un sistema de cifrado simétrico por bloques de 64 bits, de los que 8 bits (un byte) se utilizan como control de paridad (para la verificación de la integridad de la clave). Cada uno de los bits de la clave de paridad (1 cada 8 bits) se utiliza para controlar uno de los bytes de la clave por paridad impar, es decir, que cada uno de los bits de paridad se ajusta para que tenga un número impar de "1" dentro del byte al que pertenece. Por lo tanto, la clave tiene una longitud "útil" de 56 bits, es decir, realmente sólo se utilizan 56 bits en el algoritmo.

El algoritmo se encarga de realizar combinaciones, sustituciones y permutaciones entre el texto a cifrar y la clave, asegurándose al mismo tiempo de que las operaciones puedan realizarse en ambas direcciones (para el descifrado). La combinación entre sustituciones y permutaciones se llama cifrado del producto.

La clave es codificada en 64 bits y se compone de 16 bloques de 4 bits, generalmente anotadas dek1 a k16. Dado que "solamente" 56 bits sirven para el cifrado, ¡puede haber hasta 256 (o 7.2*1016) claves diferentes!

Cifradores de mochila de Merkle-Hellman.

Los sistemas criptográficos basados en el problema de la mochila y válidos para ocultar el mensajes y proveer a la vez de autenticación, tienen el inconveniente de que se resuelven en tiempo polinómico [DENN 83].

Este criptosistema ha caído en desuso debido a que la mayoría de sus implementaciones han sido rotas por criptoanálisis [SHAM 84], no obstante aún existen algunos criptosistemas basados en el que aquí se presenta que todavía son seguros, aunque muy poco utilizados.

Definición: El problema de la mochila tramposa o mochila simple o mochila fácil, puede plantearse en los siguientes términos: sea W={w1, w2, …, wn } un conjunto finito dado de números enteros, y sea s = wi1 + … + wit, con i1<…< it, una subsuma de elementos de W. Se trata de determinar el subconjunto U={wi1, …, wit } de W, conocido W y s. El nombre de mochila asignado al problema se debe a que s puede pensarse como la capacidad de una mochila, y los elementos de W como los tamaños de diferentes objetos; se trata entonces de saber si la mochila se puede llenar con un número exacto de objetos y determinar qué objetos son éstos.

Dado que W es finito, también lo es el número de posibles subconjuntos, por tanto el problema se puede resolver en tiempo finito, aunque la dificultad estriba en hacerlo de forma eficiente, es decir, en un tiempo razonable.

Ejemplo: Si tenemos que W={1, 3, 4, 5, 7, 10, 12, 15, 21, 26} y un subconjunto de él U={3, 4, 7, 10, 21, 26} cuya suma es s=71, conocido W y s resulta complicado determinar U.

Conviene señalar que puede haber dos subconjuntos de W con la misma suma, y que para determinados conjuntos W es muy sencillo encontrar la solución. Por ejemplo, si W=(1, 2, 22, 23, …,2k,…) entonces basta con calcular la expresión de s en base binaria.

Ejemplo: Si tenemos que W={1, 2, 4, 8, 16} y s=12, como 12 en base 2 es 01100, concluimos que el subconjunto que buscamos es {4, 8}.

Definición: Una sucesión de números enteros w1 < w2 < … < wk < … se dice supercreciente o una sucesión de crecimiento rápido, si se verifica que wi+1 > w1 + …+ wi , para todo i. Si W = {w1, …, wn } es una parte de una sucesión supercreciente y se conoce la suma s de un subconjunto de W, es fácil determinar dicho subconjunto. Basta considerar el mayor elemento de W menor que s, wit , luego el mayor elementos de W menor que s – wit , wi(t-1) , y así sucesivamente. Es claro que para el problema de la mochila 0 < w1.

Ejemplo: W={1, 2, 3, 6, 12, 25, 53}, se puede comprobar que wi+1 > w1 + …+ wi , para todo i y por tanto la serie es supercreciente, elegimos el subconjunto U={2, 6, 12, 53} que tiene por suma s=73. Aplicamos el resultado anterior y tenemos que 73 – 53 = 20 > 0, por tanto el 53 es parte del subconjunto, 20 – 25 = -5 < 0, por tanto 25 no es parte de U, 20 – 12 = 8 > 0, por tanto 12 es parte del subconjunto, 8 – 6 = 2 > 0, por tanto 6 es parte de U y por último 2 también es parte del subconjunto. Hemos determinado el subconjunto U={2, 6, 12, 53} fácilmente gracias a la propiedad de supercrecimiento.

Algoritmo de Merkle-Hellman (M-H) y su seguridad

Algoritmo de Merkle – Hellman

Este método se basa en el problema NP-completo de la mochila de tipo 0-1 o problema de la mochila fácil y su mayor atractivo es su fácil implementación en un programa y su gran rapidez, unas 100 veces más rápido que el RSA. También hay que decir que para cifrar bloques de 200 bits (n = 200) en el sistema de la mochila se tiene que almacenar el vector mochila W = (w1 , …, wn ) y requiere del orden de 80 Kb, si consideramos que cada wies, de media, de 400 bits, mientras que con el RSA necesitaríamos, solamente, 1 Kb para almacenar su clave.

Dado C un entero positivo, W = (w1, …, wn ) un vector con componentes wi enteros positivos para todo i. Se trata de encontrar M = (m1 , …, mn), mi = 0 ó 1, 1< i < n, Tal que C = M·W ó C = m1 w1 + … + mn wn.

Criptosistemas de Clave Pública.

En un sistema de cifrado con clave pública, los usuarios eligen una clave aleatoria que sólo ellos conocen (ésta es la clave privada). A partir de esta clave, automáticamente se deduce un algoritmo (la clave pública). Los usuarios intercambian esta clave pública mediante un canal no seguro.

Cuando un usuario desea enviar un mensaje a otro usuario, sólo debe cifrar el mensaje que desea enviar utilizando la clave pública del receptor (que puede encontrar, por ejemplo, en un servidor de claves como un directorio LDAP Lightweight Directory Access Protocol (en español Protocolo Ligero/Simplificado de Acceso a Directorio). El receptor podrá descifrar el mensaje con su clave privada (que sólo él conoce).

Introducción a la cifra con clave publica.

El principio del cifrado asimétrico (conocido como cifrado con clave pública) apareció en 1976, con la publicación de un trabajo sobre criptografía. 

En un criptosistema asimétrico (o de clave pública), las claves se dan en pares: 

• Una clave pública para el cifrado; 
• Una clave secreta para el descifrado.

El uso de claves asimétricas ralentiza el proceso de cifrado. Para solventar dicho inconveniente, el procedimiento que suele seguirse para realizar el cifrado de un mensaje es utilizar un algoritmo de clave publica junto a uno de clave simétrica. A continuación veremos como se produce el cifrado de un mensaje, mediante el cual obtenemos plena garantía de confidencialidad.

Protocolo de Diffie y Hellman para el intercambio de claves.

El ser humano ha estado buscando la forma de transmitir un secreto de una manera segura a través de un canal inseguro, por ejemplo intercambiar una clave secreta entre dos interlocutores que se encuentran físicamente distantes. Pero no es hasta noviembre de 1976 cuando dos investigadores de la Universidad de Stanford, Whitfield Diffie y Martin Hellman, proponen un algoritmo para intercambiar una clave secreta de manera computacionalmente segura, usando para ello funciones matemáticas de un solo sentido o unidireccionales.

Este protocolo se utiliza principalmente para intercambiar claves simétricas de forma segura para posteriormente pasar a utilizar un cifrado simétrico, menos costoso que el asimétrico. Se parte de la idea de que dos interlocutores pueden generar de forma conjunta una clave sin que esta sea comprometida.

Diffie-Hellman (DH) no es un mecanismo de cifrado y no se suele utilizar para cifrar datos. En cambio, es un método para intercambiar con seguridad las claves que cifran datos. Los algoritmos (DH) permiten que dos partes establezcan la clave secreta compartida que usan el cifrado y los algoritmos de hash.

Estructuras generadoras de secuencias cifrantes.

Las claves pueden ser creadas por el usuario o generadas automáticamente con la ayuda de generadores de claves los cuales se clasifican en dos tipos:

Generadores aleatorios: para generar secuencias cifrantes utilizan datos provenientes de ruido físico aleatorio (ruido de un micrófono, ruido térmico en un semiconductor, etc.) o bien provenientes del estado de una computadora (interrupciones, posición del ratón, actividad en la red, uso del teclado, etc.). Es conveniente combinar varias técnicas para que la secuencia resultante sea imposible de predecir. Este tipo de generadores se utilizan para generar claves cortas.

Generadores pseudoaleatorios: este tipo de cifradores no son totalmente aleatorios ya que para generar una secuencia obedecen a algún algoritmo o cierto procedimiento repetitivo.

La distribución de claves se refiere a los medios utilizados para distribuir una clave a dos entidades que quieran intercambiar datos. La distribución de claves es un tema primordial en un sistema de cifrado ya que de ello depende que las claves sólo sean conocidas por las entidades indicadas y así el método de cifrado sea efectivo.

Técnicas de Distribución de Claves:

• Distribución manual
• Distribución basada en centro
• Distribución basada en certificad

LFSR (linear feedback shift register).

Que se traduce como: registro de desplazamiento con retroalimentación lineal. Es un registro de desplazamiento en el cual la entrada es un bit proveniente de aplicar una función de transformación lineal a un estado anterior.

El valor inicial se denomina semilla y, como la forma de operar el registro es determinista, la secuencia de valores producidos está completamente determinada por el estado actual o el estado anterior. La secuencia tiene un periodo de repetición, es decir que la secuencia vuelve a generarse y se repite indefinidamente. Cuando el periodo de repetición es máximo, ese LFSR tiene interés criptográfico.

NLFSR (No-Lineal Feedback Shift Register).

Un es un componente común en los modernos sistemas de cifrado de flujo , especialmente en RFIDy tarjetas inteligentes aplicaciones. NLFSRs son conocidos por ser más resistente a los ataques que criptoanalíticos Registros Feedback Shift lineales ( LFSRs ). Se sabe cómo generar un n -bit NLFSR longitud máxima de 2 n , generando una secuencia de Brujin, mediante la extensión de un LFSR de longitud máxima con n etapas; , pero la construcción de otros NLFSRs grandes con largos períodos garantizados sigue siendo una problema abierto. El uso de métodos de fuerza bruta, una lista de máximo período de n -bit NLFSRs para n <25 se ha hecho , así como para n = 25 y n = 27.

Cifrados en flujo con registros de desplazamiento.

El cifrado de flujo es un tipo de cifrado en el cual el mensaje es cifrado bit por bit a traves de la operación XOR con el bit correspondiente del flujo clave S.

Este cifrado es la contra parte al cifrado por bloques, y es muy utilizado en el área de telecomunicaciones, mas específicamente se puede hablar de la telefonía móvil. En una llamada, la voz se digitaliza, es decir, se convierte en un flujo de bits. y este se encripta para ser enviado, la ventaja principal es que este cifrado funciona en tiempo real, ademas de ser lo suficientemente rápido como para mantener una comunicación fluida e ininterrumpida.

La fortaleza de los cifrados de flujo son los flujos claves, o llaves, esta es un flujo de bits de una longitud tan larga en ocasiones como el largo del flujo del mensaje, y se genera a través de un generador pseudo-aleatorio. Este generador generara un flujo al parecer aleatorio, pero que en un punto determinado, volverá a repetir la secuencia. este punto se determina dentro del mismo generador.

Criptosistemas de Cifrado en Flujo.

Los cifradores en flujo están formados por: 

• Un generador de claves: a partir de una clave de inicialización K produce una secuencia de bits igual a la longitud del mensaje, dicha secuencia de bits es empleada como la clave en el proceso de cifrado ⁄ descifrado. Tanto emisor como receptor cuentan con un generador de claves, los cuales producen claves idénticas en ambos extremos de la comunicación. 
• El algoritmo de cifrado: realiza operaciones elemento a elemento, es decir que el algoritmo de cifrado se va aplicando a un elemento de información del MCla con un elemento de la clave (ya sean bits o caracteres según se esté trabajando), para obtener así el criptograma. 

Los cifradores en flujo son apropiados para utilizarlos en los sistemas de comunicaciones de tiempo real, como lo es la telefonía móvil digital, debido a que el proceso de cifrado ⁄ descifrado se realiza elemento a elemento.

Cifradores con clave continua de un solo uso.

El método de cifrado One Time Pad es un cifrado de flujo adicional binario, donde se genera un flujo de claves aleatorias reales y luego se combina con el texto en claro para su cifrado o con el texto cifrado para su descifrado a través de una adición “OR-exclusiva” (XOR).

Se puede demostrar que un esquema de cifrado de flujo es inviolable si se cumplen las siguientes condiciones previas:

• La clave debe ser tan larga como el texto en claro.
• La clave debe ser realmente aleatoria.
• La clave debe utilizarse solo una vez.

EL PROCESO DE CIFRADOLas claves del One Time Pad se utilizan en pares. Cada usuario guarda una copia de la clave y las claves se distribuyen de un modo seguro antes del cifrado. 

La confidencialidad y autenticidad de las claves One Time Pad están garantizadas a través de una protección continua durante su distribución y almacenaje. Esto garantiza que los intrusos no puedan hacer un uso incorrecto de la clave.

Para cifrar datos de texto en claro, el remitente utiliza una cadena de clave que tiene la misma longitud que el texto en claro. La clave se utiliza mezclando (através del cifrado XOR) bit por bit, siempre un bit de la clave con un bit del texto en claro para crear un bit de texto cifrado.

A continuación, el texto cifrado se envía al destinatario.

Por parte del destinatario, el mensaje codificado está mezclado (a través del cifrado XOR) con la copia duplicada de la clave de utilización única y se ha restaurado el texto en claro.

Tanto la clave del remitente como la del destinatario se destruyen automáticamente una vez se han utilizado, para garantizar que no se pueda volver a aplicar la misma clave.

 Postulados de Golomb para secuencias cifrantes.

Son herramienta que ayudan a determinar la calidad y seguridad de una secuencia en términos de aleatoriedad (primero y seguno postulados) y su impredecibilidad (tercer postulador).

Golomb estableció tres postulados que debe cumplir una secuencia binaria para considerarse pseudoaleatoria, a continuación se exponen concretamente cada uno de dichos postulados:

• G1: la probabilidad de aparecer a lo largo de la secuencia es igual para unos y ceros, es decir que el número de unos debe ser igual al número de ceros o bien la diferencia debe ser de uno.
• G2: un cero tiene la misma probabilidad que un uno de aparecer después de un cierto n-grama (muestra de n dígitos consecutivos).
• G3: el cómputo de coincidencias entre una secuencia y su versión desplazada no debe aportar ninguna información sobre el período de la secuencia.

Modos de cifra en bloque.

En criptografía, una unidad de cifrado por bloques es una unidad de cifrado de clave simétrica que opera en grupos de bits de longitud fija, llamados bloques, aplicándoles una transformación invariante. Al realizar el cifrado, la unidad de cifrado por bloques toma como entrada un bloque de texto plano (o claro) y produce un bloque cifrado de igual tamaño. La transformación exacta es controlada utilizando una segunda entrada: la clave secreta provista por el usuario.

Para realizar el proceso inverso, el descifrado, se ingresa un bloque de texto cifrado y se produce el texto plano original. El cifrado por bloques se diferencia del cifrado por flujo (stream ciphers) en que, en este último, opera en dígitos individuales, uno tras otro, y la transformación varía durante el proceso de cifrado.

El Data Encryption Standard (DES) fue un diseño de unidad de cifrado por bloques de gran influencia. Fue desarrollado y publicado por IBM y publicado como estándar en 1977. El Advanced Encryption Standard (AES) es un sucesor de DES, adoptado en 2001.

Algoritmo IDEA (International Data Encryption Algorithm).

Es un cifrador por bloques diseñado por Xuejia Lai y James L. Massey de la Escuela Politécnica Federal de Zúrich y descrito por primera vez en 1991. IDEA fue diseñado en contrato con la Fundación Hasler, la cual se hizo parte de Ascom-Tech AG.

IDEA es libre para uso no comercial, aunque fue patentado y sus patentes se vencerán en 2010 y 2011. El nombre "IDEA" es una marca registrada y está licenciado mundialmente por MediaCrypt. IDEA fue utilizado como el cifrador simétrico en las primeras versiones de PGP (PGP v2.0) y se lo incorporó luego de que el cifrador original usado en la v1.0 ("Bass-O-Matic") se demostró insegura. Es un algoritmo opcional en OpenPGP.

IDEA es un algoritmo bastante seguro, y hasta ahora se ha mostrado resistente a multitud de ataques, entre ellos el criptoanalisis diferencial. No presenta claves debiles, y su longitud de clave hace imposible en la practica un ataque por la fuerza bruta. Como ocurre con todos los algoritmos sim_etricos de cifrado por bloques, IDEA se basa en los conceptos de confusion y difusion, haciendo uso de las siguientes operaciones elementales (todas ellas faciles de implementar):

XOR.

Suma modulo 2 (base 16)

Producto modulo 2 (base 16) + 1

El algoritmo IDEA consta de ocho rondas. Dividiremos el bloque X a codicar, de 64 bits, en cuatro partes X1, X2, X3 y X4 de 16 bits. Denominaremos Zi a cada una de las 52 subclaves de 16 bits que vamos a necesitar. Las operaciones que llevaremos a cabo en cada ronda son las siguientes:

•  Multiplicar X1 por Z1.
•  Sumar X2 con Z2.
•  Sumar X3 con Z3.
•  Multiplicar X4 por Z4.
•  Hacer un XOR entre los resultados del paso 1 y el paso 3.
•  Hacer un XOR entre los resultados del paso 2 y el paso 4.
•  Multiplicar el resultado del paso 5 por Z5.
•  Sumar los resultados de los pasos 6 y 7.
•  Multiplicar el resultado del paso 8 por Z6.
•  Sumar los resultados de los pasos 7 y 9.
•  Hacer un XOR entre los resultados de los pasos 1 y 9.
•  Hacer un XOR entre los resultados de los pasos 3 y 9.
•  Hacer un XOR entre los resultados de los pasos 2 y 10.
•  Hacer un XOR entre los resultados de los pasos 4 y 10.

La salida de cada iteracion seran los cuatro sub-bloques obtenidos en los pasos 11, 12, 13 y 14, que seran la entrada del siguiente ciclo, en el que emplearemos las siguientes seis subclaves, hasta un total de 48. Al final de todo intercambiaremos los dos bloques centrales (en realidad con eso deshacemos el intercambio que llevamos a cabo en los pasos 12 y 13). Despues de la octava iteracion, se realiza la siguiente transformacion:

•  Multiplicar X1 por Z49.
•  Sumar X2 con Z50.
•  Sumar X3 con Z51.
•  Multiplicar X4 por Z52.

Las primeras ocho subclaves se calculan dividiendo la clave de entrada en bloques de 16 bits. Las siguientes ocho se calculan rotando la clave de entrada 25 bits a la izquierda y volviendo a dividirla, y asi sucesivamente. Las subclaves necesarias para descifrar se obtienen cambiando de orden las Zi y calculando sus inversas para la suma o la multiplicacion. Puesto que 216 + 1 es un numero primo, nunca podremos obtener cero como producto de dos numeros, por lo que no necesitamos representar dicho valor. Cuando estemos calculando productos, utilizaremos el cero para expresar el numero 216 un uno seguido de 16 ceros. Esta representacion es coherente puesto que los registros que se emplean internamente en el algoritmo poseen unicamente 16 bits.

 Algoritmo AES (Advanced Encryption Standard). 

El Estándar de cifrado de datos (DES, del inglés Data Encryption Standard) es un algoritmo criptográfico diseñado para cifrar y descifrar datos utilizando bloques de 8 bytes y una clave de 64 bits.

EL DES triple (DES3) es una variación de en la que se utilizan claves de 64 bits para una clave de 192 bits. DES3 funciona cifrando primer lugar el texto sin formato utilizando los 64 primeros bits de la clave. Después el texto cifrado se descifra utilizando la siguiente parte de la clave. En el paso final, el texto cifrado resultante se vuelve a cifrar utilizando la última parte de la clave.

El Estándar de cifrado avanzado (AES, del inglés Advanced Encryption Standard) es un algoritmo de sustitución utilizado por el gobierno de los Estados Unidos.

Dos modalidades de cifrado son:

• Modalidad de bloques, un método de cifrado en el que el mensaje se divide en bloques y el cifrado se realiza individualmente en cada bloque. Puesto que cada bloque tiene, como mínimo, una longitud de 8 bytes, la modalidad de bloques permite la digna aritmética de 64 bits en el algoritmo de cifrado.
• Modalidad de secuencia, un método de cifrado en el que se cifra cada byte individualmente. Se considera generalmente una forma de cifrado débil.

Blowfish es un cifrado de bloques que funciona en bloques de datos de 64 bits (8 bytes). Utiliza una clave de tamaño variable, aunque normalmente las claves de 128 bits (16 bytes) se consideran buenas para un cifrado fuerte. Blowfish se puede utilizar en las mismas modalidades que DES.