Curso de criptografía básica para principiantes - Criptografía Asimétrica

Generación de parámetros

1) p = 3, q = 5 (se eligen don números primos como clave privada) 2) n = 15 ( se calcula el producto, es la clave pública) 3) ϕ(n)=(3-1)(5-1)=8 4) Sea e=3, entonces d=3, ya que e*d = 3*3 =9 mod 8 =1 (como este caso

solo es para mostrar el funcionamiento no importa que d sea igual a e, sin embargo en la práctica e es pequeño y d es muy grande) 5) Si el mensaje es m=2

Proceso de cifrado

6) El mensaje cifrado es c= m^e mod n, es decir, c=2³ mod 15, o sea c=8

Proceso de descifrado

7) Para descifrar el mensaje m=8³ mod 15, es decir, m=512 mod 15, asi m=2 (ya que 512/15=2 mod 15 = m)

Por lo tanto es correcto el funcionamiento.

Proceso de Firma

1) El mensaje a firmar es M, se le aplica una función hash que reduce su longitud de forma única a un mensaje H(M) de longitud de 128 o 160 bits, lo que permite ver cualquier mensaje de cualquier longitud como una cadena de caracteres de longitud constante.

2) H(M) se somete también a un proceso de codificación, por lo tanto se obtiene un número h(M), al que se le aplica la formula con la potencia d, equivalentemente con la clave privada del firmante para obtener (s =M h )^d mod n

3) Se envía entonces el mensaje firmado s

Proceso de Verificación

1) El que recibe s, se supone conoce el mensaje M, aplica la función de verificación que depende de la clave pública de quien se dice propietario del mensaje

eh' =s mod n

2) Ahora se aplica la función hash al mensaje M y si h(M)=h’ entonces acepta la firma

En un esquema con mensaje recuperable no es necesario saber el mensaje, después de que la firma es aceptada el mensaje puede recuperarse a partir de la firma.

Ejemplo simple:

Tomemos los mismos parámetros del ejemplo en el esquema de cifrado, p=3, q=5, m=2, ϕ=8, e=3, d=3

Proceso de Firma

1) La firma del documento m es: s= m^d mod n = 2³ mod 15 =8 2) El mensaje firmado es entonces (m,s) = (2,8)

Proceso de verificación

3) Aplicando la función de verificación s^e mod n = 8³ mod 15 = 2 4) Como 2 (el obtenido de la anterior fórmula) = 2 (el mensaje enviado) 5) Entonces la firma es válida

1) La longitud de las claves

Existe una gran discusión [26], sobre este aspecto pero sin duda en la actualidad se acepta que es recomendable usar claves de longitud 768 (231 dígitos) para actividades personales,1024 bits (308 dígitos) para corporaciones y 2048 (616 dígitos) para actividades de alto riesgo. La longitud de las claves tiene que ver con la seguridad del sistema si el número n pudiese ser factorizado entonces sin mucha dificultad puede calcular a d a partir de e, p, y q por lo tanto descifrar cualquier mensaje. El último récord conocido sobre factorización de números enteros producto de dos primos de la misma longitud es de 512 bits (155 dígitos) dígitos alcanzado en Jul de 1999.

2) La aleatoriedad de las claves

La generación de las claves RSA es muy importante, muchos ataques son evitados si las claves son elegidas de forma aleatoria [63], esto incrementara la seguridad del sistema.

3) método de codificación

El método que actualmente es usado para aplicaciones en el esquema de cifrado es el OAEP, este resiste a los ataques que actualmente se conocen y el estándar más conocido sobre RSA es el PKCS#1 v.2 de la RSA Data Security. En el caso de Esquemas de firma digital el método de codificación recomendable es PSS que esta descrito en PKCS#1 v 2.1

4) Elección de parámetros

La elección adecuada de los parámetros que se usan aumenta la seguridad del sistema así como su fácil y rápida implementación. Como elegir a e=65537 = (01 00 01)16, para poder efectuar la operación exponente eficientemente. Además de elegir d la clave privada de longitud grande para evitar el ataque de Wiener [45]. Los números primos p,q además de ser generados aleatoriamente deben de tener la misma longitud y no estar cerca.

