Foro de elhacker.net

NOTA: Para ver todos los capítulos sin las preguntas, referirse a este thread: Manual: Criptografía asimétrica desde cero. (http://foro.elhacker.net/criptografia/manual_criptografia_asimetrica_desde_cero-t309762.0.html)

Capítulo I.
Bueno, como prometí, hoy comenzamos con el taller de criptografía asimétrica.
Vamos a empezar con las bases y despues iremos ampliando la información. La idea es que yo voy a explicar lo mejor posible todos los conceptos y luego voy a dar links (Algunos ya existentes en el foro) para ampliar la información ya dada.
Estas son interpretaciones con el fin de hacer más legible y accesible la información que puede resultar compleja, vale aclarar que todo lo expuesto, va a ser basado de otras fuentes, que van a ser aclaradas al final.

Quiero poner unas reglas básicas para como vamos a manejarnos en el taller:
- Todas las preguntas sobre lo expuesto en este thread, deben seguir las siguientes indicaciones:
1) Aclarar a qué parte del taller está referida la pregunta.
2) Ser clara y lo más explícita posible.
3) No utilizar "escritura sms", utilizar signos de puntuación, mayúsculas y espacios y tratar de mantener las faltas de ortografía a un mínimo.
4) No preguntar cosas que ya se han preguntado.
5) Las palabras "encriptar" y "desencriptar" son anglicismos que no deben ser utilizadas. Las palabras correctas son "Cifrar" y "Descifrar". cifrar viene del inglés "Encrypt" y descifrar de "Decrypt".

Voy a comenzar un pequeño glosario de términos que a medida que avanzemos se irá llenando, si se hace muy grande, lo pasaré a un post aparte:
- Plaintext: Mensaje antes de ser cifrado.
- Ciphertext: Mensaje después de ser cifrado.
- Cifrar: Aplicar un algoritmo matemático que tiene como fin hacer teóricamente imposible la lectura de un mensaje.
- Descifrar: Aplicar un algoritmo matemático que tiene como fin volver a hacer legible un mensaje cifrado.
- Charset: Conjunto de caracteres que pueden llegar a componer a una clave (Ej: Minúsculas, Mayúsculas, espacios, números, caracteres especiales, todo el espectro ASCII).
- Brute Force: Metodo de crackeo de claves que consiste en probar secuencialmente claves hasta dar con la correcta, suele ser lento, consumidor de recursos y generalmente infeasible.
- Infeasible: Anglicismo que se utiliza para denominar hechos que en teoría son posibles, pero la cantidad de tiempo o recursos necesarios para lograr dichos hechos, excede en tal manera que los hace extremadamente impracticos.
- A.K.A.: "Also Known As" = "También conocido como".
Comenzemos entonces:
Capítulo I. Este capítulo fue escrito mientras se escuchaba: Die Toten Hosen (Opium Fürs Volk).
Qué es la criptografía asimétrica?


Entonces: El algoritmo de cifrado asimétrico, crea dos claves, una pública con la que solo se debe cifrar los datos, y una privada, que permite descifrar los datos.

Cuál es la diferencia entre un algoritmo asimétrico y uno simétrico?
Un algoritmo simétrico permite que la misma clave se pueda utilizar para cifrar y para descifrar.
La ventaja del algoritmo simétrico sobre el asimétrico, es que los simétricos suelen ser mucho más seguros con claves más pequeñas, esto significa, utilizando un ejemplo, que para obtener la seguridad que tiene un AES 128 bits (Simétrico) se debe utilizar al menos una clave de RSA 1024 bits. Otra de las ventajas de los algoritmos simétricos es que suelen ser decena de veces más rápidos para computar las claves y para cifrar los datos.

Para qué entonces utilizar criptografía asimétrica?
Sin embargo, una de las grandes fallas que tienen los algoritmos simétricos sobre los asimétricos, es el intercambio de claves, esto se explica a continuación con un ejemplo práctico.
Agustin y Bernardo quieren comunicarse por un canal, Eva, sin embargo, puede ver los paquetes que se transportan por dicho canal.

Agustin y Bernardo entonces, deciden utilizar la criptografía para evitar que Eva pueda ver su comunicación.
Comienzan utilizando criptografía simétrica.
Agustín, le envía a Bernardo la clave que van a utilizar para establecer el canal seguro. Pero Eva también puede ver esta clave.
Agustín cifra los datos que quiere enviar y Bernardo los recibe, sin embargo, Eva tiene la clave simétrica y los datos, entonces puede ver la comunicación entre Agustín y Bernardo.

Canal seguro: FAIL!

Entonces, Agustín y Bernardo, deciden utilizar criptografía asimétrica.
Agustín y Bernardo crean cada uno un par de claves Pública y Privada. Vamos a llamarlas E(A), E(B), D(A) y D(B), siendo E(A) la clave pública de Agustín, E(B) la clave pública de Bernardo, D(A) la clave privada de Agustín y D(B) la clave privada de Bernardo.
1) Agustín le envía a Bernardo E(A) y Bernardo le envía a Agustín E(B).
2) Agustín cifra con E(B) los datos que le quiere mandar a Bernardo y Bernardo cifra con E(A) los datos que le quiere mandar a Agustín.
3) Agustín descifra con D(A) los datos que recibió de Bernardo y Bernardo descifra con D(B) los datos que recibió de Agustín.
4) Eva, lo único que puede ver en el canal, son las dos claves públicas y los datos cifrados, entonces, esta no va a poder ver los datos que Agustín y Bernardo comparten.

Canal seguro: OK!!

Para los que entienden mejor con interpretaciones gráficas, aqui les presento un par:
(https://zonatic.usatudni.es/images/criptografia/criptografia_asimetrica_1.png)

(https://zonatic.usatudni.es/images/criptografia/criptografia_asimetrica_2.png)

Bases de la criptografía asimétrica.


Fuentes:
- http://es.wikipedia.org/wiki/Criptograf%C3%ADa_asim%C3%A9trica (http://es.wikipedia.org/wiki/Criptograf%C3%ADa_asim%C3%A9trica)
- http://es.wikipedia.org/wiki/Criptograf%C3%ADa_sim%C3%A9trica (http://es.wikipedia.org/wiki/Criptograf%C3%ADa_sim%C3%A9trica)
- https://zonatic.usatudni.es/es/aprendizaje/aprende-sobre-el-dnie/57-aspectos-tecnicos/196-criptografia-y-esquemas-de-clave-publica.html (https://zonatic.usatudni.es/es/aprendizaje/aprende-sobre-el-dnie/57-aspectos-tecnicos/196-criptografia-y-esquemas-de-clave-publica.html)

Cualquier duda que tengan, posteenla acá, cuando vea que no hay más preguntas, pongo el siguiente tema.

Un abrazo
APOKLIPTICO.

Toda la información expuesta en este taller, está protegida bajo licencia Creative Commons Attribution-NonCommercial-ShareAlike 2.5.
(http://i.creativecommons.org/l/by-nc-sa/2.5/ar/88x31.png) (http://creativecommons.org/licenses/by-nc-sa/2.5/ar/)

Ahí va la primera pregunta:
Tanto la criptografía simétrica como la asimétrica has dicho que utilizan claves. ¿De qué clase de claves estás hablando? Alfanuméricas, solo letras, solo números (decimal, binario, hexa).
¿Cómo de largas pueden ser estas claves, es decir, hay un máximo de caracteres?

Gracias

Cada algoritmo tiene su método de generación de claves, la longitud de las claves, se suelen expresar en "bits", cabe aclarar que 8 bits = 1 byte.
Los métodos de generación de claves, suelen basarse en un generador pseudo-aleatorio, que utiliza como "semilla" una frase (Conocida como passphrase) y una información aleatoria introducida por el usuario (por ejemplo con movimientos del mouse o teclas apretadas aleatoriamente) o sacadas de un "random pool", esto es para los sistemas operativos que lo soportan, un conjunto de información aleatoria sacada de las interacciones del usuario (movimientos del mouse, teclado, etc.) y cosas como el uso de la cpu, temperaturas registradas, etc. Esto tiene como fin maximizar la aleatoriedad de las claves creadas.

No se preocupen si al principio no se entienden muchos conceptos como "entropía" o "generador pseudo-aleatorio" estos se van a ir viendo a medida que avancemos.
Las claves que se utilizan en los algoritmos de cifrado, tanto sean simétricos como asimétricos, varían en su generación y en su tamaño dependiendo del algoritmo utilizado. Por ejemplo, RSA acepta claves de 1024, 2048 y 4096 bits y solía aceptar de 512 hasta que se mostraron inseguras. Por otro lado, RC4 (arcefour) acepta claves desde 8 hasta 2048 bits en teoría, aunque por cuestiones de seguridad, se suelen utilizar claves de al menos 128 bits.

Buenas, entonces si tenemos un mensaje, de letras, ¿habría que pasarlo a numeros para operar con el?
¿Y luego sobre el mensaje transformado a números se factoriza?

Voy a dormir que veo muchos números por mi mente  :xD

Saludos

Es que justamente, depende del algoritmo, no te preocupes, vamos a verlos todos detenidamente uno por uno.

PD: @Weston, si con "mensaje" te referis al texto a cifrar (de ahora en adelante "Plaintext"), se debe utilizar el número que representa dicho caracter en el código ASCII. Por ejemplo, la "a" es el 97 (alt+97 te va a dar una letra "a"). Luego se aplica el algoritmo a esos números, para obtener el mensaje cifrado (de ahora en adelante "Ciphertext").

PD2: @MasterPunk, acabo de entender lo que me quisiste decir. Las claves que se utilizan para cifrar, suelen no ser claves "legibles" como la que uno usa para su cuenta de mail. Suelen ser altamente aleatorias y creadas específicamente para esto. La razón de esto es lo siguiente: Esto es un poco complicado, si no lo entienden aún, lo van a entender cuando veamos criptoanálisis, entropía, etc.

Si uno tiene una clave de 64 bits (8 bytes), por ejemplo "computar", esta contiene sólo a un espectro del código ascii. Esto es las minúsculas y las mayúsculas. Si alguien que quiere atacar a nuestro cifrado, sabe esto, sus probabilidades de conseguir dicha clave, aumentan increiblemente.
La cantidad de combinaciones que hay en 16 bytes si estamos usando todo el espectro ascii (de "0" hasta "255"), son de 256^8, si por ejemplo estamos usando RC4 que es uno de los algoritmos más rápidos y tenemos una velocidad de cracking de 80.000.000 de claves por segundo, tardaríamos 7312 años en conseguir la clave (asumiendo que la última es la correcta claro).
En cambio, si nosotros supiesemos que la clave que se utiliza para crackear está compuesta por alguna de las 26 minúsculas (a esto se le llama "charset") el tiempo necesario para conseguir la clave, sería de 26^8/80.000.000 = 43 minutos y 30 segundos.

La diferencia es muy importante como pueden ver, ya que si aumenta el charset, la cantidad de posibilidades aumenta exponencialmente.

bueno voy leyendo y voy entendiendo.

primera pregunta:
vamos a ver el sifrado asimetrico genera dos claves ¿una que solo sirve para cifrar y la otra que solo sirve para descifrar? ¿o se requieren las dos para descifrar?


lei en wikipedia que

las dos claves sirven para cifrar un documento pero no se puede descifrar el documento que ya se cifro con la misma clave.

es decir agustin sifra un plantext con su clave privada y el mismo no lo podria descifrar sin la ayuda de la clave publica, pero cualquiera con su llave publica si lo podria descifrar.

¿como se logra esto?
¿quien le pone una clave de 1024bits?,  ¿el sistema debe autogenerarla?
¿cuando empezeños podemos hacer primero uno pequeño solo para analizarlo mejor o hay alguno en internet para verlo?
¿alguien sabe algo de historia (que loco lo invento)?


pd: ¿porque Plaintext y no texto-plano?

Cada uno de los que participemos en el taller tendremos dos claves: una privada y otra pública. Ambas se generarán a la vez y ambas son necesarias.
Una vez que tengamos las dos claves deberemos compartir entre nosotros únicamente la pública.
Es decir, si somos tres personas en el taller (Yo, persona2 y persona3) Yo tendré cuatro claves: Mi clave privada(1), mi clave pública(2), la clave pública de persona2(3) y la clave pública de persona3(4).
Si yo quiero enviarle un mensaje a persona2, deberé cifrar ese mensaje con la clave pública de persona2, y ese mensaje únicamente podrá ser descifrado con la clave privada de persona2 (que solo tiene él).
Si encambio yo encambio no quiero mandarle el mensaje a persona2, sino que quiero mandarselo a todos los miembros del taller deberé cifrar dicho mensaje con mi clave privada, y ese mensaje podrán desencriptarlo con mi clave pública todas aquellas personas que tengan dicha clave, es decir, los miembros del taller.

Espero haberme explicado bien porque es un poco lioso.

Salu2

@bomba1990: Me pusiste "sifrado" y despues pusiste "cifrado". Es con "c". Te voy a pedir también que trates de usar comas, puntos y mayúsculas, ya somos grandes como para andar escribiendo como si estuviesemos en primer grado.
Bueno a ver:
1) Vamos a ver el cifrado asimetrico genera dos claves: ¿una que solo sirve para cifrar y la otra que solo sirve para descifrar? ¿o se requieren las dos para descifrar?
Siendo que las "claves" son números, se podría utilizar, y de hecho se utiliza en algoritmos de firma electrónica, la clave privada para cifrar los datos, que luego se descifrarían con la clave pública. Sin embargo, en la mayoría de los algoritmos asimétricos, se utiliza la publica para cifrar y la privada para descifrar.

2) ¿como se logra esto?
Agustín si cifró su mensaje con la clave privada, va a poder descifrarla con su clave pública, ya que él tiene ambas claves. Osea, no es que cuando envía la clave pública deja de tenerla en su poder, envía una copia obviamente.

3) ¿quien le pone una clave de 1024bits?,  ¿el sistema debe autogenerarla?
El tamaño de la clave la elige el usuario, dependiendo de cuan seguro sea necesario el canal, o cuan paranóico sea el usuario, también hay que saber que cuanto mayor sea el tamaño de la clave asimétrica, más cargará el sistema cuando alguien quiera conectarse. Lo cual no sería problema si es para una conexión única, pero si es en un sitio web con https, podría sobrecargar el servidor.

