Fundamentos de criptografía

Definiciones:

Como se observa en la definición de E y D, al descifrar el mensaje cifrado con la clave k se ha de obtener el mismo mensaje que se utilizó para generar el mensaje cifrado.

Los criptosistemas se engloban en dos grandes grupos:

Teoría de la información

Cantidad de información

Definiremos cantidad de información como una medida de la disminución de la incertidumbre acerca de un suceso. La cantidad de información aportada por el suceso presenta una relación inversa respecto su probabilidad de ocurrencia.
Ii=-log2(P(xi))

Entropía

La entropía es un concepto que aparece en diversas ramas de la ciencia, como por ejemplo la termodinámica.
Dentro de la teoría de la información, la entropía será la medida del desorden de la información. La entropía H de un sistema viene definida por la suma de los productos de la probabilidad de cada suceso por su cantidad de información:
La entropía siempre será de 0<=H<=log2(N)  bits, siendo N el número de mensajes distintos. Además, será máxima cuando los sucesos sean equiprobables.

Redundancia

La entropía es un indicador de la redundancia de la información.
Definiremos índice de un lenguaje para mensajes de longitud k rk=Hk(M)/k. Éste índice indica el número de bits de información que aporta cada símbolo del mensaje de longitud k.
El índice absoluto del un lenguaje será R=log2(m), siendo m el número de símbolos del alfabeto de dicho lenguaje y suponiendo una distribución equiprobable. Este índice indica el número máximo de bits que se pueden codificar por cada símbolo.
La redundancia de un lenguaje se define como D=R-r
El índice máximo teórico de compresión de la información del mensaje M vendrá indicado por el índice de redundanciaI=D/r, haciendo especial hincapié en que éste índice es específico del mensaje y, dependiendo de la representatividad del mensaje dentro del lenguaje, será más o menos similar al índice de redundancia del lenguaje.

Entropía para dos variables

Definiciones previas: Con ello, podemos formular dos expresiones nuevas para la entropía:

Si X e Y son independientes entonces H(X//Y)=H(X)

Definiciones:

Técnicas básicas para ocultar la redundancia:

Matemática discreta

Aritmética modular

Trabaja con conjuntos de números restringidos a un tamaño delimitado, como por ejemplo aquello que se pueden formar con enteros de 8 bits, en este caso hablaríamos de aritmética módulo 256)

Definiciones básicas:

MCD (algoritmo de Euclides)

Para el cálculo del Máximo Común Divisor entre dos números.
Si m|a (m divida a a) y m|b ? m|(a-kb)?m|(a mod b)?m|(b mod c)
 
int euclides(int a, int b)
{
 int r;

 while(b) {
  r=a%b;
  a=b;
  b=r;
 }
 return a;
}
 

Inversas

MCD(a,n)=1->a tiene inversa mod n, es decir, . Y se dice que a y n son primos entre sí.

Función de Euler

Denominaremos Conjunto de Residuos CD={1,2,...,n-1}
Denominaremos Conjunto Reducido de Residuos de módulo n a todos los números primos entre sí. Por ejemplo, para n=12 CRR={1,5,7,11}
El cardinal de CRR se denomina función de Euler phi(n)
  siendo pi los factores primos de n y ei su multiplicidad.

Ejemplo: 

Teorema: si mcd(a,n)=1->mcd(a,n)=1->a^-1==1(mod n) . Por ello podremos calcular inversas: 

Problemas computacionales

Exponenciación Rápida


 
int exp_rapida(int a, int b)
{
 int z, x, res;

 z=b;
 x=a;
 res=1;

 while(z>0) {
  if((z%2)==1)
   res*=x;
  x*=x;
  z/=2;
 }
 return res;
}

Logaritmos Discretos

Es el problema inverso a la exponenciación.
Actualmente no se conoces algoritmos rápidos para calcular estos logaritmos por lo que su cálculo es computacionalmente costosísimo.

