CRIPTO II – UT II – N° 06

ASIMETRICA IV LOG DISCRETOS

cripto-scolnik-hecht

UT-2 UNIDAD TEMÁTICA N° 2: Criptografía Asimétrica. Funciones Unidireccionales. Funciones Trampa. Historia de la Criptografía Asimétrica. Protocolo de Diffie y Hellman para el intercambio de claves. Métodos asimétricos y de clave pública (PohligHellman, RSA, Fiat-Shamir). Ataques a RSA. Criptosistema de McEliece. Criptosistemas Basados en el Problema de la Mochila: MerkleHellman. Criptosistemas varios. Criptosistemas Basados en el Problema de logaritmo discreto: ElGamal, Ataque a El Gamal. Criptosistemas Basados en Curvas Elípticas.

cripto-scolnik-hecht

CRIPTOGRAFIA DE CLAVE PUBLICA LOS CRIPTOSISTEMAS DE CLAVE PUBLICA DEBEN BASARSE EN PROBLEMAS COMPUTACIONALMENTE COMPLEJOS (CLASES NP o NPNP-Completo) Y CUYAS VIAS INVERSAS SEAN SIMPLES (CLASE P) PERO NO DEDUCIBLES DE LA PRIMERA. EL MAS IMPORTANTE (PERO NO EL UNICO DE INTERES) ES EL CRIPTOSISTEMA RSA, BASADO EN EL PROBLEMA DE LA FACTORIZACION. AQUÍ PRESENTAMOS EL PROBLEMA DE LOGARITMOS DISCRETOS Y ALGUNOS DE SUS CRIPTOSISTEMAS DERIVADOS.

cripto-scolnik-hecht

PROBLEMA DE LOS LOGARITMOS DISCRETOS - 1 Sea Zp el campo finito de enteros módulo p (primo). El grupo multiplicativo Zp* (residuos modulo p, donde * implica coprimos con p, aquí es

es cíclico y se define como elemento primitivo a todo generador de Zp* inevitable!)

DEFINICION: Sean p primo, α (elemento primitivo) ∈ Zp y β ∈ Zp* , el problema de logaritmos discretos consiste en hallar un entero a, 0 ≤ a ≤ p-2, tal que α a ≡ β (mod p) A este entero a se lo llama logα β , su resolución es de complejidad clase NP

cripto-scolnik-hecht

PROBLEMA DE LOS LOGARITMOS DISCRETOS - 2 El logaritmo discreto en Zp ha sido objeto de estudio intensivo. El problema se hace prácticamente complejo de resolver para valores p cuidadosamente elegidos. En particular, se desconocen algoritmos de resolución clase P. Para evitar ataques (potencia computacional actual) p > 10150 y p-1 debe tener al menos un factor “grande”. Es (por ahora) clase NP, pero su inversa (exponenciación modular) es clase NP y muy eficiente. Su aplicación mas difundida para la criptografía de clave pública es el criptosistema ELGamal y su generalización.

cripto-scolnik-hecht

CRIPTOSISTEMAS Un criptosistema es una 5-tupla (P,C,K,E,D) que satisface las siguientes condiciones: 1. (P) es el conjunto finito de textos planos 2. (C) es el conjunto finito de textos cifrados 3. (K), el espacio de claves, es el conjunto finito de claves posibles 4. Para cada K ∈ (K), existe una regla de encripción ek ∈ E y una correspondiente regla de desencripción dk ∈ (D). !(C) y dk: (C)! !(P) son Cada ek: (P)! funciones tales que dk(ek(x))=x para cada texto plano x ∈( P)

cripto-scolnik-hecht

CRIPTOSISTEMA ELGAMAL - 1 El criptosistema desarrollado por ElGamal es nodeterministico (al contrario de RSA), dado que el texto cifrado (y) depende del texto plano (x) y de una clave aleatoria (k) elegida por el que encripta. Informalmente, consiste en “enmascarar” (x) multiplicándolo por un número (β βk) obteniendo el valor (y2=x.β βk) y acompañandolo con otro (y1=α αk). Los parámetros (α α, β) forman la clave pública. La clave privada está dada por otro número (a). Conociendo (a) se puede computar (β βk) a partir de (α αk), lo que permite recuperar (x=y2/ βk). El valor (k) puede ser fijo o una clave de sesión.

