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.
Criptografía de Clave Pública Usuario A Usuario B E (M) KPB D (E (M) ) = M KPB KSB Usuario A Usuario cualquiera E (M) KSA D (E (M) ) = M KSA KPA Confidencialidad : Firma digital (autenticación):
Comparativa entre Simétrica y Asimétrica ¿ Qué es lo deseado ? Combinar la velocidad con la seguridad ? Criptosistemas híbridos
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
Algoritmo RSA
Generación de claves
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) (f de Euler)
Este algoritmo se basa en principios de la teoría de números.
Generación de la Clave Publica
3. Seleccionar un número e: – Coprimo con z – Menor que z
Exponente de la clave publica
Generación de la Clave Privada
3. Seleccionar un número d: – e*d = 1 mod z – de-1 divide a f(n)
Exponente de la clave privada
Criptografía de Clave Pública RSA 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
RSA en Haskell
Codificar
Descodificar
Criptografía de Clave Pública RSA 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
Primalidad Determinar números primos grandes de forma aleatoria. Factorización Encontrar la factorización de un número n como producto de factores primos.
Cálculo con números grandes Eficiencia en las operaciones matemáticas cuando se trabaja con números grandes.
Teoría de Números Problemas de RSA NP-Completo NP-Completo Polinomial
Primalidad Test de primalidad Criterio para decidir si un número dado es o no primo. Test de la divisiones sucesivas. Test de pseudoprimalidad Criterio 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 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 Teoría de Números
Obteniendo números primos grandes Usar tablas publicadas Rápido. Números pequeños para objetivos criptográficos. Generación y test Generar números aleatorios impares de tamaño grande y aplicarles un test de pseudoprimalidad. Teorema de Tchebycheff La cantidad de números primos menores o iguales que N es Teoría de Números
Obteniendo números primos grandes Generación de números aleatorios de N dígitos Teoría de Números
Obteniendo números primos grandes Generación de primos aleatorios de N dígitos Teoría de Números
Test de pseudoprimalidad Test de Fermat Si 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 Teoría de Números
Test de pseudoprimalidad Test de Solovay-Strassen El 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. O (k (log n)^3) Probabilidad de que un número no sea primo y pase el test: 2-k 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]
O (k (log n)^3) Teoría de Números
Últimos avances Algoritmo AKS (2002) Manindra Agrawal, Neeraj Kayal y Nitin Saxena Departamento 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. O(K(log n)^12+e) 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)
Teoría de Números
Factorización: Test de las divisiones sucesivas Test de las divisiones sucesivas Mismo procedimiento que para comprobar la primalidad.
Ineficiente Teoría de Números
Factorización: Método del algoritmo de Euclides Método del algoritmo de Euclides Dado 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.
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 Fermat 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: …
(Gp:) Idea de Fermat si n = x2 * y2, entonces n puede factorizarse: n = (x+y)*(x-y) Como x2 > n se tiene que x > raiz(n)
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). 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: x e y son congruentes módulo p con probabilidad 0.5 tras elegir 1.177*raiz(p) números. Si p es factor de n, entonces 1 < mcd(|x-y|, n) <= n, ya que p divide tanto a |x-y| como a n.
(Gp:) Secuencia x (Gp:) Secuencia y (Gp:) mcd(|x-y|, n)
Si mcd(|x-y|, n) = n -> Fracaso 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 datos Por ejemplo: array de dígitos. ¡ Hay que implementar todas las operaciones! Teoría de Números
Trabajando con números grandes Cálculo de potencias modulares
Algoritmo de exponenciación modular La 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”. Teoría de Números
Trabajando con números grandes Máximo común divisor Más eficiente teniendo en cuenta las propiedades:
(Gp:) x, si y=0 MCD(x,y) = MCD(y, x `mod` y), otro caso
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) 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ágina siguiente |