Taller: Criptografía asimétrica.

[bomba1990]

gracias por las respuestas, disculpen mi mala ortografia, y espero con ansias la segunda entrega.

[16BITBoy]

Normalmente X sería un byte, por ejemplo si el byte es "a", nos quedaríamos con si valor ascii, que es 97. En cualquier caso eso es criptografía simétrica.

Aja, se aplica a cada byte, gracias.
Y que quieres decir con que esa es criptografia simétrica? es que no hay algoritmo en la asimetrica? eso tiene muy poco sentido :S.  Por lo que he podido leer...la diferencia entre asimetrica y simetrica no influye a nivel de la aplicacion de la clave al mensaje plano (plaintext).

Edito: no lei bien los posts, ni el de braulio ni el de apokaliptico.

Ya se que el algoritmo no es X+10 y X-10 ni de lejos, donde 10 seria una clave, claro. Eso fue solo un ejemplo para simplificar con una clave, por eso me decís que es simétrica. Pero existiendo 2 claves distintas, la publica y la privada, una para cifrar y otra para descifrar, debe de existir una relación entre ambas claves, cualquiera que sea, que permita el cifrado y descifrado, entonces ahí la pregunta de como funciona la aplicación de estas claves al plaintext, eso tal vez diría la relación que debe haber entre las dos claves, y cual es, o cuales podrían ser los algoritmos usados.

De nuevo añado xD si algo me caracteriza es que leo demasiado rapido, tanto que en ocasiones pierdo el contenido:

@16BITBoy: Eso sería criptografía simétrica, ya que el "10" estaría siendo tu clave, y eso lo utilizarías para cifrar y descifrar a "X". Como son aplicados al plaintext, depende del algoritmo.

Aja, vale creo que entiendo lo que quieres decir, entonces de esos se trata, ¿no? De elaborar un algoritmo el cual establezca la relación que debe existir entre las dos claves, para que el cifrado y el descifrado resulte con éxito. Curiosamente, hoy encontré un pequeño libro en una tienda titulado "Matemáticos, espías y piratas informáticos: codificacion y criptografia", y parece tocar el tema de la asimetrica, el algoritmo RSA, le echaré un ojo a ver que dice en él.

Gracias

[WestOn]

entonces ahí la pregunta de como funciona la aplicación de estas claves al plaintext, eso tal vez diría la relación que debe haber entre las dos claves, y cual es, o cuales podrían ser los algoritmos usados.

Eso se tratara en el apartado que puso apokliptico, criptoanálisis.

El la criptografía asimétrica los métodos utilizados para romper estos sistemas son por lo general radicalmente diferentes de los anteriores, y usualmente implican resolver un problema cuidadosamente construido en el dominio de la matemática pura. El ejemplo más conocido es la factorización de enteros.

Me imagino que los tiros irán por ahí, pero espera que nos lo diga el que sabe jeje.
Yo también espero la 2ª entrega con ganas

Saludos

[raul338]

wow... no encontraba el post

Algo para confirmar:

Si el propietario del par de claves usa su clave privada para cifrar el mensaje, cualquiera puede descifrarlo utilizando su clave pública

Ahí en realidad se esta usando la clave publica como privada y la privada como publica no? que seria algo asi como si queres decir lo mismo a todos es mejor esta forma, no se, es una suposición

Y para que alguien cifraría un plain-text con la clave privada si se supone se tiene que cifrar con la clave publica correspondiente?

[APOKLIPTICO]

Absolutamente para nada, perdón por el delay en la entrega, pero esta es una grande, van a tener mucho para leer y seguro que me van a bombardear de preguntas, aparte, esta entrega viene con un artículo sobr Diffie Hellman hecho por braulio.

[APOKLIPTICO]

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.

Código (cpp) [Seleccionar] Expandir

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".

Cifrado
Se 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".

Descifrado
Se 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".

Código (cpp) [Seleccionar] Expandir

#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
APOKLIPTICO

Toda la información expuesta en este taller, está protegida bajo licencia Creative Commons Attribution-NonCommercial-ShareAlike 2.5.

[WestOn]

 
Tengo para un buen rato, modificaré el mensaje si tengo dudas gracias por todo el material.

Saludos

PD: Respecto a lo que acaba de comentar braulio-- ¿no daria overflow con estos datos?

Código [Seleccionar] Expandir

6580797576738084736879 ^ 17 mod 3233

[braulio--]

Yo tengo una duda sobre lo de separar por bloques. ¿No es más sencillo concatenar todos los bytes en un solo número y aplicar la fórmula directamente a ese número?

OFF: amo a pink floyd.

[APOKLIPTICO]

2 razones por la cual concatenar todos los bytes en un solo número no es conveniente:
1) El número puede ser extremadamente grande, lo cual haría muchisimo más dificil manejarlo a nivel computacional, si fuese más grande que 64 bits, sería imposible manejarlo con los tipos de datos convencionales, y habría que utilizar librerías especiales.
2) El número debe ser menor al módulo siempre, lo cual limita el tamaño.

[APOKLIPTICO]

Tengo para un buen rato, modificaré el mensaje si tengo dudas gracias por todo el material.

Saludos

PD: Respecto a lo que acaba de comentar braulio-- ¿no daria overflow con estos datos?

Código [Seleccionar] Expandir

6580797576738084736879 ^ 17 mod 3233

No te olvides que "m" siempre tiene que ser menor que el módulo.
Cuando yo puse esos datos, no los puse para que sean usados todos juntos, si los ponés todos juntos, después como los separás? Esos son de 2 dígitos, pero si tenés que cifrar algo que no es un texto, vas a tener todo el espectro ascii.
Si vos te fijas, yo puse 65^17 mod 3233 y luego 80^17 mod 3233, etc.