Capítulo II. Este capítulo fue escrito mientras se escuchaba: Pink Floyd (Animals & The Wall).
Algoritmos asimétricos ya existentes.
En este capítulo, vamos a explorar los cifrados asimétricos ya existentes, cada uno va a ser explicado en profundidad, es posible que necesite continuar esta entrega en el capítulo III, ya que en este momento son las 23.06 pm (GMT -3), no tengo sueño por ahora, pero veremos que tan tarde se hace.
RSA
RSA es un algoritmo de cifrado asimétrico, creado por Ron Rivest, Adi Shamir y Len Adleman, del Instituto Tecnológico de Massachusetts (MIT) en el año 1977. Como ven, RSA son las siglas de "Rivest" "Shamir" y "Adleman". Es el primer algoritmo de cifrado asimétrico en la historia y aún es el más usado. La gran fortaleza que mantiene al RSA entre los algoritmos más seguros, es la infeasibilidad de descomponer un número grande en producto de primos.
Generación de claves:1. Cada usuario elige dos números primos distintos p y q.
* Por motivos de seguridad, estos números deben escogerse de forma aleatoria y deben tener una longitud en bits parecida. Se pueden hallar primos fácilmente mediante test de primalidad.
"Deben escogerse de forma aleatoria" no significa que uno tiene que pensar en un número y ponerlo apretando teclas en el numpad. Es cierto que el ser humano es una excelente máquina generadora de aleatoriedad, pero la mejor manera de generar números aleatorios, es utilizando lo que se conoce como "generadores pseudo-aleatorios", este término es largo de explicar, y por eso incluí un apartado sobre generadores pseudo-aleatorios al final del capítulo. Como semilla, se utilizan fuentes de aleatoriedad, por ejemplo, movimientos del mouse, temperaturas de los dispositivos, etc.
2. Se calcula n = p*q.
* n se usa como el módulo para ambas claves, pública y privada.
Módulo: En este caso, el módulo se define como el resto de una división.
Ej:
100 mod 6 = 4.
100/6 = 16 resto "4".
3. Se calcula φ (n)=(p-1)(q-1), donde φ es la función φ de Euler.
Tranquilos!! Ahora explico la funcion φ de Euler!.
La función φ(n) de Euler (phi), se define como el número de enteros positivos menores o iguales a n y
coprimos con n.
Osea, la cantidad de números menores o iguales a "n" que son
coprimos con "n", es decir que no tienen
ningun divisor común que no sea 1.
Por ejemplo:φ(36):
Primero factorizamos 36: 36 = 2 * 2 * 3 * 3 = 2^2 * 3^2.
Agarramos los primos que dividen a 36 osea "2" y "3", y aplicamos esta fórmula:
n * (1-1/p1) * (1-1/p2) * (1-1/p3) [...] (1-1/px).
Siendo cada uno de los "p" los primos que dividen a 36.
Aplicamos la fórmula y nos queda:
36 * (1-1/2) * (1-1/3) = 36 * 2/3 * 1/2 = 12.
Esto significa, que existen 12 números menores a 36 que no son divisibles ni por 2 ni por 3, estos son: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, y 35.
Fun right?.
4. Se escoge un entero positivo e menor que φ(n), que sea coprimo con φ(n).
* "e" se da a conocer como el exponente de la clave pública.
* Un exponente e muy pequeño (p. ej. e = 3) podría suponer un riesgo para la seguridad.
Volviendo al ejemplo anterior, un número entero positivo "e" menor que φ(n), que sea coprimo con φ(n) podría ser: 5, 7 ú 11.
No tienen por qué ser primos, con un "n" más grande, obtendríamos "e" que no fuesen primos.
5. Se determina un d (mediante aritmética modular) que satisfaga la congruencia de cong(1) mod φ(n)
* Expresado de otra manera, de − 1 es dividido por a φ(n)=(p-1)(q-1).
* Esto suele calcularse mediante el algoritmo de Euclides extendido.
* d se guarda como el exponente de la clave privada.
El algoritmo de Euclides Extendido, se puede utilizar para calcular "d". Siendo que este algoritmo requiere conocimientos algebráicos y de matrices que realmente no tiene ningun sentido ponerse a explicar y en caso de que hiciese falta aplicarlo en algún código, este se puede conseguir googleando un rato, voy a saltar explicarlo y vamos a pasar directamente al resultado.
Ejemplo:
1) p = 61 q = 53.
2) n = 61 * 53 = 3233
3) φ(n) = (p - 1) * (q - 1) = 3120.
4) e = 17. (Coprimo con 3120). (Este es el exponente público).
5) d = 2753
Recordemos que 17*2753 - 1 = 46800. Y que 46800 / 3120 = 15 (es exacta).
La clave pública está compuesta por "e" y por "n", osea el exponente público y el módulo.
La clave privada está compuesta por "d" y por "n", osea el exponente privado y el módulo.
Cifrando:Primero, se divide el mensaje en bloques, de tal manera, que esos bloques, se puedan representar en números menores a "n". Ejemplo:
Tengo el plaintext "APOKLIPTICO".
Yo se que si lo quisiese expresar en números, estos serían 65, 80, 79, 75, 76, 73, 80, 84, 73, 68 y 79 (en la tabla ASCII). Obviamente este es un método ineficiente de dividir el mensaje, pero para la base teórica sirve.
Entonces, para cifrar:
m^e mod n = c.
Siendo: "m" el bloque del plaintext, "e" el exponente público, "n" el módulo y "c" el bloque del ciphertext.
Ejemplo:
Mensaje = "APOKLIPTICO".
n = 3233
e = 17
d = 2753
Bloques: 65, 80, 79, 75, 76, 73, 80, 84, 73, 68 y 79 (uno para cada letra).
Aplicando la fórmula:
65^17 mod 3233 = 2790.
80^17 mod 3233 = 2933.
[...]
68^17 mod 3233 = 1759.
79^17 mod 3233 = 1370.
Descifrando:Se obtienen los paquetes cifrados y se les aplica esta fórmula:
c^d mod n = m.
Siendo: "c" el bloque del ciphertext, "d" el exponente privado, "n" el módulo y "m" es el bloque original del plaintext.
Comprobémoslo con un
ejemplo:
2790^2753 mod 3233 = 65
2933^2753 mod 3233 = 80
[...]
1759^2753 mod 3233 = 68
1370^2753 mod 3233 = 79
Ahora, ustedes se preguntarán como hago para elevar 2790 a la 2753ava potencia. La respuesta es muy simple:
No hace falta hacerlo.
Se utiliza un método llamado "exponenciación modular" que en definitiva, es aplicar el módulo cada vez que multiplicamos por la base.
Ejemplo:
77^6 mod 10:
77*77 mod 10 = 9 (Exponente = 2).
9*77 mod 10 = 3 (Exponente = 3).
3*77 mod 10 = 1 (Exponente = 4).
1*77 mod 10 = 7 (Exponente = 5).
3*77 mod 10 = 9 (Exponente = 6).
Resultado: 9.
Si uno agarra la calculadora y hace 77^6 = 208422380089 mod 10 = 9.
Esto con un pequeño loop en un programa se puede hacer rápidamente.
function modular_pow(base, exponent, modulus)
c := 1
for e_prime = 1 to exponent
c := (c * base) mod modulus
return c
Eso es en pseudocódigo para los entendidos.
Fuentes y lecturas recomendadas:http://es.wikipedia.org/wiki/RSA
http://foro.elhacker.net/criptografia/rsa_para_no_iniciados-t67109.0.html
http://es.wikipedia.org/wiki/N%C3%BAmeros_primos_entre_s%C3%AD
http://es.wikipedia.org/wiki/Algoritmo_de_Euclides#Algoritmo_de_Euclides_extendido
Diffie-Hellman
Algoritmo de intercambio de claves Diffie-Hellman por Braulio.
ElGamal
Elgamal, es un cifrado asimétrico basado en el intercambio de claves Diffie-Hellman, este algoritmo fue creado en 1985 por Taher Elgamal. Este algoritmo se puede utilizar tanto para cifrar datos como para crear firmas digitales. Este algoritmo se utiliza en el conocido sistema de cifrado y firmas digitales PGP y en su equivalente freeware GPG.
Su fortaleza se basa en la imposibilidad de calcular eficientemente el logaritmo discreto.
Generación de claves.Se elige "p" que va a ser un número primo grande.
Se elige "g" que es un generador del grupo multiplicativo Gp, esto es un número que elevado a sucesivas potencias modulo "p", va a dar todos los números del conjunto exáctamente una vez, este conjunto, está formado por todos los números que son coprimos con "p", como "p" es primo, ese conjunto contendrá todos los números de 1 a p-1:
Ejemplo:
p = 19 g = 2.
Todas las exponenciaciones son mod p:
2^1 = 2 2^7 = 14 2^13 = 3
2^2 = 4 2^8 = 9 2^14 = 6
2^3 = 8 2^9 = 18 2^15 = 12
2^4 = 16 2^10 = 17 2^16 = 5
2^5 = 13 2^11 = 15 2^17 = 10
2^6 = 7 2^12 = 11 2^18 = 1
Como ven, todos los numeros aparecen en las primeras 18 potencias. Las siguientes 18 potencias darán devuelta la misma seguidilla de números.
Se elige "k" tal que 2 <= k <= (p -2).
La clave pública será entonces compuesta por p, a y (a^k mod p).
La clave privada será entonces "k".
CifradoSe recibe la clave pública compuesta por p, a y (a^k mod p).
Se divide en bloques el plaintext como se hizo con RSA, cada bloque "m" de tal manera que queden menores a "p".
Se elige un entero aleatorio "l" tal que 2 <= l <= (p-2).
Se calcula:
d = a^l mod p
e = m * (a^k)^l mod p.
El ciphertext entonces será "d" y "e".
DescifradoSe utiliza la clave privada "k" para computar:
m = d^(p-1-k)*e mod p.
"m" es el bloque del plaintext.
Ejemplo:Elegimos "p" = 541 y "a" = 2.
Comprobamos que "a" sea generador del grupo multiplicativo finito Ap. Para esto, podemos usar herramientas existentes o programar nuestra propia pieza de código, yo hice una en c++, es muy ineficiente y hay algoritmos de aproximacion ya existentes que lo hacen más facil, este lo pueden encontrar en el apéndice "B".
Elegimos "k" = 113 tal que 2 <= k <= (p-2).
Definimos entonces:
Clave pública = p, a y a^k mod p = 541; 2; 454.
Clave privada = 113.
Plaintext = hola. Lo dividimos por caracter según su valor ascii: 104, 111, 108, 97.
Elegimos "l" = 14.
Calculamos el ciphertext:
2^14 mod 541 = 154.
104 * 454^14 mod 541 = 279.
[...]
El primer bloque cifrado sería: 154; 279.
Si lo queremos descifrar:
154^(541-1-113)*279 mod 541 = 104.
Tenemos devuelta el plaintext.
Recuerden que todas esas exponenciaciones, se deben resolver por una cuestion de aprovechamiento de recursos y facilidad, con exponenciación modular.
Fuentes y lecturas recomendadas:
http://www.usna.edu/Users/math/wdj/book/node48.html
http://www.informatics.indiana.edu/markus/i400/lecture7.ppt (Ignoren la última parte sobre criptoanálisis, zero-knowledge y escrow method).
http://es.wikipedia.org/wiki/Cifrado_ElGamal (Bastante complicado de entender, conocimientos de Álgebra de grupos)
Apéndice A: Generadores de números Pseudo-aleatorios. A.K.A. PRNG (Pseudo-Random Number Generator).Un generador pseudo-aleatorio, es una fórmula matemática que basado en un número base, llamado "semilla" o "seed", da como salida números que tratan de asemejar aleatoriedad. Por qué digo "Asemejar"? Ninguna fórmula matemática puede por si sola generar una secuencia de números realmente aleatorios, ya que en las matemáticas, hay una serie de causa-consecuencia que lleva a un resultado final, que siempre va a ser el mismo. Para ponerlo en términos más simples 2 + 2 va a ser siempre 4.
Los PRNG más famosos son el Blum Blum Shub, el Fortuna y el Mersenne Twister. Los PRNG, están presentes en gran parte de los algoritmos, ya sea como parte del cifrado en si o en la generación de claves, lo que hace que sean importantísimos para la seguridad del algoritmo, para ser seguros, deben cumplir con estas características:
a) Dar una salida que incluya todo el rango de números que se le pide de manera distribuida, maximizando la entropía, osea, tratando de que haya igual cantidad de cada número.
b) No ser previsibles.
c) La semilla no debe ser posible de conseguir teniendo la salida.
Otro factor que hace inseguros los PRNG, es la complejidad de la semilla, si un PRNG se le da como semilla un número "n", la salida de dicho PRNG será siempre la misma hasta que se cambie dicho número. Entonces, si uno tiene como semilla al crear una clave criptográfica algo demasiado simple, otra persona podría usar esa semilla para producir sus propias claves, haciendo inútil el cifrado de datos.
Apéndice B: Pequeño código para comprobar si "g" es generador de grupo multiplicativo finito "Gp".#include <iostream>
#include <math.h>
#define GENERATOR 2
#define MODULUS 19
using namespace std;
long modpow(long modulus, long base, long exponent);
int main()
{
bool testarray[MODULUS];
bool gen = true;
for(int i = 0; i < MODULUS - 1;i++) testarray[i] = false;
for(int i = 0; i < MODULUS - 1;i++)
{
long long r = modpow(MODULUS, GENERATOR, i+1);
if(testarray[r])
{
gen = false;
break;
}
testarray[r] = true;
if(i%10000 == 0) cout << i << endl;
}
if (gen) for(int i = 1; i < MODULUS; i++) if(!testarray[i])
{
gen = false;
break;
}
if (gen) cout << "Generator!" << endl;
else cout << "Not a generator" << endl;
}
long modpow(long modulus, long base, long exponent)
{
long Output = 1;
for(int i = 1; i <= exponent; i++)
{
Output = (Output * base)%modulus;
}
return Output;
}
Como ven, definí la funcion modpow que es como había dicho antes, la exponenciación modular.
Bueno, por una cuestión de que ya tienen suficiente con estos algoritmos, el algoritmo DSA, será puesto en la siguiente entrega.
Cuando vea que ya no hay más preguntas, pondré el siguiente Capítulo.
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.