Números primos

Test de primalidad por el Método de Lehmann

Se trata de uno de los métodos probabilísticos más sencillos para determinar si un número p es primo. El algoritmo es el siguiente:
  1. escogemos un número aleatorio tal que a<p
  2. calculamos b=a^((p-1)/2)(mod p)
  3. si b<>1 (mod p) y b<>-1 (mod p), p no es primo
  4. en caso contrario existe un mínimo del 50% de probabilidad de que p sea primo

Generación de primos muy grandes

Para generar un número primo de n bits se suele utilizar el siguiente procedimiento.
  1. generamos un número aleatorio de n bits asegurándonos de poner a 1 su bit más significativo y su bit menos significativo (recordar que todos los números primos son impares).
  2. Intentaremos dividir el número obtenido por una tabla de primos precalculados (normalmente se suele probar con los primos menores de 2000).
  3. Aplicamos un test de primalidad un número razonable de veces (por ejemplo 10 o 20)
  4. Si tras el test obtenemos que el número no es primo, incrementamos el número en dos unidades y repetimos el paso 2.

Primos Fuertes

Se dice que dos números son primos fuertes entre sí si se cumple:
  1. MCD((p-1),(q-1)) es pequeño
  2. p-1 y q-1 tienen algún factor f’, q’ muy grande
  3. p’-1 y q’-1  tienen algún factor primo muy grande
  4. p’+1 y q’+1 tienen algún factor primo muy grande

Criptografía clásica

Conocemos aplicaciones criptográficas ya desde la época de Julio César.
Algunos de los primeros algoritmos criptográficos:

Criptografía actual

Criptografía de Clave Privada

Redes de Freistel

La red de Freistel es una estructura de cifrado empleada en muchos algoritmos. Presenta la interesante característica de ser reversible, es decir, de poder descifrar lo cifrado utilizando la misma estructura con tan solo invertir el orden de las claves k.
La estructura de una Red Freistel típica es la siguiente:
L y M son las dos partes en que se divide el mensaje a cifrar.

Algoritmo DES (Data Encryption Standard)

Se trata del algoritmo de cifrado más extendido hoy en día.
El algoritmo de cifrado es el siguiente:

Las claves están formadas por 64 bits de los cuales 8 son de paridad. Se obtienen de la siguiente forma:

Existen una serie de claves que son consideradas débiles y por ello se debe de evitar su utilización.

Actualmente el DES con clave de 56 bits es inseguro frente a ataques de fuerza bruta. En todos sus años de existencia no se le han encontrado debilidades en cuanto a su diseño por lo que se han ideado formas de alargar la clave, haciéndolo por tanto resistente a ataques por fuerza fruta. En concreto el Triple-DES que utiliza una clave de 168 bits fraccionada en tres claves independientes de 56 bits que se utilizan, sucesivamente, para cifrar la misma información.

Criptografía de Clave Pública

Los algoritmos de clave pública son mucho más lentos que los algoritmos de clave privada por la gran longitud de la clave (necesaria para dotarlos de seguridad) de un mínimo de unos 1024 bits así como por la complejidad de cálculo.
Es por ello que, habitualmente, en lugar de cifrar asimétricamente  todo el mensaje, éste se cifra simétricamente y lo que se cifra asimétricamente es la clave privada utilizada en el cifrado simétrico.
Las dos grandes aplicaciones de la criptografía de clave pública son:


Uno de los grandes problemas de la criptografía de clave pública es el de la autenticidad de las claves públicas. Supongamos que A se comunica con criptografía asimétrica con B. ¿Cómo sabemos que la llave pública de A PA que tiene B es auténtica? Más adelante veremos formas de dar solución a este problema.

Algoritmo RSA (Rivest, Shamir, Adleman)