4) ¿cuando empezeños podemos hacer primero uno pequeño solo para analizarlo mejor o hay alguno en internet para verlo?
No se que será "empezeños", pero supongo que quisiste decir "empezemos". Los algoritmos más conocidos (RSA, DSA, ElGamal, Diffie-Hellman, etc.) están en la web, ya sea en pseudocódigo, en algún lenguaje o explicados desde el punto de vista matemático. Ya los vamos a ver uno por uno.

5) ¿alguien sabe algo de historia (que loco lo invento)?
El primer algoritmo de criptografía asimétrica inventado, fue el RSA (de los autores Rivest, Shamir y Adleman), creado en 1977 por Ron Rivest, Adi Shamir y Len Adleman del MIT (Massachusetts Institute of Technologies).

@MasterPunk: Está bien la primera parte de tu explicación, pero si yo quiero mandar un mensaje cifrado a todos los miembros del taller, tendré que cifrar cada mensaje con la clave pública de cada uno de los miembros. Si yo lo cifro con mi clave privada, cualquiera va a poder descifrarlo, ya que mi clave pública, es (valga la redundancia) "pública", yo la tendría expuesta en algun lugar para que las personas me puedan mandar mensajes, como ocurre con PGP (Pretty Good Privacy) que lo veremos más adelante. Otra cosa, me pusiste "Desencriptarlo" acordate que esa palabra no existe, el correcto es "Descifrarlo". Sin embargo, escribis claramente, con signos de puntuación, mayúsculas y sin faltas de ortografía, asi que bien hecho!.

Un abrazo
APOKLIPTICO

Me imagino que llegaremos a ver la criptografía desde un punto de vista matemático ¿no es así?

Y otra pregunta, ¿cada cuánto se irán sacando nuevos "fascículos" ? ¿Cualquiera del grupo podría escribir alguno? (esta última es porque me gustaría participar).

En la encuesta se decía que el taller consistía en crear un algoritmo, no en dar clases de criptografía; pero, APOKLIPTICO, tras ver que todos somos unos incultos y no tenemos suficientes conocimientos como para hacerlo, se ha visto obligado a enseñarnos primero para despues poder llevar a cabo el taller.

En la última línea del primer "fascículo" pone:
Rectifico: en la que era la última linea antes de que añadieran la licencia :P

¿Quieres aportar información? Seguro que todos te lo agradecemos, siempre y cuando no repitas cosas ya dichas anteriormente.

PD: si me equivoco en algo, porfavor, corregidme.

Tanto como incultos noseeeeé  :silbar:

Yo estoy leyendo por mi cuenta, del hilo de post importantes ect,  pero aún asi no me vendría mal otra entrega...
Y respecto a lo que dice braulio opino igual que MasterPunk.

Saludos ;)

Quizás he exagerado un pelín, pero era para darle un poco de humor.

Creo que ya va siendo hora de una segunda entrega (perdonadme si suena a exigencia) venga del autor que venga.

salu2 y gracias por el taller =)

Y como son esos "numeros"(la clave) aplicados al Plaintext? Yo tengo en mente en que al plaintext se le aplicaba un algoritmo... por decir a lo muy simple "X + 10" donde X es ...(¿un byte? ¿un bit? o ¿el paquete entero?) y que luego haciendo una inversa al otro algoritmo osea X - 10 pues tenemos de nuevo el plaintext.

¿Como funcionaria esto realmente? 

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.

Siento no haberme enterado de lo de el nuevo "fascículo", lo releí rápido para ver si decía algo relacionado y me pareció no ver nada.

Pregunta sencilla: ¿Qué es el plaintext?. Quizás ya lo habeis explicado y no me he enterado al leerlo. Por su traducción literaria debe de ser algo como "texto uniforme" o "texto liso" pero no le encuentro el sentido.

Gracias, salu2 )

Buenas, MasterPunk:

El texto a cifrar --> Plaintext
Algoritmo
El texto cifrado --> Ciphertext

Saludos ;)

Uff!! Que actividad que está ganando este taller! jajaja. Bueno, voy de a uno y en orden:

@Braulio: La criptografía ES matemática, asi que si, vamos a ver todo desde el punto de vista matemático tmb, claro que para eso voy a necesitar bastante ayuda, si braulio tenés ganas de ayudarme, yo agradecido, lo que si, te pido que no lo postees directamente, por ahora vamos de lo más básico hacia lo más complicado. Mi plan es una onda asi:
- Bases de la criptografía asimétrica.
- Algoritmos asimétricos existentes (los más famosos).
- Aplicaciones de los algoritmos asimétricos (aqui vamos a ver tambien conceptos de criptografía simétrica y hashes).
- Criptoanálisis.
- Creación de algoritmo.

@MasterPunk: Nadie nació sabiendo, me imaginé que muchos no iban a saber de criptografía, por eso empecé desde las bases.
@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.

@MasterPunk: Fijate que hice un glosario con los términos más usados.

@Todos: Entre hoy y mañana voy a estar haciendo la segunda entrega, como ya veo que están muy entusiasmados, denme un rato porque la tengo que componer, piensen que esta entrega incluye a los algoritmos más famosos de la criptografía asimétrica (RSA, DSA, Diffie-Hellmann y ElGamal). También pienso hacer un apéndice con criptografía de curva elíptica.

Cierto, no ví el glosario. Te agradecería que abisaras cuando editas un post anterior, o que al menos pongas la parte nueva con un color distinto durante un tiempo determinado para que llame un poco la atención de los que ya hemos leido el capítulo. Gracias

You got it! la proxima aviso.

Hola a todos ustedes, me presento: Micah Genji.

Estoy empezando a ingresar a este mundo de la criptografia.
En si estoy leyendo un libro: Una Introduccion a la CRIPTOGRAFIA
Autores: Eugenio Garcia, Miguel Angel Lopez, Jesus Ortega.

Y bueno solo estoy muy contento por un taller como este, y con vision a crear un algoritmo, en si necesita de matematicas (aunque no soy nada bueno en esta rama) que dan mayor motivacion a estudiarlas y entenderlas.

Gracias por el taller.

Preguntas:
1.En caso de las claves privadas, que a mi entender tiene a uno de los factores usados en la clave publica y asi poder descifrar.
estos factores son administradas por los diferentes algoritmos de ciframiento ( como una RSA que tengo entendido que es la mas robusta )?

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

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:


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 :)

Eso se tratara en el apartado que puso apokliptico, criptoanálisis (http://es.wikipedia.org/wiki/Criptoan%C3%A1lisis).

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 :P

Saludos

wow... no encontraba el post :xD

Algo para confirmar:


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? :huh:

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.

Capítulo II. Este capítulo fue escrito mientras se escuchaba: Pink Floyd (Animals & The Wall).
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 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:
"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.

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

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

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.

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://es.wikipedia.org/wiki/RSA)
http://foro.elhacker.net/criptografia/rsa_para_no_iniciados-t67109.0.html (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/N%C3%BAmeros_primos_entre_s%C3%AD)
http://es.wikipedia.org/wiki/Algoritmo_de_Euclides#Algoritmo_de_Euclides_extendido (http://es.wikipedia.org/wiki/Algoritmo_de_Euclides#Algoritmo_de_Euclides_extendido)

---

Algoritmo de intercambio de claves Diffie-Hellman por Braulio. (https://docs.google.com/document/edit?id=1Z2Kl0Qkeffvf_fMeS5rccmmZCpF_AXLXw_znG1rytRw&hl=en&authkey=CMzhiNEJ)

---

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.usna.edu/Users/math/wdj/book/node48.html)
http://www.informatics.indiana.edu/markus/i400/lecture7.ppt (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 (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
APOKLIPTICO

Toda la información expuesta en este taller, está protegida bajo licencia Creative Commons Attribution-NonCommercial-ShareAlike 2.5.
(http://i.creativecommons.org/l/by-nc-sa/2.5/ar/88x31.png) (http://creativecommons.org/licenses/by-nc-sa/2.5/ar/)

 ;-)
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?

;)

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.

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.

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.

Por ahora no tengo dudas o mejor dicho no las publicaré, pero si puedo compartir con todos este link muy bueno acerca de RSA: http://www.di-mgt.com.au/rsa_alg.html

Saludos, sigue asi ;)

Ok, perfecto.

Buenas:
Aiba que fallo...
Yo por el momento no tengo dudas relacionado con lo que has publicado, pero lo sigo releyendo porque 'tiene sustancia' :P, pero si me gustaría saber en el lenguaje que se va a programar. ¿C/C++? ¿Phyton?
Saludos ;)

Yo creo que el lenguaje idóneo sería C/C++, se que es un lenguaje de medio nivel, muy versatil y util, eficiente y optimizable. No estoy familiarizado con todos los lenguajes como para decir que "hay que usar C++", pero se que por ejemplo, Visual Basic no vamos a usar.

Habria que hacer la estructura del algoritmo, hacerlo en un lenguaje base tipo C/C++ ... y el que lo quiera que lo pase a otro lenguaje (yo pienso pasarlo a vb cueste lo que cueste :xD)

Ademas, seria bueno hacerlo multilenguaje

para lo del lenguaje deberiamos hacerlo en pseudocodigo y algun lenguaje que decidamos entre todos(como c++) y despues cada quien lo puede pasar a otro lenguaje y lo postea

La eficiencia de VB es muy baja, un código en VB te tarda muchisimo más que en C++.

Pero funcionaria igual :)

No te preocupes de la eficiciencia, esta claro que un lenguaje interpretado siempre sera mas lento que uno compilado. El que lo quiera pasar al lenguaje que quiera es libre de hacerlo. No desviemos el tema

Por supuesto, aparte, siempre se pueden hacer las funciones en C++, compilar una dll e importarlas en VB, yo lo he hecho muchas veces.

Mira esto:
Calcular 31^100000000 mod 5200:

#include <iostream>
#include <ctime>
using namespace std;
 
int main()
{
    long startime = clock();
    long out = modpow(5200, 31, 100000000);
    cout <<  (float) (clock() - startime) / CLOCKS_PER_SEC;
}
 
long modpow(long modulus, long base, long exponent)
{
    long Output = 1;
    for(int i = 1; i <= exponent; i++)
    {
        Output = (Output * base)%modulus;
    }
    return Output;
}

Option Explicit
Private Declare Function GetTickCount Lib "kernel32" () As Long
 
Private Sub Form_Load()
Dim starttime As Long
Dim res As Long
starttime = GetTickCount
res = modpow(5200, 31, 100000000)
MsgBox (GetTickCount() - starttime)
End
End Sub
 
Function modpow(ByVal modulus As Long, ByVal base As Long, ByVal exponent As Long)
Dim i As Long
Dim output As Long
output = 1
For i = 1 To exponent
DoEvents
output = (output * base) Mod modulus
Next i
modpow = output
End Function
 
 

Resultados:
C++: 4,391 Segundos.
VB: 58 hs, 20 minutos.

Relación: C++ es 47825 veces más rápido que VB.

PD: Y si uso OpenCL y calculo con la GPU, puedo calcularlo 100 veces más rápido. Esto es en C++.

Buenas, sabía que habría una gran diferencia pero, guau, es más de la que pensaba  :o
Pero es lo suyo, para esto, generar claves, etc, es mejor C/C++ o python.

Por cierto cuando pones:
¿Cómo se expresaría 'tal que'? ¿Cómo un ''=="?

Saludos ;)

PD: Esta muy bien lo de Diffie-Hellman, gracias.

Respecto a lo del lenguaje, creo que es más importante el algoritmo que el lenguaje en el que lo vayamos a hacer. Lo que tenemos que hacer entre todos es el algoritmo y no el código.

"Tal que" no estoy seguro de como se expresaría, pero con un "==" estoy seguro de que no.

"tal que" significa "que cumpla los siguientes requerimientos.
En ese caso, significa que "k" cumpla los requerimientos de estar entre 2 y (p - 2).