cripto-scolnik-hecht

CRIPTOSISTEMA ELGAMAL - 2 Sea p primo tal que el problema de logaritmo discreto en Zp sea clase NP, sea α ∈ Zp elemento primitivo y β ∈ Zp* Sean los conjuntos (P) = Zp*, (C) = Zp* x Zp* y (K) = {(p, α, a, β) : β ≡ αa (mod p) Los valores (p, α, β) son públicos y a privado. Encripción Para K=(p, α, a, β) y un nro aleatorio (secreto) k ∈ Zp-1, se define ek(x,k) = (y1, y2) donde y1= αk (mod p) e y2=x βk (mod p) Desencripción dk(y1, y2)=y2(y1a)-1 (mod p)

cripto-scolnik-hecht

CRIPTOSISTEMA ELGAMAL - 3 MICROEJEMPLO ELGAMAL: Sean p=2579, α=2, a=765 ∴ β=2765 mod 2579 = 949 Sea x=1299 y k=853 Encripción y1=2853 mod 2579=435; y2=1299(949853) mod 2579=2396 Desencripción x=2396 (435765)-1 mod 2579 = 1299

cripto-scolnik-hecht

LOGARITMO DISCRETO-1 CRIPTOANALISIS: ALGORITMOS DE RESOLUCION DE LOGARITMOS DISCRETOS

El problema de logaritmo discreto puede ser resuelto por búsqueda exhaustiva (fuerza bruta) en O(p) tiempo y O(1) espacio. Precomputando y almacenando pares (a, αa mod p) y ordenando por el segundo valor, basta localizar ese valor y obtener su log discreto a. Si p > 10150 esto es computacionalmente imposible en tiempo O(p) y en espacio O(p) .

cripto-scolnik-hecht

LOGARITMO DISCRETO-2 ALGORITMO SHANKS Complejidad O(√ √p) o algoritmo baby-step giant-step (ref. knuth-menezes) (obtener a= logα β (0 ≤ a ≤ p-2) dado β≡ αa mod p)

Dado m=√ √(p-1)  computar α mj mod p, (0 ≤ j ≤ m-1) √ Ordenar (j, α mj mod p) respecto al 2° valor (lista A) Computar β α -i mod p, (0 ≤ i ≤ m-1) Ordenar (i, β α -i mod p) respecto al 2° valor (lista B) Encontrar un par (j,y) ∈ A y (i,y) ∈ B (2° valor coincidente 6. Definir a= logα β =m j + i (mod p)

1. 2. 3. 4. 5.

cripto-scolnik-hecht

LOGARITMO DISCRETO-3 MICROEJEMPLO SHANKS: (Sea p=809, α =3, β=525 y se busca a=log3 525)

Se tiene m= √808 √  =29, entonces: α29 mod 809 = 99 Se computan las listas ordenadas A=(j, 99j mod 809) y B=(i, 525 (3i)-1 mod 809, donde (i,j) van desde 0 hasta 28 inclusives. Hay una sola coincidencia de 2° valor en A! !(10,644) y B! !(19,644) ∴ a= log3 525=29x10+19=309 (verifique!)

cripto-scolnik-hecht

LOGARITMO DISCRETO-4 ALGORITMO POHLIG-HELLMAN Complejidad O(∑ ∑1,k ci (ln n+√ √pi))

Sólo aplicable si p-1 fue factoreado y si contiene sólo factores “pequeños” (p-smooth). Sea n=p-1=∏ ∏1k pi ci , ei >0

(obtener a= logα β (0 ≤ a ≤ p-2) dado β≡ αa mod p) 1.

Sea q=pi y c=ci , Para (1 ≤ i ≤ k) iterar: 1. Calcular γi= α ni/q mod p , para (0 ≤ i ≤ q-1) 2. Asignar j=0 y βj= β 3. Mientras ( j ≤ c-1 ) iterar: 1. Calcular δ = βj n/qj+1 mod p 2. Hallar i tal que δ = γi

3. aj = i

2.

4. βj+1 = βj α -aj(q^j) mod p 5. j = j + 1 4. Obtener congruencia a ≡ (∑ ∑0c-1aiqi) mod p Aplicar TRC al sistema de k-congruencias y obtener a

cripto-scolnik-hecht

LOGARITMO DISCRETO-5 MICROEJEMPLO POHLIG-HELLMAN Sea α = 2, β = 18 y p = 29. Se busca a = log2 18 Entonces n = p-1 = 28 = 22 71 , Primero se calcula a mod 4 y luego a mod 7. Empezando, q=2 y c=2 γ0=1 , γ1= α28/2 mod 29=28 δ = β 28/2 mod 29 =28 ∴ a0=1 β1= β0 α -1 mod 29=9 y β1 28/4 mod 29=28 como γ1= 28 mod 29, a1=1 ∴ a ≡ (1.20+1.21) mod 4=3 mod 4 Terminando, q=7 y c=1 β 28/7 mod 29=184 mod 29 = 25 γ1= α28/7 mod 29=16 , γ2=24 , γ3=7 , γ4=25 y a0=4 ∴ a ≡ (4.70) mod 7=4 mod 7 Finalmente, aplicando TRC a las dos congruencias: a=11 mod 28, o sea a=11 es el log discreto

cripto-scolnik-hecht

LOGARITMO DISCRETO-6 ALGORITMO INDEX-CALCULUS (algoritmo 3.68 Menezes et al) (algoritmo 5.6 Stinson)

Es el algoritmo mas potente conocido para calcular logaritmos discretos. La técnica no se aplica a todos los grupos cíclicos (Zp*, F2m*, etc.) pero cuando fuese posible, normalmente, se resuelve en tiempo subexponencial O(eo(n)). Se basa en la selección de una base (S) irreducible en el grupo cíclico y obtener un sistema de relaciones lineales con logaritmos discretos en (S), el cual se resuelve obteniendo a.

cripto-scolnik-hecht

LOGARITMO DISCRETO-7 CRIPTOANALISIS (RESUMEN): ALGORITMOS DE RESOLUCION DE LOGARITMOS DISCRETOS

El criptoanálisis de criptosistemas basados en el problema de logaritmos discretos es fundamental porque constituye la base de seguridad de algoritmos críticos como el DSA (NIST), ECPKE, ECSA, HEPKE, etc.

cripto-scolnik-hecht

LOGARITMOS DISCRETOS EN CAMPOS FINITOS-1 Hasta este momento hemos tratado este problema dentro del grupo multiplicativo Zp*. El criptosistema ElGamal puede ser generalizado para ser aplicado en cualquier grupo cíclico finito G con una operación o arbitraria en el cual el problema logaritmo discreto sea clase NP. Dos categorías de grupos G que cumplen son: 1. El grupo multiplicativo del campo de Galois GF(pn) 2. El grupo de una curva elíptica o curva hiperelíptica definida sobre un campo finito

cripto-scolnik-hecht

LOGARITMOS DISCRETOS EN CAMPOS FINITOS-2 LOGARITMOS DISCRETOS EN (G, o) Sea G un grupo finito con operación de grupo o , α ∈ G, β ∈ H, donde H ={α αi : i ≥0} es el subgrupo generado por el elemento primitivo α. Objetivo: Encontrar el único entero a tal que (1 ≤ a |H|-1) y αa= β, donde αa = α o…o α (a veces) Este entero a es el log discreto logα β

≤

cripto-scolnik-hecht

CRIPTOSISTEMA ELGAMAL GENERALIZADO Sea G un grupo finito con operación de grupo o , α ∈ G, β ∈ H, donde H ={α αi : i ≥0} es el subgrupo generado por el elemento primitivo α y el problema log discreto en H sea clase NP. Sean los conjuntos (P) = G, (C) = G x G y (K) = {(G, α, a, β) : β = αa} Los valores (α α, β) son públicos y a privado. Encripción Para K=(G, α, a, β) y un nro aleatorio (secreto) k ∈ Z|H|, se define ek(x,k) = (y1, y2) donde y1= αk e y2=x o βk Desencripción dk(y1, y2)=y2 o (y1a)-1

cripto-scolnik-hecht

CURVAS ELIPTICAS-1 DEFINICION DE CURVA ELIPTICA Sea p>3 primo. La curva elíptica y2=x3+ax+b sobre Zp es el conjunto de soluciones (x,y) ∈ Zp x Zp a la congruencia: y2 ≡ x3+ax+b (mod p)

(*)

donde (a,b) ∈ Zp son constantes tales que 4a3+27b2 ≠ 0 (mod p) junto a un punto especial O , llamado el punto en el infinito (*)

con esta ecuación se puede definir una curva elíptica sobre cualquier campo GF(pn), para p>3 primo

cripto-scolnik-hecht

CURVAS ELIPTICAS-2 Se puede transformar la curva elíptica E en un grupo abeliano definiendo una operación adecuada sobre sus puntos. La operación se representa aditivamente y se define así: (recordar que todas las operaciones se ejecutan en Zp) P=(x1,y1) y Q=(x2,y2) son puntos en E. Si x2=x1 e y2=-y1, entonces P + Q = O Caso contrario, P + Q = (x3,y3) λ2-x1-x2 e y3= λ(x1-x3)-y1 y donde donde x3=λ λ=(y2-y1)/(x2-x1) si P≠ ≠Q o si P=Q λ=(3x12+a)/(2y1) finalmente se define P + O = O + P = P (para todo P) Ahora E es un grupo abeliano con elemento identidad O. Las inversas (para todo x,y) son simples de calcular: -(x,y)=(x, -y)

cripto-scolnik-hecht

CURVAS ELIPTICAS-3 MICROEJEMPLO DE CURVAS ELIPTICAS

Sea E la curva elíptica y2=x3+x+6 sobre Z11. Primero se determinan los puntos en E. Para todo x ∈ Z11 se computa x3+x+6 (mod 11) y luego se trata de resolver y2 ≡ x3+x+6 (mod 11). Para cada z=x3+x+6 (mod 11) se testea primero si z ∈ RC(11) (residuo cuadrático modulo 11, calcular símbolo de Jacobi [Legendre]). Dado que 11≡ ≡3(mod 4) y existe una fórmula explícita para raíces cuadradas modulares de residuos cuadráticos modulo p de esta clase de primos, se aplica: ±z(11+1)/4 mod 11 = ±z3 mod 11 Los resultados se muestran en la placa siguiente, observar que y2=11-y1.

cripto-scolnik-hecht

CURVAS ELIPTICAS-4 x

z=x3 + x + 6 (mod 11)

z ∈ RC(11)?

0

6

No

1

8

No

2

5

Si

4, 7

3

3

Si

5, 6

4

8

No

5

4

Si

6

8

No

7

4

Si

2, 9

8

9

Si

3, 8

9

7

No

10

4

Si

y1-2

2, 9

2, 9

cripto-scolnik-hecht

CURVAS ELIPTICAS-5 Se han hallado 12 elementos no nulos de E. Por ejemplo, de la primer fila solución se deducen 2 puntos (x,y): (2,4) y (2,7). Por lo tanto E contiene 13 elementos, doce no nulos y el punto en el infinto O. Como todo grupo de orden primo es cíclico, se deduce que E es isomorfo a Z13 y todo punto no nulo (punto en el infinito O) es un generador de E. Supongamos que se toma como generador a α=(2,7). Se pueden calcular entonces las “potencias” de α (que se escriben como múltiplos dada la operación suma). P. Ej: computar 2 α=(2,7)+(2,7) λ = (3.22+1) (2.7)-1 (mod 11) = 2 . 3-1 (mod 11) =8 x3 = 82 - 2 – 2 (mod 11) = 5 y3 = 8 (2-5) – 7 (mod 11) = 2 ∴ 2 α=(5, 2)

cripto-scolnik-hecht

CURVAS ELIPTICAS-6 De esta forma se obtienen los 12 elementos no nulos de E, probando que (2, 7) es un generador: α=(2, 7) 2 α=(5, 2) 3 α=(8, 3) 4 α=(10, 2) 5 α=(3, 6) 6 α=(7, 9) 7 α=(7, 2) 8 α=(3, 5) 9 α=(10, 9) 10 α=(8, 8) 11 α=(5, 9) 12 α=(2, 4) Una curva elíptica E definida sobre Zp (p>3 primo) tiene aproximadamente p puntos sobre ella. Mas precisamente su número #E será (Hasse): p+1-2√ √p ≤ #E ≤ p+1+2√ √p También se puede computar exactamente #E por medio del algoritmo de Schoof de complejidad O((log p)3) Una vez computado E se necesita hallar un subgrupo cíclico H en el cual el problema del logaritmo discreto sea clase

NP o NPNP-Completo a fin de

criptosistema ELGAMAL generalizado.

poder aplicar el

cripto-scolnik-hecht

CURVAS ELIPTICAS-7 TEOREMA: Sea E una curva elíptica definida sobre Zp donde p>3 primo, entonces existen enteros n1 y n2 tales que E es isomorfo a Zn1 x Zn2 Además n2|n1 y n2|(p-1) Por lo tanto si se pueden computar n1 y n2 se deduce que E tiene un subgrupo cíclico isomorfo a Zn1 el que puede ser usado en el criptosistema ELGAMAL generalizado. Notar que si n2=1, E es un grupo cíclico. Además si #E es primo o el producto de dos primos, E es un grupo cíclico con índice de grupo cíclico.

cripto-scolnik-hecht

CRIPTOSISTEMA DE CURVAS ELIPTICAS MENEZES-VANSTONE-ELGAMAL Sea E una curva elíptica definida sobre Zp (p>3 primo), tal que contiene un subgrupo cíclico H, para el cual el problema log discreto sea al menos clase NP. Sean los conjuntos (P) = Zp*, (C) = E x Zp* x Zp* y (K) = {(E, α, a, β) : β = a α} donde α ∈ E Los valores (p, α, β) son públicos y a privado. Encripción Para K=(E, α, a, β) y un nro aleatorio (secreto) k ∈ Z|H|, y para x=(x1, x2) ∈ Zp* x Zp* se define donde: ek(x,k) = (y0, y1, y2) y0=k α (c1,c2)=k β y1=c1x1 mod p y2= c2x2 mod p Desencripción Para un cifrado y= (y0, y1, y2) se define dk(y)= (y1c1-1 mod p , y2c2-1 mod p) donde ay0=(c1, c2)

cripto-scolnik-hecht

CRIPTOSISTEMA DE CURVAS ELIPTICAS MENEZES-VANSTONE-ELGAMAL MICROEJEMPLO - 1 Usando el ejemplo de curva elíptica anteriormente desarrollado, supongamos que α=(2,7) y que el “exponente” secreto sea a=7, de manera que: β=7α α=(7,2) Supongamos que se desea encriptar x=(x1, x2)=(9, 1) y se elije la clave aleatoria k=6. Observar que x ∉ E. Se computa: 1. yo=k α=6(2, 7)=(7,9) 2. k β=6(7,2)=(8,3) o sea c1=8 y c2=3 3. y1=c1x1 mod p=8.9 mod 11=6 4. y2=c2x2 mod p=3.1 mod 11=3 y el cifrado será y= (y0, y1, y2) =((7,9), 6, 3)

cripto-scolnik-hecht

CRIPTOSISTEMA DE CURVAS ELIPTICAS MENEZES-VANSTONE-ELGAMAL MICROEJEMPLO - 2 El cifrado es y= (y0, y1, y2) =((7,9), 6, 3) Para desencriptar, se computa: 1. (c1, c2) = a yo = 7 (7, 9) = (8, 3) 2. x = (y1c1-1 mod p , y2c2-1 mod p)= = (6 . 8-1 mod 11, 3 . 3-1 mod 11)= = (6 . 7 mod 11, 3 . 4 mod 11)= = (9, 1) que era el texto plano.

cripto-scolnik-hecht

CRIPTOSISTEMAS DE CURVAS ELIPTICAS CRIPTOANALISIS DE CURVAS ELIPTICAS Los algoritmos de Shanks y Pohlig-Hellman se aplican sobre el problema de logaritmo discreto de curvas elípticas. No se conoce ninguna adaptación del algoritmo index-calculus para atacar este problema en curvas elípticas. Sin embargo existe un metodo que explota ciertos isomorfismos entre curvas elípticas y otros campos finitos y que permite atacar eficientemente a cierta clase de curvas elípticas (las curvas supersingulares) (algoritmo Menezes-OkamotoVanstone). Dejando de lado esta clase de curvas elípticas, aquellas que posean un subgrupo cíclico H de orden 2160 proveen suficiente seguridad, siempre que ese orden-1 posea al menos un factor primo grande que bloquee el ataque Pohlig-Hellman.

cripto-scolnik-hecht

CONCLUSION