criptografía de clavecriptografía de clave...
Post on 21-Oct-2018
228 Views
Preview:
TRANSCRIPT
1
Criptografía de claveCriptografía de clave pública
Índice
Criptografía Clave PúblicaCriptografía Clave PúblicaCaracterísticasComparativa cifrado simétrico vs. asimétrico
RSAOperaciones de Cifrado y DescifradoGeneración de ClavesGeneración de Claves
Firma DigitalFunciones Hash
2
CriptografíaTexto Texto Clave Compartida
Canal
Texto Cifrado
Claro Claro
Cifrado Simétrico
Cifrado Asimétrico
Criptografía simétrica. Resumen
La criptografía simétrica usa una única claveLa criptografía simétrica usa una única claveClave compartida por emisor y por receptorSi se revela la clave, las comunicaciones o los mensajes cifrados se verán comprometidosSe dice simétrica porque las partes son iguales De ahí que no es posible proteger al emisor de que el receptor falsifique el mensaje y diga que fue enviado por el emisor
3
Criptografía asimétrica
Dos claves:Dos claves: pública (KUa)
Conocida por todo el mundoUsada para cifrar mensajes y verificar la firma de un mensaje
privada (KRA)Conocida únicamente por el propietarioU d d if j fi jUsada para descifrar mensajes y para firmar mensajes
asimétrica: las partes no son igualesFuncionamiento basado la Teoría de Números
Criptografía asimétrica
Desarrollada para tratar dos problemas claveDesarrollada para tratar dos problemas claveDistribución de claves: cómo poder establecer comunicaciones seguras sin tener que confiar una clave privada a un Centro de Distribución de Claves(Key Distribution Center o KDC)Firma digital: como verificar que un mensaje llega intacto del que afirma ser su emisor
El invento se debe a Whitfield Diffie & Martin Hellman.Universidad de Stanford. 1976.
Conocido previamente en entornos secretos
4
Criptografía asimétrica
Criptografía asimétrica. Características
Características de las clavesCaracterísticas de las claves
Es fácil computacionalmente cifrar/descifrar mensajes cuando se conoce la clave de cifrado/descifrado respectivamenteNo es posible computacionalmente encontrar la clave de descifrado únicamente a partir del algoritmo y la clave de cifrado Usan las funciones unidireccionales con trampa
Son reversibles. Cualquiera de las dos claves pueden usarse para cifrar y descifrar. Todo lo que se cifre con la clave pública puede ser descifrado con la clave privada y viceversa.
)]([)]([ MEDMEDM KRbKUbKUbKRb ==
5
Funciones unidireccionales con trampa
Funciones matemáticas de un sólo sentido (one-way functions)
Permiten usar la función en sentido directo [cálculo sencillo] para cifrar y descifrar (usuarios legítimos)
Fuerzan el sentido inverso [cálculo complejo] para el ataque o criptoanálisis de la cifra
f (M) = C es siempre fácil.f -1(C) = M es difícil salvo que se tenga la trampa.
Funciones con trampa más usadas
Problema de la factorizaciónProblema de la factorizaciónCálculo directo: producto de dos primos grandes
p·q = n
Cálculo inverso: factorización de número granden = p·q
Problema del logaritmo discretoCál l di t i ió di tCálculo directo: exponenciación discreta
αx mod n = βCálculo inverso: logaritmo discreto
x = logαβ mod n
6
Cifrado asimétrico.Posibilidades de Cifrado
Clave pública destino (KUd t – KRd t)Clave pública destino (KUdest KRdest)
Clave pública de origen (KUorig – KRorig)
Clave privada de origen (KRorig – KUorig)p g ( orig orig)
Clave privada de destino (¿?)
Cifrado con clave pública de destino
Sólo destinatario podrá descifrar el mensaje (KRdest)p j ( dest)
Proporciona:confidencialidadintegridad
si el mensaje es alterado no se podrá descifrar
No proporcionap pautenticidad del emisor
Cualquiera pudo haber generado el mensaje cifradono repudio
El emisor puede negar que ha sido el quien cifró el mensaje
7
Cifrado con clave pública de destino
A puede enviar un mensaje cifrado a BA puede enviar un mensaje cifrado a B utilizando la clave pública de B, KUb
C = EKUb (M)
B puede descifrar el mensaje utilizando su l i d bclave privada, KRbM = DKRb (C) = DKRb (EKUb (M))
Cifrado con clave pública de origen
Si en vez de utilizar la clave pública de destino, elSi en vez de utilizar la clave pública de destino, el emisor usa su propia clave pública, la cifra no tiene sentido bajo el punto de vista de sistemas de clave pública ya que sólo él o ella sería capaz de descifrar el criptograma (deshacer la operación de cifra) con su propia clave privada.
P d í if j ól l iPodría usarse para cifrar un mensaje que sólo el propio emisor pueda descifrar. Sin embargo, para este uso es más adecuado el cifrado simétrico ya que es más eficiente.
8
Cifrado con clave privada de origen
Cualquier usuario podrá descifrar el mensaje (KUorig)Cualquier usuario podrá descifrar el mensaje (KUorig)No proporciona confidencialidadSí proporciona:
integridadsi el mensaje es alterado no se podrá descifrar
autenticidad del emisor. Sólo el emisor puede haber cifrado el mensaje con su clave privada ya que sólo el tiene esa claveprivada, ya que sólo el tiene esa clave
no repudioel emisor no puede negar que ha sido el quien cifró el mensaje
¡Es el mecanismo que hace posible la firma digital!
Cifrado con clave privada de origen
A puede enviar un mensaje cifrado a BA puede enviar un mensaje cifrado a B utilizando la clave su privada, KRa.
C = EKRa (M)
B puede descifrar el mensaje utilizando laB puede descifrar el mensaje utilizando la clave pública de A, KUa
M = DKUa (C) = DKUa (EKRa (M))
9
Criptografía asimétrica: Confidencialidad y autenticación
Criptografía asimétrica. Aplicaciones
Aplicaciones principales:Aplicaciones principales:Cifrado: proporciona confidencialidadFirma digital: proporciona autenticación (además de integridad y no repudio)Intercambio de claves: útil para intercambiar claves de sesión
Al l i d d dAlgunos algoritmos son adecuados para todos los usos, mientras que otros son específicos de un uso concreto
10
Seguridad de los criptosistemas de clave pública
Ataques de búsqueda exhaustiva por fuerza brutaAtaques de búsqueda exhaustiva por fuerza bruta posiblesDefensa
Longitud de las claves ( >1024 bits)Funciones trampa: en la enorme diferencia de dificultad entre los problemas fáciles (cifrar/descifrar) y los difíciles (criptoanálisis)Normalmente, el problema difícil se conoce, pero es lo suficientemente complejo como para no ser viable resolverlosuficientemente complejo como para no ser viable resolverlo
ProblemasSe necesita usar números muy grandesLentitud
Comparativa: autenticación
Cifrado simétrico Cifrado asimétricoCifrado simétricoNo permite autenticación del emisor No permite por lo tanto no repudioÚ
Cifrado asimétricoPermite autenticaciónPermite no repudio del emisorPermite garantizar la integridad del mensaje
Únicamente permite garantizar la integridad del mensaje
11
Comparativa: gestión de claves
Cifrado simétrico Cifrado asimétricoCifrado simétricoPara n participantes, entran en juego
n * (n-1) / 2 claves
Cifrado asimétricoPara n participantes, entran en juego
2 * n claves
EJEMPLOEJEMPLO
Para n = 100 (100 participantes)
─ Simétrico: 100x99/2 = 4950 claves.
─ Asimétrico: 2x100 = 200 claves
Comparativa
Cifrado simétrico Cifrado asimétricoCifrado simétrico
Espacio de Claves>= 128 bits
Vida de las claves
Cifrado asimétrico
Espacio de Claves>= 1024 bits
Vida de las ClavesMuy corta (seg. o min.)Claves de sesión
Larga (meses o años)
12
Comparativa
Cifrado simétrico Cifrado asimétricoCifrado simétricoVelocidad de Firma
Muy altaDel orden de 100 a 1000 veces más rápidos
Seguridad
Cifrado asimétricoVelocidad de Firma
Muy bajaUsos
claves sesiónfirma digital (f. hash)
SeguridadReside en la seguridad de la propia clave
Reside en la dificultad computacional de encontrar la clave privada a partir de la clave pública.
Principales algoritmos
Diffie-HellmanDiffie-HellmanDiffie-Hellman. 1976.
ElGammalT. ElGammal. 1985.
RSARonald Rivest, Adi Shamir y Leonard Adleman.1976
13
RSA
Diseñado por Rivest, Shamir & Adleman delDiseñado por Rivest, Shamir & Adleman del Massachusetts Institute of Technology (MIT) en 1977 Es el algoritmo de clave pública más conocido y usadoBasado en exponenciación
La exponenciación conlleva O((log n)3) operaciones (fácil) Usa enteros grandes (1024 bits)Seguridadg
Basada en el coste de factorizar números grandesLa factorización conlleva O(e log n log log n) operaciones (difícil)
RSA
CifradoCifradoC = Me mod n
DescifradoM = Cd mod n = (Me)d mod n = Med mod n
Requisitos∃ e, d, n / Med mod n = M ∀ M < n(Me mod n) y (Cd mod n) sean fáciles de calcularConocidos e y n sea imposible calcular d
14
Generación de claves RSASeleccionar dos números primos grandes: p, qCalcular módulo de su grupo de trabajo n = p·q
nota ø(n)=(p-1)(q-1)Seleccionar clave de cifrado e
1<e<ø(n), mcd(e,ø(n))=1 Obtener clave de descifrado d
e·d=1 mod ø(n) y 0≤d≤nSi d es inversa de e entonces e·d = 1+k·ø(n) para algún k
Clave PúblicaPU={e,n}
Clave Privada PR={d,n}Guardar en secreto o destruir p, q y ø(n)
Generación de claves RSAEjemplo
Se seleccionan dos primos: p=5 & q=11
Se calcula n = p·q n = 5 x 11 = 55
Se calcula ø(n)=(p–1)·(q-1)ø(n)= 4 x 10 = 40
Se selecciona e con la condición de que cumpla mcd(e,40)=1se elige e=3se elige e=3
Se determina d a partir de la relación d·e = 1 mod 40 y d < 40 El valor es d=27 ya que 27x3 = 81 = 40x2 + 1
15
RSA: Cifrado y Descifrado
Para cifrar un mensaje M el emisor:Para cifrar un mensaje M, el emisor:Obtiene la clave pública del receptor PU={e,n}Calcula: C = Me mod n, dónde 0≤M<n
Para descifrar el criptograma C, el propietario:Usa su clave privada PR={d,n}Calcula: M = Cd mod nCalcula: M = C mod n
El mensaje M debe ser menor que el módulo n (se parte en bloques si es necesario)
RSA: Cifrado y DescifradoEjemplo
Dado un mensaje M = 36 (36 < 55)Dado un mensaje M 36 (36 < 55)
Cifrado:C = 363 mod 55 = 16
Descifrado:M = 1627 mod 55 = 36
16
Seguridad en RSA
Aproximaciones para atacar el algoritmo RSA:Aproximaciones para atacar el algoritmo RSA:Búsqueda de la clave por fuerza bruta (no es factible computacionalmente debido al tamaño de los números)Ataques matemáticos (basados en la dificultad de calcular ø(n), factorizando el módulo n)Timing attacks (durante el descifrado)Chosen Ciphertext Attack (explotando las propiedades de RSA)
Ataques matemáticosSe pueden identificar 3 aproximaciones:
Factorizar n=p·q, entonces calcular ø(n) y luego dDeterminar ø(n) directamente y calcular dEncontrar d directamente
Los matemáticos creen que todos son equivalentes a factorizarSe han producido pequeñas mejoras a lo largo de los años
Desde mayo de 2005 lo máximo que se ha conseguido es factorizar un número de 200 dígitos decimales (663 bits) con el algoritmo Lattice Sieve
Las mejoras más importantes se deben a la mejora de los algoritmosLattice Sieve es el mejor algoritmo actualmente. Reemplaza al algoritmoLattice Sieve es el mejor algoritmo actualmente. Reemplaza al algoritmo Generalized Number Field Sieve, que a su vez había reemplazado al algoritmo Quadratic Sieve
Actualmente se supone que una clave RSA de 1024-2048 bits es segura
Se debe asegurar que p, q son de un tamaño similar y que cumplen otras restricciones
17
Timing attacks
Desarrollados por Paul Kocher a mediados de los 90Desarrollados por Paul Kocher a mediados de los 90Se basan en estudiar las variaciones de tiempo en las operacionesInfiere el tamaño del operando en función del tiempo que tarda la operaciónEn el caso de RSA se estudia el tiempo invertido en la exponenciaciónAcciones preventivas
Usar un algoritmo de exponenciación de tiempo constanteAñadir retardos aleatorios
Chosen Ciphertext AttacksRSA es vulnerable a un Chosen Ciphertext Attack (CCA)Un atacante selecciona criptogramas y recupera el texto originalElige cripotogramas para explotar propiedades de RSA y de esa forma conseguir información para el criptoanálisisLos ataques simples se pueden prevenir añadiendo texto de rellenoPara variantes más sofisticadas, es necesario modificar el texto sin cifrar usando una técnica denominada Optimal Asymmetric Encryption Padding (OASP)
18
Firma Digital
Garantiza que un documento proviene de quién lo ha firmado
Proporciona Autenticación, Integridad y no RepudioDocumento se cifra con KRorig
Sólo el poseedor de la clave privada puede haberlo hechoKUorig permite comprobar la validez del documento
Problema: ineficiencia cifrado No se firma el documento completo, sino un resumenFunciones unidireccionales de resumen : funciones hash
Funciones Hash
A partir de un mensaje M, una función hash o resumenA partir de un mensaje M, una función hash o resumenH(M), genera un resumen del mismo.
Ejemplo:M = La reunión es a las 20:30H(M) = 03fgi8
Se puede usar para garantizar la integridad de un mensaje o archivo.Su utilidad más extendida es la firma digitalSu utilidad más extendida es la firma digital.
En realidad lo que se firma digitalmente no es el mensaje completo sino un hash o resumen del mismo.
19
Funciones Hash: EjemploAgrupación de texto en bloques
E n u n r i n c ó n d e69 110 32 117 110 32 114 105 110 99 243 110 32 100 101
-1312 224 990 -15840 -6868 -22806
Tamaño bloque: 3Función matemática sobre elementos del bloque
(A – B) * CPrimer Bloque: (69 – 110) * 32 = -1312
Valor Hash a partir de valores parcialesEjemplo: suma de todos los resultados intermedios
l a M a n c h a d e c32 108 97 32 77 97 110 99 104 97 32 100 101 32 99
u y o n o m b r e n o q117 121 111 32 110 111 109 98 114 101 32 110 111 32 113
8927-444 -8658 1254 7590
2738
8669
1312 224 990 15840 6868 22806
-7372 -4365 1144 6500
-11399
6831
Funciones Hash: EjemploCualquier cambio mínimo en el texto produce un cambio radical en
E n u n r i n c o n d e69 110 32 117 110 32 114 105 110 99 111 110 32 100 101
-1312 224 990 -1320 -6868 -8286
q pel resultado de la función Hash
Así, si cambiamos rincón por rincon, el valor de la función Hash pasa de -11.399 a 3.121
l a M a n c h a d e c32 108 97 32 77 97 110 99 104 97 32 100 101 32 99
u y o n o m b r e n o q117 121 111 32 110 111 109 98 114 101 32 110 111 32 113
8927-444 -8658 1254 7590
2738
8669
-7372 -4365 1144 6500
3121
6831
20
F. Hash: Propiedades (I)H(M) será segura si tiene las siguientes características:
1. Unidireccionalidad: conocido un resumen H(M), debe ser computacionalmente imposible encontrar M a partir de dicho resumen.
2. Compresión: a partir de un mensaje de cualquier longitud, el resumen H(M) debe tener una longitud fija. Lo normal es que la longitud de H(M) sea menor que el mensaje M.
3. Facilidad de cálculo: debe ser fácil calcular H(M) a partir de un mensaje M.
4. Difusión: el resumen H(M) debe ser una función compleja de todos los bit d l j M d t l f i l t difi d lbits del mensaje M, de tal forma que simplemente modificando un solo bit del mensaje M, el hash H(M) debería cambiar radicalmente (al menos la mitad de sus bits).
F. Hash: Propiedades (II)5. Colisión simple: conocido M, será p ,
computacionalmente imposible encontrar otro M’ tal que H(M) = H(M’). Esto se conoce como resistencia débil a las colisiones.
6. Colisión fuerte: será computacionalmente imposible encontrar un par (M, M’) de forma que H(M) = H(M’). Esto se conoce como resistencia fuerte a las colisiones.
ataque por la paradoja del cumpleaños.
21
F. Hash: Algoritmos comunesMD5: Ron Rivest 1992. Mejoras al MD4 y MD2 (1990), es más lento, pero
i l d id d G d 128 bitcon mayor nivel de seguridad. Genera un resumen de 128 bits.SHA-1: National Institute of Standards and Technology (NIST), 1994. Similar a MD5, pero con resumen de 160 bits. Existen otras propuestas conocidas como SHA-256 y SHA-512, posibles estándares.RIPEMD: Comunidad Europea, RACE, 1992. Resumen de 160 bits.N-Hash: Nippon Telephone and Telegraph, 1990. Resumen: 128 bits.Snefru: Ralph Merkle, 190. Resúmenes entre 128 y 256 bits. Ha sido criptoanalizado y es lento.Tiger: Ross Anderson, Eli Biham, 1996, Resúmenes de hasta 192 bits. Optimizado para máquinas de 64 bits (Alpha)Optimizado para máquinas de 64 bits (Alpha).Panama: John Daemen, Craig Clapp, 1998. Resúmenes de 256 bits de longitud. Trabaja en modo función hash o como cifrador de flujo.Haval: Yuliang Zheng, Josef Pieprzyk y Jennifer Seberry, 1992. Admite 15 configuraciones diferentes. Hasta 256 bits.
Message Digest 5 (MD5)Obsoleto desde mediados de 2005. No obstante, es interesante su estudio dada la sencillez del algoritmo y su generalidad.Algoritmo básico de Message Digest 5:
Dado un mensaje M, se convierte en un bloque múltiplo de 512 bits, añadiendo bits al final si es necesario.Existen cuatro vectores iniciales: A, B, C y D, de 32 bits cada uno (32x4=128 bits). Se realizan diversas operaciones lógicas entre estos vectores y el primer bloque de 512 bits del mensaje.Esta operación da como resultado un nuevo conjunto de vectores A’, B’, C’ y D’. Se realiza la misma función con el segundo bloque de 512 bits del mensaje. Al terminar, el algoritmo entrega un resumen que corresponde a los últimos 128 bits de estas operaciones.
22
Firma Digital: pasos protocolo
G ( é )Generar resumen del documento (método conocido por todos)Cifrar resumen con clave privada emisorEnviar documento junto resumen firmado al receptorReceptor genera un resumen del documento recibido, usando la misma función unidireccional de resumen. Después descifra con la clave pública del origen el resumen firmadoSi el resumen firmado coincide con el resumen que él ha generado la firma es válidagenerado, la firma es válida
Firma DigitalSe ofrecen conjuntamente los servicios de:
No rechazo, ya que nadie excepto A podría haber firmado el documentoAutenticación, ya que si el documento viene firmado por A, podemos estar seguros de su identidad, dado que sólo él ha podido firmarloIntegridad del documento, ya que en caso de ser modificado, resultaría imposible hacerlo de forma tal que se generase la misma función de resumen que había sido firmada.No privacidad!!!!
top related