En cuanto lo que dice braulio, eso es real, el algoritmo es lo más importante de todo, sin embargo, hay mucha gente que quizas no entiende un algoritmo si se lo expresa utilizando matemáticas y álgebra, pero si lo entiende si se lo muestra como un código...
Esos códigos, era simplemente para remarcar la diferencia entre lenguajes, VB es un excelente lenguaje en cuanto a la facilidad de armar interfaces gráficas o GUI, es por eso que yo recomiendo hacer programas híbridos, la parte que requiere mucha capacidad de cómputo, en C++, la interfaz gráfica, en VB.

APOKLIPTICO ... tu codigo en vb me demora solamente 24 segundos :P

long C++ != long vb

int C++ == long vb
long C++ == Currency vb


Son los cambios de variables, y como dije no desviemos mas del tema y cada uno se encaragará de usar el lenguaje que quiera a la hora de hacer el algoritmo

Como quieras, raul338, como andan esas lecturas?

Wow.... solo me falta leer el de Diffie-Hellman y "procesar" el funcionamiento de ElGamal ya que ... a simple vista ya es algo complejo como para entender a la primera :xD

Buenas chicos, tengo unas preguntas sobre el primer capítulo (Perdón por la tardanza, comencé tarde a leerlo):

• ¿Por qué los cifrados simétricos son mas seguros que los asimétricos con claves mas pequeñas?
• Si cifro un mensaje utilizando mi clave privada, ¿es posible que alguien teniendo el texto cifrado y la clave pública, obtenga mi clave privada?

Un saludo y muchas gracias APOKLIPTICO por el taller, me fascina la criptografía ;D

a) Porque la seguridad en los algoritmos asimétricos se basa entre o otras cosas en la dificultad de factorizar enteros. Es bastante sencillo factorizar un número de 20 dígitos, no así con uno de 300.

b) Teoricamente es posible, pero usando números tan grandes el tiempo que se tardaría en conseguirlo supera los miles de años. (cifra inventada, pero me suena)

1) Los cifrados asimétricos, se basan en funciones trampa y en el uso de números primos, estos números, deben de ser muy grandes para evitar que puedan ser sacados fácilmente. Los cifrados simétricos, usan cualquier número como clave, lo cual aumenta mucho el espectro de claves posibles, haciendo más dificil quebrarlo utilizando fuerza bruta.
Pongamos como ejemplo en RSA, el módulo "n". Este es la multiplicación de dos números primos, para averiguar estos primos, se debería factorizar "n", obteniendo los primos iniciales. Si por ejemplo, quisiésemos con fuerza bruta sacar una clave de un RC4, deberíamos probar sucesivamente todas las claves.

2) Eso es lo que se llama un "known plaintext" attack. Los algoritmos asimétricos, no suelen ser vulnerables a estos ataques. Pongamos un ejemplo con RSA también:
Yo tengo la clave pública, osea el exponente público (e) y el módulo (n), el plaintext (m) y obviamente el ciphertext (c), tendríamos una ecuación asi:
m^e mod n = c.
Ahora si quisiésemos sacar el exponente privado:
c^d mod n = m.

Deberíamos resolver la ecuación: log(m,c) mod n. Lo cual es infeasible debido a la dificultad de calcular logaritmos discretos, que es una de las bases de la criptografía asimétrica, asi como la dificultad de factorizar un número primo.

Dios... me alejo unos momentos este puente y todo lo que esta evolucionando esto. Voy a tener que ponerme al día en cuanto termine el examen que tengo este jueves.

Yo estoy igual que bitboy.. me he ido de puente y no he podido mirar los nuevos post. Tengo para rato. Cuando acabe postearé mis dudas.

Yo estoy leyendo lo que puso freeze, por lo demás ok.

Saludos ;)

Un hilo muy interesante apokalipto.

Pongamos el caso de que yo deseo establecer una relación segura (tipo ssh) con otra máquina osea que A desea establecer una relación segura con B.

La primera vez que establezco la conexión tengo que encontrar la forma de enviarle una clave de un sistema simétrico. Esa clave no se puede enviar en una transmisión abierta porque podría ser conocida por una tercera parte (man in the middle)  y por tanto podría conocer cualquier cosa al conocer la clave de cifrado.

Así que los pasos a seguir son:

1. Conexión a la máquina B.
2. Envío de mi clave pública.
3. Recepción de su clave pública.
4.  cifro un mensaje en el que está la clave dei algoritmo simético que usaré. La cifro con su clave pública.
5. Cuando B recibe mi mensaje puede descomprimirlo porque ha sido codificado con su clave pública y el tiene su clave privada. Al leer ese mensaje conoce la clave que usará para leer mensajes

Las demás veces ya no necesitaré todo eso pues tanto A como B conocen la clave de abrir mensajes

En todo esto, un posible man in the middle no ha podido obtener ninguna información válida porque no tiene la clave privada de A ni la de B.

Ahora bien estas son mis dudas:

Todo esto para poder enviarle una clave de un protocolo simétrico que es mas seguro y eficiente; sin embargo ya pude enviar un mensaje seguro utilizando un sistema asimétrico así que ¿para qué quiero el simétrico? Osea ¿en que casos merece la pena dar estos pasos para enviar a otra parte una clave de un protocolo simétrico?

Supongo que si yo tuviera que tener una clave distinta para cada posible interlocutor necesitaría muchas claves y eso lo resuelvo mejor con la clave/privada/pública. Sin embargo con el sistema simétrico puedo tener una sola clave para datos particularmente importantes y común a todos los interlocutores. El riesgo de esto es que el conocimiento de esa clave abre el sistema por completo y por tanto hay que tener especial cuidado en donde se almacenan (igual que donde se guarda la clave privada).

Al final de todo esto lo que estoy haciendo es un certificado propio ¿no es así?

 ;D

Por otra parte en mi modesta opinión quien quiera introducirse en criptografía debe hacerse cargo que el código va en C o en ensamblador y que todo es pura matemática. Por esa razón aquellos que realmente se interesen en estos temas deberían darse un paseo por el foro de C. Por poder se puede implementar en vb o php si se quiere, pero este es el reino de C y de ensamblador.

Para quien no lo sepa eso que dije de "man in the middle" es una técnica hack que se usa para conocer los mensajes que una parte dirije a otra. En la práctica es oir lo que A dice a B y por tanto parece lo mas adecuado para intentar averiguar claves de códigos cifrados.

Gracias! Y es "APOKLIPTICO". jeje


1) Se dice "Clave de cifrado" no de "cifrado".
2) De hecho, el algoritmo Diffie-Hellman está específicamente diseñado para intercambio de claves, no es un algoritmo de cifrado per se.
3) Un ataque MITM es posible siempre y cuando este MITM pueda modificar los paquetes que van y vienen. (Crea su propio par de claves pública y privada y reemplaza la pública real).

1) El cifrado simétrico es mucho más rápido, eficiente y seguro con claves más pequeñas que el asimétrico, por ejemplo RSA:
Yo cifro m^e mod n = c
(m = plaintext, e = exponente público, n = módulo y c = ciphertext).
Y descifro c^d mod n = m
(m = plaintext, d = exponente privado, n = módulo y c = ciphertext).
Ahora, la cantidad de ciclos que son necesarios para correr esta rutina:

long modpow(long modulus, long base, long exponent)
{
    long Output = 1;
    for(int i = 1; i <= exponent; i++)
    {
        Output = (Output * base)%modulus;
    }
    return Output;
}

Son muchisimos más que por ejemplo, un XOR para el RC4 del plaintext con el keystream.

Es por esto que conviene casi siempre utilizar un cifrado híbrido simétrico-asimétrico.


En realidad, podés utilizar una clave distinta simétrica para cada interlocutor, osea, las claves simétricas son muchísimo más faciles de generar que las asimétricas (son simplemente un número aleatorio, no tiene que pasar tests de primalidad, ni ser generador como en ElGamal, no hay que calcular Phi).


Opino lo mismo, aunque raul338 ha probado que compilando los codigos en VB y haciendo buen uso de los tipos de datos, la diferencia de velocidad no es tanta.

Mucho gusto conocerte.

Efectivamente.

El problema es que si quieres usar criptografía simétrica tendrás que enviar al receptor la clave para que pueda leer lo que le enviarás. Si el envío de esa clave lo haces por medio de criptografía asimétrica aseguras que quien recibe esa clave es quien debe ser y nadie mas. Si no lo haces así no puedes tener la seguridad de que esa clave no haya caído en malas manos. Si de lo que se trata es de seguridad es un factor a tener en cuenta. De hecho tengo que verlo mas profundamente pero ¿no es eso en definitiva lo que hace ssh?

Por cierto para temas de test de primalidad y semillas tengo una lista de los 10.000 primeros números primos si a alguien le interesa que me lo haga saber.

Un saludo

Se puede evitar el ataque MITM con certificados, firmas digitales, cosas que veremos más adelante.

Ya pero es que al final ¿no estas haciendo una forma primaria de certificado?

Porque al utilizar criptografía asimétrica estas creando una relación de confianza entre ambas partes que te lleva a dar una clave que otorga al receptor en un espacio de confianza adicional. Los certificados son mas elaborados, pero en lo básico estamos en eso.

De todas formas creo que te estoy desviando el interesante hilo así que me callo y leo que tengo mucho que aprender je je je

 ;D

El tema es que los certificados, pueden asegurar quien es el emisor, es la base del PKI (public key infraestructure), son sistemas criptográficos que cuando los veamos, vamos a tener que ampliar a Hashes y criptografía asimétrica, ya que el PKI integra esas tres tecnologías.

Hola. Lo primero que haré será disculparme por haber tardado tanto en leer el segundo tema; no he tenido tiempo hasta ahora.

Hice una prelectura encuanto fue publicado el tema, pero, como me faltaban muchos conocimientos en matemáticas como para comprenderlo, no entendí nada =S

Hoy me puse enserio con el tema y, a base de google, wikipedia, y mucha paciencia he llegado a entender (más o menos) estos algoritmos.

¿Es esto suficiente como para pasar al siguiente tema, o debo sabermelos como la tabla de multiplicar? Es decir, el siguiente capítulo (y sus posteriores) parten de la base de este tema o esto ha sido solo una explicacion para poder comprender lo importante que viene detrás.

(creo que no soy el único que quiere saber esto :P)

No hace falta que se los sepan, como vos decis "como la tabla de multiplicar", es simplemente para saber de qué estamos hablando y de tener una referencia. No les voy a tomar prueba jajajaj.
Lo que pasa es que uno no puede hablar x ejemplo de PKI, sin entender RSA y diffie-hellman.

Es decir, que la cosa se complica T_T

Sisi, se viene más jodido en las próximas entregas. Depende de como venga con el estudio, este finde es posible que ya salga.

 :-( :-( :-( :-( :-(
Te has olvidado de nosotros

¿Cómo vas con los estudios? Y lo que es más importante (para nosotros), ¿Como va el tema 3?

=)

:xD ¡Yo también quiero el tema 3! jaja

Saludos

Jajaja, está al 50%, hoy lo termino, acabo de llegar de la fiesta por el día de las madres y bueno, ahora me voy a poner a terminarlo jejeje.
Sorry por la tardanza...

Capítulo III. Este capítulo fue escrito mientras se escuchaba: Yes (The Ladder + Fragile + Union) y Genesis (Foxtrot + From Genesis to revelation + Nursery crime).

Continuamos entonces con lo dejado en el capítulo anterior, faltaba describir DSA, luego vamos a hacer un pequeño vistazo sobre hashes y algoritmos de cifrado simétricos, no tanto en profundidad como los asimétricos, pero suficiente como para que puedan entender la siguiente entrega (Public Key Infraestructure, Certificados y sistemas de autenticación).

Comenzemos entonces:
NOTA: Para los que no tienen ni idea de lo que es un hash, recomiendo que lean primero esa parte, y luego comenzar con DSA, ya que este tiene contenidos sobre hashes.


Como ven, estamos hablando de un algoritmo de firma digital, no de cifrado. Una firma digital, es una manera de comprobar que un archivo determinado está siendo enviado por la persona correcta. Es decir, evitar que un documento sea manipulado mientras se transmite por canales inseguros.

Generación de claves:
1) Se elige un algoritmo de Hash estándar, generalmente se suele usar SHA-1 o SHA-256, para más seguridad.
2) Se elige la longitud de la clave en bits, utilizando dos valores "L" y "N", siendo "L" un múltiplo de 64, generalmente por una cuestión de seguridad de más de 1024 bits, y "N" la longitud de la salida del Hash.
3) Se elige un número primo "q" de como máximo "N" bits de longitud.
4) Se elige un número primo "p" de como máximo "L" bits de longitud, que se utilizará como módulo. (p-1) debe ser múltiplo de "q".
5) Se calcula "g" de esta manera: g = h^((p-1) /q) mod p, siendo "h" un número arbitrario entre [2, p-1). Si esta fórmula da como resultado "1" se debe elegir otro "h". Generalmente por cuestiones de eficiencia se suele elegir h = 2.

Se publican "p" "q" y "g" a los demás usuarios del sistema, estos serán los parámetros que les permitirán a los demás usuarios calcular sus propias claves autenticadas:

