Capítulo IV. Este capítulo fue escrito mientras se escuchaba: Yes (Magnification), Pink Floyd (The Final Cut), Green Day (Dookie), Oasis (Dig out your soul).
Guten tag homies! Volvemos entonces a metaforicamente encontrarnos, esta vez con la intención de conocer en profundidad las PKI (Public Key Infraestructure), en la que está incluido los certificados y los sistemas de autenticación. También, a pedido de la gente, va a haber un apéndice con los test de primalidad más usados.
Let us begin then:
PKI (Public Key Infraestructure).
En criptografía, una infraestructura de clave publica (o, en inglés, PKI, Public Key Infrastructure) es una combinación de hardware y software, políticas y procedimientos de seguridad que permiten la ejecución con garantías de operaciones criptográficas como el cifrado, la firma digital o el no repudio de transacciones electrónicas.
En definitiva, las PKI son las únicas formas de realmente reducir al mínimo los riesgos de seguridad debido a canales inseguros de comunicación. Ya que se crean certificados que luego servirán para firmar las claves publicas de cifrados asimétricos, que a su vez se utilizarán para cifrar claves simétricas y que estas a su vez se utilizaran para crear los canales seguros.
Las PKI, se conforman de la siguiente manera:
- CA (Certificate Authority o Autoridad de Certificación): Encargada de firmar las claves criptográficas, generando certificados. La seguridad que se le atribuye a un determinado certificado, se basa en la confianza que se le tiene a la CA. Si uno no puede confiar en un determinado CA, no se puede confiar en el certificado.
- Certificados digitales: Son en definitiva claves públicas firmadas digitalmente, utilizadas para generar canales seguros. Para una explicación más profunda, ver el apartado "Certificados Digitales".
- Computadoras y servidores: Estos son los que gozarán de los beneficios de las PKI, ya sea firmando sus claves gracias al CA, verificando que una clave pública venga de donde tiene que venir y no haya sido modificada o autentificandose utilizando claves firmadas.
- VA(Verification Authority o Autoridad de Verificación), LDAP (Lightweight Directory Access Protocol) o directorios X.500: Estos son los encargados de guardar todas las claves y suministrarlos a los que lo solicitan, siempre y cuando tengan los privilegios para pedirlos. Generalmente los certificados de autenticación son dados a todos los que lo soliciten, para verificar que las claves sean válidas. Estas son también las encargadas de verificar cuales son los certificados digitales que han expirado o han sido revocados.
- RA (Registration Authorities o Autoridad de Registración): Los RA's son necesarios cuando el CA no puede manejar todo el volumen de registraciones/revocaciones de claves, las RA's son las encargadas de manejar todos los datos, ordenarlos y filtrarlos y luego enviarlos a la CA para que firme las claves. Es decir, si una persona quiere firmar una clave, debe ir a la RA, hacer todos los trámites necesarios, y luego el CA recibe la clave, la firma y la reenvía al RA, que luego se la suministrará a la persona original.
Pongamos un ejemplo para verlo más claramente.
APOK quiere crear su servidor web, destinado a un e-commerce. Como leyó los tutoriales en el elhacker.net, sabe que debe tener conexiones seguras para sus clientes.
1) Elige como algoritmo simétrico AES-256 bits y para cifrar las claves del mismo, RSA-2048 bits.
2) Crea su clave RSA-2048 bits y contrata a un CA, le envía su clave pública y esta la firma con la clave de firmado y le devuelve un certificado digital.
3) Una vez creado el servidor, un cliente intenta conectarse:
4) El cliente, recibe el certificado digital, como la CA es una entidad conocida y su sistema operativo ya tiene cargado el certificado de verificación, este lo verifica como válido.
5) El cliente crea una clave aleatoria simétrica para el cifrado AES-256 bits y se la envía al server.
Una vez creado el canal seguro, ambos pueden comenzar a intercambiar datos.
Esta es la base del Handshake de TLS(Transport Layer Security) que es el sucesor de SSL (Secure Sockets Layer).
Fuentes:
http://en.wikipedia.org/wiki/Public_key_infrastructure
http://en.wikipedia.org/wiki/Transport_Layer_Security
- Cryptography for Dummies by Chey Cobb. (No puedo poner el link ya que está bajo Copyright, pero entre nos, google es su amigo). Parecerá medio estúpido por el nombre, pero es un libro muy didáctico y explicativo. Lo recomiendo.
Certificados digitales.
Un certificado digital es un documento digital mediante el cual un tercero confiable (una autoridad de certificación) garantiza la vinculación entre la identidad de un sujeto o entidad y su clave pública.
El certificado contiene usualmente el nombre de la entidad certificada, número de serie, fecha de expiración, una copia de la clave pública del titular del certificado (utilizada para la verificación de su firma digital) y la firma digital de la autoridad emisora del certificado de forma que el receptor pueda verificar que esta última ha establecido realmente la asociación.
Recuerdan cuando vimos que la criptografía asimétrica estaba expuesta a ataques de MITM (Man in the middle)? Bueno, los certificados son la manera de evitar estos ataques MITM.
Recordemos un poco:
Un ataque MITM, es una técnica que se utiliza para capturar y/o modificar información que transita una red de computadoras. Se basa en, utlizando diversas técnicas (Arp poisoning, redes switcheadas, captura de paquetes wi fi, etc), situarse entre dos o más computadores, de tal manera que se pueda ver y/o modificar los paquetes que se transmiten entre las mismas. Entonces:
Si uno lo traslada a la criptografía asimétrica, un atacante "Eve" (de Eavesdropper = Escuchar secretamente), podría modificar las claves públicas que se transmiten entre Alice y Bob, con unas creadas por él mismo, permitiendo de esta manera descifrar cualquier paquete que transite el canal supuestamente seguro.
Para evitar esto, se crearon los Certificados digitales, que permiten que las claves públicas creadas por una persona que intenta crear un canal seguro, puedan ser identificadas como seguras, es decir que no fueron manipuladas.
Para esto, la clave va a ser firmada digitalmente por una "CA", "Certificate Authority" o "Autoridad de Certificación". Esta va a ser la encargada de crear y revocar certificados digitales, asi como de hacer de "Autoridad de confianza" (Trusted Third Party), dando seguridad de que las claves no fueron manipuladas.
Generando un certificado.Para generar un certificado, primero tenemos que elegir que algoritmos utilizaremos, los tamaños de las claves y parametros de los algoritmos y si vamos a utilizar un CA o vamos a hacer como nuestro propio CA.
Una herramienta para crear claves y certificados, es la conocida OpenSSL, opensource y distribuida bajo GNU.
En caso de que contratemos un CA, lo único que tendremos que hacer, es crear nuestra propio par de claves y enviarle la clave pública al CA, de esta manera, el CA la firma y nos la devuelve firmada, este será nuestro certificado.
OpenSSL por ejemplo, creará dos archivos con extension .key y .csr siendo la clave privada y pública respectivamente.
El certificado, será un archivo con extensión .crt.
Si quieren, pueden analizar un certificado conectándose a una página de manera segura y descargándolo.
En firefox, se hace yendo al candadado de abajo a la derecha, en la tab de seguridad "ver certificado", "Detalles" y luego "exportar".
Esto guardará el archivo .crt y lo podremos examinar.
Si queremos hacer de nuestro propio CA, vamos a tener que crear nuestro certificado CA.
Primero, debemos crear nuestro CA. Esto genera la clave privada (que será usada para firmar) y la clave pública o certificado CA (que será utilizado para verificar las firmas). La clave privada debe ser guardada, ya que cualquiera en posesión de esta clave, podría generar claves firmadas, que luego podrían ser utilizadas para ataques MITM. La clave pública o certificado CA, debe ser distribuido a todas las personas que vayan a recibir claves públicas firmadas por nuestro CA, para que puedan verificarlas.
Luego, generaremos nuestro par de claves publica y privada y firmaremos la clave pública utilizando nuestra clave privada del CA.
Ahora tenemos nuestro par de claves para ser utilizadas en cualquier conexión segura (HTTPS, FTPS, etc.).
Obviamente es mucho más facil hacer firmar nuestro par de claves por una entidad reconocida, pero esto suele costar dinero.
Fuentes:http://es.wikipedia.org/wiki/Infraestructura_de_clave_p%C3%BAblica
http://en.wikipedia.org/wiki/Transport_Layer_Security
http://www.openssl.org/
http://es.wikipedia.org/wiki/Certificado_digitalhttp://www.akadia.com/services/ssh_test_certificate.html
Apéndice A: Tests de Primalidad.Los tests de primalidad tienen el fin de probar con certeza si un número natural es primo, es decir que solo es divisible por si mismo y por 1. Estos números son muy importantes para los algoritmos asimétricos como ya hemos visto. Existen dos tipos de test de primalidad: los determinísticos y los probabilísticos. Los primeros, determinan con un 100% de seguridad, que el número es primo. Los segundos, determinan con un porcentaje menor al 100% de probabilidad, cuanto más tiempo se los deja funcionar, menor va a ser la probabilidad de que un número no sea primo.
1) Test simple o test ingenuo. (Deterministico).Este es el más conocido de todos los tests, y se trata simplemente de probar dividiendo todos los números naturales entre 2 y n-1 siendo "n-1" el supuesto número primo.
Este test es el menos eficiente de todos, es decir el que más tiempo toma, sin embargo, se le puede hacer optimizaciones para mejorar su eficiencia:
a) Probar sólo hasta la raiz cuadrada de "n". Esto es debido a que si n es compuesto, puede ser factorizado en al menos dos valores, y al menos uno de estos valores debe ser menor o igual a la raiz cuadrada de n.
b) Se pueden saltear la prueba de divisibilidad no probando los números múltiplos de 2 excepto 2. Esto es debido a que si un número es divisible por un múltiplo de dos, será divisible por 2 también.
c) Se puede optimizar aún más si se observa que todos los primos excepto por 2 y 3 pueden ser formados con la fórmula 6*k +/- 1 siendo "k" un número natural (esto no significa que todos los números 6*k +/- 1 sean primos. Ej:k=4 6*4+1 = 25) . Esto acelera al menos 3 veces el test de primalidad.
d) También se pueden ir guardando todos los números primos que se vayan encontrando, de esta manera se puede acelerar aún más la prueba, pero esto requiere mucha memoria para guardar los mismo.
Les dejo un código en C++ que incluye las optimizaciones a, b y c y su diferencia en velocidad.
#include <ctime>
#include <stdlib.h>
#include <iostream>
#include <math.h>
using namespace std;
bool IsPrime0(long long number);
bool IsPrime1(long long number);
bool IsPrime2(long long number);
bool IsPrime3(long long number);
long long modpow(long long modulus, long long base, long long exponent);
int main()
{
long long number = 0;
int tantes = 0;
int tdesp = 0;
bool prime;
cout << "Introduzca un numero para probar su primalidad: ";
cin >> number;
if(number == 0 || number == 1)
{
cout << "\nError: Numero introducido invalido." << endl;
return 0;
}
cout << "Calculando sin optimizacion...";
tantes = clock();
prime = IsPrime0(number);
cout << number % 3;
tdesp = clock();
if(prime) cout << "\nNumero primo\n";
else cout << "\nNumero no primo\n";
cout << "Tiempo de calculo: " << (tdesp - tantes) / (float) CLOCKS_PER_SEC << " Segundos." << endl << endl;
cout << "Calculando con 1 optimizacion...";
tantes = clock();
prime = IsPrime1(number);
tdesp = clock();
if(prime) cout << "\nNumero primo\n";
else cout << "\nNumero no primo\n";
cout << "Tiempo de calculo: " << (tdesp - tantes) / (float) CLOCKS_PER_SEC << " Segundos." << endl << endl;
cout << "Calculando con 2 optimizaciones...";
tantes = clock();
prime = IsPrime2(number);
tdesp = clock();
if(prime) cout << "\nNumero primo\n";
else cout << "\nNumero no primo\n";
cout << "Tiempo de calculo: " << (tdesp - tantes) / (float) CLOCKS_PER_SEC << " Segundos." << endl << endl;
cout << "Calculando con 3 optimizaciones...";
tantes = clock();
prime = IsPrime3(number);
tdesp = clock();
if(prime) cout << "\nNumero primo\n";
else cout << "\nNumero no primo\n";
cout << "Tiempo de calculo: " << (tdesp - tantes) / (float) CLOCKS_PER_SEC << " Segundos." << endl;
return 0;
}
bool IsPrime0(long long number)
{
for(long long i = 2; i < number; i++)
{
if(number%i == 0)
{
return false;
}
}
return true;
}
bool IsPrime1(long long number)
{
for(long long i = 2; i <= sqrt(number); i++)
{
if(number%i == 0)
{
return false;
}
}
return true;
}
bool IsPrime2(long long number)
{
if(number%2 == 0 && number != 2) return false;
for(long long i = 3; i < sqrt(number); i+= 2)
{
if(number%i == 0)
{
return false;
}
}
return true;
}
bool IsPrime3(long long number)
{
bool minus = false;
if(number == 2) return true;
if(number%2 == 0 || number%3 == 0) return false;
for(long long i = 5; i <= sqrt(number); i=i)
{
if(number%i == 0)
{
return false;
}
if(!minus)
{
i += 2;
minus = true;
}
else
{
i += 4;
minus = false;
}
}
return true;
}
En mi pc, para probar la primalidad de un número primo de 49 bits tardó:
Sin optimizaciones: Demasiado.
Con 1 Optimización: 1.64 Segundos.
Con 2 Optimizaciones: 2.016 Segundos. Curioso que este tarda más que el primero.
Con 3 Optimizaciones: 1.375 Segundos.
Con las optimizaciones parece realmente poco tiempo comparado con el test sin optmizaciones, sin embargo, vamos a ver que este algoritmo tiene una eficiencia muy baja.
Fuente: http://es.wikipedia.org/wiki/Test_de_primalidad2) Test Miller-Rabin (Probabilístico).El test original creado por Miller que es determinístico, está basado en la hipótesis de Riemann, que aún no ha sido probada, es por esto, que Rabin lo modificó para convertirlo en probabilístico. No voy a tratar la parte matemática del algoritmo, ya que es extremadamente compleja y realmente no está a mi nivel y supongo que tampoco lo estará para la mayoría de uds.
El algoritmo es el siguiente:
1) Elegimos un número "n" para probar su primalidad mayor a 2 y obviamente impar.
2) Calculamos "s" de la siguiente manera, dividimos "n - 1" por 2 hasta conseguir un número impar. Entonces "s" va a ser la cantidad de veces que se dividió "n-1" para conseguir un impar. Osea n-1 = 2^s * d. Siendo "d" el número impar.
3) Se elige aleatoria y uniformemente un "a" tal que 0 < a < n. Uniforme, quiere decir que no se va a elegir dos veces el mismo "a", por cuestiones de eficiencia (no tiene sentido probar dos veces un "a").
4) Se calcula p0 = a^d mod n y p(r) = a^((2^r)*d) mod n. Siendo "r" todos los valores naturales entre [0;s]. Si p0 <> 1 y todos los p(r) <> n-1 entonces "n"
no es primo.
5) Si no se cumplen p0 <> 1 y p(r) <> n-1, entonces "n" es probablemente un número primo.
6) Cuantos más "a" se prueben, mayor será la probabilidad de que "n" sea primo.
La probabilidad de que un número pasado por el test Miller-Rabin sea realmente primo, siempre y cuando los "a" escogidos sean aleatorios y uniformes, es de 1-(1/4)^k. Esto significa, que con solo probar 10 "k", tendremos un 99.99990463% de certeza de que "n" es primo.
Bueno, estas funciones les permitiría aplicar el Miller-Rabin para probar primalidad. Es posible que me haya equivocado en el código y no toma valores demasiado altos, probablemente debido a un error de overflow en el módulo. Si alguien quiere optimizarlo, mejor aún!
NOTA: Modifiqué la función modpow para optimizarla con el algoritmo de la exponenciación binaria. Ahora es muchisimo más rápido.
bool MillerRabin(long long number, int tries)
{
srand(time(NULL));
if(number == 2) return true;
if(number%2 == 0) return false;
for(int r = 0; r < tries; r++)
{
long long nminus1 = number -1;
int s = 0;
do
{
nminus1 /=2;
s++;
}while(nminus1%2 == 0);
long long a = ((long long)(rand() / (double) RAND_MAX * (number - 2) + 1))%1000; //Límite en 1000 para ayudar al cómputo y evitar overflows.
bool prime = false;
long long firstmp = modpow(number, a, nminus1);
if(firstmp != 1 && firstmp != number -1)
{
for(int i = 1; i <= s; i++)
{
if(modpow(number, a, nminus1*pow(2,i)) == (number - 1))
{
prime = true;
break;
}
}
}
else prime = true;
if(!prime) return false;
}
return true;
}
long long modpow(long long modulus, long long base, long long exponent) //Optimized Modpow with binary exponentiation.
{
long long Output = 1;
long long nbase = base;
long len = log(exponent) / log(2.0f) + 1;
char *binexp = new char[len +10];
lltoa(exponent, binexp, 2);
binexp[len] = 0;
for(int i = len - 1; i >= 0; i--)
{
if(binexp[i] == '1') Output = fmod((Output * nbase),modulus);
nbase = fmod((nbase * nbase),modulus);
}
return Output;
}
Fuentes:
http://planetmath.org/encyclopedia/MillerRabinPrimeTest.html
http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test3) Test de Fermat. (Probabilistico)1) Se elige un número para aplicarle el test de primalidad "n".
2) Se elige aleatoria y uniformemente "a".
3) Se calcula p = a^(n-1) mod n.
4) Si "p" <> 1, entonces n
no es primo.
5) Si "p" = 1, entonces n es probablemente primo.
6) Si se desea mayor seguridad sobre la primalidad, se debe calcular otros valores de "a".
La probabilidad de que un número pasado por el test de Fermat sea realmente primo, siempre y cuando los "a" escogidos sean aleatorios y uniformes, es de 1-(1/2)^k. Esto significa que debemos calcular al menos 20 valores de "a" para tener la misma probabilidad de éxito que el algoritmo Miller-Rabin.
Sin embargo, existe una excepció para esto:
Los números de Carmichael (y no estoy hablando de la identidad secreta de "Chuck"), son números compuestos para los cuales todos los valores de a que sean coprimos con "n", "p" nos va a dar siempre 1. Esto genera una falla en el algoritmo, ya que es posible que un número compuesto de carmichael aparezca como primo. Sin embargo, los números de Carmichael son raros, hay 20138200 antes de 10^21, parecen muchos, pero en realidad significa que la probabilidad de que escogiendo un número al azar entre (2;10^21), este sea un número de Carmichael, es de 0,00000000000201382%, que es muy poca, aparte de que el "a" que se escoje, tiene que ser coprimo con el número de Carmichael.
Devuelta, les presento una función para aplicar test de Fermat:
bool Fermat(long long number, int tries)
{
srand(time(NULL));
if(number == 2) return true;
if(number%2 == 0) return false;
for(int r = 0; r < tries; r++)
{
long long a = ((long long)(rand() / (double) RAND_MAX * (number - 2) + 1))%1000; //Límite en 1000 para ayudar al cómputo.
cout << "a= " << a << endl;
bool prime = false;
long long firstmp = modpow(number, a, number - 1);
cout << firstmp << endl;
if(firstmp != 1) prime = false;
else prime = true;
if(!prime) return false;
}
return true;
}
long long modpow(long long modulus, long long base, long long exponent) //Optimized Modpow with binary exponentiation.
{
long long Output = 1;
long long nbase = base;
long len = log(exponent) / log(2.0f) + 1;
char *binexp = new char[len];
lltoa(exponent, binexp, 2);
binexp[len] = 0;
for(int i = len - 1; i >= 0; i--)
{
if(binexp[i] == '1') Output = fmod((Output * nbase),modulus);
nbase = fmod((nbase * nbase),modulus);
}
return Output;
}
Fuentes:
http://en.wikipedia.org/wiki/Carmichael_number
http://en.wikipedia.org/wiki/Fermat_primality_testBueno, hasta aquí llegue con los algoritmos, se que me falta el Solovay-Strassen(Probabilistico) y el AKS(Deterministico). Pero la verdad es que están muy por encima de mi nivel y realmente entre la estadística de hoy y la criptografía, voy a dormir en un colchón de números XD.
Si alguien se anima a describirlos de tal manera que todos los demas los podamos entender, por favor, no duden en hacerlo.
Bueno, aqui termina el Capítulo IV, ya la próxima entrega, vamos a comenzar con criptoanálisis, para lo cual la estadística me va a venir como anillo al dedo (expresión porteña que significa que va a servir mucho).
Como siempre, las preguntas que tengan, posteenlas en este thread. Nos vemos!!
Cualquier error que se llegue a encontrar, por favor comunicarmelo por PM.
Un abrazo
APOKLIPTICOToda la información expuesta en este taller, está protegida bajo licencia Creative Commons Attribution-NonCommercial-ShareAlike 2.5.
Autor
En línea