Es uno de los algoritmos asimétricos más sencillos de implementar. Pese a ello es unas 1000 veces más lento que el DES.
Sus especificaciones las podemos encontrar en el documento PKCS#1 de RSA Laboratorios.
Una clave RSA de 512 bits viene ofrecer la misma seguridad que una clave DES de 56 bits ?clave débil. A partir de 786 bits de clave RSA ya se comienza a considerar seguro, aunque hoy en día ya comienzan a ser típicas claves de 1024 o 2048 bits.

Protocolos criptográficos y estándares

 Modos de Cifrado por Bloques

ECB (Electronic CodeBook)

El mensaje a cifrar se divide en bloques de longitud fija (normalmente de 8 bytes) y se cifran éstos por separado con la misma clave. Presenta la ventaja de que si hay una alteración del mensaje cifrado únicamente afectará a algunos de sus bloques. Por el contrario, su principal defecto reside en que bloques iguales presentarán el mismo código cifrado. Otro gran problema es que un atacante que intercepte el mensaje cifrado podrá alterar el orden de los bloques sin problemas e incluso substituirlos por otros distintos.

2.6.1.2 CBC (Cipher Book Chaining mode)

En éste método cada bloque cifrado se realimenta  con una operación XOR al bloque siguiente para a continuación cifrarlo. Su esquema de funcionamiento para el cifrado y el descifrado es el siguiente:
La principal ventaja es que los bloques iguales ya no se cifrarán de la misma forma (salvo que los primeros n bloques de dos mensajes distintos sean iguales; esto se soluciona fácilmente introduciendo al comienzo del mensaje un bloque con información aleatoria). Si se produjese un error en la transmisión, éste sólo afectaría a un total de dos bloques consecutivos

2.6.1.3 CFB (Cipher FeedBack mode)

Este método se utiliza en aquellas aplicaciones que necesitan cifrar y transmitir bytes discretos en lugar de bloques. Para ello utilizaremos un registro de desplazamiento y la operación XOR tal y como indica el siguiente esquema:

2.6.2  Definiciones básicas

Aplicaciones criptográficas en comunicaciones (clave pública):

Suponemos un emisor A que quiere enviar un mensaje a los rceptores B, C y D

Cifrado del mensaje

A genera una llave de sesión y cifra el mensaje en clave privada utilizando esa llave de sesión.
A cifra en clave pública la llave de sesión utilizando la clave pública de B. Hará lo mismo para C y para D.
A envía el mensaje cifrado a los destinatarios agregando las diversas claves de sesión cifradas para cada uno de los destinatarios.
Para descifrar el mensaje B, C o D utilizarán sus respectivas claves privadas para descifrar la clave de sesión y con ella podrán descifrar el mensaje.

Firmado del mensaje

En este caso se pretende demostrar la autenticidad del mensaje.
A calcula el resumen del mensaje y lo cifra utilizando su propia clave privada.
B, C y D podrán comprobar la autenticidad del mensaje calculando el resumen del mensaje y comparándolo con el resumen que A cifró. Para descifrarlo utilizará la clave pública de A.
Si el resumen calculado y el transmitido es igual entonces se podrá afirmar que el mensaje es auténtico.
Resulta importante insistir en que la finalidad de de la firma es la de permitir demostrar la autenticidad del mensaje. Así se ha de poder acceder al mensaje firmado incluso si no se dispone de las herramientas criptográficas necesarias para la comprobación de la firma.

Cifrado y firmado del mensaje

Este caso es una combinación de los dos anteriores.
Con objeto de no dar ninguna información al posible intruso, firmaremos primero el mensaje y después cifraremos el conjunto.
Tanto para firmar como para cifrar utilizaremos las técnicas descritas anteriormente.

Métodos para la autentificación de las claves públicas

Para cerciorarnos de que una clave pública pertenece efectivamente a quién afirma poseerla tenemos dos grandes posibilidades:
  1. contacto directo con esa persona, por ejemplo en persona o por teléfono
  2. confianza en un tercero que acredite la pertenencia (notario): autoridades certificadoras

 Certificados X509