CCE otro tipo de criptografía de clave pública es el que usa curvas elípticas definidas en un campo finito. La diferencia que existe entre este sistema y RSA es el problema matemático en el cual basan su seguridad. RSA razona de la siguiente manera: te doy el número 15 y te reta a encontrar los factores primos. El problema en el cual están basados los sistemas que usan curvas elípticas que denotaremos como CCE es el del logaritmo discreto elíptico, en este caso su razonamiento con números sería algo como: te doy el número 15 y el 3 y te reta a encontrar cuantas veces tienes que sumar el mismo 3 para obtener 15.

En lo que sigue nos dedicaremos a explicar un poco lo más importante de los CCE

1) Entenderemos como una curva elíptica a una ecuación de la forma siguiente:

y +axy +by =x ³ +cx +dx +e

Donde las constantes a,b,c,d y e pertenecen a cierto conjunto llamado campo F, que para propósitos de la criptografía o es un campo primo (Zp) o un campo de característica 2, o sea donde los elementos son n-adas de ceros y unos (F2ⁿ)

2) A un punto que satisface la ecuación anterior se le llama punto racional. Si el campo es finito, entonces el conjunto de puntos (x,y) que satisfacen la ecuación es finito y es llamado conjunto de puntos racionales de la curva E sobre el campo F. Al conjunto de puntos racionales lo podemos representar como

EO P , P₂, P ,..., P:, ₁ 3 n

E representa la ecuación y O es un punto que no tiene coordenadas y hace el papel de cero (llamado punto al infinito) ya que en este conjunto los puntos puede sumarse y tiene las mismas propiedades que la suma de los números enteros, es decir lo que se conoce como un grupo abeliano.

Ejemplo: veamos una curva elíptica simple, si la ecuación es y=x³+4x+3 y el campo Z5, es decir el conjunto {0,1,2,3,4}, entonces las parejas que satisfacen la ecuación son {(2,2), (2,3}, por lo tanto la curva elíptica es E: {O, (2,2), (2.3)}. En este caso E tiene 3 puntos racionales.

3) La suma de estos puntos tiene una explicación geométrica muy simple, si la gráfica representa a todos los puntos que satisfacen la ecuación de la curva elíptica, y queremos sumar a P y Q, trazamos una línea recta que pase por P y Q, la ecuación de la curva es de grado 3 y la línea de grado 1, entonces existen siempre tres soluciones, en este caso la tercera solución esta dibujada como el punto -P-Q, enseguida se procede a dibujar una línea recta paralela al eje Y que pase por -P-Q, esta línea vertical también intercepta tres veces a la recta, todas las líneas verticales interceptan al punto especial llamado infinito y que geométricamente esta en el horizonte del plano, el tercer punto es por definición P+Q, como se muestra en la figura

4) No es difícil obtener fórmulas para calcular las coordenadas del punto P+Q a partir de las coordenadas del punto P y del punto Q. Por ejemplo si el campo de definición de la curva es un campo primo Zp, entonces las fórmulas de suma son las siguientes

2 (

λλ

x

−

−

=

x

x₁ x

3

2

)

−−

=

y x

y

1

3

1

3

−

⎧

y

y

2

1

, P

≠

Q

⎪⎪

−

x

x₁

=

λ

2

3x₁²

+

a

⎪⎪

P

Q

=

,

2 y

1

5) La anterior forma de sumar puntos de una curva elíptica es un poco extraña sin embargo, es esta extrañeza lo que permita que sea un poco más difícil romper los CCE. En el área de las matemáticas conocida como teoría de grupos se sabe que estos grupos son muy simples llamados grupo abelianos finitos lo que permite también que los CCE sean fácil de implementar, llamaremos al número de puntos racionales de la curva como el orden de la curva. En nuestro ejemplo P0=O, P1=(2,2), P2=(2,3), donde 2P1=P2.