1) Se elige "x" por un método suficientemente aleatorio tal que 0 < x < q.
2) Se calcula y = g^x mod p.
La clave pública será (p, q, g, y). La privada es "x".
Recordemos que la exponenciación modular es calculable utilizando la fórmula ya expuesta, y que no es necesario calcular primero la exponenciación y luego el módulo.

Firmando.
1) Ya se conoce la función hash utilizada "H".
2) Se genera un número aleatorio "k" creado para el mensaje tal que 0 < k < q. Se descarta este "k" una vez utilizado.
3) Se calcula r = (g^k mod p) mod q.
4) Se calcula s = (k^-1 * (H(m) + x*r)) mod q. Recordemos que H(m) es la función de hash aplicada al mensaje a firmar "m".
5) Se debe recalcular la firma en caso de que r = 0 o s = 0, a pesar de que dichos escenarios son bastante poco probables.

La firma digital será entonces (r, s).

Verificando la firma.
1) La firma será inválida si las condiciones "0 < r < q" y "0 < s < q" no son satisfechas.
2) Se calcula w = s^-1 mod q.
3) Se calcula u1 = (H(m) * w) mod q.
4) Se calcula u2 = (r*w) mod q.
5) Se calcula v = ((g^u1 * y^u2) mod p) mod q.

Aclaración: k^-1 mod q, representa el inverso multiplicativo de "k", que en este caso, no es solo 1/k.
k^-1 mod q se define tal que k^-1 * k mod q = 1.
Por ejemplo: k = 21 q = 100. k^-1 mod 100 = 81. Ya que 21 * 81 mod 100 = 1.
Se puede calcular tanto con fuerza bruta (lo que puede llevar mucho tiempo), como con el algoritmo de euclides extendido (el mismo que se utiliza para calcular el exponente privado de RSA).

La firma se valida si v = r.

Como ven, en este algoritmo la clave privada se utiliza para firmar, y la pública se utiliza para comprobar la firma. Los parámetros

Ejemplo:
Generamos una clave:
1) Elijo como algoritmo de Hash uno ficticio, por cuestiones de practicidad para el ejemplo.
2) Como longitud de claves en bits, elijo L = 64 y N = 8. Devuelta, para hacerlo práctico para el ejemplo.
3) Elijo un número primo "q" de hasta 8 bits. q = 97.
4) Elijo un número primo "p" de hasta 64 bits, que se utilizará como módulo tal que (p-1) es múltiplo de "q". p = 389. 388 = 97 * 4.
5) g = 2^((389-1)/97) mod 389 = 16.
Tenemos entonces los parámetros (389, 97, 16).

Ahora calculamos las claves:
1) Elegimos "x" = 25.
2) Calculamos y = 16^25 mod 389 = 142.
Clave pública = (389, 97, 16, 142).
Clave privada = 25.

Firmamos un mensaje:
1) Tenemos la función de hash ficticia con una salida de 8 bits. Supongamos que H(m) = 75.
2) Se genera un número aleatorio "k" = 66.
3) Se calcula r = (16^66 mod 389) mod 97 = 76.
4) Se calcula s = (66^-1 * (75 + 25*76)) mod 97 = 2 (66^-1 mod 97 = 25).
5) Se debe recalcular la firma en caso de que r = 0 o s = 0, a pesar de que dichos escenarios son bastante poco probables.
La firma entonces va a ser (76, 2).

Verificamos la firma.
1) 0 < 76 < 97 y 0 < 2 < 97.
2) Se calcula w = 2^-1 mod q = 49.
3) Se calcula u1 = (75 * 49) mod 97 = 86.
4) Se calcula u2 = (76*49) mod 97 = 38.
5) Se calcula v = ((16^86 * 142^38) mod 389) mod 97= 76.
6) r = v --> Firma verificada!.

Fuentes:
http://www.itl.nist.gov/fipspubs/fip186.htm (http://www.itl.nist.gov/fipspubs/fip186.htm)
http://es.wikipedia.org/wiki/DSA (http://es.wikipedia.org/wiki/DSA)

---

No se dejen confundir con la palabra "claves", esta no tiene nada que ver con las claves que se utilizan en criptografía para cifrar o descifrar datos. Probablemente la definición de wikipedia sea un poco confusa al principio, asi que vamos a hecharle un poco de claridad:

Tenemos un texto, documento o cualquier información, la llamaremos "m".
Tenemos también una función de hash o resumen, la llamaremos H().
Entonces:
Cuando se aplica H(m), se realizan un conjunto de operaciones matemáticas, que dan como resultado un resumen del mensaje original, que en un algoritmo real y seguro, debe tener las siguientes características:
- Determinado. Esto quiere decir, que dado un valor de entrada igual, la salida debe de ser igual, es decir:
Si se calcula H(m) = x
Y luego H(m) = y
Entonces x = y.
- Uniforme. Esto siginifica que la salida debe de ser lo más uniforme posible, es decir se debe utilizar todo el rango de salida de manera pareja y maximizando la entropía.
- Irreversible. Si se calcula H(m) = x, resultará infeasible calcular "m" teniendo "x". Esto se puede lograr utilizando funciones "trampa" como el módulo y los operadores binarios "AND" "OR" y "NOT".
- No relación entre tamaños de salida/entrada. Esto singifica que el tamaño de la salida no debe ser afectado por el tamaño de la entrada, ya sea que la entrada es muy pequeña, o muy grande, el tamaño de salida no debe de estar conectado con el de entrada.
- Tamaño máximo de salida fijo. Esto significa que cada algoritmo debe ajustarse a un tamaño de salida estandarizado, los valores no pueden superar este tamaño máximo. Por ejemplo, en MD5, el tamaño máximo es 128 bits.
- Eficiente. Se busca que el algoritmo de hash consuma la menor cantidad de recursos, sin perder seguridad.


Algoritmos de Hash más conocidos:
GOST             256 bits
HAS-160         160 bits
HAVAL            128 to 256 bits
MD2                    128 bits
MD4                    128 bits
MD5                    128 bits       
RadioGatún            Up to 1216 bits
RIPEMD-64            64 bits
RIPEMD-160    160 bits
RIPEMD-320    320 bits
SHA-1            160 bits
SHA-224            224 bits
SHA-256            256 bits
SHA-384            384 bits
SHA-512            512 bits
Skein            256, 512 or 1024 bits
Snefru            128 or 256 bits
Tiger                    192 bits
Whirlpool            512 bits
FSB                    160 to 512 bits
ECOH            224 to 512 bits
SWIFFT            512 bits

Colisiones de Hash.

Una colisión de Hash, es cuando la salida de un algoritmo de hash, es idéntica para dos mensajes diferentes, es decir:
H(m1) = x
H(m2) = y
x = y.
m1 <> m2.
Probabilísticamente hablando, es imposible crear una función de hash que tenga una salida diferente para cada mensaje, ya que el tamaño del valor de entrada puede ser [0, inf) y la salida, puede ser [0, Hmax] siendo Hmax el tamaño máximo de salida de un Hash. Sin embargo, se considera generalmente infeasible encontrar dos mensajes diferentes m1 y m2 tal que H(m1) = H(m2), debido a la regla de uniformidad y irreversibilidad, que asegura que la salida no va a tener ninguna correlación aparente con la entrada.
Calcular con fuerza bruta una colisión de hash, requiere muchísimos recursos, se ha logrado únicamente utilizando redes de cómputo.
Por ejemplo, MD5, tiene una salida de 128 bits, eso significa que hay 2^128 posibilidades distintas o 256^16.
Utilizando software de cracking que utiliza la GPU para crackear, yo puedo calcular 950 Millones de hashes por segundo, aún así, si quisiese calcular el espectro entero de md5, tardaría aproximadamente 11358 trillones de años en calcularlo.

Sin embargo, se han encontrado vulnerabilidades de hashes, que hacen que crear colisiones con ataques especializados sean no solo feasibles, sino extremadamente simples de lograr. Como ejemplo, el algoritmo de hashing md5, fue quebrado por Tao Xie y Dengguo Feng de tal manera que se puede calcular una colision en una fracción de segundo.

Por si les interesa crackear hashes con su GPU: http://foro.elhacker.net/criptografia/rompiendo_hashes_y_passwords_rar_con_la_gpu-t277060.0.html (http://foro.elhacker.net/criptografia/rompiendo_hashes_y_passwords_rar_con_la_gpu-t277060.0.html)

Fuentes:
http://en.wikipedia.org/wiki/Hash_function (http://en.wikipedia.org/wiki/Hash_function) (La versión en español no es muy buena).
http://es.wikipedia.org/wiki/Colisi%C3%B3n_%28hash%29 (http://es.wikipedia.org/wiki/Colisi%C3%B3n_%28hash%29)
http://en.wikipedia.org/wiki/MD5 (http://en.wikipedia.org/wiki/MD5)

---

Como ya vimos en otras entregas, generalmente se suele utilizar la criptografía simétrica conjunta con la asimétrica, ya que la asimétrica provee un canal seguro para compartir la clave, pero no posee la eficiencia y velocidad de un algoritmo simétrico.

Ejemplos de algoritmos simétricos muy usados son:
Twofish 128, 192 o 256 bits.
Serpent 128, 192 o 256 bits
AES (Rijndael) 128, 192 o 256 bits
Blowfish 8–448 bits en múltiplos de 8 bits.
CAST5 40-128 bits.
RC4 40–2048 bits
TDES 168, 112 o 56 bits
IDEA 128 bits

Por qué utilizar criptografía simétrica?
- Mayor velocidad.
Si analizamos un cifrado asimétrico muy común como RSA con uno simétrico como AES, veremos que AES utiliza pocas operaciones y estas operaciones son generalmente lineales, es decir, se computan rápidamente. Las claves generadas para AES, se generan pseudoaleatoriamente y no deben tener ninguna característica especial.
Sin embargo, RSA utiliza bastantes operaciones que requieren exponenciación modular, que con exponentes grandes, necesitará miles de veces la cantidad de ciclos que se utilizan para una operación de AES. Por otro lado, la generación de claves para RSA requiere test de primalidad que requieren mucha capacidad de cómputo y esta aumenta de manera no lineal con el tamaño de las claves, es decir, calcular una clave de 2048 bits va a tardar mucho más que el doble que una de 1024 bits.

- Mayor seguridad con claves más pequeñas.
Debido a que se reducen las posibles claves con RSA debido a que los valores generadores son números primos, este requiere que sean mucho más grandes que si fuese una clave simétrica, que puede ser cualquier número.
Una clave de 1024 bits de un algoritmo asimétrico, da la misma seguridad que una clave de aproximadamente 80 bits de un algoritmo simétrico, una de 2048 bits asimétrica da la misma seguridad que una de 112 bits simétrica y una de 3072 bits es equivalente a una de 128 bits. Esto varía dependiendo de los cifrados involucrados.
Por otro lado, una clave de 256 bits simétrica, solo se iguala con una clave de 15360 bits asimétricos. Calcular una clave de tal tamaño, puede tardar muchisimo tiempo computacional.

- Poseen un riesgo mucho menor de ser rotos por la computación cuántica.
En este momento se están haciendo investigaciones sobre la siguiente era de la información, la computación cuántica, gracias al algoritmo de Shor, se podría factorizar una multiplicación de dos primos utilizando una de estas computadoras feasiblemente, dando por concluida la era de los algoritmos asimétricos actuales. En otras palabras, se tardaría el mismo tiempo en utlizar una clave asimétrica en una computadora normal, que crackearla en una computadora cuántica equivalente. Los algoritmos simétricos, reducirían su complejidad de crackeo a la mitad gracias a la computación cuántica, es decir que una clave de 128 bits, equivaldría a una de 64 bits en seguridad. Sin embargo, esto se puede solucionar duplicando el tamaño de las claves, a expensas de un tiempo de cómputo ligeramente mayor.
Esto quiere decir: Si van a guardar información cifrada por mucho tiempo, utilizen un algoritmo simétrico y claves muy grandes.

Fuentes:
http://en.wikipedia.org/wiki/Advanced_Encryption_Standard (http://en.wikipedia.org/wiki/Advanced_Encryption_Standard) (Muy bueno).
http://www.mscs.dal.ca/~selinger/md5collision/ (http://www.mscs.dal.ca/~selinger/md5collision/)
http://es.wikipedia.org/wiki/Criptograf%C3%ADa_sim%C3%A9trica (http://es.wikipedia.org/wiki/Criptograf%C3%ADa_sim%C3%A9trica)
http://en.wikipedia.org/wiki/Key_size (http://en.wikipedia.org/wiki/Key_size)

---

Apéndice A: Entropía.

Vamos a explicarlo con un ejemplo práctico:
Tenemos un archivo, este archivo, puede contener cualquiera de los caracteres en el código ascii, cada uno representado por un número del 0 al 255.
Podemos entonces contar la cantidad de cada caracter en ese archivo, es decir la frecuencia.
Por ejemplo: "0" = 10, "1" = 3, "2" = 1, (...), "254" = 4, "255" = 0.
Una vez contados la cantidad de caracteres, calculamos las frecuencias relativas, es decir, xi/n, siendo "n" el tamaño del archivo en bytes. Por ejemplo: "0" = 0.025, "1" = 0.050, etc.
Una vez que hicimos todos esos cálculos, calculamos la entropía del archivo:

Entropia = sum(-xir[ i ] * log(xir[ i ], 2))
Siendo: xir[ i ] la frecuencia relativa de cada elemento "i", log(x,y) es el logaritmo de "x" base "y" y sum() es la sumatoria.

Esto va a dar un número entre 0 y 8. Este número, representa la entropía del archivo, siendo "0" sin entropía y "8" con entropía máxima, es decir que existe la misma cantidad de los 256 caracteres.
Los buenos algoritmos de compresión y de cifrado, dan como salida una entropía cercana a 8, sin importar la entropía de la entrada.
Este es el primer criterio que se utiliza para el criptoanálisis de un algoritmo, ya que si su entropía de salida es baja, se considera que no es lo suficientemente seguro.

Fuente:
http://es.wikipedia.org/wiki/Entrop%C3%ADa_%28informaci%C3%B3n%29 (http://es.wikipedia.org/wiki/Entrop%C3%ADa_%28informaci%C3%B3n%29)

Les paso un código que hice: http://foro.elhacker.net/criptografia/calcular_entropia_de_un_archivo_en_c-t237720.0.html (http://foro.elhacker.net/criptografia/calcular_entropia_de_un_archivo_en_c-t237720.0.html)

---

Bueno, la siguiente entrega, vamos a tratar sistemas criptográficos como PKI, Certificados y sistemas de autenticación, vayan leyendo, posteen sus preguntas y como siempre, cuando no haya más preguntas, posteo la siguiente entrega.
Un abrazo
APOKLIPTICO

Toda la información expuesta en este taller, está protegida bajo licencia Creative Commons Attribution-NonCommercial-ShareAlike 2.5.
(http://i.creativecommons.org/l/by-nc-sa/2.5/ar/88x31.png) (http://creativecommons.org/licenses/by-nc-sa/2.5/ar/)

esta muy buena la tercera entrega, hay bastante para leer. despues hare las preguntas de lo que no entienda.

Como siempre muy interesante APOKLIPTICO. Mucho por leer y por madurar pero ahora mismo me asalta una duda

Actualmente pensamos en un plain text como una colección de caracteres ascii pero ¿qué pasa si el texto a cifrar por muy plain que sea está en unicode?

Porque ahí cada caracter es representado por un mínimo de dos códigos y en el caso de ideogramas chinos hasta cuatro según tengo entendido. Desde un punto de vista criptográfico da igual cifrar algo que tenga 8 bytes que algo que tenga 16 pero desde el punto de vista de la desencriptación no.

¿o es que tengo mal entendido el unicode?

Lo demás ya lo iré leyendo con calma que este es un tema que hay que tomar a pequeños sorbos.

 ;D

Genial, Muy muy bueno!!!!!! Aún lo sigo leyendo y ando haciendo unas pruebas x)

EDIT:

Apok, toy haciendo una prueba de rendimiento con la pequeña prueba que tu hiciste en C:

Eso en C# me ha dado 1.9 segundos, qué equipo tienes tu?

Muy buena pregunta, Unicode como vos decis, utiliza más de 1 byte para representar un caracter. Sin embargo, desde un punto de vista criptográfico, ese caracter, se puede dividir en dos bytes, y así tratarlo.
Esto me da el pie para explicar la diferencia entre un block-cipher y un stream-cipher.
Verán, un block-cipher, divide el plaintext en bloques de una longitud determinada, de esta manera, se pueden tratar los archivos grandes y pequeños sin problemas.
Por otro lado, los stream-cipher, son algoritmos que cifran byte a byte, es el caso del rc4, que da un keystream que luego es utilizado para cifrar el plaintext utilizando XOR.

Un abrazo
APOKLIPTICO

APOKLIPTICO, publiqué un edit cuando tu posteaste, puedes leerlo.

Saludo.

Mirá en mi firma.

Gracias por el tema, ya habia ganas de otra entrega  :)

Saludos!

xD No me había dado cuenta de tu firma, era bien tarde :P Bueno, sigo leyendo el taller que me había atrazado por cuestiones de tiempo.

ESTOY INTERESADO EN APRENDER PERO EN REALIDAD NO SE NADA DEL TEMA PODRIAS AYUDARME POR DND COMENZAR

1) Podés empezar por leyendo las reglas.
2) Podes seguir con cumpliéndolas, por ejemplo, no escribir en mayúsculas.
3) Este taller de criptografía enseña todo desde 0, comenzá leyendo el primer capítulo, seguí con el segundo y asi sucesivamente.

Como va eso?
Preguntas?
Están leyendo?

Abrazo
APOKLIPTICO

Sep, estamos leyendo pero queda mas o menos claro ñ_ñ gracias.

Buenas, bien de momento, haciendo ejemplos a mano me salen bien, con cifras peques.
Aquí (http://www.ditutor.com/estadistica/frecuencia_relativa.html) dejo un ejemplo muy sencillo para los que ya olvidaron como se realiza el cálculo de la frecuencia relativa en problema típico.

Saludos!

Hasta ahora voy bien, pero lento ya que el tiempo es poco  :¬¬

hehe..

Saludos!

yo tambien estoy leyendo, y aprendiendo desenpolvando los libros de matematica y aprendiendo. ademas las clases de la uni ocupan bastante el tiempo.

Y si, la facu (universidad) siempre nos toma bastante tiempo.
Sin embargo, para cuando hagamos criptoanálisis, vamos a aplicar muchos conceptos aprendidos en estadística, percentiles, medias, medianas, modas, varianza, desviacion estandar, coeficiente variabilidad, asimetría y curtosis.

Lo que es yo lo llevo bastante bien.  Ahora estoy trabajando en el test de primalidad de Miller-Rabin y en breve espero poder postear una función en C que lo hace para números largos.

Será una buena ayuda porque para RSA, DSA, etc se debe partir de dos números primos. Con ese test de primalidad será posible obtener números primos de cualquier tamaño.

De todas formas para quien quiera hacer cositas y tener números primos tengo la lista de los 10.000 primeros números primos y así no necesitan calcularlos. Quien tenga interes que me lo diga y en paz.

 ;D

Los tests de primalidad, mmh, para la siguiente entrega hago un apéndice sobre los mismos.

En cuanto a los números primos, ak: http://primes.utm.edu/lists/ (http://primes.utm.edu/lists/) hay una lista de los primeros 50 millones de números primos.

xD vaya dejo un code aqui que no esta bien del todo, pero para salir del apuro:

 
#include <stdio.h>
 
#include <stdlib.h>
 
#define pausa printf("\n"); getchar();
 
 
int main()
 
{
 
    int j, num, i=1, n=2, colum=0;
 
             printf("Cantidad de numeros primos que quiere obtener: ");
 
    scanf("%d",&num);
 
    printf("\n");
 
 
 
    while(i <= num)
 
    {
 
        for(j=2; n%j !=0; j++);
 
        if(j == n)
 
        {
 
            printf("%d ",n);
 
            if(++colum%13 == 0)
 
               printf("\n");
 
            i++;
 
        }
 
        n++;
 
    }
 
    pausa
 
    return 0;
 
}

Ya que lo encontré no puedo evitar postearlo xD....aunque la lista de los 50 millones es mejor jeje.

Saludos ;)

Este es el más básico (y lamentablemente tambien el menos eficiente) de los tests de primalidad, ver si es divisible por todos los números anteriores mayores a 1 y menores a si mismo.

Sin embargo, se le pueden cambiar algunas cosas:
1) No hace falta que pruebes divisibilidad por todos los números entre [2;n-1], podés limitar la prueba a [2;sqrt(n)] siendo sqrt() raiz cuadrada.

2) Se pueden guardar todos los números primos que se van encontrando y probando la divisibilidad contra estos primos, en vez de probar todos los números. Ya que si un número es divisible por "15" singifica que también va a ser divisible por 3 y por 5, ambos primos.

3) Si no se quiere implementar lo dicho en el punto "2)" Se puede hacer antes de someterlo al loop for, un test de divisbilidad por los primos más básicos, es decir, 2, 3, 5, 7, 11 y 13 o quizas algunos más, de esta manera, se ahorran algunos ciclos del procesador eliminando los numeros pares, los que terminan en "5", etc.

Efectivamente. Eso es lo que estoy haciendo: ver si es divisible entre números primos pequeños y conocidos. Si pasa eso entonces entra en el loop. Para eso utilizo la lista de los 10.000 primeros números primos.

Así lo estoy haciendo je je je.

De todas formas quisiera saber cual es el test de primalidad que te parece mas eficiente para números grandes.

Un saludo

Lo que dije igual era para el algoritmo de WestOn. Miller-Rabin es un buen algoritmo, hay varios igual, algunos deterministicos, pero bueno, ya los vamos a ver en el proximo, espero poder sacarlo este finde, estoy atareadísimo con Estadística I.

bueno bueno que yo no digo nada para meterte presión ni nada. Solo que estoy en ello porque me divierte y cuando puedas si quieres pues ya hablarás sobre ello y si no quieres no. Yo de momento leo lo que pones y agradezco tu dedicación nada mas.

Si para entonces está hecho igual te sirve (o igual no) para explicar lo que quieras pero nada mas. Nada de presión ni cosas de esas. Se te agradece tu tiempo y tus ganas y suerte con la estadística que es un peñazo.

 :laugh:

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:


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:
(http://www.isp-planet.com/img/pki-figure.gif)

- 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/Public_key_infrastructure)
http://en.wikipedia.org/wiki/Transport_Layer_Security (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.

---

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:

(http://www.owasp.org/images/2/21/Main_the_middle.JPG)

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://es.wikipedia.org/wiki/Infraestructura_de_clave_p%C3%BAblica)
http://en.wikipedia.org/wiki/Transport_Layer_Security (http://en.wikipedia.org/wiki/Transport_Layer_Security)
http://www.openssl.org/ (http://www.openssl.org/)
http://es.wikipedia.org/wiki/Certificado_digital (http://es.wikipedia.org/wiki/Certificado_digital)
http://www.akadia.com/services/ssh_test_certificate.html (http://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_primalidad (http://es.wikipedia.org/wiki/Test_de_primalidad)

2) 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://planetmath.org/encyclopedia/MillerRabinPrimeTest.html)
http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test (http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test)

3) 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/Carmichael_number)
http://en.wikipedia.org/wiki/Fermat_primality_test (http://en.wikipedia.org/wiki/Fermat_primality_test)

Bueno, 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
APOKLIPTICO

Toda la información expuesta en este taller, está protegida bajo licencia Creative Commons Attribution-NonCommercial-ShareAlike 2.5.
(http://i.creativecommons.org/l/by-nc-sa/2.5/ar/88x31.png) (http://creativecommons.org/licenses/by-nc-sa/2.5/ar/)

Buenas, gracias por el tema IV, voy a leerle mas a fondo
No importa, thx por el code.

Saludos ;)

...

Despues de leer unas cuantas veces el capútulo tres creo que ya estoy preparado para pasar al cuarto =) (y tiene bastante buena pinta  :D)

Voy un pelín atrasado, pero os observo desde el fondo y no os vais a escapar >:D

Gente, voy corrigiendo los errores del código que voy viendo, y me voy a hacer una función de módulo que acepte números de cualquier tamaño (como strings).

Muy interesante je je je.

Respecto al test de Miller-Rabin lo tengo ya terminado, pero me estoy tomando un tiempo para asegurarme que está bien y no hay errores porque lo he hecho con gmp para números grandes y eso se sale del C estandar, es engorroso y lo ideal sería que la gente se lo pudiera pastear sin mas como una función. Por eso prefiero asegurarme no vaya a ser que en vez de ayudar lo joda todo je je je.

Respecto a los certificados me asalta una duda. Pongo la cosa tal como lo entiendo:

sistema asimétrico
Pongamos que A conecta la primera vez con B para establecer un canal seguro de comunicación. Si solo uso un sistema asimétrico el procedimiento es enviarle mi clave pública y que él me envíe la suya.

Cuando quiero A quiere enviar algún dato a B lo que hace es firmarlo con su clave pública y así solo lo podrá ver B. Igualmente si B quiere enviarme algo a A lo firmará con la clave pública de A y solo lo podrá ver A.

Man in the middle
El problema de esto tal como está expuesto es que un tercero C (de canalla) esté en el medio. Si A envía su clave pública a B la intercepta y en cambio envía la suya. B recibe una clave pública que cree que es de A pero no. Es de C.Cada vez que B firma algo con la clave pública de A en realidad lo  está haciendo con la de C y aunque cree que se lo envia a A en realidad se lo envía a C. Es decir, C se entera de todo.

certificados
La solución para evitar esto es que una tercera parte garantice que la clave pública de A es realmente de A. Para ello lo que hace es firmar la clave pública de A con su propia clave pública y así quien recibe una clave pública de A firmada por la entidad en la que se confía se tiene la seguridad de que esa clave pública es de quien dice ser. Si en esa situación el Canalla intentara lo mismo que antes no funcionaría porque la clave pública que envía a B no está firmada por la entidad de certificados. Esa es la razón por la que la entidad de certificados (CA) debe ser de toda confianza y si alguien consigue la clave privada de ese CA podrá firmar como si fuera ella y por tanto los certificados ya no serán seguros.

