encriptación de la información
Post on 18-Mar-2016
59 Views
Preview:
DESCRIPTION
TRANSCRIPT
Encriptación de la Información
José Miguel Horcas AguileraBlanca Bautista Perez
Javier Fernández González
ÍNDICE
-DEFINICION Y CARÁCTERÍSTICAS DE ENCRIPTACIÓN- HISTORIA- SUSTITUCIÓN- TRANSPOSICIÓN- ALGORITMOS SIMÉTRICOS Y ASIMÉTRICOS - RSA EN HASKELL -TÉCNICAS MATEMÁTICAS APLICADAS A LA CRIPTOGRAFÍA- EL FUTURO DE LA CRIPTOGRAFÍA- REFERENCIAS
Criptografía. Definición
Es el arte o ciencia de cifrar y descifrar información mediante técnicas especiales.
¿Para qué se usa?
- Permitir un intercambio de mensajes de forma confidencial por un medio inseguro.
Pág 3/59
¿Cómo funciona el cifrado?
Ek : Función para Encriptar (Cifrar)
Dk :Función para Desencriptar (Descifrar)
Pág 4/59
Historia(I)
Se distinguen varias épocas:
Criptografía clásica:
- Época de los romanos y griegos en campañas militares.- Algoritmo de sustitución simple y transposición. - Destaca el Cifrado de César
Criptografía Medieval:-Ruptura de los cifrados de sustitución.-Aparición de los cifrados de sustitución múltiple. (Leon Battista Alberti)
Pág 5/59
Historia(II)
Claude Shannon: En 1949 publicó “La teoría de la información” -Establece toda la base teórica de la criptografía y
criptoanálisis.
Segunda Guerra mundial: Máquinas electromecánicas. “Enigma”.
Pág 6/59
Tipos de CifradoUna vez que el emisor y receptor acuerdan
que algoritmo de cifrado usar, se distinguen dos tipos de cifrado:
Cifrado simétrico: Si la clave de cifrado y descifrado es la misma.
Cifrado asimétrico:Se hace uso de dos claves distintas:
Pública: Generalmente para cifrar.Privada: Generalmente para descifrar.
Pág 7/59
Métodos de encriptación de la Información
• Cifrado César • Código por sustitución de letras• Código por transposición• Criptografía de clave secreta.DES• Criptografía de clave pública. RSA
Pág 8/59
Cifrado César(I)
Funcionamiento:- Reemplaza cada letra del alfabeto por otra más adelante en el
alfabeto. Siempre a la misma distancia.- La clave especifica la distancia.
Ejemplo:
Clave de sustitución: 3
Pág 9/59
Para cifrar y descifrar:
Donde n es la clave, x la letra a cifrar y 27 el número de letras del alfabeto.
Cifrado César. Código (II)
Pág 10/59
Código por Sustitución de Letras(I)
Funcionamiento:- Reemplaza cada letra del alfabeto por otra.- La clave especifica el tipo de sustitución.
Ejemplo:
Clave de sustitución: A B C D E F G H I J K L M N Ñ O P Q R S T U V W X Y Z
I C Ñ H O M T L B S A R Q P E W J F V U K X D Y N Z G
Cifrar: . EJEMPLO . HOLA
OSOQJRWLWRI
Pág 11/59
Código por Sustitución de Letras(II)
Problema.Puede romperse fácilmente para textos planos usando la
frecuencia relativa de las letras.
(Ejemplo: la ‘a’ es la letra más usada en español).
Mejora.Cambiar la sustitución de cada letra de acuerdo con un
patrón periódico (sustitución múltiple).
Pág 12/59
Código por Sustitución de Letras(III)
Ejemplo. Sustitución múltiple.Seleccionamos un periodo L. Por ejemplo L=2;
La clave de sustitución sería:
0: A H L O
L O H A
A H L O
O L A H
1:
0 1 0 1
O H H oO H H OH OH O L A
Posición:
T. Cifrado:
T. Plano:
Pág 13/59
Código por TransposiciónPara aplicarlo, se considera el texto en filas de L
(10 por ejemplo) letras cada una, y se envía el texto columna a columna:
- El código se puede romper probando varias longitudes de fila distintas.
- Combinando sustitución con transposición se puede alcanzar una seguridad fiable con algoritmos de bajo coste computacional.
Pág 14/59
DES (Data Encription Standard) (I)
HistoriaEn 1977, el gobierno de EEUU lo adoptó como método de
encriptación para información no clasificada.
CaracterísticasEs un cifrado simétrico, caracterizado por:
. Forma de cifrar y descifrar conocidas
. La clave es secreta (desconocida)
Fue desarrollado por IBM, y usa una combinación de sustituciones y transposiciones.
Existen chips VLSI encargados que realizan este tipo de cifrado.
Chip VLSIPág 15/59
DES (Data Encription Standard) (II)
¿Cómo funciona?- Dividimos el texto plano en bloques de 64 bits.- La clave secreta es de 64 bits:
- 56 bits útiles para el algoritmo - 8 bits de paridad
- Se divide en 16 fases idénticas denominadas rondas.- PI y PF son funciones de transposición inversas entre sí: Facilita carga y descarga de los bloques sobre el HW.-La función F mezcla la mitad del bloque con parte de la clave (subclave). A la salida se combina con la otra mitad del bloque y se intercambian.
-Para descifrar las subclaves se introducen en orden inverso. Pág 16/59
DES (Data Encription Standard) (III)
ProblemaLa seguridad de cualquier cifrado simétrico reside en mantener
secreto de la clave.
ConsecuenciaLa clave k debe distribuirse de forma segura.
¿Cómo?
- Usando una clave maestra, acordada al reunirse físicamente.Sirve para transmitirse la clave k. La clave maestra se usa muy rara vez.
Pág 17/59
Criptografía de Clave Pública(Algoritmos asimétricos)
A diferencia de los algoritmos simétricos, ahora vamos a disponer de 2 tipos de claves (por cada usuario) :
- Clave pública- Clave privada
La clave pública la conoce todo el mundo y la privada es secreta y va ligado a un usuario.
Es imposible (ó muy difícil) deducir la clave secreta a partir de clave pública.
Pág 18/59
Criptografía de Clave Pública
Usuario A Usuario BE (M)
KPB D (E (M) ) = MKPBKSB
Usuario A Usuario cualquieraE (M)
KSA D (E (M) ) = MKSAKPA
Confidencialidad :
Firma digital (autenticación):
Pág 19/59
Comparativa entre Simétrica y Asimétrica
Simétrico Asimétrico
Más seguro X
Más rápido X
Número de claves
N*(N-1) 2*N
Problema más significativo
Distribución de claves
Velocidad
¿ Qué es lo deseado ?Combinar la velocidad con la seguridad
Criptosistemas híbridos Pág 20/59
Criptografía de Clave Pública
El algoritmo más conocido es el RSA
Fue desarrollado en 1977. (Rivest, Shamir, Adleman)
Actualmente es el primer sistema criptográfico y el mas utilizado.
Podemos cifrar y firmar digitalmente.
RSA
Pág 21/59
Algoritmo RSA
Generación de claves
1. Seleccionar dos números primos grandes, p y q, (típicamente mayores que 10100).
2. Calcular: n = p x q
z = (p-1) x (q-1) (φ de Euler)
• Este algoritmo se basa en principios de la teoría de números.
Pág 22/59
Generación de la Clave Publica
3. Seleccionar un número e:- Coprimo con z- Menor que z
Exponente de la clave publica
Pág 23/59
Pág 24/59
Generación de la Clave Privada
3. Seleccionar un número d:- e*d = 1 mod z- de-1 divide a φ(n)
Exponente de la clave privada
Pág 25/59
Pág 26/59
Pág 27/59
Criptografía de Clave PúblicaRSA
Funcionamiento :
a. Considerar el texto plano como una cadena de bits. Dividirlo en bloques de valor P tales que 0 ≤ P < n. Para ello agrupar en trozos de k bits, donde 2k < n
b. Cifrar el mensaje haciendo C = Pe mod n
c. Enviar C por el canal
d. Descifrar el mensaje haciendo P = Cd mod n
Pág 28/59
RSA en Haskell
Pág 29/59
• Codificar
Pág 30/59
• Descodificar
Pág 31/59
Pág 32/59
Criptografía de Clave PúblicaRSA
Ejemplo del RSA :
P = 61
Q = 53
N = P * Q = 3233
E = 17
D = 2753
Para cifrar M :C = E (M) = Me mod n = m17 mod 3233
Para descifrar C :M = D (C) = Cd mod n = c2753 mod 3233
Pág 33/59
PrimalidadDeterminar números primos grandes de forma aleatoria. FactorizaciónEncontrar la factorización de un número n como producto de
factores primos.
Cálculo con números grandesEficiencia en las operaciones matemáticas cuando se trabaja
con números grandes.
Teoría de Números
Problemas de RSA
Pág 34/59
Primalidad
Test de primalidadCriterio para decidir si un número dado es o no primo.
Test de la divisiones sucesivas. Test de pseudoprimalidadCriterio para decidir, con un alto grado de probabilidad, si un
número dado es o no primo. Test basado en el Teorema pequeño de Fermat. Test de Solovay-Strassen Test de Miller-Rabin
Pág 35/59
Teoría de Números
Dado un número impar, consiste en tomar todos los números impares en el intervalo [3 .. raíz(n)] y comprobar si alguno es divisor de n.
Test de las divisiones sucesivas
Pág 36/59
Teoría de Números
Obteniendo números primos grandes
Usar tablas publicadasRápido.Números pequeños para objetivos criptográficos.
Generación y testGenerar números aleatorios impares de tamaño grande
y aplicarles un test de pseudoprimalidad.
Teorema de TchebycheffLa cantidad de números primos menores o iguales que N es
Pág 37/59
Teoría de Números
Obteniendo números primos grandes Generación de números aleatorios de N dígitos
Pág 38/59
Teoría de Números
Obteniendo números primos grandes Generación de primos aleatorios de N dígitos
Pág 39/59
Teoría de Números
Test de pseudoprimalidad
Test de FermatSi n es primo, entonces para cualquier b con mcd(b,n) = 1, se tiene que:
Números de Carmichael -> son compuestos y verifican la igualdad.
Probabilidad de que un número no sea primo y pase el test:
2-k
Pág 40/59
Teoría de Números
Test de pseudoprimalidad
Test de Solovay-StrassenEl método consiste en elegir K naturales 0 < b < n aleatoriamente.
Para cada uno de estos números b se calcula: y
Si estos valores no son congruentes módulo n; entonces el número es compuesto.
Probabilidad de que un número no sea primo y pase el test:
2-k
Pág 41/59
Teoría de Números
Test de pseudoprimalidad
Test de Miller-Rabin n > 2 impar. m: impar n-1 = 2k * m ó a: aleatorio [2, n-2]
para algún r: [1, k-1]
http://www.haskell.org/haskellwiki/Prime_numbersPág 42/59
Teoría de Números
Últimos avances Algoritmo AKS (2002)Manindra Agrawal, Neeraj Kayal y Nitin SaxenaDepartamento de Computación del Instituto de Investigaciones de
Kanpur (India)Basado en una versión simplificada del Pequeño Teorema de Fermat:
Primer algoritmo determinístico matemáticamente demostrado, de tiempo polinómico.
Las constantes de la complejidad son muchas más costosas que en los actuales algoritmos probabilísticos.
Pág 43/59
Teoría de Números
Factorización
Uno de los ataques contra el algoritmo RSA consiste en descomponer en factores primos el número n de la clave pública.
Test de las divisiones sucesivas Método del algoritmo de Euclides Método de Fermat Método de Legendre Método rho de Pollard (Monte Carlo)
Pág 44/59
Teoría de Números
Factorización: Test de las divisiones sucesivas
Test de las divisiones sucesivasMismo procedimiento que para comprobar la primalidad.
Pág 45/59
Teoría de Números
Factorización: Método del algoritmo de Euclides
Método del algoritmo de EuclidesDado un número compuesto n entre dos valores f y g, el método consiste en multiplicar todos los números
primos comprendidos entre f y g, y a continuación aplicar el algoritmo de Euclides al número n y al producto resultante.
Si n es grande también se requiere mucho tiempo de computación.
Pág 46/59
Teoría de Números
Factorización: Método de Fermat Método de Fermat
¿El número 100895598169
es primo?
Es el producto de 898423 por 11230, ambos
primos.
Mersenne FermatPág 47/59
Teoría de Números
Factorización: Método de Fermat Método de Fermat
El método consiste en encontrar un cuadrado.
1. Dado n, escoger un x > raiz(n).2. Calcular x2 – n. Si es un cuadrado hemos terminado, sino:3. Calcular (x+1)2 – n. Si es un cuadrado hemos terminado, sino:…
Idea de Fermatsi n = x2 * y2, entonces n puede factorizarse: n = (x+y)*(x-y)Como x2 > n se tiene que x > raiz(n)
Pág 48/59
Teoría de Números
Factorización: Método de Legendre Método de Legendre
Número de soluciones de la congruencia:
Números primos -> Soluciones triviales -> Números compuestos -> Admite más soluciones.
El método intenta determinar soluciones no triviales a la congruencia.
Como si (x+y) es una solución no trivial, un factor de n se calcula hallando el mcd(x+y,n).
Pág 49/59
Teoría de Números
Factorización: Método rho de Pollard Método rho de Pollard (Método de Monte Carlo)Se basa en el algoritmo de la liebre y la tortuga y en:o x e y son congruentes módulo p con probabilidad 0.5 tras elegir
1.177*raiz(p) números.o Si p es factor de n, entonces 1 < mcd(|x-y|, n) <= n, ya que p divide
tanto a |x-y| como a n.
Secuencia x
Secuencia y
mcd(|x-y|, n)
Si mcd(|x-y|, n) = n -> Fracaso Pág 50/59
Teoría de Números
Trabajando con números grandes.
El tipo Integer de Haskell Números enteros de precisión ilimitada. Mismas operaciones que Int.
Tipo abstracto de datosPor ejemplo: array de dígitos.¡ Hay que implementar todas las operaciones!
5 7 2 0 1 8 9 7 1 3 6 4 0 0 4 5 6 2 7 8 9 6 4 1 2 2 5 1 3
Pág 51/59
Teoría de Números
Trabajando con números grandes Cálculo de potencias modulares
Algoritmo de exponenciación modularLa idea consiste en obtener la representación del exponente n en dígitos binarios (dt, dt-1, …d2,d1) con dt=1, y hallar los distintos cuadrados sucesivos (mod m) de la base a: (a1, a2, a4, … a2*t), para después multiplicar módulo m las potencias a2*I correspondientes a los dígitos binarios di que sean “1”.
Pág 52/59
Teoría de Números
Trabajando con números grandes Máximo común divisorMás eficiente teniendo en cuenta las propiedades:
x, si y=0MCD(x,y) =
MCD(y, x `mod` y), otro caso
Pág 53/59
Teoría de Números
Trabajando con números grandes
Algoritmo extendido de Euclides
extendedEuclid :: Integer -> Integer -> (Integer, Integer, Integer)
a, b -> (u,v,d)
Pág 54/59
Teoría de Números
El futuro de RSA
Romper el código cifrado con RSA buscando la factorización de n es prácticamente imposible incluso con los ordenadores de la próxima década.
Factorizar un número de 500 dígitos necesita 1025 años a 1us por instrucción.
Cuando se consiga, podríamos elegir números primos mayores y el sistema volvería a ser seguro.
El futuro de la criptografía
Pág 55/59
El futuro de la criptografía
Criptografía CuánticaHace uso de los principios de la física cuántica.
El futuro de la criptografía
Más información en:http://giq.ifae.es/EducationalMaterial/Cripto.pdf
Criptografía Cuántica. M. Baig. de la Universidad Autónoma de Barcelona.
Grupo de Física Teórica.
¿Sin mucho futuro?
El nuevo ataque está basado en las
suposiciones hechas sobre el tipo de errores
que pueden aparecer en los mensajes cuánticos.
Pág 56/59
RSA-HASKELL
Colección de herramientas criptográficas escritas en Haskell para trabajar mediante línea de comandos.
Referencias
http://netsuperbrain.com/rsa-haskell.html
Generar claves:
sskeygen
Cifrar un documento:
ssencrypt friend.public.key message.txt
Descifrar un documento:
ssdecrypt private.key message.txt.ss
public.key private.key
message.txt.ss
message.txtPág 57/59
Bibliografía sobre Teoría de Números
Referencias
Pág 58/59
G. H. HARDY andE. M. WRIGHTUna introducción a la teoría de números
Primera Edición: 1938
Bibliografía sobre Teoría de Números
Referencias
Pág 58/59
RICHARD CRANDALL andCARL POMERANCEPrime Numbers: A Computational Perspective
2ª ed.: 2005
Artículos sobre Teoría de Números
Referencias
Pág 58/59
CARL POMERANCE• “Computational Number Theory”• “Prime Numbers and the Search for Extraterrestrial Intelligence”• “Primality testing with Gaussian periods”
COLING RUNCIMAN• “Lazy wheels sieves and spirals of primes”
Bibliografía sobre criptografía y seguridad
Referencias
Pág 58/59
top related