 Autor
|
Tema: Manual: Criptografía asimétrica desde cero. (Leído 46,372 veces)
|
APOKLIPTICO
 Desconectado
Mensajes: 3.871
Toys in the attic.
|
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 "encript ar" y "desenc riptar" 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?La criptografía (Del griego, literalmente «escritura oculta») asimétrica es el método criptográfico que usa un par de claves para el envío de mensajes. Las dos claves pertenecen a la misma persona a la que se ha enviado el mensaje. Una clave es pública y se puede entregar a cualquier persona, la otra clave es privada y el propietario debe guardarla de modo que nadie tenga acceso a ella. 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:   Bases de la criptografía asimétrica.Los sistemas de cifrado de clave pública se basan en funciones-trampa de un solo sentido que aprovechan propiedades particulares, por ejemplo de los números primos. Una función de un solo sentido es aquella cuya computación es fácil, mientras que su inversión resulta extremadamente difícil. Por ejemplo, es fácil multiplicar dos números primos juntos para obtener uno compuesto, pero es difícil factorizar uno compuesto en sus componentes primos. Una función-trampa de un sentido es algo parecido, pero tiene una "trampa". Esto quiere decir que si se conociera alguna pieza de la información, sería fácil computar el inverso. Por ejemplo, si tenemos un número compuesto por dos factores primos y conocemos uno de los factores, es fácil computar el segundo.
Dado un cifrado de clave pública basado en factorización de números primos, la clave pública contiene un número compuesto de dos factores primos grandes, y el algoritmo de cifrado usa ese compuesto para cifrar el mensaje. El algoritmo para descifrar el mensaje requiere el conocimiento de los factores primos, para que el descifrado sea fácil si poseemos la clave privada que contiene uno de los factores, pero extremadamente difícil en caso contrario. Fuentes: - http://es.wikipedia.org/wiki/Criptograf%C3%ADa_asim%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.htmlCualquier duda que tengan, posteenla en ESTE thread, 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. 
|
|
|
|
« Última modificación: 5 Noviembre 2010, 13:23 pm por APOKLIPTICO »
|
En línea
|
AMD Phenom II 1075T X6 @ 290 Mhz x 11 (HT 2036 Mhz NB Link 2616 Mhz) 1.23 Vcore
ASUS M4A89GTD-PRO/USB3
2x2gb G-Skill RipjawsX DDR3 1600 Mhz CL7 (7-8-7-24-25-1T)
Seagate 500 Gb
XFX HD4850 512Mb GDDR3. 650 Mhz/995 Mhz 1.1 Tflops.
|
|
|
APOKLIPTICO
Desconectado
Mensajes: 3.871
Toys in the attic.
|
Capítulo II. Este capítulo fue escrito mientras se escuchaba: Pink Floyd (Animals & The Wall).
Algoritmos asimétricos ya existentes.
En este capítulo, vamos a explorar los cifrados asimétricos ya existentes, cada uno va a ser explicado en profundidad, es posible que necesite continuar esta entrega en el capítulo III, ya que en este momento son las 23.06 pm (GMT -3), no tengo sueño por ahora, pero veremos que tan tarde se hace. RSA RSA es un algoritmo de cifrado asimétrico, creado por Ron Rivest, Adi Shamir y Len Adleman, del Instituto Tecnológico de Massachusetts (MIT) en el año 1977. Como ven, RSA son las siglas de "Rivest" "Shamir" y "Adleman". Es el primer algoritmo de cifrado asimétrico en la historia y aún es el más usado. La gran fortaleza que mantiene al RSA entre los algoritmos más seguros, es la infeasibilidad de descomponer un número grande en producto de primos. Generación de claves:1. Cada usuario elige dos números primos distintos p y q.
* Por motivos de seguridad, estos números deben escogerse de forma aleatoria y deben tener una longitud en bits parecida. Se pueden hallar primos fácilmente mediante test de primalidad. "Deben escogerse de forma aleatoria" no significa que uno tiene que pensar en un número y ponerlo apretando teclas en el numpad. Es cierto que el ser humano es una excelente máquina generadora de aleatoriedad, pero la mejor manera de generar números aleatorios, es utilizando lo que se conoce como "generadores pseudo-aleatorios", este término es largo de explicar, y por eso incluí un apartado sobre generadores pseudo-aleatorios al final del capítulo. Como semilla, se utilizan fuentes de aleatoriedad, por ejemplo, movimientos del mouse, temperaturas de los dispositivos, etc. 2. Se calcula n = p*q.
* n se usa como el módulo para ambas claves, pública y privada. Módulo: En este caso, el módulo se define como el resto de una división. Ej: 100 mod 6 = 4. 100/6 = 16 resto "4". 3. Se calcula φ (n)=(p-1)(q-1), donde φ es la función φ de Euler. Tranquilos!! Ahora explico la funcion φ de Euler!. La función φ(n) de Euler (phi), se define como el número de enteros positivos menores o iguales a n y coprimos con n. Osea, la cantidad de números menores o iguales a "n" que son coprimos con "n", es decir que no tienen ningun divisor común que no sea 1. Por ejemplo:φ(36): Primero factorizamos 36: 36 = 2 * 2 * 3 * 3 = 2^2 * 3^2. Agarramos los primos que dividen a 36 osea "2" y "3", y aplicamos esta fórmula: n * (1-1/p1) * (1-1/p2) * (1-1/p3) [...] (1-1/px). Siendo cada uno de los "p" los primos que dividen a 36. Aplicamos la fórmula y nos queda: 36 * (1-1/2) * (1-1/3) = 36 * 2/3 * 1/2 = 12. Esto significa, que existen 12 números menores a 36 que no son divisibles ni por 2 ni por 3, estos son: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, y 35. Fun right?. 4. Se escoge un entero positivo e menor que φ(n), que sea coprimo con φ(n).
* "e" se da a conocer como el exponente de la clave pública.
* Un exponente e muy pequeño (p. ej. e = 3) podría suponer un riesgo para la seguridad. Volviendo al ejemplo anterior, un número entero positivo "e" menor que φ(n), que sea coprimo con φ(n) podría ser: 5, 7 ú 11. No tienen por qué ser primos, con un "n" más grande, obtendríamos "e" que no fuesen primos. 5. Se determina un d (mediante aritmética modular) que satisfaga la congruencia de cong(1) mod φ(n)
* Expresado de otra manera, de − 1 es dividido por a φ(n)=(p-1)(q-1).
* Esto suele calcularse mediante el algoritmo de Euclides extendido.
* d se guarda como el exponente de la clave privada. El algoritmo de Euclides Extendido, se puede utilizar para calcular "d". Siendo que este algoritmo requiere conocimientos algebráicos y de matrices que realmente no tiene ningun sentido ponerse a explicar y en caso de que hiciese falta aplicarlo en algún código, este se puede conseguir googleando un rato, voy a saltar explicarlo y vamos a pasar directamente al resultado. Ejemplo: 1) p = 61 q = 53. 2) n = 61 * 53 = 3233 3) φ(n) = (p - 1) * (q - 1) = 3120. 4) e = 17. (Coprimo con 3120). (Este es el exponente público). 5) d = 2753 Recordemos que 17*2753 - 1 = 46800. Y que 46800 / 3120 = 15 (es exacta). La clave pública está compuesta por "e" y por "n", osea el exponente público y el módulo. La clave privada está compuesta por "d" y por "n", osea el exponente privado y el módulo. Cifrando:Primero, se divide el mensaje en bloques, de tal manera, que esos bloques, se puedan representar en números menores a "n". Ejemplo: Tengo el plaintext "APOKLIPTICO". Yo se que si lo quisiese expresar en números, estos serían 65, 80, 79, 75, 76, 73, 80, 84, 73, 68 y 79 (en la tabla ASCII). Obviamente este es un método ineficiente de dividir el mensaje, pero para la base teórica sirve. Entonces, para cifrar: m^e mod n = c. Siendo: "m" el bloque del plaintext, "e" el exponente público, "n" el módulo y "c" el bloque del ciphertext. Ejemplo: Mensaje = "APOKLIPTICO". n = 3233 e = 17 d = 2753 Bloques: 65, 80, 79, 75, 76, 73, 80, 84, 73, 68 y 79 (uno para cada letra). Aplicando la fórmula: 65^17 mod 3233 = 2790. 80^17 mod 3233 = 2933. [...] 68^17 mod 3233 = 1759. 79^17 mod 3233 = 1370. Descifrando:Se obtienen los paquetes cifrados y se les aplica esta fórmula: c^d mod n = m. Siendo: "c" el bloque del ciphertext, "d" el exponente privado, "n" el módulo y "m" es el bloque original del plaintext. Comprobémoslo con un ejemplo: 2790^2753 mod 3233 = 65 2933^2753 mod 3233 = 80 [...] 1759^2753 mod 3233 = 68 1370^2753 mod 3233 = 79 Ahora, ustedes se preguntarán como hago para elevar 2790 a la 2753ava potencia. La respuesta es muy simple: No hace falta hacerlo. Se utiliza un método llamado "exponenciación modular" que en definitiva, es aplicar el módulo cada vez que multiplicamos por la base. Ejemplo: 77^6 mod 10: 77*77 mod 10 = 9 (Exponente = 2). 9*77 mod 10 = 3 (Exponente = 3). 3*77 mod 10 = 1 (Exponente = 4). 1*77 mod 10 = 7 (Exponente = 5). 3*77 mod 10 = 9 (Exponente = 6). Resultado: 9. Si uno agarra la calculadora y hace 77^6 = 208422380089 mod 10 = 9. Esto con un pequeño loop en un programa se puede hacer rápidamente. function modular_pow(base, exponent, modulus) c := 1 for e_prime = 1 to exponent c := (c * base) mod modulus return c
Eso es en pseudocódigo para los entendidos. Fuentes y lecturas recomendadas:http://es.wikipedia.org/wiki/RSA
http://foro.elhacker.net/criptografia/rsa_para_no_iniciados-t67109.0.html
http://es.wikipedia.org/wiki/N%C3%BAmeros_primos_entre_s%C3%AD
http://es.wikipedia.org/wiki/Algoritmo_de_Euclides#Algoritmo_de_Euclides_extendido
Diffie-Hellman Algoritmo de intercambio de claves Diffie-Hellman por Braulio.
ElGamal Elgamal, es un cifrado asimétrico basado en el intercambio de claves Diffie-Hellman, este algoritmo fue creado en 1985 por Taher Elgamal. Este algoritmo se puede utilizar tanto para cifrar datos como para crear firmas digitales. Este algoritmo se utiliza en el conocido sistema de cifrado y firmas digitales PGP y en su equivalente freeware GPG. Su fortaleza se basa en la imposibilidad de calcular eficientemente el logaritmo discreto. Generación de claves.Se elige "p" que va a ser un número primo grande. Se elige "g" que es un generador del grupo multiplicativo Gp, esto es un número que elevado a sucesivas potencias modulo "p", va a dar todos los números del conjunto exáctamente una vez, este conjunto, está formado por todos los números que son coprimos con "p", como "p" es primo, ese conjunto contendrá todos los números de 1 a p-1: Ejemplo: p = 19 g = 2. Todas las exponenciaciones son mod p: 2^1 = 2 2^7 = 14 2^13 = 3 2^2 = 4 2^8 = 9 2^14 = 6 2^3 = 8 2^9 = 18 2^15 = 12 2^4 = 16 2^10 = 17 2^16 = 5 2^5 = 13 2^11 = 15 2^17 = 10 2^6 = 7 2^12 = 11 2^18 = 1 Como ven, todos los numeros aparecen en las primeras 18 potencias. Las siguientes 18 potencias darán devuelta la misma seguidilla de números. Se elige "k" tal que 2 <= k <= (p -2). La clave pública será entonces compuesta por p, a y (a^k mod p). La clave privada será entonces "k". CifradoSe recibe la clave pública compuesta por p, a y (a^k mod p). Se divide en bloques el plaintext como se hizo con RSA, cada bloque "m" de tal manera que queden menores a "p". Se elige un entero aleatorio "l" tal que 2 <= l <= (p-2). Se calcula: d = a^l mod p e = m * (a^k)^l mod p. El ciphertext entonces será "d" y "e". DescifradoSe utiliza la clave privada "k" para computar: m = d^(p-1-k)*e mod p. "m" es el bloque del plaintext. Ejemplo:Elegimos "p" = 541 y "a" = 2. Comprobamos que "a" sea generador del grupo multiplicativo finito Ap. Para esto, podemos usar herramientas existentes o programar nuestra propia pieza de código, yo hice una en c++, es muy ineficiente y hay algoritmos de aproximacion ya existentes que lo hacen más facil, este lo pueden encontrar en el apéndice "B". Elegimos "k" = 113 tal que 2 <= k <= (p-2). Definimos entonces: Clave pública = p, a y a^k mod p = 541; 2; 454. Clave privada = 113. Plaintext = hola. Lo dividimos por caracter según su valor ascii: 104, 111, 108, 97. Elegimos "l" = 14. Calculamos el ciphertext: 2^14 mod 541 = 154. 104 * 454^14 mod 541 = 279. [...] El primer bloque cifrado sería: 154; 279. Si lo queremos descifrar: 154^(541-1-113)*279 mod 541 = 104. Tenemos devuelta el plaintext. Recuerden que todas esas exponenciaciones, se deben resolver por una cuestion de aprovechamiento de recursos y facilidad, con exponenciación modular. Fuentes y lecturas recomendadas:
http://www.usna.edu/Users/math/wdj/book/node48.html
http://www.informatics.indiana.edu/markus/i400/lecture7.ppt (Ignoren la última parte sobre criptoanálisis, zero-knowledge y escrow method).
http://es.wikipedia.org/wiki/Cifrado_ElGamal (Bastante complicado de entender, conocimientos de Álgebra de grupos)
Apéndice A: Generadores de números Pseudo-aleatorios. A.K.A. PRNG (Pseudo-Random Number Generator).Un generador pseudo-aleatorio, es una fórmula matemática que basado en un número base, llamado "semilla" o "seed", da como salida números que tratan de asemejar aleatoriedad. Por qué digo "Asemejar"? Ninguna fórmula matemática puede por si sola generar una secuencia de números realmente aleatorios, ya que en las matemáticas, hay una serie de causa-consecuencia que lleva a un resultado final, que siempre va a ser el mismo. Para ponerlo en términos más simples 2 + 2 va a ser siempre 4. Los PRNG más famosos son el Blum Blum Shub, el Fortuna y el Mersenne Twister. Los PRNG, están presentes en gran parte de los algoritmos, ya sea como parte del cifrado en si o en la generación de claves, lo que hace que sean importantísimos para la seguridad del algoritmo, para ser seguros, deben cumplir con estas características: a) Dar una salida que incluya todo el rango de números que se le pide de manera distribuida, maximizando la entropía, osea, tratando de que haya igual cantidad de cada número. b) No ser previsibles. c) La semilla no debe ser posible de conseguir teniendo la salida. Otro factor que hace inseguros los PRNG, es la complejidad de la semilla, si un PRNG se le da como semilla un número "n", la salida de dicho PRNG será siempre la misma hasta que se cambie dicho número. Entonces, si uno tiene como semilla al crear una clave criptográfica algo demasiado simple, otra persona podría usar esa semilla para producir sus propias claves, haciendo inútil el cifrado de datos.
Apéndice B: Pequeño código para comprobar si "g" es generador de grupo multiplicativo finito "Gp".#include <iostream> #include <math.h> #define GENERATOR 2 #define MODULUS 19 using namespace std; long modpow(long modulus, long base, long exponent); int main() { bool testarray[MODULUS]; bool gen = true; for(int i = 0; i < MODULUS - 1;i++) testarray[i] = false; for(int i = 0; i < MODULUS - 1;i++) { long long r = modpow(MODULUS, GENERATOR, i+1); if(testarray[r]) { gen = false; break; } testarray[r] = true; if(i%10000 == 0) cout << i << endl; } if (gen) for(int i = 1; i < MODULUS; i++) if(!testarray[i]) { gen = false; break; } if (gen) cout << "Generator!" << endl; else cout << "Not a generator" << endl; } long modpow(long modulus, long base, long exponent) { long Output = 1; for(int i = 1; i <= exponent; i++) { Output = (Output * base)%modulus; } return Output; }
Como ven, definí la funcion modpow que es como había dicho antes, la exponenciación modular.
Bueno, por una cuestión de que ya tienen suficiente con estos algoritmos, el algoritmo DSA, será puesto en la siguiente entrega.
Cuando vea que ya no hay más preguntas, pondré el siguiente Capítulo.
Cualquier error que se llegue a encontrar, por favor comunicarmelo por PM.
Un abrazo
APOKLIPTICOToda la información expuesta en este taller, está protegida bajo licencia Creative Commons Attribution-NonCommercial-ShareAlike 2.5.
|
|
|
|
|
En línea
|
AMD Phenom II 1075T X6 @ 290 Mhz x 11 (HT 2036 Mhz NB Link 2616 Mhz) 1.23 Vcore
ASUS M4A89GTD-PRO/USB3
2x2gb G-Skill RipjawsX DDR3 1600 Mhz CL7 (7-8-7-24-25-1T)
Seagate 500 Gb
XFX HD4850 512Mb GDDR3. 650 Mhz/995 Mhz 1.1 Tflops.
|
|
|
APOKLIPTICO
Desconectado
Mensajes: 3.871
Toys in the attic.
|
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: DSA (Digital Signature Algorithm). 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. DSA (Digital Signature Algorithm, en español Algoritmo de Firma digital) es un estándar del Gobierno Federal de los Estados Unidos de América o FIPS para firmas digitales. Fue un Algoritmo propuesto por el Instituto Nacional de Normas y Tecnología de los Estados Unidos para su uso en su Estándar de Firma Digital(DSS), especificado en el FIPS 186. DSA se hizo público el 30 de agosto de 1991, este algoritmo como su nombre lo indica, sirve para firmar y no para cifrar información. Una desventaja de este algoritmo es que requiere mucho más tiempo de cómputo que RSA. 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.htmhttp://es.wikipedia.org/wiki/DSA
Hashes En informática, hash se refiere a una función o método para generar claves o llaves que representen de manera casi unívoca a un documento, registro, archivo, etc., resumir o identificar un dato a través de la probabilidad, utilizando una función hash o algoritmo hash. Un hash es el resultado de dicha función o algoritmo.
Una función de hash es una función para resumir o identificar probabilísticamente un gran conjunto de información, dando como resultado un conjunto imagen finito generalmente menor (un subconjunto de los números naturales por ejemplo). 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
Fuentes:
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://en.wikipedia.org/wiki/MD5
Criptografía Simétrica La criptografía simétrica es un método criptográfico en el cual se usa una misma clave para cifrar y descifrar mensajes. Las dos partes que se comunican han de ponerse de acuerdo de antemano sobre la clave a usar. Una vez ambas tienen acceso a esta clave, el remitente cifra un mensaje usándola, lo envía al destinatario, y éste lo descifra con la misma. 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 (Muy bueno).
http://www.mscs.dal.ca/~selinger/md5collision/
http://es.wikipedia.org/wiki/Criptograf%C3%ADa_sim%C3%A9trica
http://en.wikipedia.org/wiki/Key_size
Apéndice A: Entropía.Entropía es un concepto en termodinámica, mecánica estadística y teoría de la información. La entropía se concibe como una "medida del desorden" o la "peculiaridad de ciertas combinaciones". Como la entropía puede ser considerada una medida de la incertidumbre, y la información tiene que ver con cualquier proceso que permite acotar, reducir o eliminar la incertidumbre; resulta que el concepto de información y el de entropía están ampliamente relacionados entre sí, aunque se necesitaron años de desarrollo de la mecánica estadística y de la teoría de la información antes de que esto deviniera aparente. 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%29Les paso un código que hice: 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 en ESTE thread, cuando no haya más preguntas, posteo la siguiente entrega.
Un abrazo
APOKLIPTICOToda la información expuesta en este taller, está protegida bajo licencia Creative Commons Attribution-NonCommercial-ShareAlike 2.5.
|
|
|
|
« Última modificación: 5 Noviembre 2010, 13:24 pm por APOKLIPTICO »
|
En línea
|
AMD Phenom II 1075T X6 @ 290 Mhz x 11 (HT 2036 Mhz NB Link 2616 Mhz) 1.23 Vcore
ASUS M4A89GTD-PRO/USB3
2x2gb G-Skill RipjawsX DDR3 1600 Mhz CL7 (7-8-7-24-25-1T)
Seagate 500 Gb
XFX HD4850 512Mb GDDR3. 650 Mhz/995 Mhz 1.1 Tflops.
|
|
|
APOKLIPTICO
Desconectado
Mensajes: 3.871
Toys in the attic.
|
Capítulo IV. Este capítulo fue escrito mientras se escuchaba: Yes (Magnification), Pink Floyd (The Final Cut), Green Day (Dookie), Oasis (Dig out your soul). Guten tag homies! Volvemos entonces a metaforicamente encontrarnos, esta vez con la intención de conocer en profundidad las PKI (Public Key Infraestructure), en la que está incluido los certificados y los sistemas de autenticación. También, a pedido de la gente, va a haber un apéndice con los test de primalidad más usados. Let us begin then: PKI (Public Key Infraestructure). En criptografía, una infraestructura de clave publica (o, en inglés, PKI, Public Key Infrastructure) es una combinación de hardware y software, políticas y procedimientos de seguridad que permiten la ejecución con garantías de operaciones criptográficas como el cifrado, la firma digital o el no repudio de transacciones electrónicas. En definitiva, las PKI son las únicas formas de realmente reducir al mínimo los riesgos de seguridad debido a canales inseguros de comunicación. Ya que se crean certificados que luego servirán para firmar las claves publicas de cifrados asimétricos, que a su vez se utilizarán para cifrar claves simétricas y que estas a su vez se utilizaran para crear los canales seguros. Las PKI, se conforman de la siguiente manera:  - CA (Certificate Authority o Autoridad de Certificación): Encargada de firmar las claves criptográficas, generando certificados. La seguridad que se le atribuye a un determinado certificado, se basa en la confianza que se le tiene a la CA. Si uno no puede confiar en un determinado CA, no se puede confiar en el certificado. - Certificados digitales: Son en definitiva claves públicas firmadas digitalmente, utilizadas para generar canales seguros. Para una explicación más profunda, ver el apartado "Certificados Digitales". - Computadoras y servidores: Estos son los que gozarán de los beneficios de las PKI, ya sea firmando sus claves gracias al CA, verificando que una clave pública venga de donde tiene que venir y no haya sido modificada o autentificandose utilizando claves firmadas. - VA(Verification Authority o Autoridad de Verificación), LDAP (Lightweight Directory Access Protocol) o directorios X.500: Estos son los encargados de guardar todas las claves y suministrarlos a los que lo solicitan, siempre y cuando tengan los privilegios para pedirlos. Generalmente los certificados de autenticación son dados a todos los que lo soliciten, para verificar que las claves sean válidas. Estas son también las encargadas de verificar cuales son los certificados digitales que han expirado o han sido revocados. - RA (Registration Authorities o Autoridad de Registración): Los RA's son necesarios cuando el CA no puede manejar todo el volumen de registraciones/revocaciones de claves, las RA's son las encargadas de manejar todos los datos, ordenarlos y filtrarlos y luego enviarlos a la CA para que firme las claves. Es decir, si una persona quiere firmar una clave, debe ir a la RA, hacer todos los trámites necesarios, y luego el CA recibe la clave, la firma y la reenvía al RA, que luego se la suministrará a la persona original. Pongamos un ejemplo para verlo más claramente. APOK quiere crear su servidor web, destinado a un e-commerce. Como leyó los tutoriales en el elhacker.net, sabe que debe tener conexiones seguras para sus clientes. 1) Elige como algoritmo simétrico AES-256 bits y para cifrar las claves del mismo, RSA-2048 bits. 2) Crea su clave RSA-2048 bits y contrata a un CA, le envía su clave pública y esta la firma con la clave de firmado y le devuelve un certificado digital. 3) Una vez creado el servidor, un cliente intenta conectarse: 4) El cliente, recibe el certificado digital, como la CA es una entidad conocida y su sistema operativo ya tiene cargado el certificado de verificación, este lo verifica como válido. 5) El cliente crea una clave aleatoria simétrica para el cifrado AES-256 bits y se la envía al server. Una vez creado el canal seguro, ambos pueden comenzar a intercambiar datos. Esta es la base del Handshake de TLS(Transport Layer Security) que es el sucesor de SSL (Secure Sockets Layer). Fuentes:
http://en.wikipedia.org/wiki/Public_key_infrastructure
http://en.wikipedia.org/wiki/Transport_Layer_Security
- Cryptography for Dummies by Chey Cobb. (No puedo poner el link ya que está bajo Copyright, pero entre nos, google es su amigo). Parecerá medio estúpido por el nombre, pero es un libro muy didáctico y explicativo. Lo recomiendo.
Certificados digitales. Un certificado digital es un documento digital mediante el cual un tercero confiable (una autoridad de certificación) garantiza la vinculación entre la identidad de un sujeto o entidad y su clave pública.
El certificado contiene usualmente el nombre de la entidad certificada, número de serie, fecha de expiración, una copia de la clave pública del titular del certificado (utilizada para la verificación de su firma digital) y la firma digital de la autoridad emisora del certificado de forma que el receptor pueda verificar que esta última ha establecido realmente la asociación. Recuerdan cuando vimos que la criptografía asimétrica estaba expuesta a ataques de MITM (Man in the middle)? Bueno, los certificados son la manera de evitar estos ataques MITM. Recordemos un poco: Un ataque MITM, es una técnica que se utiliza para capturar y/o modificar información que transita una red de computadoras. Se basa en, utlizando diversas técnicas (Arp poisoning, redes switcheadas, captura de paquetes wi fi, etc), situarse entre dos o más computadores, de tal manera que se pueda ver y/o modificar los paquetes que se transmiten entre las mismas. Entonces:  Si uno lo traslada a la criptografía asimétrica, un atacante "Eve" (de Eavesdropper = Escuchar secretamente), podría modificar las claves públicas que se transmiten entre Alice y Bob, con unas creadas por él mismo, permitiendo de esta manera descifrar cualquier paquete que transite el canal supuestamente seguro. Para evitar esto, se crearon los Certificados digitales, que permiten que las claves públicas creadas por una persona que intenta crear un canal seguro, puedan ser identificadas como seguras, es decir que no fueron manipuladas. Para esto, la clave va a ser firmada digitalmente por una "CA", "Certificate Authority" o "Autoridad de Certificación". Esta va a ser la encargada de crear y revocar certificados digitales, asi como de hacer de "Autoridad de confianza" (Trusted Third Party), dando seguridad de que las claves no fueron manipuladas. Generando un certificado.Para generar un certificado, primero tenemos que elegir que algoritmos utilizaremos, los tamaños de las claves y parametros de los algoritmos y si vamos a utilizar un CA o vamos a hacer como nuestro propio CA. Una herramienta para crear claves y certificados, es la conocida OpenSSL, opensource y distribuida bajo GNU. En caso de que contratemos un CA, lo único que tendremos que hacer, es crear nuestra propio par de claves y enviarle la clave pública al CA, de esta manera, el CA la firma y nos la devuelve firmada, este será nuestro certificado. OpenSSL por ejemplo, creará dos archivos con extension .key y .csr siendo la clave privada y pública respectivamente. El certificado, será un archivo con extensión .crt. Si quieren, pueden analizar un certificado conectándose a una página de manera segura y descargándolo. En firefox, se hace yendo al candadado de abajo a la derecha, en la tab de seguridad "ver certificado", "Detalles" y luego "exportar". Esto guardará el archivo .crt y lo podremos examinar. Si queremos hacer de nuestro propio CA, vamos a tener que crear nuestro certificado CA. Primero, debemos crear nuestro CA. Esto genera la clave privada (que será usada para firmar) y la clave pública o certificado CA (que será utilizado para verificar las firmas). La clave privada debe ser guardada, ya que cualquiera en posesión de esta clave, podría generar claves firmadas, que luego podrían ser utilizadas para ataques MITM. La clave pública o certificado CA, debe ser distribuido a todas las personas que vayan a recibir claves públicas firmadas por nuestro CA, para que puedan verificarlas. Luego, generaremos nuestro par de claves publica y privada y firmaremos la clave pública utilizando nuestra clave privada del CA. Ahora tenemos nuestro par de claves para ser utilizadas en cualquier conexión segura (HTTPS, FTPS, etc.). Obviamente es mucho más facil hacer firmar nuestro par de claves por una entidad reconocida, pero esto suele costar dinero. Fuentes:http://es.wikipedia.org/wiki/Infraestructura_de_clave_p%C3%BAblica
http://en.wikipedia.org/wiki/Transport_Layer_Security
http://www.openssl.org/
http://es.wikipedia.org/wiki/Certificado_digitalhttp://www.akadia.com/services/ssh_test_certificate.html
Apéndice A: Tests de Primalidad.Los tests de primalidad tienen el fin de probar con certeza si un número natural es primo, es decir que solo es divisible por si mismo y por 1. Estos números son muy importantes para los algoritmos asimétricos como ya hemos visto. Existen dos tipos de test de primalidad: los determinísticos y los probabilísticos. Los primeros, determinan con un 100% de seguridad, que el número es primo. Los segundos, determinan con un porcentaje menor al 100% de probabilidad, cuanto más tiempo se los deja funcionar, menor va a ser la probabilidad de que un número no sea primo. 1) Test simple o test ingenuo. (Deterministico).Este es el más conocido de todos los tests, y se trata simplemente de probar dividiendo todos los números naturales entre 2 y n-1 siendo "n-1" el supuesto número primo. Este test es el menos eficiente de todos, es decir el que más tiempo toma, sin embargo, se le puede hacer optimizaciones para mejorar su eficiencia: a) Probar sólo hasta la raiz cuadrada de "n". Esto es debido a que si n es compuesto, puede ser factorizado en al menos dos valores, y al menos uno de estos valores debe ser menor o igual a la raiz cuadrada de n. b) Se pueden saltear la prueba de divisibilidad no probando los números múltiplos de 2 excepto 2. Esto es debido a que si un número es divisible por un múltiplo de dos, será divisible por 2 también. c) Se puede optimizar aún más si se observa que todos los primos excepto por 2 y 3 pueden ser formados con la fórmula 6*k +/- 1 siendo "k" un número natural (esto no significa que todos los números 6*k +/- 1 sean primos. Ej:k=4 6*4+1 = 25) . Esto acelera al menos 3 veces el test de primalidad. d) También se pueden ir guardando todos los números primos que se vayan encontrando, de esta manera se puede acelerar aún más la prueba, pero esto requiere mucha memoria para guardar los mismo. Les dejo un código en C++ que incluye las optimizaciones a, b y c y su diferencia en velocidad. #include <ctime> #include <stdlib.h> #include <iostream> #include <math.h> using namespace std; bool IsPrime0(long long number); bool IsPrime1(long long number); bool IsPrime2(long long number); bool IsPrime3(long long number); long long modpow(long long modulus, long long base, long long exponent); int main() { long long number = 0; int tantes = 0; int tdesp = 0; bool prime; cout << "Introduzca un numero para probar su primalidad: "; cin >> number; if(number == 0 || number == 1) { cout << "\nError: Numero introducido invalido." << endl; return 0; } cout << "Calculando sin optimizacion..."; tantes = clock(); prime = IsPrime0(number); cout << number % 3; tdesp = clock(); if(prime) cout << "\nNumero primo\n"; else cout << "\nNumero no primo\n"; cout << "Tiempo de calculo: " << (tdesp - tantes) / (float) CLOCKS_PER_SEC << " Segundos." << endl << endl; cout << "Calculando con 1 optimizacion..."; tantes = clock(); prime = IsPrime1(number); tdesp = clock(); if(prime) cout << "\nNumero primo\n"; else cout << "\nNumero no primo\n"; cout << "Tiempo de calculo: " << (tdesp - tantes) / (float) CLOCKS_PER_SEC << " Segundos." << endl << endl; cout << "Calculando con 2 optimizaciones..."; tantes = clock(); prime = IsPrime2(number); tdesp = clock(); if(prime) cout << "\nNumero primo\n"; else cout << "\nNumero no primo\n"; cout << "Tiempo de calculo: " << (tdesp - tantes) / (float) CLOCKS_PER_SEC << " Segundos." << endl << endl; cout << "Calculando con 3 optimizaciones..."; tantes = clock(); prime = IsPrime3(number); tdesp = clock(); if(prime) cout << "\nNumero primo\n"; else cout << "\nNumero no primo\n"; cout << "Tiempo de calculo: " << (tdesp - tantes) / (float) CLOCKS_PER_SEC << " Segundos." << endl; return 0; } bool IsPrime0(long long number) { for(long long i = 2; i < number; i++) { if(number%i == 0) { return false; } } return true; } bool IsPrime1(long long number) { for(long long i = 2; i <= sqrt(number); i++) { if(number%i == 0) { return false; } } return true; } bool IsPrime2(long long number) { if(number%2 == 0 && number != 2) return false; for(long long i = 3; i < sqrt(number); i+= 2) { if(number%i == 0) { return false; } } return true; } bool IsPrime3(long long number) { bool minus = false; if(number == 2) return true; if(number%2 == 0 || number%3 == 0) return false; for(long long i = 5; i <= sqrt(number); i=i) { if(number%i == 0) { return false; } if(!minus) { i += 2; minus = true; } else { i += 4; minus = false; } } return true; }
En mi pc, para probar la primalidad de un número primo de 49 bits tardó: Sin optimizaciones: Demasiado. Con 1 Optimización: 1.64 Segundos. Con 2 Optimizaciones: 2.016 Segundos. Curioso que este tarda más que el primero. Con 3 Optimizaciones: 1.375 Segundos. Con las optimizaciones parece realmente poco tiempo comparado con el test sin optmizaciones, sin embargo, vamos a ver que este algoritmo tiene una eficiencia muy baja. Fuente: http://es.wikipedia.org/wiki/Test_de_primalidad2) Test Miller-Rabin (Probabilístico).El test original creado por Miller que es determinístico, está basado en la hipótesis de Riemann, que aún no ha sido probada, es por esto, que Rabin lo modificó para convertirlo en probabilístico. No voy a tratar la parte matemática del algoritmo, ya que es extremadamente compleja y realmente no está a mi nivel y supongo que tampoco lo estará para la mayoría de uds. El algoritmo es el siguiente: 1) Elegimos un número "n" para probar su primalidad mayor a 2 y obviamente impar. 2) Calculamos "s" de la siguiente manera, dividimos "n - 1" por 2 hasta conseguir un número impar. Entonces "s" va a ser la cantidad de veces que se dividió "n-1" para conseguir un impar. Osea n-1 = 2^s * d. Siendo "d" el número impar. 3) Se elige aleatoria y uniformemente un "a" tal que 0 < a < n. Uniforme, quiere decir que no se va a elegir dos veces el mismo "a", por cuestiones de eficiencia (no tiene sentido probar dos veces un "a"). 4) Se calcula p0 = a^d mod n y p(r) = a^((2^r)*d) mod n. Siendo "r" todos los valores naturales entre [0;s]. Si p0 <> 1 y todos los p(r) <> n-1 entonces "n" no es primo. 5) Si no se cumplen p0 <> 1 y p(r) <> n-1, entonces "n" es probablemente un número primo. 6) Cuantos más "a" se prueben, mayor será la probabilidad de que "n" sea primo. La probabilidad de que un número pasado por el test Miller-Rabin sea realmente primo, siempre y cuando los "a" escogidos sean aleatorios y uniformes, es de 1-(1/4)^k. Esto significa, que con solo probar 10 "k", tendremos un 99.99990463% de certeza de que "n" es primo. Bueno, estas funciones les permitiría aplicar el Miller-Rabin para probar primalidad. Es posible que me haya equivocado en el código y no toma valores demasiado altos, probablemente debido a un error de overflow en el módulo. Si alguien quiere optimizarlo, mejor aún! NOTA: Modifiqué la función modpow para optimizarla con el algoritmo de la exponenciación binaria. Ahora es muchisimo más rápido. bool MillerRabin(long long number, int tries) { srand(time(NULL)); if(number == 2) return true; if(number%2 == 0) return false; for(int r = 0; r < tries; r++) { long long nminus1 = number -1; int s = 0; do { nminus1 /=2; s++; }while(nminus1%2 == 0); long long a = ((long long)(rand() / (double) RAND_MAX * (number - 2) + 1))%1000; //Límite en 1000 para ayudar al cómputo y evitar overflows. bool prime = false; long long firstmp = modpow(number, a, nminus1); if(firstmp != 1 && firstmp != number -1) { for(int i = 1; i <= s; i++) { if(modpow(number, a, nminus1*pow(2,i)) == (number - 1)) { prime = true; break; } } } else prime = true; if(!prime) return false; } return true; } long long modpow(long long modulus, long long base, long long exponent) //Optimized Modpow with binary exponentiation. { long long Output = 1; long long nbase = base; long len = log(exponent) / log(2.0f) + 1; char *binexp = new char[len +10]; lltoa(exponent, binexp, 2); binexp[len] = 0; for(int i = len - 1; i >= 0; i--) { if(binexp[i] == '1') Output = fmod((Output * nbase),modulus); nbase = fmod((nbase * nbase),modulus); } return Output; }
Fuentes:
http://planetmath.org/encyclopedia/MillerRabinPrimeTest.html
http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test3) Test de Fermat. (Probabilistico)1) Se elige un número para aplicarle el test de primalidad "n". 2) Se elige aleatoria y uniformemente "a". 3) Se calcula p = a^(n-1) mod n. 4) Si "p" <> 1, entonces n no es primo. 5) Si "p" = 1, entonces n es probablemente primo. 6) Si se desea mayor seguridad sobre la primalidad, se debe calcular otros valores de "a". La probabilidad de que un número pasado por el test de Fermat sea realmente primo, siempre y cuando los "a" escogidos sean aleatorios y uniformes, es de 1-(1/2)^k. Esto significa que debemos calcular al menos 20 valores de "a" para tener la misma probabilidad de éxito que el algoritmo Miller-Rabin. Sin embargo, existe una excepció para esto: Los números de Carmichael (y no estoy hablando de la identidad secreta de "Chuck"), son números compuestos para los cuales todos los valores de a que sean coprimos con "n", "p" nos va a dar siempre 1. Esto genera una falla en el algoritmo, ya que es posible que un número compuesto de carmichael aparezca como primo. Sin embargo, los números de Carmichael son raros, hay 20138200 antes de 10^21, parecen muchos, pero en realidad significa que la probabilidad de que escogiendo un número al azar entre (2;10^21), este sea un número de Carmichael, es de 0,00000000000201382%, que es muy poca, aparte de que el "a" que se escoje, tiene que ser coprimo con el número de Carmichael. Devuelta, les presento una función para aplicar test de Fermat: bool Fermat(long long number, int tries) { srand(time(NULL)); if(number == 2) return true; if(number%2 == 0) return false; for(int r = 0; r < tries; r++) { long long a = ((long long)(rand() / (double) RAND_MAX * (number - 2) + 1))%1000; //Límite en 1000 para ayudar al cómputo. cout << "a= " << a << endl; bool prime = false; long long firstmp = modpow(number, a, number - 1); cout << firstmp << endl; if(firstmp != 1) prime = false; else prime = true; if(!prime) return false; } return true; } long long modpow(long long modulus, long long base, long long exponent) //Optimized Modpow with binary exponentiation. { long long Output = 1; long long nbase = base; long len = log(exponent) / log(2.0f) + 1; char *binexp = new char[len]; lltoa(exponent, binexp, 2); binexp[len] = 0; for(int i = len - 1; i >= 0; i--) { if(binexp[i] == '1') Output = fmod((Output * nbase),modulus); nbase = fmod((nbase * nbase),modulus); } return Output; }
Fuentes:
http://en.wikipedia.org/wiki/Carmichael_number
http://en.wikipedia.org/wiki/Fermat_primality_testBueno, hasta aquí llegue con los algoritmos, se que me falta el Solovay-Strassen(Probabilistico) y el AKS(Deterministico). Pero la verdad es que están muy por encima de mi nivel y realmente entre la estadística de hoy y la criptografía, voy a dormir en un colchón de números XD. Si alguien se anima a describirlos de tal manera que todos los demas los podamos entender, por favor, no duden en hacerlo.
Bueno, aqui termina el Capítulo IV, ya la próxima entrega, vamos a comenzar con criptoanálisis, para lo cual la estadística me va a venir como anillo al dedo (expresión porteña que significa que va a servir mucho).
Como siempre, las preguntas que tengan, posteenlas en ESTE thread. Nos vemos!!
Cualquier error que se llegue a encontrar, por favor comunicarmelo por PM.
Un abrazo
APOKLIPTICOToda la información expuesta en este taller, está protegida bajo licencia Creative Commons Attribution-NonCommercial-ShareAlike 2.5.
|
|
|
|
« Última modificación: 5 Noviembre 2010, 13:24 pm por APOKLIPTICO »
|
En línea
|
AMD Phenom II 1075T X6 @ 290 Mhz x 11 (HT 2036 Mhz NB Link 2616 Mhz) 1.23 Vcore
ASUS M4A89GTD-PRO/USB3
2x2gb G-Skill RipjawsX DDR3 1600 Mhz CL7 (7-8-7-24-25-1T)
Seagate 500 Gb
XFX HD4850 512Mb GDDR3. 650 Mhz/995 Mhz 1.1 Tflops.
|
|
|
APOKLIPTICO
Desconectado
Mensajes: 3.871
Toys in the attic.
|
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! Criptoanálisis. Criptoanálisis (del griego kryptós, "escondido" y analýein, "desatar") es el estudio de los métodos para obtener el sentido de una información cifrada, sin acceso a la información secreta requerida para obtener este sentido normalmente. Típicamente, esto se traduce en conseguir la clave secreta. En el lenguaje no técnico, se conoce esta práctica como romper o forzar el código, aunque esta expresión tiene un significado específico dentro del argot técnico.
"Criptoanálisis" también se utiliza para referirse a cualquier intento de sortear la seguridad de otros tipos de algoritmos y protocolos criptográficos en general, y no solamente el cifrado. Sin embargo, el criptoanálisis suele excluir ataques que no tengan como objetivo primario los puntos débiles de la criptografía utilizada; por ejemplo, ataques a la seguridad que se basen en el soborno, la coerción física, el robo, el keylogging y demás, aunque estos tipos de ataques son un riesgo creciente para la seguridad informática, y se están haciendo gradualmente más efectivos que el criptoanálisis tradicional. 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.La teoría de la complejidad computacional es la rama de la teoría de la computación que estudia, de manera teórica, la complejidad inherente a la resolución de un problema computable. Los recursos comúnmente estudiados son el tiempo (mediante una aproximación al número y tipo de pasos de ejecución de un algoritmo para resolver un problema) y el espacio (mediante una aproximación a la cantidad de memoria utilizada para resolver un problema). Se pueden estudiar igualmente otros parámetros, tales como el número de procesadores necesarios para resolver el problema en paralelo. La teoría de la complejidad difiere de la teoría de la computabilidad en que ésta se ocupa de la factibilidad de expresar problemas como algoritmos efectivos sin tomar en cuenta los recursos necesarios para ello. 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://en.wikipedia.org/wiki/Computational_complexity_theory
http://es.wikipedia.org/wiki/Cota_superior_asint%C3%B3tica (Ver también artículo en inglés).
Tipos de criptoanálisis. 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 attackEn 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 attackEn 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 attackEn 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 AttackEn 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.
Ejemplos prácticos Para más ejemplos prácticos: http://warzone.elhacker.net. Tiene muy buenos desafíos.Ciphertext-only attackAlgoritmo: Sustitución simple.Ciphertext: Jw ahcitosjro jy cr grxaarswgpgxotao ro jyxjtoadjo, cxawazgdo stjucjrxjpjrxj igtg jw gwabao yarxopáxauo djw dowot dj ughjzg, dowot djrxgw, dowot pcyucwgt, powjyxagy dj wg pjryxtcguaor, dowot rjctowofauo dj ugtguxjt wjbj, yardtopj sjhtaw v dowot xtgy uatcfag. Xgphajr yj cyg igtg xtgxgt ucgdtoy arswgpgxotaoy, uopo woy ecj yj itjyjrxgr jr gtxtaxay, gtxtaxay tjcpgxoadj v gtxtaxay foxoyg.
Jy cygdo jr ougyaorjy igtg xtgxgt gurj, djhado g ycy itoiajdgdjy grxaarswgpgxotagy, v lg yado jnijrdadg jr Kgior jr sotpg xoiaug igtg gurj dj gdcwxoy. 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.htmlAunque 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 attackAlgoritmo: 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 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#MaleabilidadRelated 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
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
APOKLIPTICOToda la información expuesta en este taller, está protegida bajo licencia Creative Commons Attribution-NonCommercial-ShareAlike 2.5.
|
|
|
|
« Última modificación: 5 Noviembre 2010, 13:25 pm por APOKLIPTICO »
|
En línea
|
AMD Phenom II 1075T X6 @ 290 Mhz x 11 (HT 2036 Mhz NB Link 2616 Mhz) 1.23 Vcore
ASUS M4A89GTD-PRO/USB3
2x2gb G-Skill RipjawsX DDR3 1600 Mhz CL7 (7-8-7-24-25-1T)
Seagate 500 Gb
XFX HD4850 512Mb GDDR3. 650 Mhz/995 Mhz 1.1 Tflops.
|
|
|
APOKLIPTICO
Desconectado
Mensajes: 3.871
Toys in the attic.
|
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í. 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.
Medidas estadísticas
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.  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.  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.
Periodo corto. 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).
Pruebas de aleatoriedad FIPS140-1. 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://www.csm.ornl.gov/~dunigan/fips140.txt
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 (en el thread del taller) y cuando estén listos, empezamos a crear.
Un abrazo
APOKLIPTICOEl código bájenlo por acá 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.
|
|
|
|
« Última modificación: 11 Noviembre 2010, 23:14 pm por APOKLIPTICO »
|
En línea
|
AMD Phenom II 1075T X6 @ 290 Mhz x 11 (HT 2036 Mhz NB Link 2616 Mhz) 1.23 Vcore
ASUS M4A89GTD-PRO/USB3
2x2gb G-Skill RipjawsX DDR3 1600 Mhz CL7 (7-8-7-24-25-1T)
Seagate 500 Gb
XFX HD4850 512Mb GDDR3. 650 Mhz/995 Mhz 1.1 Tflops.
|
|
|
APOKLIPTICO
Desconectado
Mensajes: 3.871
Toys in the attic.
|
|
|
|
|
|
En línea
|
AMD Phenom II 1075T X6 @ 290 Mhz x 11 (HT 2036 Mhz NB Link 2616 Mhz) 1.23 Vcore
ASUS M4A89GTD-PRO/USB3
2x2gb G-Skill RipjawsX DDR3 1600 Mhz CL7 (7-8-7-24-25-1T)
Seagate 500 Gb
XFX HD4850 512Mb GDDR3. 650 Mhz/995 Mhz 1.1 Tflops.
|
|
|
|
 |