¿Es esto? ¿lo tengo bien entendido?

Tengo mas preguntas pero esperaré a ver si esto que he puesto está bien.

 ;D

Esto en realidad, está incorrecto, con las claves públicas, se cifra. Solo puede firmar una clave la CA.


En esto, lo mismo que te dije antes, con las claves públicas se cifra. Solo el CA firma claves.


En realidad, la CA firma las claves con su clave privada, la clave pública del CA es el certificado de verificación, se utiliza para validar las claves.

Pero bueno, más o menos lo tenés claro.
Esperamos tu código de miller-rabin!.
Un abrazo
APOKLIPTICO

Wow... me voy un rato y ya postean tuto nuevo :) buenisimo, ya tengo para leer esta semana

Joer no se porque me ha dado por confundir cifrar que firmar je je je.

El código de Miller Rabin no funciona bien de momento. He metido un número que se que es primo y me dice que no lo es. Tengo que hacer algunas pruebas aún pero pienso que mañana estará ja ja ja

En cuanto a los certificados:

Existe la posibilidad de crear yo mi propio CA. Eso es razonable si no necesito interoperar con esos certificados fuera de mi dominio porque obviamente yo confío en mi mismo. El inconveniente de eso es que los demás no confian en mi.

La segunda opción es contratar a una empresa CA externa tal como verisign. El problema de eso es que ellos cobran y si necesito muchos certificados puede ser un problema presupuestario.

Hay varios tipos de certificados: los x509 creo que son aquellos en los que yo tengo mi propia CA pero hay otros.

Por otra parte esté la cuestión del formato de los certificados. El mas utilizado es el PEM y DER que se suelen usar para las claves privadas. Todo esto lo tengo muy confuso. De hecho creo que estos formatos se corresponden con marcas registradas y así el pkcs#12 es el que usa Microsoft, PEM en el mundo unix y DER. Entiendo que esto debe ser un problema porque habrá veces que hay que extraer la información de un DER para convertirlo a PEM o lo que sea.

Aquí un enlace sobre los PEM, DER y pkcs
http://publikaccion.blogspot.com/2007/05/tipos-de-formatos-de-certificados.html (http://publikaccion.blogspot.com/2007/05/tipos-de-formatos-de-certificados.html)

Aquí hay una buena ayuda para openssl (aunque en ingles) que ayuda a ver las distintas opciones y posibilidades.
http://www.madboa.com/geek/openssl/ (http://www.madboa.com/geek/openssl/)

Aquí hay un resumen de los distintos formatos PKCS
http://es.wikipedia.org/wiki/PKCS (http://es.wikipedia.org/wiki/PKCS)

Esto si que es un lio. Dificilo no pero lioso si.

 ;D

Capítulo V. Este capítulo fue escrito mientras se escuchaba: Foo Fighters (In your honor), Funkadelic (Maggot Brain).

Hola gente! Como va todo?
Bueno, estuve viendo un poco todo lo que es criptoanálisis, bueno es un área bastaaante extensa, pero vamos a tratar de cubrir lo más posible. Empecemos entonces!


En resumen, el criptoanálisis estudia los algoritmos y los ciphertexts con el fin de encontrar posibles maneras de romper los cifrados o al menos de disminuir su complejidad, también se incluye el análisis de ciphertexts para conseguir el algoritmo de cifrado, en caso de que este se desconozca.

Hay distintos tipos de ataques, dependiendo en la cantidad de información que poseamos sobre el cifrado, es decir, si poseemos el algoritmo, poseemos el máximo de la información posible para el criptoanálisis, ya que con este, podemos hacer nuestros propios ciphertexts con claves que nosotros definamos. Sin embargo, hay un nivel mayor de información, que sucede cuando poseemos de antemano una vulnerabilidad del algoritmo, por ejemplo, dos ciphertexts idénticos originados en base a claves diferentes y plaintexts iguales, lo que significa que hay una colisión en el algoritmo.

Pero antes de empezar a definir los distintos criptoanálisis, vamos a explicar un concepto clave, el de la complejidad.


Esto quiere decir, la complejidad es una estimación de los recursos necesarios para determinada tarea. Por ejemplo, la complejidad de un algoritmo de fuerza bruta es exponencial, ya que esta aumenta de dicha manera a medida que aumenta la cantidad de caracteres.

Para definir la complejidad, se utiliza la notación Big "O" ó "Cota asintótica". La complejidad se puede definir en caso de que existan variables probabilísticas como "Cota superior asintótica", "Cota inferior asintótica" y "Cota ajustada asintótica" las cuales sirven para definir respectivamente los peores y mejores casos, y el promedio de casos de complejidad.
Volviendo al ejemplo anterior, la complejidad de un algoritmo de fuerza bruta, es O(C^n) C > 1.
Utilizando ahora como ejemplos los algoritmos de test de primalidad vistos en el capítulo anterior:
Ingenuo sin optimizaciones: O(n).
Ingenuo hasta sqrt(n): O(sqrt(n)).
Ingenuo probando solo primos hasta sqrt(n): O(sqrt(n) / ln(n)).
Miller-Rabin: O(a*log^3(n)). Siendo "a" la cantidad de iteraciones.
Fermat: O(log(n)).
Solovay-Strassen: O(log(n)).
AKS deterministic test: O(log^5(n)).

La complejidad de un algoritmo puede ser (en orden de los más eficientes a los menos eficientes).
Constante O(1).
Logarítmica O(log(n)).
Potencia fraccional O(n^c) 0 < c < 1.
Lineal O(log(n)).
Cuasi-Lineal O(n*log(n)).
Cuadrática O(n^2).
Polinómica O(n^c) c > 1.
Exponencial O(c^n) c > 1.
Factorial O(n!).

De esta manera, se pueden evaluar que tan feasibles son las rupturas de determinado algoritmo.
Fuentes:
http://es.wikipedia.org/wiki/Criptoan%C3%A1lisis (http://es.wikipedia.org/wiki/Criptoan%C3%A1lisis)
http://en.wikipedia.org/wiki/Computational_complexity_theory (http://en.wikipedia.org/wiki/Computational_complexity_theory)
http://es.wikipedia.org/wiki/Cota_superior_asint%C3%B3tica (http://es.wikipedia.org/wiki/Cota_superior_asint%C3%B3tica) (Ver también artículo en inglés).

---

Ciphertext-only attack.
En este ataque se posee uno o más ciphertexts y se desea conseguir el plaintext o la clave de cifrado. Estos ataques se utilizan cuando no se poseen o no son necesarios los plaintexts para compararlo con el ciphertext. Un caso famoso es el criptoanálisis hecho a la máquina de cifrado "Enigma" utilizada en la segunda guerra mundial. Casos más recientes, incluyen el ataque al protocolo PPTP de microsoft, que utilizaba RC4 y el de WEP que también utiliza el mismo. Como sabemos, el algoritmo de generación de keystream del RC4 contiene fallas que generan colisiones, con suficiente keystream, se puede conseguir la clave y de esta manera conseguir el plaintext.
También cualquier ataque de fuerza bruta, se incluye en esta categoría.

Known-plaintext attack
En este caso, se posee uno o más ciphertexts y sus correspondientes plaintexts. Estos se pueden analizar con el fin de encontrar la clave de cifrado.
Históricamente, el algoritmo Vernam o XOR, es suceptible a este tipo de análisis, ya que si plaintext XOR clave = ciphertext, al ser XOR una operación reversible, ciphertext XOR plaintext = clave.
Algunas versiones del algoritmo de cifrado de ZIP también es suceptible a este tipo de ataques, reduciendo la complejidad del ataque a niveles casi constantes.

Chosen-plaintext attack
En este tipo de ataques, se posee la capacidad de cifrar cualquier plaintext y obtener los ciphertexts, pero no se posee la clave. Y tiene como fin obtener la misma. Este parece un caso poco realista, pero sin embargo, este ataque va a ser el más importante para nosotros, ya que si uno posee una clave pública de un cifrado asimétrico, posee la capacidad de cifrar, pero no de descifrar. Esto es lo que uno va a buscar.
Una variante del Chosen-plaintext attack, es el "Adaptive chosen-plaintext attack" en el cual se cifran determinados plaintexts y basado en la información obtenida, se continúa cifrando.

Chosen-ciphertext attack
En este caso, se posee la capacidad de elegir el ciphertext que se quiere descifrar y obtener su plaintext, pero sin poseer la clave de descifrado ni de cifrado (en caso de un algoritmo asimétrico). Y se pretende obtener las mismas.
ElGamal es un algoritmo que es débil contra este tipo de ataques y se debe modificar para que sea utilizable en estos contextos sin presentar un riesgo de seguridad.
También existe una variante Adaptive de este ataque. En el cual se descifran determinados ciphertexts y basado en la información obtenida, se continúa descifrando ciphertexts hasta obtener la clave.

Related-key Attack
En este ataque, se obtienen diversos ciphertexts cifrados con distintas claves, pero que estas claves tienen alguna relación matemática, por ejemplo que son acumulativas, son múltiplos entre sí o se conoce que una parte de la clave nunca cambia.
El criptoanálisis que se hizo con WEP, está basado en este tipo de ataques.

---

Para más ejemplos prácticos: http://warzone.elhacker.net (http://warzone.elhacker.net). Tiene muy buenos desafíos.

Ciphertext-only attack

Algoritmo: Sustitución simple.
Ciphertext: Este es uno de los algoritmos de cifrado más simples, que constan en reemplazar con un patrón determinado cada letra por otra letra.
Por ejemplo, la "A" con una "T", la "D" con una "J", etc.
Primero, tenemos que determinar que clase de plaintext estamos tratando de conseguir. En este caso, vamos a asumir que es una oración en español. En un caso real y más complejo, se puede conseguir la información mirando la extensión del archivo, algún encabezado o header o buscando el origen de dicho ciphertext.

Para este ciphertext, vamos a utilizar un ataque conocido como "análisis de frecuencias" que se basa en la premisa de que en un determinado idioma, se utilizan algunas letras más que otras. En el español, estas vienen en este orden: "E A O S R N I D L C T U M P B G V Y Q H F Z J X W K". De la más frecuente a la menos frecuente.

Para esto, podemos utilizar esta herramienta, creada por un Spider-Net usuario de elhacker.net.
http://foro.elhacker.net/programacion_vb/source_the_golden_bug_analisis_de_frecuencia-t231056.0.html (http://foro.elhacker.net/programacion_vb/source_the_golden_bug_analisis_de_frecuencia-t231056.0.html)
Aunque también podemos utilizar cryptool.

Analizamos la frecuencia, y vemos que la "G" es la que tiene mayor frecuencia, seguida por J O T A X Y R D W C U P I S H F V B Z E K L N M Q. "M" y "Q" no aparecen en el texto, entonces las ponemos al final.
Reemplazamos las primeras 2 letras "JW", y nos queda "AC", parece ser "AL" entonces cambiamos todas las "W" por "L" en vez de "C".
Continuamos analizando las palabras más pequeñas, ya que son las más reconocibles. A medida que vayamos encontrando las sustituciones, vamos a poder ir descifrando cada vez más el texto.
Tengan en cuenta que es posible que sobre todo en textos pequeños, la correlacion de frecuencias no sea exacta. Cuanto más grande es el texto a descifrar, más fácil será hacerlo.
Se lo dejo a uds para que practiquen. Fíjense si lo pueden descifrar (por favor no posteen las soluciones).

Ahora, algo muy importante: Como hago para enseñarle a un programa a interpretar cuando ha conseguido el plaintext?.
Esto es algo muy importante, ya que uno puede fácilmente ver cuando una imagen, documento, texto o programa está correctamente descifrado, pero como hace un programa?
En caso de un texto cifrado, se puede analizar buscando palabras comunes. Si este es una imagen, se pueden buscar patrones que caracterizan a determinada imágenes. Pero sin embargo, uno puede ahorrarse todo esto buscando headers, estos son strings o caracteres que sirven para identificar que un determinado archivo es de determinado tipo. Por ejemplo, los ejecutables comienzan con "MZ" o "PE", los rar dicen "RAR" al inicio del archivo, y así sucesivamente.

Otro de los métodos utilizados para identificar un plaintext, es utilizando la entropía, como ya vimos, la entropía es un análisis del desorden, los algoritmos de cifrado y compresión buenos, suelen tener una salida de entropía casi máxima, sin importar los datos de entrada. Esto nos puede servir si estamos descifrando un texto, para identificarlo, ya que su entropía va a ser muy baja.


Known-plaintext attack

Algoritmo: XOR.
Ciphertext: "25 15 1C 0F 09 49 03 01 49 16 1C 0E 50 00 19 05 0E 19 1A 08 0F 4F 11 11 1D 0A
4C 05 11 54 0F 0C 1D 0C 11 0C 02 9F 07 50 11 07 43 1C 04 17 1A 19 05 0D 11 10
49 07 0A 41 05 01 0A 4C 0A 1F 19 19 02 9E 8C 11 43 4B 2F 1B 09 04 3D 0C 00 0D
50 07 0A 4C 0C 06 1B 05 16 0C 08 1F 01 0A 08 06 50 11 07 43 1A 0F 50 0B 0E 1F
1D 11 17 08 07 00 41 00 1D 04 15 0C 13 00 06 43 0B 04 50 0C 98 08 00 17 1B 49
02 0D 08 15 1D 1F 03 49 00 15 1B 02 4F 15 15 02 0A 1F 49 02 11 05 02 0C 08 1F
01 0A 08 06 03 54 0A 0C 01 41 1C 0E 4B 0F 1B 19 04 1D 0C 08 13 11 09 86 0D 47".

Está en hexa ya que si lo pongo en ascii, no van a poder ver muchos de los símbolos.

Ahora, imagínense que nos revelan la fuente del plaintext por alguna razón.
Plaintext: "Desde su uso original para la formación en seguridad de una compañía, CrypTool ha evolucionado en un destacado proyecto de código abierto para temas relacionados con la criptografía."

Entonces, sabemos que el algoritmo XOR, aplica un or exclusivo byte por byte de esta manera: si el plaintext es "computadora" y la clave "1234":
c o m p u t a d o r a
1 2 3 4 1 2 3 4 1 2 3

El XOR es reversible, osea que si m XOR k = c, entonces, c xor k = m.
Pero también significa que m XOR c = k. Es decir, que plaintext xor ciphertext = clave.
Sabiendo esto, podemos calcular la clave:
Vamos a hacer XOR byte a byte hasta que veamos que la clave empieza a repetirse.
25 15 1C 0F 09 49 03 01 49 03 01 49
44 65 73 64 65 20 73 75 20 75 73 6f
61 70 6f 6b 6c 69 70 74 69 63 6f  61

Entonces vemos que la clave es: "apokliptico".

Chosen-Plaintext Attack.