6) Los CCE basan su seguridad en el Problema del Logaritmo Discreto Elíptico (PLDE), esto quiere decir que dados P,Q puntos de la curva hay que encontrar un número entero x tal que xP = Q (xP = P+P+…+P, x veces). Obsérvese que a diferencia del PFE (Problema de Factorización Entera) el PLDE no maneja completamente números, lo que hace más complicado su solución.

7) La creación de un protocolo con criptografía de curvas elípticas requiere fundamentalmente una alta seguridad y una buena implementación, para el primer punto se requiere que la elección de la curva sea adecuada, principalmente que sea no-supersingular y que el orden del grupo de puntos racionales tenga un factor primo de al menos 163 bits, además de que este orden no divida al orden de un número adecuado de extensiones del campo finito [13][27], para que no pueda ser sumergido en él, si el campo es ZP, se pide que la curva no sea anómala o sea que no tenga p puntos racionales. Todo esto con el fin de evitar los ataques conocidos. Para el caso de la implementación hay que contar con buenos programas que realicen la aritmética del campo finito, además de buenos algoritmos que sumen puntos racionales, tanto en el caso de Zp como F2ⁿ, en este último se toma una base polinomial que tenga el mínimo de términos por ejemplo un trinomio para generar los elementos del campo finito esto si la implementación es en software, y se toma una base normal si es en hardware. Además de contemplar que las operaciones de puntos racionales pueden hacerse en el espacio proyectivo, esto elimina el hacer divisiones, ahorrando tiempo.

8) Lo anterior se ve reflejado en las ventajas que ofrecen los CCE en comparación con RSA, la principal es la longitud de la clave secreta. Se puede mostrar que mientras en RSA se tiene que usar una clave de 1024 para ofrecer una considerable seguridad, los CCE solo usan 163 bits para ofrecer la misma seguridad, así también las claves RSA de 2048 son equivalentes en seguridad a 210 de CCE. Esto se debe a que para resolver el PLDE el único algoritmo conocido toma tiempo de ejecución totalmente exponencial, mientras que el algoritmo que resuelve PFE incluso también el PLD en Zp toman un tiempo subexponencial.

9) Otra buena noticia sobre CCE es que los elementos de los puntos racionales pueden ser elementos de un campo finito de característica 2, es decir pueden ser arreglos de ceros y unos de longitud finita (01001101110010010111), en este caso es posible construir una aritmética que optimice la rapidez y construir un circuito especial para esa aritmética, a esto se le conoce como Base Normal Optima.

10)Lo anterior permite con mucho que los CCE sean idóneos para ser implementados en donde el poder de cómputo y el espacio del circuito sea reducido, donde sea requerida una alta velocidad de procesamiento o grandes volúmenes de transacciones, donde el espacio de almacenamiento, la memoria o el ancho de banda sea limitado. Lo que permite su uso en Smart Cards, Teléfonos celulares, Fax, Organizadores de Palma, PCs, etcétera.

11)En la actualidad existen varios estándares que permiten el uso adecuado y óptimo de los CCE, entre los cuales se encuentran: IEEE P1363 [75] (Institute of Electrical and Electronics Engineers), el ANSI X9.62, ANSI X9.63, ANSI TG17, ANSI X12 (American National Standards Institute), UN/EDIFACT, ISO/IEC 14888, ISO/IEC 9796-4, ISO/IEC 14946 (International Standards Organization), ATM Forum (Asynchronous Transport Mode), WAP (Wireless Application Protocol). En comercio electrónico: FSTC (Financial Services Technology Consortion), OTP 0.9 (Open Trading Protocol), SET (Secure Electronic Transactions). En internet IETF (The Internet Engineering Task Force), IPSec (Internet Protocol Security Protocol)

12) Los CCE son el mejor candidato para reemplazar a las aplicaciones que tienen implementado RSA, estas definen también esquemas de firma digital, Intercambio de claves simétricas y otros. Los CCE se pueden estudiar en [14][31][35][69][71].