Capítulo 6: Criptografía de clave pública
-
Upload
juan-manuel-garcia -
Category
Technology
-
view
55 -
download
2
Transcript of Capítulo 6: Criptografía de clave pública
![Page 1: Capítulo 6: Criptografía de clave pública](https://reader036.fdocumento.com/reader036/viewer/2022071723/55c4389abb61ebe0118b45c9/html5/thumbnails/1.jpg)
OutlineClave publica
Protocolo de Diffie-HellmanCriptosistema RSA
Criptosistema de ElGamal
CRIPTOGRAFIA DE CLAVE PUBLICA
Juan Manuel Garcıa Garcıa
30 de septiembre de 2010
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA
![Page 2: Capítulo 6: Criptografía de clave pública](https://reader036.fdocumento.com/reader036/viewer/2022071723/55c4389abb61ebe0118b45c9/html5/thumbnails/2.jpg)
OutlineClave publica
Protocolo de Diffie-HellmanCriptosistema RSA
Criptosistema de ElGamal
Clave publicaConceptos basicosCriptosistemas de clave publica
Protocolo de Diffie-Hellman
Criptosistema RSAGeneracion de clavesCifrado y descifradoEjemplo
Criptosistema de ElGamalGeneracion de clavesCifradoDescifradoEjemplo
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA
![Page 3: Capítulo 6: Criptografía de clave pública](https://reader036.fdocumento.com/reader036/viewer/2022071723/55c4389abb61ebe0118b45c9/html5/thumbnails/3.jpg)
OutlineClave publica
Protocolo de Diffie-HellmanCriptosistema RSA
Criptosistema de ElGamal
Conceptos basicosCriptosistemas de clave publica
Conceptos basicos
I Clave de cifrado y descifrado son distintas.
I La clave de cifrado es denominada clave publica.
I La clave de descifrado es la clave privada.
I Resuelve el problema de la distribucion de claves.
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA
![Page 4: Capítulo 6: Criptografía de clave pública](https://reader036.fdocumento.com/reader036/viewer/2022071723/55c4389abb61ebe0118b45c9/html5/thumbnails/4.jpg)
OutlineClave publica
Protocolo de Diffie-HellmanCriptosistema RSA
Criptosistema de ElGamal
Conceptos basicosCriptosistemas de clave publica
Criptosistemas de clave publica
Algunos criptosistemas de clave publica son:
I Protocolo de intercambio de claves de Diffie-Hellman
I Criptosistemas RSA
I Criptosistema ElGamal
I Criptosistemas basados en curvas elıpticas
I Criptosistema Paillier
I Criptosistema Cramer-Shoup
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA
![Page 5: Capítulo 6: Criptografía de clave pública](https://reader036.fdocumento.com/reader036/viewer/2022071723/55c4389abb61ebe0118b45c9/html5/thumbnails/5.jpg)
OutlineClave publica
Protocolo de Diffie-HellmanCriptosistema RSA
Criptosistema de ElGamal
Protocolo de Diffie-Hellman
I Propuesto por Diffie y Hellman fue el inicio de la criptografıade clave publica. Se trata de un protocolo para la distribucionde claves secretas a traves de un canal inseguro.
I Como parametros del sistema se eligen un numero primo p yun entero g , raız primitiva modulo p, comunes a todos losusuarios.
I Como clave privada, cada usuario elige un elemento s ∈ Zp−1.
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA
![Page 6: Capítulo 6: Criptografía de clave pública](https://reader036.fdocumento.com/reader036/viewer/2022071723/55c4389abb61ebe0118b45c9/html5/thumbnails/6.jpg)
OutlineClave publica
Protocolo de Diffie-HellmanCriptosistema RSA
Criptosistema de ElGamal
I Cuando dos usuarios A y B, con claves privadas sA y sB ,quieren establecer una clave secreta comun, el protocolo es elsiguiente:
1. A calcula kA = g sA (mod p),2. B calcula kB = g sB (mod p),3. A y B se intercambian kA y kB a traves del canal inseguro,4. A calcula k = ksA
B = g sB sA (mod p),5. B calcula k = ksB
A = g sAsA (mod p),
I La clave secreta se obtiene a partir de k.
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA
![Page 7: Capítulo 6: Criptografía de clave pública](https://reader036.fdocumento.com/reader036/viewer/2022071723/55c4389abb61ebe0118b45c9/html5/thumbnails/7.jpg)
OutlineClave publica
Protocolo de Diffie-HellmanCriptosistema RSA
Criptosistema de ElGamal
Generacion de clavesCifrado y descifradoEjemplo
Generacion de claves RSA
I Sean p y q dos primos diferentes elegidos aleatoriamente y sean = pq. La funcion de Euler de n esta dada por
φ(n) = (p − 1)(q − 1).
I Se elige un numero 1 < e < φ(n) tal que
gcd(e, φ(n)) = 1,
y obteniendo d como
d = e−1 (mod φ(n)).
I Entonces, d es el exponente privado y e es el exponentepublico.
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA
![Page 8: Capítulo 6: Criptografía de clave pública](https://reader036.fdocumento.com/reader036/viewer/2022071723/55c4389abb61ebe0118b45c9/html5/thumbnails/8.jpg)
OutlineClave publica
Protocolo de Diffie-HellmanCriptosistema RSA
Criptosistema de ElGamal
Generacion de clavesCifrado y descifradoEjemplo
Cifrado y descifrado
I La funcion de cifrado de un mensaje M, donde 0 ≤ M < n, es
E(M) = Me (mod n)
I La funcion de descifrado de un texto cifrado C es
D(C ) = Cd (mod n)
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA
![Page 9: Capítulo 6: Criptografía de clave pública](https://reader036.fdocumento.com/reader036/viewer/2022071723/55c4389abb61ebe0118b45c9/html5/thumbnails/9.jpg)
OutlineClave publica
Protocolo de Diffie-HellmanCriptosistema RSA
Criptosistema de ElGamal
Generacion de clavesCifrado y descifradoEjemplo
Ejemplo: Generacion de claves
I Sean p = 23 y q = 67, entonces
n = 23 · 67 = 1541
yφ(n) = 22 · 66 = 1452.
I El exponente publico e es elegido de forma tal que1 < e < φ(n) y
gcd(e, φ(n)) = gcd(e, 1452) = 1
.
I Por ejemplo, e = 7 satisface estas condiciones.
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA
![Page 10: Capítulo 6: Criptografía de clave pública](https://reader036.fdocumento.com/reader036/viewer/2022071723/55c4389abb61ebe0118b45c9/html5/thumbnails/10.jpg)
OutlineClave publica
Protocolo de Diffie-HellmanCriptosistema RSA
Criptosistema de ElGamal
Generacion de clavesCifrado y descifradoEjemplo
Ejemplo: Generacion de claves
I Entonces, el exponente privado d es calculado como
d = e−1 (mod φ(n))
= 7−1 (mod 1452)
= 415
utilizando el algoritmo extendido de Euclides.
I Entonces la clave publica es el par (e, n) = (7, 1541) y la claveprivada es d = 415.
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA
![Page 11: Capítulo 6: Criptografía de clave pública](https://reader036.fdocumento.com/reader036/viewer/2022071723/55c4389abb61ebe0118b45c9/html5/thumbnails/11.jpg)
OutlineClave publica
Protocolo de Diffie-HellmanCriptosistema RSA
Criptosistema de ElGamal
Generacion de clavesCifrado y descifradoEjemplo
Ejemplo: Cifrado y descifrado
I Supongamos que el mensaje en plano es M = 25.
I El mensaje cifrado es
C = 257 mod 1541 = 1416
.
I Del mensaje cifrado C = 1416 obtenemos el mensajedescifrado
M = 1416415 mod 1541 = 25.
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA
![Page 12: Capítulo 6: Criptografía de clave pública](https://reader036.fdocumento.com/reader036/viewer/2022071723/55c4389abb61ebe0118b45c9/html5/thumbnails/12.jpg)
OutlineClave publica
Protocolo de Diffie-HellmanCriptosistema RSA
Criptosistema de ElGamal
Generacion de clavesCifrado y descifradoEjemplo
Ejercicios
1. Sean p = 1009 y q = 3001, entonces n = 3028009. Generarun par de claves RSA.
2. Con la clave publica cifrar el mensaje M = 1942.
3. Romper el mensaje C = 769763 si fue cifrado mediante RSAcon la clave publica (e, n) = (263, 2772221), utilizando elmetodo ρ de Pollard.
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA
![Page 13: Capítulo 6: Criptografía de clave pública](https://reader036.fdocumento.com/reader036/viewer/2022071723/55c4389abb61ebe0118b45c9/html5/thumbnails/13.jpg)
OutlineClave publica
Protocolo de Diffie-HellmanCriptosistema RSA
Criptosistema de ElGamal
Generacion de clavesCifradoDescifradoEjemplo
Generacion de clave
Cada entidad A debe hacer lo siguiente:
1. Generar un primo grande p y un generador g del grupomultiplicativo Z∗
p de los enteros modulo p.
2. Seleccionar un entero aleatorio a, 1 ≤ a ≤ p − 2, y calcularga mod p.
3. La clave publica de A es (p, g , ga); la clave privada es a.
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA
![Page 14: Capítulo 6: Criptografía de clave pública](https://reader036.fdocumento.com/reader036/viewer/2022071723/55c4389abb61ebe0118b45c9/html5/thumbnails/14.jpg)
OutlineClave publica
Protocolo de Diffie-HellmanCriptosistema RSA
Criptosistema de ElGamal
Generacion de clavesCifradoDescifradoEjemplo
Cifrado
B cifra un mensaje dirigido a A.B hace lo siguiente:
1. Obtener la clave publica (p, g , ga) autentica de A.
2. Representar el mensaje como un entero m en el rango{0, 1, . . . , p − 1}.
3. Seleccionar un entero aleatorio k , 1 ≤ k ≤ p − 2.
4. Calcular γ = gk mod p y δ = m · (ga)k mod p.
5. Enviar el mensaje cifrado c = (γ, δ) a A.
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA
![Page 15: Capítulo 6: Criptografía de clave pública](https://reader036.fdocumento.com/reader036/viewer/2022071723/55c4389abb61ebe0118b45c9/html5/thumbnails/15.jpg)
OutlineClave publica
Protocolo de Diffie-HellmanCriptosistema RSA
Criptosistema de ElGamal
Generacion de clavesCifradoDescifradoEjemplo
Descifrado
Para recuperar el mensaje en texto plano m de c , A hace losiguiente:
1. Usar la clave privada a para calcular γp−1−amod (Nota:γp−1−a = γ−a = g−ak).
2. Recuperar m = (γ−a) · δ mod p.
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA
![Page 16: Capítulo 6: Criptografía de clave pública](https://reader036.fdocumento.com/reader036/viewer/2022071723/55c4389abb61ebe0118b45c9/html5/thumbnails/16.jpg)
OutlineClave publica
Protocolo de Diffie-HellmanCriptosistema RSA
Criptosistema de ElGamal
Generacion de clavesCifradoDescifradoEjemplo
Ejemplo: Generacion de claves
1. La entidad A selecciona el primo p = 2357 y un generadorg = 2 de Z∗
2357.
2. A elige la clave privada a = 1751 y calcula
ga mod p = 21751 mod 2357 = 1185.
3. La clave publica de A es (p = 2357, g = 2, ga = 1185).
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA
![Page 17: Capítulo 6: Criptografía de clave pública](https://reader036.fdocumento.com/reader036/viewer/2022071723/55c4389abb61ebe0118b45c9/html5/thumbnails/17.jpg)
OutlineClave publica
Protocolo de Diffie-HellmanCriptosistema RSA
Criptosistema de ElGamal
Generacion de clavesCifradoDescifradoEjemplo
Ejemplo: Cifrado
Para cifrar un mensaje m = 2035, B selecciona un entero aleatoriok = 1520 y calcula
γ = 21520 mod 2357 = 1430
yδ = 2035 · 11851520 mod 2357 = 697.
B envıa γ = 1430 y δ = 697 a A.
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA
![Page 18: Capítulo 6: Criptografía de clave pública](https://reader036.fdocumento.com/reader036/viewer/2022071723/55c4389abb61ebe0118b45c9/html5/thumbnails/18.jpg)
OutlineClave publica
Protocolo de Diffie-HellmanCriptosistema RSA
Criptosistema de ElGamal
Generacion de clavesCifradoDescifradoEjemplo
Ejemplo: Descifrado
Para descifrar, A calcula
γp−1−a = 1430605 mod 2357 = 872,
y recupera m calculando
m = 872 · 697 mod 2357 = 2035.
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA
![Page 19: Capítulo 6: Criptografía de clave pública](https://reader036.fdocumento.com/reader036/viewer/2022071723/55c4389abb61ebe0118b45c9/html5/thumbnails/19.jpg)
OutlineClave publica
Protocolo de Diffie-HellmanCriptosistema RSA
Criptosistema de ElGamal
Generacion de clavesCifradoDescifradoEjemplo
Ejercicios
1. Si la clave publica de El Gamal de un usuario es(p, g , ga) = (2011, 3, 1415), cifrar el mensaje m = 333.
2. Si el mensaje cifrado c = (243, 1352) lo fue con la clavepublica previa, romper el cifrado utilizando busquedaexhaustiva de logaritmo discreto.
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA