parte 3
Temas
Llaves privada y pública.
Características de las llaves.
Algoritmos asimétricos:
RSA.
ElGamal.
Curvas elípticas.
Dr. Josiane J. Rodríguez Suárez 2
Criptografía asimétrica
Características de las llaves Comunicación con cifrado
asimétrico
Cada integrante en la comunicación {kprivE,kpubE} {kpubR, kprivR}
cifrada tiene un par de llaves:
Privada: Solo él la conoce: kpriv.
Pública: Todo el mundo la conoce: kpub.
Emisor Receptor
Lo que se cifra con una, se descifra con la
otra. Cifrado (emisor): c = C(m, kpubR)
No es posible descifrar con la misma. Descifrado (receptor): m = D(c, kprivR)
Dr. Josiane J. Rodríguez Suárez 3 Dr. Josiane J. Rodríguez Suárez 4
Características de los algoritmos
Tipos de algoritmos de cifrado
Texto original Texto cifrado Texto descifrado
HOLA KROD HOLA
RSA
Llave Pública Llave Privada
del receptor del receptor
Dr. Josiane J. Rodríguez Suárez 5 Dr. Josiane J. Rodríguez Suárez 6
RSA RSA
Rivest-Shamir-Adleman Requerimientos solicitados
RSA siglas de sus inventores. Facilidad de generar kpub y kpriv.
Basado en el libro: “ ‘New directions in Debe ser fácil generar c teniendo kpub.
cryptography’, IEEE Transactions on Facilidad de obtener m mediante c
Information Theory”, Noviembre, 1976. teniendo kpriv.
En él se establecen los requerimientos No viable obtener kpriv a partir de kpub.
que debe cumplir un algoritmo de llave No viable obtener m a partir de kpub y c.
pública.
Conmutables cifrado y descifrado
Es el estándar de cifrado de llave pública.
Dr. Josiane J. Rodríguez Suárez 7 Dr. Josiane J. Rodríguez Suárez 8
RSA RSA
Características del algoritmo Consideración previa: m Z
Asimétrico. El algoritmo hace uso de números
grandes…, muy muy grandes.
Por bloques.
El mensaje m no se trabaja como cadena de
Utiliza aritmética modular y exponencial.
símbolos ni bits (como los métodos
Fortaleza basada en la dificultad de simétricos) sino como UN NÚMERO.
calcular el logaritmo discreto.
Es fácil transformar m en número: Se
transforma a binario y de binario a decimal.
m es un número entero.
Dr. Josiane J. Rodríguez Suárez 9 Dr. Josiane J. Rodríguez Suárez 10
RSA - Algoritmo de cifrado y descifrado
RSA Comprobación del descifrado
Generación de llaves:
Seleccionar p,q primos (grandes). m<n
Calcular n = pq d = e mod (n)
Calcular (n) = (p-1)(q-1) Cifrado: c = m mod n
Seleccionar un e tal que MCD((n), e) = 1
Descifrado: m = c mod n
Calcular d tal que d = e mod (n)
kpriv = {n,d} m = c mod n
kpub = {n,e} m = (m mod n) mod n
m = m mod n
Cifrado m < n: c = m mod n
m = m mod n
Descifrado: m = c mod n m=m
Dr. Josiane J. Rodríguez Suárez 11 Dr. Josiane J. Rodríguez Suárez 12
RSA - Algoritmo de cifrado y descifrado Criptografía asimétrica
Ejemplo numérico Comunicación con cifrado asimétrico
Mensaje a cifrar m: m = 65
Emisor c = 2790 Receptor
Generación de llaves:
Seleccionar p,q primos: p = 61, q = 53
{kprivE,kpubE} kprivR:{3233, 2753}
Calcular n = pq: n = 3233
(n) = 3120
Calcular (n) = (p-1)(q-1):
e = 17
kpubR:{3233, 17}
Seleccionar un e tal que MCD((n), e) = 1
Calcular d tal que d = e mod (n) d = 2753
kpriv = {n,d} kpriv = {3233,2753} Cifrado (emisor): c = C(65, {3233,17})
kpub = {n,e} kpub = {3233,17}
Cifrado m < n: c = m mod n c = 2790 Descifrado (receptor): m = D(2790,{3233,2753})
Descifrado: m = c mod n m = 65
Dr. Josiane J. Rodríguez Suárez
Dr. Josiane J. Rodríguez Suárez 13 Dr. Josiane J. Rodríguez Suárez 14
RSA
Notas Práctica 2
Profesionalmente las llaves tienen longitudes de Diseñar e implementar una versión ligera de
512, 1024 y 2048 bits.
RSA que cifre y descifre en Lenguaje C:
En RSA:
e: encode.
d: decode. Considera primos pequeños: 5,7,11,13,17 y 19.
Se usan los algoritmos de Euclides para
encontrar e y d en: Cifrar el mensaje M total letra por letra
MCD((n), e) = 1 Utiliza un alfabeto de letras minúsculas.
d = e mod (n)
Dr. Josiane J. Rodríguez Suárez 15 Dr. Josiane J. Rodríguez Suárez 16
ElGamal
ElGamal
Inventado en 1984 por Taher ElGamal.
ElGamal Es la base del protocolo de firma digital.
Dr. Josiane J. Rodríguez Suárez Dr. Josiane J. Rodríguez Suárez
ElGamal - Algoritmo de cifrado y descifrado
ElGamal Ejemplo numérico
Elementos públicos globales: Elementos públicos globales:
q primo. q primo: q = 71
a raíz primitiva de q. a raíz primitiva de q: a=7
a genera al grupo multiplicativo Zq: Zq
Generación de llaves:
Generación de llaves:
Seleccionar x < q -1: x=5
Seleccionar x < q -1
Calcular y = a mod q: y = 51
Calcular y = a mod q
kpriv = x: kpriv = 5
kpriv = x
kpub = {q,a,y}: kpub = {71,7,51}
kpub = {q,a,y}
Cifrado m < q: m = 30
Cifrado m < q:
Seleccionar k < q: k=3
Seleccionar k < q
Calcular K = y mod q: K = 23
Calcular K = y mod q
Calcular c1 = a mod q: c1 = 59
Calcular c1 = a mod q
Calcular c2 = Km mod q: c2 = 51
Calcular c2 = Km mod q
c = {c1,c2}: c = {59,51}
c = {c1,c2}
Descifrado:
Descifrado:
Calcular K = c1 mod q: K = 23
Calcular K = c1 mod q
m = c2 K mod q: m = 30
m = c2 K mod q
Dr. Josiane J. Rodríguez Suárez Dr. Josiane J. Rodríguez Suárez
Curva elíptica
La ecuación de Weierstrass:
Curvas elípticas y2 + axy + by = x3 + cx2 + dx + e
es lo que se conoce como forma general de
una curva elíptica (EC).
Dr. Josiane J. Rodríguez Suárez Dr. Josiane J. Rodríguez Suárez
Curva elíptica Curva elíptica
Ejemplos: Propiedades algebraicas:
Sus puntos forman un grupo aditivo: G+
Cerradura: P+Q EC
Elemento neutro: Es el punto en el : 0
Elemento inverso: P + P1 = 0
2 3
y =x -x 2
y =x -x+1 3 La EC y2 = x3 + ax + b formará grupo si:
4a2 + 27b3 0
Observemos que no son elipses.
Dr. Josiane J. Rodríguez Suárez Dr. Josiane J. Rodríguez Suárez
Curva elíptica Curva elíptica
Coordenadas de las figuras:
1) xR = ((yQyP)/(xQxP))3 - xP - xQ
yR = ((yQyP)/(xQxP))(xP-xR) - yP
3
2) xR = ((3xP3 +a)/(2yP)) - xP - xQ
yR = ((3xP2 +a)/(2yP)) (xP - xR) - yP
3) –Q = P(x,-y)
4) P+0=P
Dr. Josiane J. Rodríguez Suárez Dr. Josiane J. Rodríguez Suárez
Curva elíptica criptográfica Curva elíptica criptográfica
Son EC discretas, cuyas coordenadas son Ejemplo: EC23(1,1): y2 mod 23 = (x3 + x + 1) mod 23
tomadas de Zp o GF(2 )
EC sobre Zp:
ECp(a,b): y2 mod p = (x3 + ax + b) mod p
Dr. Josiane J. Rodríguez Suárez Dr. Josiane J. Rodríguez Suárez
Curva elíptica criptográfica Curva elíptica criptográfica
Las operaciones son las mismas que en el
Ejemplo: EC23(1,1): y2 mod 23 = (x3 + x + 1) mod 23 continuo, solo que ahora se utiliza mod p:
P+0=P
SiP(x,y) -P=(x,-y)
(0,1) (3,10) (5,4) (7,11) (11,13) (13,7) (18,3)
P+Q=R:
(0,22) (3,13) (5,19) (7,12) (11,20) (13,16) (18,20) xR = (l2 -xP-xQ) mod p
yR = (l(xP-xR)-yP) mod p
(1,7) (4,0) (6,4) (9,7) (12,4) (17,3) (19,5) l = ((yQ-yP)/(xQ-xP)) mod p Si P Q
l = ((3xP2 +a)/(2yP)) mod p Si P = Q
(1,16) 0 (6,19) (9,16) (12,19) (17,20) (19,18) nP = P+P+P+…+P, n veces
Dr. Josiane J. Rodríguez Suárez Dr. Josiane J. Rodríguez Suárez
Cifrado con EC Cifrado con EC
La suma en ECC es equivalente a la Generación de llaves pública y privada:
multiplicación en RSA. Cada integrante selecciona una kpriv = n:
Las sumas consecutivas a la A: KprivA = nA
B: KprivB = nB
exponenciación.
Cada integrante genera su kpub = nG
Por lo que:
A: KpubA = nAG
RSA: c= m
mod n B: KpubB = nBG
ECC: Q = kP
Dr. Josiane J. Rodríguez Suárez Dr. Josiane J. Rodríguez Suárez
Cifrado con EC
Cifrado con EC Ejemplo
Sea EC751(-1,188): y2 mod 751 = (x3 - x + 188) mod 23 y G = (0,376),
Cifrado: cifrar Pm = (562,201).
Generación de llaves pública y privada en receptor B:
Cm(Pm) = {kG, Pm + kKpub } receptor
KprivB = nB = 58
KpubB = nBG = (201,5)
Cifrado en A:
Descifrado: Seleccionar k aleatorio: k = 386
Cm(Pm) = {kG, Pm + kKpub } = {386(0,376), (562,201)+386(201,5)}
receptor
Pm = Pm + kKpubreceptor – Kpriv receptor * kG = {(676,558),(385,328)}
Descifrado en B:
Segundo elemento de Cm Primer elemento de Cm Pm = Pm + kKpubreceptor – Kpriv receptor * kG = (2o elemento de Cm) - Kpriv receptor * (1er elemento)
= (385, 328) – 58 (676, 558) = (385, 328) - (239, 377)
= (385, 328) + (239, -377) = (385, 328) + (239, 374)
= (562, 201)
Dr. Josiane J. Rodríguez Suárez Dr. Josiane J. Rodríguez Suárez
