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 anterior | Volver al principio del trabajo | Página siguiente  |