UNIVERSIDAD AUTONOMA
DE BUCARAMANGA
FIRMAS DIGITALES UTILIZANDO
CURVAS ELIPTICAS
Msc Miguel Cadena Carter
Msc Juan Carlos Martínez Q
Laboratorio de Computo especializado
UNAB
UNIVERSIDAD AUTONOMA
DE BUCARAMANGA
PROBLEMA
• Transmisión de información en
forma segura en un medio inseguro.
– Redes Lan
• Manejo de documentos
– Internet
• Comercio electrónico
UNIVERSIDAD AUTONOMA
DE BUCARAMANGA
SERVICIOS
• Autenticidad
Se debe garantizar que la identidad del
emisor este directamente relacionada con el
documento
• Integridad
Se debe eliminar la posibilidad de
alteraciones al documento
• No repudio
Criptografía
UNIVERSIDAD AUTONOMA
DE BUCARAMANGA
• Simétrica o Convencional (una sola clave)
– Se encripta y se decripta con la misma clave
– Rápida
– Grandes cantidades de información
• Pública (dos clave)
–
–
–
–
–
Clave Privada (KR)
Clave Pública (KU)
Se encripta con una clave, se decripta con la otra.
Lenta
Cantidades pequeñas de información (una clave de
criptografia convencional)
UNIVERSIDAD AUTONOMA
DE BUCARAMANGA
FUNCIONES HASH
h = H(M)
• El propósito de una función hash es producir
una “huella digital” de un archivo.
• Tiene las siguientes características
– H puede aplicarse a mensajes de cualquier
tamaño.
– H produce salidas de longitud fija
– H(M) fácil de calcular en hardware y software
– Comp. infactible encontrar M’ tal que H(M’)=
h
UNIVERSIDAD AUTONOMA
DE BUCARAMANGA
FUNCION SHA1
• Produce un resumen del archivo de 160
Bits de longitud.
• Divide el mensaje en bloques de 512
bits, agrega un “1” seguido de “0”s
cuando el bloque es < 512.
• Procesa cada bloque en secuencia
utilizando la salida de cada bloque como
entrada para el próximo.
UNIVERSIDAD AUTONOMA
DE BUCARAMANGA
Qué es una firma digital?
U n a firm a e s u n a p ro p ie d a d p riva d a d e u n u su a rio o
p ro ce so q u e u sa p a ra firm a r m e n sa je s. L a firm a d ig ita l
sirve p a ra e sta b le ce r la id e n tid a d d e l e m iso r y
la
a u te n ticid a d d e l m e n sa je .
S e a B e l re ce p to r d e u n m e n sa je e n via d o p o r A . L a
firm a d ig ita l d e b e sa tisfa ce r lo s sig u ie n te s re q u isito s:
1 . B d e b e p o d e r va lid a r la firm a d e A .
2. Debe
se r
“co m p u ta cio n a lm e n te
d íficil”
p a ra
cu a lq u ie ra , in clu ye n d o B , fa lsifica r la firm a d e A .
3 . E n ca so d e d isp u ta p o r la firm a d e u n m e n sa je ,
d e b e se r p o sib le p a ra u n a te rce ra p a rte re so lve r la
d isp u ta e n tre A Y B .
UNIVERSIDAD AUTONOMA
DE BUCARAMANGA
FIRMAS DIGITALES
• Garantizan autenticidad e integridad
• Para evitar repudiación se utiliza un
servidor de certificados (Notaria)
• No garantizan secreto
UNIVERSIDAD AUTONOMA
DE BUCARAMANGA
CARACTERISTICAS
• Los procedimientos de firmas digitales
se apoyan en problemas matemáticos
cuya solución es computacionalmente
infactible si se desconocen las claves de
acceso
• El conocimiento de las claves de acceso
permite la solución del problema en
forma rápida.
ESQUEMA GENERAL DE FIRMA DIGITAL
UNIVERSIDAD AUTONOMA
DE BUCARAMANGA
Emisor (A)
Receptor (B)
||
m
m
h’
Comparación
D
h
E
M = Mensaje
h = Hash del mensaje (emisor)
h’ = Hash del mensaje (receptor)
E = Proceso de encriptamiento
|| = Concatenación
EKRa[H(m)]
KRa
D = Decriptamiento
Kpuba = Clave pública de A
KRa = Clave privada de A
Kpuba
UNIVERSIDAD AUTONOMA
DE BUCARAMANGA
Firmas Digitales Utilizando Curvas
Elípticas
• El algoritmo se basa en el problema del
logaritmo discreto en el grupo formado por
los puntos de una curvas elíptica definida en
un cuerpo de Galois.
• El mejor algoritmo conocido corre en tiempo
exponencial.
Qué es una curva elíptica?
UNIVERSIDAD AUTONOMA
DE BUCARAMANGA
Una curva elíptica E sobre Zp ( p>2) esta definida por
una ecuación de la forma
y2 = x3 + ax + b,
(1)
donde a, b Zp, y 4a3 + 27b2  0 (mod p), junto con un
punto especial 0, llamado el “punto en el infinito”.
El conjunto E(Zp) consiste en todas las puntos (x, y),
xZp, yZp, que satisfacen la ecuación (1), junto con
el punto 0.
UNIVERSIDAD AUTONOMA
DE BUCARAMANGA
Qué es una curva elíptica?
Ejemplo 3 (curva elíptica sobre Z23)
Sea p = 23 y E: y2 = x3 + x definida sobre Z23.
Los puntos en E(Z23) son los siguientes:
(0, 1) (0,5) (1, 18) (9,5) (9,18) (11,10) (11,13) (13,5)
(13, 18) (15,3) (15,20) (16,8) (16,15) (17,10) (17,13) (18,10)
(18,13) (19,1) (19,22) (20,4)(20,19) (21,6) (21,17)
UNIVERSIDAD AUTONOMA
DE BUCARAMANGA
UNIVERSIDAD AUTONOMA
DE BUCARAMANGA
Formula de adición
Existe una regla para “sumar” dos puntos sobre una
curva elíptica E(Zp), de tal forma que la suma sea otro
punto de la curva.
El conjunto de puntos E(Zp) junto con la operación de
suma anteriormente mencionada forman un grupo
abeliano, donde el punto infinito O es el elemento
neutro.
UNIVERSIDAD AUTONOMA
DE BUCARAMANGA
Formula de adición
Sean P = (x1, y1) y Q = (x2, y2) dos puntos distintos en
una curva elíptica E. Entonces la suma de P y de Q,
denotada por R = (x3, y3), se define de la forma
siguiente.
Primero trace la línea a través
P y Q; esta línea intercepta la
curva elíptica E en un tercer
punto. Entonces R es la
reflexión de este punto sobre
el eje x.
UNIVERSIDAD AUTONOMA
DE BUCARAMANGA
Formula de adición
Si P = (x1, y1), entonces el doble de P, denotado R =
(x3, y3) se define como sigue. Primero trace la línea
tangente a la curva elíptica en P. Esta línea intercepta a
la curva elíptica en un segundo punto. La reflexión de
este punto respecto al eje x es R.
1. P + O = O + P = P para todo el
P E(Zp).
2. Si P = (x, y) E(Zp), entonces
(x, y) + (x, - y) = O. El punto (x, - y)
se denota por - PE(Zp), y se
llama inverso aditivo de P.
UNIVERSIDAD AUTONOMA
DE BUCARAMANGA
Formula de adición
Sean P = (x1, y1) E(Zp) y Q = (x2, y2) E(Zp), dondeP
- Q. Entonces P+Q = (x3, y3), donde
x3 = 2 - x1 - x2,
y3 = (x1 -x3) - y1,
Suma de Puntos
UNIVERSIDAD AUTONOMA
DE BUCARAMANGA
UNIVERSIDAD AUTONOMA
DE BUCARAMANGA
CUERPOS
• Conjunto de elementos con dos operaciones
definidas (suma, multiplicación)
• Suma es un grupo aditivo abeliano
• Multiplicación es un grupo multiplicativo
abeliano (todos los elementos 0 tienen su
inverso multiplicativo)
• El campo es finito si tiene un número finito
de elementos. El orden de F es el numero de
elementos de F.
• Ejemplos Reales, Complejos, Enteros mod
p.
UNIVERSIDAD AUTONOMA
DE BUCARAMANGA
CUERPO F2m
• Los elementos de F2m son polinomios
de grado menor que m con coeficientes
en el cuerpo F2.
• El Cuerpo F2m es finito y tiene 2m
elementos que se pueden representar
por cadenas de unos y ceros con una
longitud máxima de m
CUERPO F2m
UNIVERSIDAD AUTONOMA
DE BUCARAMANGA
• Operaciones en F2m
–
–
–
–
–
Suma
Resta
Multiplicación
Cálculo del Inverso Multiplicativo
Exponenciación
UNIVERSIDAD AUTONOMA
DE BUCARAMANGA
Curva elíptica en el Cuerpo F24
g0 = (0001)
g7 = (1011)
g1 = (0010)
g8 = (0101)
g2 = (0100)
g9 = (1010)
g3 = (1000)
g10 = (0111)
g4 = (0011)
g11 = (1110)
g5 = (0110)
g12 = (1111)
g6 = (1100)
g13 = (1101)
g7 = (1011)
g14 = (1001)
g15 = (0001)
g = (0010)
f(x) = x4 + x + 1.
WWW.CERTICOM.COM
UNIVERSIDAD AUTONOMA
DE BUCARAMANGA
Curvas Elípticas
• El conjunto conformado por las
soluciones a la curva mas el punto en el
infinito junto con la operación de suma
de puntos conforman un grupo aditivo.
UNIVERSIDAD AUTONOMA
DE BUCARAMANGA
Qué es un grupo?
U n g ru p o e s u n a e stru ctu ra a lg e b ra ica q u e co n siste d e
u n co n ju n to G ju n to co n u n a o p e ra ció n + d e fin id a p a ra
ca d a p a r d e e le m e n to s d e G , q u e sa tisfa ce :
1 . a + b  G p a ra to d o a , b  G (C la u su ra tiva )
2 . a + (b + c) = (a + b ) + c, p a ra to d o a , b , c  G
(A so cia tiva ).
3 . E xiste u n e  G ta l q u e e + a = a + e = a p a ra
to d o  G (E xiste n cia d e u n e le m e n to id e n tid a d )
4 .P a ra ca d a a  G , e xiste u n e le m e n to b  G ta l q u e
a + b = b + a = e (In ve rso )
-1 .
E l e le m e n to b se d e n o m in a e l in ve rso y se d e n o ta p o r a
U n g ru p o G se d e n o m in a “a b e lia n o ” si a + b = b *+ a p a ra
to d o a , b  G . O rd e n u n o g ru p o e s e l n ú m e ro e le m e n to s e n e l
co n ju n to G .
UNIVERSIDAD AUTONOMA
DE BUCARAMANGA
Ejemplos de Grupos
Ejemplo 1 (Los enteros modulo n)
Zn = {0, 1, 2,.., n - 1}, bajo la adición modulo n, forman un
grupo de orden n.
Si p es un número primero, entonces los elementos
diferentes a cero de Z*p = {1, 2,.., p -1}, forman un grupo de
orden p – 1, bajo operación de multiplicación modulo p.
UNIVERSIDAD AUTONOMA
DE BUCARAMANGA
El problema del logaritmo
discreto
• Sea G un grupo finito cíclico de orden n. Sea  un
generador de G y sea   G. El logaritmo discreto de
 a la base  , expresado como Log es el único
