advertisement

c2 Criptografia

50 %
50 %
advertisement
Information about c2 Criptografia
Entertainment

Published on January 5, 2008

Author: brod

Source: authorstream.com

advertisement

ALGORITMOS DE ENCRIPTAMIENTO:  ALGORITMOS DE ENCRIPTAMIENTO THIERRY DE SAINT PIERRE GERENTE COMERCIAL eBUSINESS TECHNOLOGY Algoritmos de encriptamiento:  Algoritmos de encriptamiento TEMARIO Fundamentos de criptografía Algoritmos clásicos: Sustitución, transposición, one pad Teoría matemática: Teoría de la información. Complejidad de problemas en criptografía. Aritmética modular. Terminología:  Terminología encryption (enciphering) = encriptación, cifrar: proceso de esconder un mensaje de tal forma de esconder su contenido cipher = - código, clave (nombre) - cifrar, encriptar (verbo) Ciphertext: mensaje encriptado cryptogram = criptograma decryption = decriptar cryptography = criptografía Arte y ciencia de encriptar los mensajes cryptanalysis = criptoanálisis , análisis criptográfico, ciencia de quebrar los textos cifrados. Algoritmo criptográfico: Función matemática utilizada para encriptar y desencriptar. Algoritmos restringidos son los algoritmos que deben permanecer secretos, y son compartidos entre las partes Definiciones:  Definiciones Sistema criptográfico Familia de transformaciones invertibles dependientes de un parámetro o llave k Ek con k en K. Si M : espacio de los mensajes C: espacio de los códigos Entonces el sistema criptográfico debe verificar: Algoritmo de encriptamiento Ek : M --> C es una transformación invertible. C = Ek (M) Existe un algoritmo inverso Dk = Ek-1 llamado el algoritmo de decriptamiento tal que: Dk : C --> M y Dk(C) = Dk(Ek(M)) = M Las llaves deben definir de manera unívoca el mensaje encriptado: Ek1 (M) <> Ek2 (M) si k1 <> k2 Fortaleza de un sistema criptográfico:  Fortaleza de un sistema criptográfico Principio de Keerckhoff: La fortaleza de un algoritmo se basa en mantener secreta la llave y no en mantener secreto el algoritmo. La dificultad de adivinar la llave o de probar todas las llaves posibles (^k: estimación k) La dificultad de invertir el algoritmo de encriptamiento si no se conoce la llave (^M: estimador M) La dificultad para decriptar un mensaje completo suponiendo que se sabe decriptar una parte. El secreto sobre las propiedades del mensaje (p.ej: alguna palabra que se repite al comienzo y al final del mensaje). Clasificación de Algoritmos:  Clasificación de Algoritmos Algoritmos simétricos Basados en una sola llave secreta tanto para encriptar como para desencriptar. Dos categorías: Stream Bloques Algoritmos asimétricos La llave de encriptación (llave pública) es diferente a la llave de encriptación (llave privada). Criptoanálisis:  Criptoanálisis Es la ciencia de recuperar el mensaje original a partir del texto encriptado, sin conocer la llave. Un ataque criptoanálitico exitoso permite recuperar el mensaje o la llave. Existen 4 categorías de criptoanálisis: Ataque con solo mensaje cifrado. Dados C1 = Ek (M1) , C2 = Ek (M2), ... deducir M1, M2 , ... Ataque con mensajes originales conocidos. Dados M1, C1 = Ek (M1) , M2 , C2 = Ek (M2), ... Se debe deducir la llave K. Ataque con mensajes originales seleccionados. Se pueden elegir los Mi, que van a ser encriptados en Ci = Ek (Mi) . Se debe deducir la llave K. Ataque con mensajes originales seleccionados en foma adaptativa. Se eligen los mensajes a encriptar según el resultado de los mensajes anteriores. Seguridad de Algoritmos:  Seguridad de Algoritmos Solo los algoritmos de tipo “one time pad” son inquebrables La criptografía se interesa en los algoritmos llamados computacionalmente seguros, ie que no pueden ser quebrados con los recursos disponibles. 4 categorías para quebrar un algoritmo: Quiebre total: se encuentra la llave K tal que Dk(C) = M Deducción Global: se encuentra un algoritmo alternativo A equivalente a Dk sin conocer K. Quiebre local: solo se encuentra el mensaje original M. Deducción de informacion: se obtiene cierta información sobre la llave o el mensaje inicial. Es importante que el valor de la información a proteger sea siempre inferior al costo de quebrar la seguridad que la protege Algoritmo de Cesar:  Algoritmo de Cesar Algoritmo de Cesar Algoritmo usado por Julio Cesar en sus campañas. El algoritmo consiste en desplazar cada letra del mensaje tres caracteres a la derecha: i.e. A -> D, B-> E, etc. Todo algoritmo que transforma la letra i del alfabeto en la letra i + j es llamado Algoritmo tipo Cesar: E: i --> i+ j El algoritmo de decriptamiento es: D: i --> i - j Analisis criptográfico: Se utiliza la distribución de frecuencia de las letras. La distribución de las letras en el espacio de los mensajes M es la misma que en el espacio de los códigos C. Algoritmo de Cesar:  Algoritmo de Cesar Ejemplo: L FPDH VDZ L FRQTXHUHG --> I CAME I SAW I CONQUERED con j=3. A partir de la palabra encriptada QJAAH determinar cuál es la palabra inglesa original. Hay que intentar con las 26 posibles traslaciones. Respuesta : 2 palabras posibles: BULLS , HARRY Las frecuencias de las letras en el inglés son: F(e) = 13% F(a) = 7% . Las frecuencias de i, n, o, r, t varían entre 7% y 9%. Del mismo modo en el espacio de los códigos la frecuencia sería F(h) = 13% , F(d)= 7% , etc. Supuesto: Conocimiento de la distribución de letras (o mensajes) en el alfabeto inicial. Algoritmo de Sustitución monoalfabática:  Algoritmo de Sustitución monoalfabática Sustitución: se reemplazan los bits, caracteres o bloques de caracteres por un sustituto. Generalización del código de Cesar: se le asigna a cada letra del alfabeto una letra aleatoria. Si numeramos las letras : 1,2,3,4 …., 25, 26 23, 2,4,15, …, 8,1 Encriptamiento E: x --> y Decriptamiento D : y --> x Análisis criptográfico: utiliza las frecuencias de las letras del alfabeto. Para este tipo de algoritmos existen n! llaves, donde n es el número de letras en el alfabeto. Otros algoritmos de sustitución:  Otros algoritmos de sustitución Sustitución homofónica: es similar al anterior solo que cada letra se puede substituir por un conjunto de caracteres. Por ejemplo la A se puede substituir por 5, 13, 25 o el 56. ROT 13: es un algoritmo frecuentemente encontrado en los sistemas UNIX. Cada letra es rotada 13 veces ( A -> N, B-> O, etc) . Se tiene que P= ROT 13 (ROT 13 (P)) Sustitución polialfabética:  Sustitución polialfabética Sustitución polialfabetica Se utilizan d alfabetos de encriptamiento C1, C2 ...., Cd. Si definimos fi : A -->Ci entonces el mensaje M = m1 ....md md+1 .... m2d se transforma en Ek(M) = f1( m1 )f2(m2) ....fd(md ) f1(md+1 ).... fd(m2d ). Encriptamiento de Vignerer Caso especial donde fi(a) = (a + ki) (mod n) define el shift en el alfabeto. La llave se escribe K = k1k2 ...kd. Por ejemplo K = HOST = (7,14,18,19) entonces: M = INDI VIDU ALCH ARAC TER K = HOST HOST HOST HOST HOS Ek(M) = PBVB CWVN HZUA HFSV ASJ Encriptamiento de Beauford fi(a) = (ki - a) (mod n) Transposición monoalfabética:  Transposición monoalfabética Transposición o permutación: se rearregla el orden de los bits, de los caracteres o de los bloques de caracteres. Sea Zd los enteros de 1 a d y f:Zd --> Zd una permutación. Los bloques de d caracteres son encriptados a la vez. La llave es la tupla (d,f) . Sea el mensaje M = m1 ....md md+1 .... m2d ... Entonces el mensaje encriptado es: Ek(M) = mf(1) ... mf(d) m d+f(1) ... md+f(d) ... Ejemplo: sea d=4 y f = (2 3 4 1) Se recorta el mensaje en bloques de largo 4 : M = CRYP TOGR APHY Luego el criptograma es: PCRY RTOG YAPH Criptoanálisis: Se decripta utilizando información de distribución de las letras del lenguaje , así como la distribución de las tuplas (th, an, ..) y tripletas (the, ...). Los rotores y la máquina Enigma:  Los rotores y la máquina Enigma Rotores Cada rotor es una permutación arbitraria del alfabeto. La salida de un rotor se encuentra conectada a la entrada del rotor siguiente. Por ejemplo en una máquina de 4 rotores; la A -> F, luego la F -> Y, luego Y -> E y finalmente la E-> C. La máquina Enigma: Inventada por un ingeniero alemán durante la I guerra mundial, utilizada posteriormente en la II GM por los alemanes. Las llaves se definían mediante 3 rotores. Una vez posicionados los rotores se ingresaba el carácter a encriptar y se obtenía como resultado el carácter encriptado. Se encriptaba así, sucesivamente todo el texto. A cada encriptamiento el rotor se desplazaba permitiendo romper el esquema estadístico del idioma. Para decriptar el mensaje era necesario tener la misma máquina y conocer el posicionamiento inicial de los rotores. Un equipo de criptógrafos polacos logró descifrar la máquina enigma informando a los ingleses. XOR:  XOR XOR es la operación: 0  0 = 0 0  1 = 1 1  0 = 1 1  1 = 1 Propiedad (M  K)  K = M Es un algoritmo simétrico. Algoritmo Crypt del UNIX:  Algoritmo Crypt del UNIX UNIX posee dos algoritmos de encriptamiento: El algoritmo CRYPT utilizado para encriptar las password El programa crypt que puede usar cualquier usuario para encriptar sus datos. Algoritmo CRYPT: Basado en algoritmo DES. Utiliza la password como llave de encriptamiento y encripta con esta llave una palabra de 64 bits inicializada en zero. Este resultado es encriptado (con la pwd ) 25 veces sucesivas. Finalmente se transforman esos 64 bits en una cadena de 11 caracteres que son almacenados en /etc/passwd. Para complicar el decriptamiento se le agrega una semilla de 2 caracteres que depende de la hora del día. Programa Crypt (1):  Programa Crypt (1) El programa passwd: al tipear la pwd, esta es encriptada, se le agrega la semilla y se compara con lo que contiene el archivo de passwords. Ejemplo: Password Semilla Password encriptada nutmeg Mi MiqkFWCm1fNJI ellen1 ri ri79KNd7V6.Sk El programa crypt: Basado en la máquina enigma con un sólo rotor. cbw : Crypt Breaker´s Workbench es un programa que decripta automáticamente los archivos encriptados con crypt. Trucos para mejorar la seguridad de crypt: Comprimir el archivo antes de encriptarlo, de esta forma cbw no sabe cuando ha adivinado correctamente la llave pues no reconoce las palabras. Llave de una sola pasada: Algoritmo de Vernam:  Llave de una sola pasada: Algoritmo de Vernam “ One-time pad “ Se genera una llave aleatoria K a lo menos del largo del mensaje M a encriptar. La llave K es producida por un algoritmo de generación de números aleatorios seguros. Propiedades: La llave es conocida por los dos usuarios que comunican, esa llave debe ser más larga que cualquier mensaje que deseen intercambiar. Para cada mensaje se genera una nueva llave aleatoria K. Encriptamiento: C = Ek(M) = M Xor K Decriptamiento: D = C Xor K Es un alg. de encriptamiento inquebrable pues la llave es modificada aleatoriamente para cada mensaje, la unica forma de decriptar el mensaje es adivinarlo !. Encriptamiento con llaves en flujo:  Encriptamiento con llaves en flujo Stream ciphers El emisor y el receptor generan simltáneamente una secuencia de bits seudo-aleatorios a partir de una misma llave inicial. Estos bits son utilizados por el emisor para encriptar el mensaje con un Xor y por el receptor para decriptarlo via un Xor. La fuerza del alg. de encriptamiento reside en la capacidad de tener un algoritmo que genere secuencias de bits seudo-aleatorios. Caracteristica: no propaga errores, muy rápido. + llave Generador bits aleatorios Mensaje Mensaje encriptado Criterios de diseño de Algoritmos criptográficos:  Criterios de diseño de Algoritmos criptográficos El espacio de llaves debe ser grande. Los criptogramas no deben heredar las propiedades estadísticas del lenguaje de base. Lo ideal es que el criptograma parezca dato aleatorio. Debe ser sometido a intensos tests y análisis antes de ser usado. Lo complicado de su diseño no es una garantía de que sea seguro. El problema es: Cómo garantizar que un algoritmo es seguro ? La idea es demostrar que para quebrarlo es al menos necesario hacer una búsqueda exhaustiva de la llave. Por otro lado es necesario evaluar el lapso de tiempo en el cual se quieren segurizar los datos: En el mundo financiero se necesita protección transiente. En el área de gobierno o militar la información “clasificada” debe ser protegida por años. Slide22:  FUNDAMENTOS MATEMÁTICOS Teoría de la Información Complejidad de Algoritmos Teoría de los números Teoría de la información:  Teoría de la información Teoría desarrollada por Shannon (1948). Teoría de codificación para corregir errores en canales con ruido y teoría del encriptamiento. La cantidad de información en un mensaje es el promedio de bits necesarios para codificar todos los mensajes optimamente. La entropía de un mensaje M que puede tener Mi variantes es: H(M) = Suma P(Mi) Log 2 ( 1 / P(Mi) ) Cada término Log 2 ( 1 / P(Mi) representa el número de bits necesario para codificar el mensaje Mi. H(M) = log 2 n si hay n mensajes equiprobables. H(M) = 0 si hay un solo mensaje con P(M) = 1. En este último caso cómo no hay variedad de mensajes no hay información. Ejemplos: Entropía del campo “sexo” es 1 pues se necesita 1 bit para codificar este campo. Entropía de un campo “dia de la semana “ es 3 pues se necesitan tres bits para codificar este campo La redundancia de un lenguaje:  La redundancia de un lenguaje La tasa r de un mensaje de largo k es: r = H(M) / k. Para el ingles, cuando k es grande se estima r entre 1,0 y 1,5 bits/caracter. Consideramos el valor de 1,3. La tasa absoluta R de un lenguaje se calcula como el número de bits necesarios para codificar el lenguaje cuando los mensajes son equiprobables. Por ej: para un lenguaje con 26 caracteres es necesario Log 2 26 = 4,7. Los lenguajes son redundantes, pues algunas estructuras y letras ocurren más frecuentement e que otras. P. ej en ingles son frecuentes e,t,a, th, en , .... Se define la redundancia como D = R - r. El ratio D/R mide el % de redundancia. El caso del ingles:D = R – r = 4,7 – 1,3 = 3,4 D/R = 3,4/4,7 = 79%. De la misma forma se puede calcular la redundancia de un lenguaje con 2 letras utilizando probabilidades condicionales P(Mi / Mj). Error y secreto:  Error y secreto Error: entropía condicional de un mensaje M dado el criptograma C: HC (M) = Suma P(C) Suma PC (M) . log 2 (1 /PC(M) ) C M donde PC(M) es la probabilidad condicional de un mensaje M dado el criptograma C. Secreto de una llave K: HC (K) = Suma P(C) Suma PC (K) . log 2 (1 /PC(K) ) donde PC(K) es la probabilidad condicional de una llave K dado el criptograma C. Si Hc(K) es cero no hay incertidumbre sobre el criptograma, luego se puede quebrar. La distancia de unicidad de un criptograma es el largo mínimo del mensaje que hace que Hc(K) tienda a cero. Dist_Unic = HC(K) / D , donde D es la redundancia. Los criptogramas con distancia infinita son inquebrables. En el caso de un algoritmo de sustitución si todas las llaves son equiprobables, el largo del mensaje para poder quebrar la llave es la distancia de unicidad: N=H(K)/D = log 2 n! /D. Para el inglés, N = log2 26! / 3,2 = 27,6. Se requiere un codigo de largo 28 para quebrar el criptograma Complejidad de Algoritmos:  Complejidad de Algoritmos La teoría de complejidad de algoritmos clasifica los problemas calculables según el tiempo (asintótico) óptimo necesario para calcular una respuesta al problema. La complejidad se mide por un orden O(f(n)) donde f(n) representa el termino de mayor orden. Algortimo lineal : O(n) Algoritmos polinomiales O(n) donde  es una constante. Algoritmos exponenciales O( t f(n) ) Clases de Algoritmos:  Clases de Algoritmos La teoría de la complejidad considera el espacio y tiempo mínimo para resolver la instancia de un problema en una máquina de Turing. Clase P: existe un algoritmo deterministico cuyo peor caso está acotada por una función polinomial. Clase NP: existe un algoritmo no-deterministico polinomial para resolver el problema. No se conocen algoritmos polinomiales determinísticos para resolver los problemas en esta clase. La máquina de Turing que se utiliza analiza todas las alternativas en paralelo. La mayoría de los algoritmos simétricos y todos los de llave pública/privada son NP completos. El criptoanalisis prueba los textos M y llaves K en paralelo y aplica el alg. De encriptación que es polinomial. Problemas NP-completos: problemas de clase NP que son equivalentes. Si existe un algoritmo polinomial determinístico para uno de ellos entonces tambien existe un algoritmo para los otros. Problema del vendedor viajero, Problema de satisfabilidad: dado una proposicion booleana F(X), existe una asignación (V, F) de esas variables X que resulte en que F(X) = V ? EXPTIME: problemas sólo solubles con algoritmos de tiempo exponencial. Es claro que P  NP. NO se ha podido demostrar que P  NP ni que son iguales Complejidad de problemas usados en criptología:  Complejidad de problemas usados en criptología Factorización Sea N, existen enteros p, q > 1 tal que p.q = N ? Clase NP Números primos es N primo ? Clase NP Problema exponencial Sean g,x pertenecientes a GF(N) Existe un entero s > 0 tal que s = g x (mod N). Clase P Teoría matemática:  Teoría matemática Aritmética modular a = b (mod n) ssi a = b + kn para algún k b es llamado el residuo de a modulo n. Además n divide a-b. El conjunto de residuos de modulo n es: (0, 1, 2, ...., n-1). Los enteros modulo n con la suma y la multiplicación forman un anillo commutativo (propiedades de asociatividad, conmutatividad y distributividad). Además cómo “módulo n “ es un homomorfismo del anillo de los enteros en el anillo de los enteros modulo n podemos reducir (mod n) y luego hacer la operación (+,*) o bien hacer la operación y luego reducir (mod n) (a+b) (mod n) =( a(mod n) + b(mod n) ) (mod n) (a*b) (mod n) =( a(mod n) * b(mod n) ) (mod n) En particular a1a2 ...am (mod 9) = a1 + a2 + ... + am (mod9) Mod n y Números primos:  Mod n y Números primos La criptografía utiliza mucho la función Mod n porque calcular el logaritmo discreto y las raices cuadradas mod n es dificil En cambio el cálculo exponencial es simple. Por ejemplo calcular ( a25 ) mod n se reduce a 6 multiplicaciones: ((((( a2 mod n) * a) mod n)2 mod n) 2 mod n) 2 mod n )* a ) mod n Números primos: aquellos números sólo divisibles por 1 y ellos mismos. Dos números son relativamente primos entre ellos si el mayor común divisor entre ellos es 1: mcd (x,y) = 1. Teorema del residuo chino:  Teorema del residuo chino Teorema previo: Sean p1, ... pr primos relativos entre ellos. Y sea n = p1 . p2 ... pr. Entonces: f(x) (mod n ) = 0 ssi f(x) (mod pi) = 0 para i=1, ..., r. Corolario Para resolver ax = b (mod n) es necesario resolver el sistema de congruencias: ax = b (mod pi) para i=1, ..., r. Teorema del residuo chino Sean p1, ... pr primos relativos entre ellos. Y sea n = p1. p2 ... pr. Entonces el sistema de congruencias: x = xi (mod pi) para i=1,...,r. tiene una solución común en el intervalo (0,n-1). Cuerpo de Galois:  Cuerpo de Galois Campo de Galois GF(p) Para un primo p definimos en el campo de los enteros modulo n las operaciones * (mod n) y + (mod n). Para cada a en (1, p-1) tenemos un inverso único a-1 tanto para + cómo para *. Se trata luego de un campo. Campos de Galois GF(2n) Aritmética módulo 2 sobre polinomios de grado n. El polinomio es de la forma a(x) = an-1 x n-1 + ... + a1 x + a0 dónde los coeficientes an-1 , ... ,a1 , a0. son enteros modulo n. En este caso los ai valen 0 o 1. Por ejemplo 11001 corresponde al polinomio x4 +x3 + 1 en GF(25). Cada elemento a(x) es un residuo módulo p(x) dónde p(x) es un polinomio irreducible de grado n. Luego de multiplicar 2 polinomios hay que reducir el resultado con el polinomio irreducible. GF(2n):  GF(2n) Los calculos en GF(2n) son más eficientes en tiempo y espacio que en GF(p) Se suma utilizando el or exclusivo: u + v mod 2 = u  v Se multiplica utilizando el and booleano: u + v = u and v Ejemplo : a = 10101 , b = 01100 y c=a+b = 11001 En cambio si consideramos a y b cómo las representaciones booleanas de 21 y 12 , la suma 21 + 12 = 33 y 21 * 12 = 252 = 4 (mod 31) requiere mas cálculos. Factorización:  Factorización Factorizar un número equivale a encontrar sus factores primos: Ej: 60 = 2*2*3*5 , 252601 = 41*61*101 Existe un buen número de algoritmos de factorización: Quadratic Sieve >Elliptic Curve Method Number Filed Sieve En la actualidad la factorización se realiza mediante redes de computadores: En 1994 se factorizó un número de 129 digitos (428 bits) con 1600 máquinas calculando durante 8 meses.