Realmente no se me pudo ocurrir un ejemplo simple para el Chosen-Plaintext attack, si alguien se le ocurre, por favor avíseme y lo posteamos.
Mientras tanto, para los que se atreven, un documento (http://www.google.com/url?url=http://citeseerx.ist.psu.edu/viewdoc/download%3Fdoi%3D10.1.1.65.2636%26rep%3Drep1%26type%3Dpdf&rct=j&sa=U&ei=BzDPTMKJJZaI4gaNqPXcDA&ved=0CCQQFjAF&q=chosen-plaintext+attack+example&usg=AFQjCNGKTPWzWbf7bRyOOOZts76ikcu7NQ&cad=rja) sobre el ataque Chosen-Plaintext al que fue vulnerable SSL en una de sus versiones:.

Chosen-Ciphertext Attack.

ElGamal es uno de los ejemplos más remarcables de Chosen-Ciphertext Attack.
http://es.wikipedia.org/wiki/Cifrado_ElGamal#Maleabilidad (http://es.wikipedia.org/wiki/Cifrado_ElGamal#Maleabilidad)

Related Key Attack.

El ejemplo clásico de este ataque, es el de WEP, este algoritmo utiliza RC4 para generar su keystream, que luego se utilizará para cifrar los datos de la red inalámbrica. Sin embargo, este utiliza vectores de inicialización, es decir bits utilizados para evitar que si se cifra los mismos plaintext con la misma clave de como resultado el mismo ciphertext, demasiado pequeños, causando colisiones y que estos puedan llevar al crackeo de la clave.

Aquí hay una descripción completa de la vulnerabilidad del cifrado WEP.
http://foro.elhacker.net/hacking_wireless/vulnerabilidades_del_cifrado_wep-t54992.30.html (http://foro.elhacker.net/hacking_wireless/vulnerabilidades_del_cifrado_wep-t54992.30.html)

---

Bueno, aqui termina el Capítulo V, ya la próxima entrega, vamos a continuar con criptoanálisis, utilizando estadística básica, como la moda, la media, las frecuencias, etc.
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
APOKLIPTICO

Toda la información expuesta en este taller, está protegida bajo licencia Creative Commons Attribution-NonCommercial-ShareAlike 2.5.
(http://i.creativecommons.org/l/by-nc-sa/2.5/ar/88x31.png) (http://creativecommons.org/licenses/by-nc-sa/2.5/ar/)

¿Puedo sugerir que los distintos capitulos se pongan en el post principal? Creo que facilitaria mucho la lectura y a tener una referencia.

Por lo demás el post esta genial, se agradece y mucho ;)

Saludos!

Decis ponerlos en un post aparte?

Creo que lo que quiere decir es que edites el primer post y pongas todos los capítulos juntos.

En cualquier caso es un gran trabajo.

Lo lamento, pero los posts tienen un largo máximo, y no me entran todos en uno, y no puedo intercalar un post despues del primero. Voy a ponerlos todos juntos en otro thread aparte, ok?

PD: Como van esas lecturas? preguntas?

Ya lo he visto nada mas entrar xD

Muchas gracias, asi la lectura es algo mas amena y no tiene que andar uno buscando.

Por lo demas ninguna duda, creo que esta todo bastante bien explicado, y las cosas de matemáticas se encuentran bien por internet.

Saludos!

Edito: Creo que deberias de cambiar en el otro post esto "Como siempre, las preguntas que tengan, posteenlas en este thread", para que la gente no se confunda y eso XD!

Ya mismo lo estoy modificando jejeje, el problema de copy & paste...

Solo para decir que ando muy liado, pero en cuanto pueda vuelvo a la faena je je je.

Eso del criptoanalisis suena muy interesanete xDDD. Además tengo por ahi el código Miller-Rabin que en cuanto pueda dedicarle tiempo quedará como es debido osea funcionando ja ja ja.

Un saludo

Yo estoy todavía trabajando en la parte de estadística, es bastante extenso y quiero que lo entiendan, ya que sirve mucho para descubrir patrones en cosas que deberían ser aleatorias.

Hey gracias por el tema, estuve un poco liado con examenes que luego se me amontona todo  :xD

Saludos!

Capítulo VI (Final!). Este capítulo fue escrito mientras se escuchaba: The Beatles (2009 Remastered discography).

Buenas! Hoy les traigo la última entrega del taller de Criptografía Asimétrica. La idea es que cuando todos ya estén listos, nos pongamos a crear un algoritmo nuevo. Avisen entonces cuando ya estén, asi podemos ponernos.
Esta entrega va a ser distinta de las demás, estuve trabajando en un código que hace diversos testeos en generadores pseudoaleatorios, con el fin de encontrar fallas en los mismos. Para que un PRNG sea seguro para ser usado en criptografía, debe cumplir con las siguientes normas:
- Tener períodos largos.
- La salida debe tener una distribución uniforme.
- Los espacios entre ciertos valores, no corresponden a los de una distribución aleatoria.
- No debe haber correlación entre los valores sucesivos de la salida.
El programa que creé, prueba todas menos la última, que como vamos a ver más adelante, es una de las más importantes.

NOTA: El programa crea un par de gráficos que muestran la distribución de frecuencias y otro que muestra la distribución de las diferencias. Para esto, van a necesitar un programa llamado Graph. Lo pueden bajar de aquí (http://www.padowan.dk/graph/). Es freeware, asi que no van a tener problemas.

El código está adjuntado al post, es demasiado grande para pegarlo y realmente no confío en rapidshare y similares.
El código utiliza el PRNG que utiliza c++, que es el clásico generador lineal congruencial con distintos parámetros según el compilador. Pero se puede utilizar cualquier prng con solo codearlo en el programa.
Como entrada, el código pide un tamaño de la muestra, que luego va a ser multiplicado por 256, para que sea posible que haya al menos uno de cada uno de los 256 posibles caracteres. Utiliza memoria dinámica para guardar los valores, es claro que tiene un límite este número, si lo exceden, no va a poder asignarlo y a pesar de que tiene un chequeo, probablemente crashee.
Como salida, da algunos datos estadísticos y luego hace unas pruebas aprobadas por el FIPS140-1 para probar aleatoriedad de la muestra. Vamos a verlos uno por uno. Al final de cada medida estadística puse el valor buscado en un PRNG ideal, debemos acercarnos lo más posible a este valor.
Defino antes de empezar un par de conceptos:
Función de distribución: Muestra cuantas veces aparecen cada uno de los valores en un gráfico.
Función de distribución uniforme: Función ideal en la cual todos los valores aparecen la misma cantidad de veces, un PRNG debe aproximarse lo más posible a dicha distribución.

---

Tamaño de la muestra (n): 256 * x. Siendo "x" el tamaño que el usuario elija. Si esta excede "4000", se toman solo los primeros 4000 * 256 datos. Esto es por el teorema central del límite que dice que si se toman muestras suficientemente grandes, las medidas estadísticas van a ser idénticas con un márgen de error despreciable en comparación con las medidas de la muestra total. Es más que nada para agilizar los cálculos.

Mean, Media o promedio (Xm): Media aritmética estándar. Xm = Sum(xi) / n. Sumatoria de todos los valores dividido la cantidad de valores. Valor buscado = 127,5 (255/2).

Mode, Moda o Modo (Mo): Valor modal, es decir el más repetido de todos. Puede existir más de uno, pero solo se muestra el primero que se encuentra. Valor buscado = No definida, es decir, que no haya un valor que salga más que otros.

Anti-Mode o Anti-Moda (aMo): Probablemente tenga otro nombre que desconozco, pero representa el valor menos repetido en la muestra. Valor buscado = No definida, es decir, que no haya un valor que salga menos que otros.

Standard deviation, desviación estandar o desviación típica(Sx): Es una medida de dispersión que indica que tan distribuidos están los valores a lo largo de los rangos, en este caso, 0-255. Sx = sqrt(Sum((xi - Xm)^2) / n) = sqrt(Sum(xi^2)/n - Xm^2). Valor buscado = 73.9.

Assimetry coefficient o coeficiente de asimetría (As): Determina que tan simétrica es la distribución, si hay valores que se repiten más que otros, va a afectar la simetría. Sin embargo, si el/los valores que se repiten, lo hacen de la misma manera que x+Xm mod 256 siendo "x" el valor, entonces no va a afectar la simetría. El lado que cause la asimetría, es decir, que tenga mayor frecuencia, se denomina "sesgo". Si As > 0, entonces el sesgo está hacia la derecha, si As < 0, el sesgo estará hacia la izquierda. Si As = 0, la distribución será perfectamente simétrica. As = Sum((xi - Xm)^3) / n / Sx^3. Valor buscado = 0, es decir que sea simétrica.

(http://upload.wikimedia.org/wikipedia/commons/thumb/1/1c/SkewedDistribution.png/200px-SkewedDistribution.png)
Aquí vemos que el sesgo está hacia la derecha, con un As > 0.

Kurtosis o curtosis (Ks): Determina que tan distantes están distribuidos los valores al rededor de la media. Las distribuciones definidas teóricas, como por ejemplo la Normal, la de Gauss, la de Poisson, la uniforme, etc. Tienen una curtosis esperada.

Ks = Sum((xi - Xm)^4) / n / Sx^4 - 3.

(http://upload.wikimedia.org/wikipedia/commons/thumb/e/e6/Standard_symmetric_pdfs.png/800px-Standard_symmetric_pdfs.png)
D: Distribución de Laplace. Ks = 3.
S: Distribución secante hiperbólica. Ks = 2
L: Distribución logística. Ks = 1.2
N: Distribución normal. Ks = 0
C: Distribución coseno aumentada. Ks = −0.593762.
W: Distribución de Wagner. Ks = -1.
U: Distribución uniforme. Ks = -1.2.
Valor buscado = -1.2, es decir, uniforme.

Entropy o entropía (Ep): Busca la uniformidad en la muestra, se centra en la repetición de cada uno de los caracteres posibles. Ep = Sum(-fr(i) * log2(fr(i))). Donde fr(i) son las frecuencias relativas, es decir, las veces que se repite "i" sobre "n". Valor buscado = 8.

Deciles D(x): Un decil representa el valor que acumula el x*10% (siendo 0 < x < 10) de la muestra. Es decir, si tenemos un gráfico de una distribución, dividimos verticalmente el gráfico en 10 partes iguales, el valor del eje "x" en donde cae la primera división, es el primer decil, el valor del eje "x" en donde cae la segunda división, es el segundo decil y así sucesivamente. Para calcular, se deben ir sumando las frecuencias de cada uno de los valores, hasta que la siguiente suma supere n/10*x, llamamos entonces el valor de ese valor "i", a la suma de frecuencias la llamamos F(n-1) y la fórmula es: D(x) = i + (x/10 * n - F(n-1)) / f(i).

Valor buscado = x * 25.5.

---

Uno de los tests necesarios para un PRNG, es probar que no tenga un período muy corto. Todos los PRNG tienen un período, es decir, un momento en el cual vuelve a empezar la sucesión de dígitos aleatorios. Esto puede ser problemático para un algoritmo criptográfico, ya que si se consigue una parte del PRNG, se puede asumir que va a ser exactamente igual una vez que se reinicie el período. Sin embargo, los buenos PRNG, tienen períodos muy largos, por ejemplo el Mersenne Twister tiene un período de 2^19337 -1, suficiente para cualquier cifrado. Sin embargo, el PRNG que viene por defecto en C++ (linear congruential generator) tiene un período de 2^24 es decir = 16777216 o 16 Mbytes. Si uno usase eso como keystream para cifrar un archivo utilizando xor cuyo tamaño es mayor a 16 Mbytes, con conseguir parte del plaintext, se podrían descifrar otras partes del archivo.

Buscando estas fallas, el programa busca en la muestra completa primero por una cuestion de eficiencia si hay dos valores consecutivos iguales a los primeros dos valores de la muestra, si estos coinciden, prueba entonces los siguientes 10 valores (esto es modificable cambiando el define PERIOD_SAMPLE) si estos coinciden, comienza a probar toda la muestra. Si la muestra no es lo suficientemente grande como para tener dos períodos completos, entonces da un mensaje de "repetición de período" probable, si puede completar la prueba, entonces da un mensaje de "repetición de período" conclusivo. Por último muestra el tamaño del período en potencias de 2. Valor buscado >= 2^32 (4 Gbytes).

---

Estas pruebas son las estándares creadas por el FIPS, con el fin de determinar si una muestra es lo suficientemente aleatoria. Consiste en cuatro tests: Monobit test (stream y block), poker test, runs test y long run test. Todos estos tests se deben hacer con una muestra de 20000 bits o 2500 bytes. Sin embargo, en el programa utilizo para el monobit test una muestra de 500 bytes aleatoria escojida aleatoriamente, para los demás tests, se utilizan muestras aleatorias de 2500 bytes.

Monobit test (stream y block): Consiste en medir cuantos "1" y cuantos "0" hay en una muestra y sacar una razón. El test se puede aplicar tanto con streams, es decir con el total de la muestra, o con bloques de distintos tamaños, en el programa de 8192 a 16 bits y luego se promedian las razones. En definitiva, se trata de ver si hay uniformidad entre 1s y 0s como habría en una muestra realmente aleatoria. Valores buscados [0.966557 ; 1.035840] para todas las razones. Es posible que para los tests de bloques más pequeños falle el test, es decir que en alguno de los bloques, no haya ni "1" ni "0", esto significa que hay al menos una sucesion de dos o cuatro "255" o "0" y deben ser ignorados, solo en las distribuciones más perfectas esto no ocurre. Si ya falla la de 64 bits, va a fallar luego el "long run test".

Poker test: Analiza de a nibbles (grupo de 4 bits) como si fuesen manos de poker, buscando fallas en la aleatoriedad. Se busca la frecuencia de cada uno de los nibbles (es decir de 0000 a 1111) y luego se aplica esta fórmula: Pt = (16/5000) * SUM(f(i)^2) - 5000.
Valor buscado: 1.03 <= Pt <= 57.4.

Runs test: Analiza cuantas sucesiones de los mismos bits repetidos, ya sean "0" o "1", hay en una muestra. Se deben contar la cantidad de repeticiones de x bits por separado para los "1" y para los "0".
Las repeticiones de más de 6 bits, se cuentan como si fuesen de 6. Piensen que "1" significa que no se repite ni una vez, es decir que si el bit analizado es "0" el siguiente es "1" y viceversa.
Valores buscados:
                1                       2,267 - 2,733
                2                       1,079 - 1,421
                3                       502 - 748
                4                       223 - 402
                5                        90 - 223
                6+                       90 - 223

Long runs test: Este test es facil y se puede incorporar en el anterior, en definitiva, falla si se encuentra algun bit que se repita más de 33 veces ya sea 0 o 1.

Correlación entre valores sucesivos.

Esto significa que se pueda encontrar una relación entre cada uno de los valores, que permita, teniendo uno de los valores, calcular el siguiente de manera feasible y en tiempo polinómico o cuasi polinómico. El programa no incluye testeos para buscar correlación, entonces puede no detectar ciertos PRNG que en teoría parecen perfectos, pero en la realidad contienen graves fallas.
Prueben por ejemplo modificar el PRNG del programa por lo siguiente:

unsigned long long val = 0;
unsigned long long rnd()
{
    val++;
    if(val%255 == 0) val++;
    if(val%65024 == 0) val++;
    return val;
}

Este "PRNG" tiene un período de 2^32 y medidas estadísticas cuasi perfectas.
Sin embargo, la sucesión de valores es perfectamente predecible, ya que lo único que hace es sumarle "1" al valor anterior. Los dos "if" sirven para evitar que tenga período corto.
El generador lineal congruencial tiene el mismo problema ya que los parámetros que se utilizan para calcular el siguiente valor, están hardcodeados y varían sólo un poco, con conseguir pocos valores, se podría conseguir rápidamente el siguiente valor de la secuencia. Esto sumado a su período corto, hacen a éste PRNG como potencialmente inseguro.

---

Fuentes:
http://en.wikipedia.org/wiki/Linear_congruential_generator (http://en.wikipedia.org/wiki/Linear_congruential_generator)
http://www.csm.ornl.gov/~dunigan/fips140.txt (http://www.csm.ornl.gov/~dunigan/fips140.txt)
http://en.wikipedia.org/wiki/Mersenne_twister (http://en.wikipedia.org/wiki/Mersenne_twister)


Este es el fin del capítulo VI y el fin de la parte teórica del taller de criptografía asimétrica. Posteen todas las dudas que tengan y cuando estén listos, empezamos a crear.
Un abrazo
APOKLIPTICO

El código bájenlo por acá http://web.i.elhacker.net/archivos/StatisticalAnalysis.rar (http://web.i.elhacker.net/archivos/StatisticalAnalysis.rar) (Gracias Novlucker!)

Toda la información expuesta en este taller, está protegida bajo licencia Creative Commons Attribution-NonCommercial-ShareAlike 2.5.
(http://i.creativecommons.org/l/by-nc-sa/2.5/ar/88x31.png) (http://creativecommons.org/licenses/by-nc-sa/2.5/ar/)

disculpa apokaliptico, y ahora que viene.  despues de la parte eorico que vamos ha hacer, practicar??

Perdonen el abandono, estoy extremadamente ocupado con estudios, tengo todos parciales la semana que viene y la otra.
Pero bueno, como andan esas lecturas? Entendieron algo o es todo chino básico?
Pregunten lo que no entienden, ak estamos para aprender, no importa si parece extremadamente tonta o demasiado complicada la pregunta, uds háganla y se les responderá.

Un abrazo
APOKLIPTICO

Hola a todos!

Bueno, hoy terminé con la facultad, y quería retomar el taller.
Que les parece? Continuamos??

Digan los que todavía están activos en el foro, si veo que pasan unos días y nadie responde, mando un par de PMs

Abrazo
APOKLIPTICO

El lunes me libero de todo :P

Hasta del foro :xD

Yo empiezo vacaciones alrededor del 23 so, podría continuar desde ahí.

Buenas, yo tambien estuve estudiando y además ahora esta la navidad a la vuelta de la esquina....
A principios de enero me paso de nuevo por el foro porque ahora no tengo mucho tiempo ;)

Saludos!

interesante, he ojeado todo, y esta re entrete jajaj, me me dan ganas de hacerme un cifrado personal xd... auque de tanto ver algoritmos extraño el colegio porque me hacen falta los conocimientos que tendre  al terminar la escuela... y mas todavia al entrar a la universidad...jajaja... gracias por el aporte APOKALIPTICO...(nunca mas pusiste" un abrazo apokaliptico"  :xD)...saludos

Francamente apokliptico, creo que has hecho un trabajo fenomenal. Puedo decir que habré dedicado a este taller unas 8 horas (incluyendo las búsquedas en Google sobre conceptos matemáticos que no controlaba) y debo decir que en el único apartado en el cual me he perdido un poco es en el último capítulo cuando empiezas a definir la kurtosis.
Por lo demás, he aprendido mucho y ya hay ganas de crear un algoritmo propio :D
Sólo una pregunta,  ¿cómo utilizaremos las medidas estadísticas nombradas en el último post?
¡Saludos!

Excelente explicación. Uno de los mejores protocolos de conexión remota es SSH2 RSA, que por supuesto usa criptografía asimétrica utilizando como bien dices una clave pública para cifrar la información y una privada para descifrarla. Saludos.

Pd.: por favor que la gente deje de usar telnet, ftp y similares... comprobad con nmap si los teneis habilitados y cerrad los puertos.

estoy hecho un lio con los conceptos basicos de la criptografia asimetrica :S

según entiendo, si tengo 2 sujetos A y B, y el sujeto B quiere recibir información cifrada, por parte del sujeto A, el sujeto B tendrá un clave privada (que él elige) y una clave publica que según entiendo es generada por un programa como el PGP (estoy diciendo barbaridades aqui?  :-( ) la clave pública es generada a partir de la privada.

entonces el sujeto A, usando el programa (en este caso PGP), cifra su mensaje usando la clave publica del sujeto B, y de paso le envia su clave publica, por si quiere recibir alguna respuesta.

Creo que estoy mal en mis afirmaciones por lo que agradecería las correcciones del caso.

saludos

Eso es básicamente como se cifra un mensaje, la única correcion que te hago es que la clave pública no se cifra a partir de la privada, las dos se generan desde un principio.

Vaya es muy buena lección de criptografía, haber si encuentro un buen rato en que dedicarme a aprender, muchísimas gracias por el aporte.

Enhorabuena por la capacidad de síntesis y el enorme trabajo que supone poner toda esa información en el foro. Me parece una buena base con la que empezar a estudiar el tema de la criptografía informática y sus aplicaciones en los sistemas de comunicación.

Un 10 para la selección de bandas sonoras. Todos y cada uno de los temas que escuchaba el autor del taller forman parte de mi propia banda sonora y me siento identificado con esa música. Una excelente elección.

Y por último, una pequeña crítica...

Al principio del taller dices dos cosas que me han llamado la atención. La primera es que pides a los que escriban comentarios que no usen "lenguaje SMS" y que traten de escribir sin faltas ni errores gramaticales... Bien. Me parece una buena sugerencia. Estoy cansado de que me duela la vista al leer lo que escribe la gente en cualquier sitio de Internet. Un poco de escritura legible no viene mal... El problema es que todo el texto del taller contiene un buen número de errores tanto sintácticos como gramaticales, amén de un puñado no despreciable de faltas. Predicar con el ejemplo suele ser la mejor forma de conseguir seguidores...

Y la segunda cosa que rechinaba al leerla es la siguiente... Dices que las palabras cifrar y descifrar no deben usarse, ya que en realidad son mala traduciones del inglés encrypt y decrypt. Bien. Cien por cien correcto. Me parece fantástico que alguien lo explique por fin en un foro de informática... ¿Cuál es el problema? Que, de nuevo, no predicas con el ejemplo. Por citar sólo el primer comunicado del taller, usas las siguientes palabras: link, thread, post, crackeo, infeasible, postear... Todas ellas son malas traducciones del inglés que, además, no existen en castellano. Unas posibles equivalencias serían:

• link ---> enlace
• thread ---> hilo de conversación, comunicado, ensayo...
• post ---> publicación, comunicado, comentario...
• crackeo ---> No existe. En castellano, la palabra equivalente al cracking inglés es craqueo, pero sólo se aplica al proceso de fraccionamiento térmico del petróleo. La traducción correcta sería, precisamente, descifrado.
• infeasible ---> inviable
• postear ---> publicar, comunicar, comentar...

La lista podría seguir un poco más, pero creo que ya se entiende lo que quiero decir, ¿no?

Una observación... No pretendo criticar por criticar. Ya he dicho al principio de mi comentario que el trabajo hecho por el creador de este taller me parece magnífico. Sólo quiero destacar estas dos pequeñas discrepancias por si sirven de ayuda para mejorar posteriores trabajos. La coherencia y el predicar con el ejemplo son dos buenos puntos de apoyo para crear información correcta y fácil de entender.

Un cordial saludo.

FE DE ERRATAS:

En mi anterior comentario, he escrito lo siguiente:


Obviamente, quería decir:

<<... Dices que las palabras encrιρtar y desencrιρtar no deben usarse...>>

Pido perdón por el error. He sido incapaz de editar el comentario original para corregirlo...

Reitero mi saludo.

Muy bueno este taller, la verdad, he aprendido bastante sobre criptografía, aunque creo que el último se me ha escapado algo de mis conocimientos ya que aún no he cursado Estadística, pero pronto lo haré.

Un saludo.

Exelente taller y muy bien explicado, a gente como yo que aun va a 1 de batxi y no llega a este nivel de matemáticas le ira perfecto.

Como anillo al dedo  ;-) gracias loco!

gente... que les parece esta app? se ajusta a criptografia asimetrica? disculpen mi ignorancia respecto al tema, pero recien me estoy metiendo en esto.

http://www.qlink.it

gracias!

hola, gracias por la información que compartes.

Una pregunta a tu criterio. cuál crees que es el mejor sistema de protección de la comunicaciòn en redes de sensores. La arquitectura ZIGBEE (simétrica) o la arquitectura THREAD (asimétrica). Gracias por la respuesta.