El estándar X509 es el de utilización más extendida para la certificación de personas y entidades.
Los certificados X509 son objetos públicos.
Los campos más importantes de un certificado X509 son los siguientes:

Estructura del X509

Un certificado X509 está formado por la agrupación de varios campos. La estructura típica será: El campo DN (Distinguished Name) está a su vez formado por varios campos. Los más habituales son: Los certificados de las autoridades certificadoras (CA) los pueden firmar otras CA o pueden estar firmados por sí misma (autofirmado).
Por tanto cualquier CA podrá certificar a personas, entidades u otras CA, indistintamente.

Obtención de un certificado

El principal problema de los certificados es su obtención e instalación.
Para obtenerlos la autoridad certificadora debería de asegurarse de forma fiable de que quién le pide el certificado y quién lo recibe es la misma persona o entidad.
Para instalarlos, deberíamos de cerciorarnos de que podemos confiar tanto en la autoridad certificadora como del propietario del mismo.

Los pasos para la obtención de un certificado son los siguientes:

  1. decidir los datos personales que aparecerán en el certificado
  2. decidir el algoritmo de clave pública (normalmente será el RSA)
  3. generar el par de llaves pública-privada: el estándar indica que los debería de generar el interesado. La legislación española reconoce el derecho del usuario a generar su propia clave privada. En cualquier caso la autoridad certificadora jamás debería de conocer la clave privada del certificado, de otra forma podrá descifrar nuestros mensajes e incluso suplantar nuestra identidad.
  4. petición del certificado a la autoridad certificadora. El PKCS#10 de RSA Laboratorios define la estructura del Certificate Request (CR). El procedimiento es el siguiente:
    1. el usuario genera el par de claves. Con ellas firma el CR (que ya estará completado con sus datos). De esta forma la autoridad certificadora sabrá que el poseedor de la clave pública es quien ha fabricado y firmado el CR.
    2. Tras la recepción del CR la autoridad decide si emitir o no el certificado. Si decide certificar, emitirá un documento de carácter legal especificando qué se certifica.
    3. Una vez todo esté correcto la CA entregará al cliente el certificado, bien de forma personal, o bien a través de la web u otros medios.


En el PKCS#12 se propone un objeto destinado al transporte de información personal protegido por contraseña.

Utilización de los certificados

Para el trabajo cotidiano con certificados se utilizan dos bases de datos de certificados: Los certificados apuntarán a sus autoridades certificadoras.

Además existen otras dos bases de datos:

Cada uno de los certificados propios tendrá una llave privada.

Revocación de  los certificados

Es fundamental especialmente si la clave privada ha sido comprometida.
En la base de datos de la autoridad certificadora se marca el certificado afectado como revocado.

Ahora el problema reside en la comprobación de si un certificado dado se encuentra o no revocado.
El X509 propone  los Certificate Revocated List (CRL) como método de comprobación de revocaciones. Se trata de un lista emitida por la autoridad certificadora que contiene los números de serie de aquellos certificados que han sido revocados. Esta lista estará firmada por la propia CA con el objeto de demostrar su autenticidad.
El inconveniente de este método es la consulta de la CRL ya que éstas se publican de forma periódica.

Reglas BER y DER

Con el objeto de permitir la transferencia de certificados entre cualquier tipo de arquitectura y máquina se han normalizado la forma de codificación de los datos binarios.
Así la organización ISO definió el estándar BER (Binary Encoding Rules) que se base en el formato de estructuras de datos ASN1 (también del ISO).
Asimismo se definió el DER (Distinguished Encoding Rules) como subconjunto reducido del BER.
Para la transferencia en texto plano de los certificados (principalmente para su utilización a través del correo electrónico) se definió el formato PEM (Private Enhaced Mail) el cuál es un objeto DER codificado en MIME.