Add a comment

Related presentations

Related pages

Criptografia Nó a Nó

Criptografia Nó a N ...
Read more

C2 - Roteiro 6

Programa de Extensão da UnB em Criptografia e Segurança Computacional C2- Infraestrutura de Chaves Públicas Módulo 6 de 6 - 6 horas - pre-requisito ...
Read more

PPTP X L2TP

Criptografia mais alta; Verifica a integridade dos dados; Encapsula duas vezes. Abraço. Carlos Henrique Lucas. Als Antwort markiert Carlos Henrique Lucas ...
Read more

Sustituciones Polialfabéticas | Kriptópolis

Así, usando d alfabetos de cifrado (periodo d): C1, C2, ..., Cd y con alfabeto de texto llano A: f sub i A -> C sub i; i = 1 ... d. Entonces el mensaje:
Read more

Satélite e-Commerce | Star One C4 Como fazer apontamento?

Vou captar o C4 com mesma antena do C2 sem mexer na antena? Com o satélite StarOne C4 a ponto de entrar em atividade ...
Read more

[PHP] $cripto = ''; $tam = strlen($password); $i=1; for ...

$cripto = $cripto. $c2; ... $i = $i + 1; } //fim criptografia $senha = $cripto; clone this paste RAW Paste Data Pastebin.com Tools ...
Read more

Códigos y Criptografía Francisco Rodríguez Henríquez ...

Códigos y Criptografía Francisco Rodríguez Henríquez Software Security Through Code Obfuscation.
Read more

Symmetric-key algorithm - Wikipedia, the free encyclopedia

Cryptomeria/C2; CRYPTON; CS-Cipher; DEAL; DES-X; DFC; E2; FEAL; FEA-M; FROG; G-DES; GOST; Grand Cru; Hasty Pudding cipher; Hierocrypt; ICE; IDEA NXT; Intel ...
Read more

NOVO SATELITE DA CLARO STARONE C4 - CRIPTOGRAFIA NAGRA 4 ...

NOVIDADES DO NOVO SATÉLITE DA CLARO STARONE C4, SAIBA QUAL A CRIPTOGRAFIA? QUAL APONTAMENTO? E SE JÁ ESTA EM FUNCIONAMENTO
Read more

Apontamento para Satélite StarOneC2 - YouTube

APONTAMENTO PARA O STAR ONE C2 (satelite da Claro) - Duration: 6:57. ... CRIPTOGRAFIA NAGRA 4? QUAL APONTAMENTO? JÁ ESTA FUNCIONANDO?
Read more