entero x , 0  x  n-1, tal que  = x
Si el grupo es aditivo el problema del logaritmo discreto es:
Dados P y Q miembros del grupo, encontrar un numero k tal
que kP = Q; k se denomina el logaritmo discreto de Q en la base
P
Ejemplo
UNIVERSIDAD AUTONOMA
DE BUCARAMANGA
En el grupo Z*13 cual es el logaritmo discreto de 8 en la base 7.
7x mod 13 = 8
•
•
•
•
•
•
•
•
•
•
70
71
72
73
74
75
76
77
78
79
mod
mod
mod
mod
mod
mod
mod
mod
mod
mod
13
13
13
13
13
13
13
13
13
13
=
=
=
=
=
=
=
=
=
=
1
7
10
5
9
11
12
6
3
8
UNIVERSIDAD AUTONOMA
DE BUCARAMANGA
ESQUEMA DE FIRMA NYBERGRUEPPEL
• Sea e el valor hash del documento
• Sea E una curva elíptica
• Sea P un punto de la curva con un orden
grande y primo.
• Sea s la clave privada del emisor
s=H(f1)
• Sea Q = sP la clave publica del emisor
UNIVERSIDAD AUTONOMA
DE BUCARAMANGA
ESQUEMA DE FIRMA NYBERGRUEPPEL
• Generar un número aleatorio k y
calcular
R = kP
• Usando la componente x del Punto P
como si fuese un entero,calcular.
c = x + e mod n
d = k - sc mod n
UNIVERSIDAD AUTONOMA
DE BUCARAMANGA
ESQUEMA DE FIRMA NYBERGRUEPPEL
• El par (c,d) es la firma del documento
representado por el valor hash
• Para verificar La firma se debe calcular
R’= dP + cQ
Usando la componente x de R’
e’ = c-x’ mod n
Se calcula un nuevo hash del documento y si
el mismo es igual a e’ , la firma es correcta.
1,2
COMPARISON OF SECURITY LEVELS
ECC and RSA & DSA
UNIVERSIDAD AUTONOMA
DE BUCARAMANGA
1
6000
5000
0,8
Key Size
(Bits)
4000
ECC
0,6 3000
RSA &DSA
2000
0,4
1000
0,2
0
0
10000
1E+12
1E+36
Tim e to Break Key (MIPS Years)
[ELIPCUR1] CERTICOM WHITE PAPER. REMARKS ON THE SECURITY OF THE ELLIPTIC CURVE
CRIPTOSYSTEM. CERTICOM. 1997
UNIVERSIDAD AUTONOMA
DE BUCARAMANGA
Conclusiones
• La teoría de curvas elípticas y los desarrollos de software de
dominio publico permiten a través de su estudio la construcción
de aplicaciones que ofrecen los servicios de Autenticidad e
Integridad.
• Los servicios de secreto e intercambio de claves de criptografía
simétrica se pueden implementar fácilmente a partir de las
aplicaciones realizadas.
• Es necesaria el mejoramiento de las técnicas de programación
para evitar la exposición de información critica en memoria y
los ataques por desbordamiento de pila.
• Se requiere mayor investigación sobre métodos para
generación de buenas curvas en tiempo polinomial.
APLICACIÓN PARA REALIZAR FIRMAS DIGITALES
UNIVERSIDAD AUTONOMA
DE BUCARAMANGA
Descargar

Firmas digitales utilizando curvas elípticas