Trabajo sobre criptografia

Etimológicamente criptología quiere decir escritura secreta. Actualmente tiene el significado de ciencia de la comunicación segura, su objetivo es que dos partes puedan intercambiar información sin que una tercera parte no autorizada, a pesar de que capte los datos, sea capaz de descifrar la información. La criptografía actúa mediante criptosistemas; un criptosistema o sistema cifrado es un sistema que permite cifrar los mensajes de tal forma que una persona no autorizada no pueda descifrar el mensaje. La criptografía es la ciencia de diseñar criptosistemas.

El criptoanálisis trata de romper los criptosistemas para apoderarse de la información cifrada.

Criptosistemas Clásicos(Simétricos)

Un criptosistema clásico está formado por un quinteto de conjuntos (P, C, K, E, D), donde:

P es un conjunto finito cuyos elementos se llaman ?textos claros? (plain text), estos serían los mensajes que se quieren enviar tal cual.

C es un conjunto finito cuyos elementos se llaman ?criptotextos?, esto sería lo que resulta una vez que la información se cifra.

K es un conjunto finito cuyos elementos se llaman ?claves? (keys).

E = {E_k / k pertenece K} donde E_k : P --> C, E_k --> transformaciones criptograficas

D = {D_k / k pertenece K} donde D_k : C --> P, cumpliendo que D_k(E_k(x)) = x para todo x peteneciente a P.

Esto se basa en que las 2 partes se ponen de acuerdo en la clave y en mantenerla secreta.

La clave k da las transformaciones E_k y D_k.

Un criptoanalista intercepta c pero como no conoce la clave k no es capaz de recuperar p. Cualquier persona que conozca la clave k puede descifrar el mensaje. La clave debe intercambiarse por un canal seguro y además el conjunto de las claves debe ser enorme.

Este criptosistema se llama simétrico ya que el conocimiento de la clave permite las operaciones de cifrar y descifrar.

a --> 0
b --> 1
.
.
z --> 26
z₂₇ --> Alfabeto

1-P = C = K = Z₂₇
Para cada k perteneciente a Z₂₇

E_k(x) := x + k (mod 27) para x perteneciente a Z₂₇
D_k(x) := x - k (mod 27) para x perteneciente a Z₂₇

k=3

E₃(CESAR) = FHVDQ
E₃(ZAMORA)=CDORUD

Este sistema se conoce como cifra de César. Como sólo hay 27 posibles claves se prueban todas las posibles claves hasta que se encuentra la correcta.

E_d(x) := d(x) para todo x perteneciente a Z₂₇
D_d(x) := d^-1(x) para todo x perteneciente a Z₂₇
|K| = 27! > 10²⁸

El que |K| sea tan grande implica que este criptosistema no se pueda analizar a lo bruto.

Este criptosistema se llama criptosistema de sustitución.

Principio de Kerchhoff: El criptoanalista conoce el criptosistema que se usa.

Este criptosistema es fácilmente analizable. Su debilidad es el análisis de frecuencias, esto es debido a la redundancia inherente de los lenguajes naturales. Cada lenguaje natural tiene una distribución de frecuencias del alfabeto que es característica; por

ejemplo, en castellano:

e --> 14.75 %
a --> 13.25 %

Cualquier idioma tiene una distribución de frecuencias característica.

Se compara la distribución de frecuencias del texto claro con la distribución de frecuencias de los símbolos del criptotexto.

También se puede hacer una análisis de frecuencias de pares de letras consecutivas, de ternas de letras...

Estos dos criptosistemas son criptosistemas de sustitución monoalfabética, la transformación sustituye una letra por otra, pero siempre es la misma.

Criptosistema afín.

K = {(a,b) perteneciente a Z₂₇ x Z₂₇ / mcd (a,27) = 1}

E_k(x) := ax+b (mod 27) para todo x perteneciente a Z₂₇
D_k(x) := a^-1(x-b) (mod 27) para todo x perteneciente a Z₂₇

a se toma primo con 27 para que tenga inverso en Z₂₇. En este caso |K| = 27 · 29. Este es un subsistema del caso anterior.

Se diseñaron los sistemas polialfabéticos en los que cada símbolo del alfabeto se sustituye por otro pero dependiendo de la posición de la letra se cambia por una letra u otra, así analizando la distribución de símbolos en el criptotexto no permite descifrar el mensaje.

Criptosistemas de sustitución monoalfabética -> Análisis de frecuencias

Criptosistemas Polialfabéticos:

E_k(x₁....x_m) = (x₁+k₁, x₂+k₂, ....,x_m+k_m) ( mod 27)
D_k(x₁....x_m) = (x₁-k₁, x₂-k₂, ....,x_m-k_m) ( mod 27)

Consideramos una sucesión periódica de desplazamientos. El primer símbolo se desplaza k₁ posiciones, el segundo k₂ posiciones y así hasta el último y luego repetimos el proceso para los siguiente m símbolos.

MENSAJE SECRETO se cifraría como:

El criptotexto ya no se puede analizar mediante el análisis de frecuencias. Esta cifra perduró durante siglos, hasta que en el s. XIX se descifró. Se debe aplicar el Test de Kasiski: En los textos hay palabras que se repiten a menudo y si la distancia entre partes iguales del texto es múltiplo de m entonces se van a cifrar de la misma forma. Se buscan estas coincidencias a lo largo del texto. Al conocer la longitud de la palabra se puede aplicar análisis de frecuencias sobre los símbolos en las posiciones congruentes módulo m.

Shanonn demostró que se puede encontrar un criptosistema incondicionalmente seguro, esto es aunque el criptoanalista disponga de infinitos recursos de computación y de infinito tiempo no va a poder descifrar el criptosistema.

P = C = K = (Z₂)^m

k perteneciente a Z₂^m , k = (k₁, k₂,?.k_m)

E_k(x₁....x_m) = (x₁+k₁, x₂+k₂,?.x_m+k_m) (mod 2)

D_k(y₁....y_m) = (y₁+k₁, y₂+k₂,?.y_m+k_m) (mod 2)

Este criptosistema tiene seguridad incondicional. En este caso la longitud de la clave es igual a la longitud del texto.

Si generamos una clave aleatoria todas las sucesiones de m bits son igualmente probables. Este sistema se denomina one-time pad; la clave sólo se usa una vez. Este sistema en la práctica sirve de poco ya que genero una clave de igual tamaño que lo que queremos transmitir, pero en criptosistemas simétricos ambas partes deben conocer la clave y debe haber un canal seguro por el que se puedan transmitir los m bits de la clave, pero si podemos hacer esto entonces podemos transmitir los m bits del texto sin cifrar por este canal seguro.

DES (Data Encrytion Standart):

Fue diseñado en USA(70) con la idea de que fuese un estándar y fuese usado por las empresas en las transacciones. Fue criticado ya que usa una clave secreta de 64 bits, pero de éstos sólo 56 son la clave ya que hay 8 bits de control (corrección de errores).Este sistema no ofrecía seguridad suficiente. El espacio de claves es enorme pero con ordenadores potentes se puede encontrar la clave.

AES (Advanced Encryption Standart):

Este criptosistema es mucho más avanzado que el anterior y está en fase de proyecto.

Todos los criptosistemas clásicos se han ido rompiendo.

Problemas fundamentales de los criptosistemas clásicos:

- El problema de la seguridad (Shanonn 1949, Bell System Journal). Shanonn dio una definición de lo que es la seguridad de un criptosistema; definió la seguridad incondicional, ésta se establece cuando un criptosistema es seguro con independencia de los medios disponibles (infinita potencia de cálculo). Si un criptosistema es incondicionalmente seguro no se puede romper. Se demostró la existencia de criptosistemas de seguridad incondicional (cifrar de Vernann) aunque d.p.v práctico no tienen utilidad. Los criptosistemas más modernos se basan en la seguridad computacional. La idea es considerar un criptosistema computacionalmente seguro cuando aunque haya un algoritmo que rompa el sistema éste requiera un tiempo de computación tan grande que sea inviable llevarlo a la práctica.

- El problema del manejo y distribución de claves. Los criptosistemas clásicos son de clave secreta, cualquiera que conozca la clave puede descifrar la información. Estos criptosistemas son vulnerables aunque no se sepa como criptoanalizarlos si se intercepta la clave secreta.

- El problema de la autentificación. Los criptosistemas convencionales no proporcionan ningún método para que el receptor del mensaje pueda tener la seguridad de que quien envió el mensaje es quien debería haberlo enviado y no una tercera parte. El mensaje podría ser alterado y no se podría saber si esta situación se ha producido.

Criptografía de Clave Pública

En un criptosistema clásico hay un espacio de claves y para cada clave k hay una función E_k de encriptación y otra D_k de desencriptación. Cualquier persona que conozca k conoce E_k y D_k; pero además si se conoce E_k se conoce D_k y viceversa; así k, E_k y D_k deben ser secretas.

En 1976 se trató de buscar un criptosistema en el cual el conocimiento de cómo encriptar no implicase el conocimiento de cómo desencriptar. Esto permite usar un criptosistema en el cual E_k fuese pública pero no fuese factible calcula D_k. E_k y D_k deben ser inversas pero si uno conoce E_k no se debe poder obtener D_k. Esto apareció por primera vez en un artículo de W. Diffie y M. Hellman (New direction cryptography).

Estos criptosistemas se basan en la función de dirección única. Una función de dirección única:
f

es una función tal que es ?fácil? d.p.v computacional calcular f(x) para todo x perteneciente a X pero que por el contrario es ?difícil? para la mayoría de los y pertenecientes a Y encontrar un x perteneciente a X / f(x) = y (suponiendo que exista).

Por el momento no se ha demostrado la existencia de funciones de dirección única pero si se conocen funciones que se piensa que son de dirección única y que se usan en la práctica ya que de momento nadie ha sido capaz de invertir las funciones.

Si E_k fuese de dirección única ni siquiera el destinatario sería capaz de desencriptar .

Una de las primeras y presumible función de dirección única fue:

f(x), Z_p(x)
p = 2⁶⁴ - 59
f(x) = x^2elevado(24) + 17 + a₁x^{2elevado(24)+3} + a₁x³ + a₃x² + a₄x + a₅
a_i = enteros de 19 digitos.

En un criptosistema no servirían las funciones de dirección única. Se usa una variante que son las funciones de dirección única con trampa (trapdoor), que son funciones en las que es ?fácil? calcular f(x), es fácil calcular x / f(x) = y dado y es posible revelar un algoritmo eficiente para calcular f ?hacia delante? sin que el conocimiento del mismo proporcione un algoritmo eficiente para calcular f ?hacia atrás?. Con esta función el destinatario ya puede desencriptar la información. Esto llevó al concepto de criptosistema de clave pública en el que hay una clave pública que conoce todo el mundo y otra secreta para desencriptar que sólo conoce el destinatario, con lo que ya no hay que intercambiar la clave secreta.

Cada usuario del criptosistema se construye una función de encriptación E_u y una función de desencriptación D_u que cumplen las siguientes propiedades:

CP2- Existen algoritmos eficientes para calcular E_u(x) y D_u(x) para todo x.

CP3- Existe una clave secreta (conocida sólo por u) que permite obtener rápidamente

D_ua partir de E_u pero el conocimiento de E_u no hace factible hallar un algoritmo D_u^* que ratifica D_u^*(E_u(x)) = x para todo x.

Cada usuario u hace público el algoritmo para calcular E_u, los E_u se ponen en un directorio que es público. El algoritmo que permite calcular D_u es mantenido en secreto por u.

Si A quiere enviar un mensaje m a B, A busca E_B en el directorio y calcula E_B(m), A envía c = E_B(m) y B calcula D_B(E_B(m)). Un criptoanalista conoce c = E_B(m).

CP4- E_u(D_u(x)) = x

CP5- No es factible encontrar a partir de E_u una función D_u^* tal que E_u(D_u^*(x)) = x

Definición: Una función H: X ->Y con |X| = l, |Y| = k y k mucho menor que l se llama ?función hash? si es fácil calcular H(x) para todo x perteneciente a X y cumple:

1) No es factible encontrar dos valores distintos x != x' tales que H(x) = H(x') ("H es resistente a la colisión")
2) Dada y perteneciente a Im H no es factible encontrar x perteneciente a X tal que H(x) = y ("H es resistente a la preimagen")

A envía m a B firmado. A calcula H = H(m) y envía a B el par (m,H(m)). B aplica H a m y obtiene H(m), si coincide con H sabe que el mensaje es auténtico suponiendo que H proviene realmente de A.

A envía m a B firmado, A calcula H = H(m). A calcula E_BD_A(H) y envía a B(m, E_BD_A(H)) (se encripta la firma). B calcula E_AD_B(E_BD_A(H)) = E_AD_A(H) = H. A continuación B comprueba que H(m) = H.

Al aplicar EA la única forma de obtener la firma desencriptada es que previamente haya sido encriptada con Da que sólo A conoce.

Si A negase haber enviado el mensaje B podría ir a una 3ª parte y demostrar que A ha enviado el mensaje (sólo A ha podido utilizar D_A).

El Criptosistema RSA

Riverest-Shamir-Adleman: Criptosistema RSA (A method for obtaining digital signatures and public key cryptosystems- Comunications of the ACM 1978)

Se piensa que el criptosistema RSA es tan seguro como lo era en 1978.

?Exponenciación modular con exponente y módulos fijos?

?Extracción de raíces módulo n?: Dados y, m, n perteneciente a Z⁺ hallar (en caso de que exista) un x tal que x^m sea equivalente a y (mod n)

Es fácil calcular las imágenes pero la extracción de raíces módulo n no es factible computacionalmente a menos que se conozca una información adicional, que si se conoce entonces es fácil volver hacia atrás; esto se logra conociendo la factorización de m en números primos ya que es fácil obtener las raíces m-ésimas.

Dados m y n nadie conoce un algoritmo eficiente para la extracción de raíces módulo n pero no se ha demostrado que este algoritmo no exista.

RSA = (P, C, K, E, D) donde:

P = C = Z_n, con n = pq p y q primos

K = {(n, e, d)/ ed equivalente a 1 (mod þ(n))}

Para cada k = (n, e, d)

E_k(x) : = x^e (mod n) para todo x perteneciente a Z_n

D_k(x) : = x^d (mod n) para todo x perteneciente a Z_n

E_k(x) : = x^e (mod n) para todo x perteneciente a Z_n

þ(n) = número de enteros positivos menores que n y primos con n.

Z_n = {0, 1, ..., n-1}

En Z_n sólo tienen inverso los x tales que mcd(x,n) = 1

Z_n^* = {x perteneciente a Z_n / mcd(x,n) = 1} es un grupo finito

En el caso del sistema RSA:

þ(n) = þ(pq) = þ(p)þ(q) = (p-1)(q-1)

| Z_n^*| = p-1 si p es primo

Para todo x perteneciente a Z_nD_k(E_k(x)) = x

Teorema (Lagrange): Si G es un grupo finito y x pertenece a G, entonces x^|G| = 1

Corolario (Euler): Si x pertenece a Z⁺, mcd(x,n) = 1, entonces x^þ(n) equivalente a 1 (mod n)

Corolario (Teorema pequeño de Fermat): Si p es primo, x^p equivalente a x (mod p)

x^p-1 equivalente a 1 (mod p)

x^p equivalente a x (mod p)

x perteneciente a Z_n^*

E_k(x) equivalente a x^e (mod n)

D_k(E_k(x)) equivalente a (x^e)^d ( (mod n) equivalente a x^ed (mod n) equivalente a x^tþ(n)+1 (mod n) equivalente a

(x^þ(n))^t x (mod n) equivalente a x (mod n)

ed equivalente a 1 (mod þ(n)) <=> ed = tþ(n) +1

El par (n,e) constituye la clave pública mientras que d, p y q se mantienen en secreto.

Cada usuario u elige dos primos distintos grandes (512 bits = 154 dígitos decimales) p_u y q_u y calcula n_u = p_u * q_u (n recibe el nombre de módulo).
Se calcula þ(n_u)) = (p_u- 1)(q_u - 1) = |Z^*_{nsubindice(u)}| . u elige un entero e_u tal que 1 < e_u < þ(n_u) y mcd(e_u,þ(n_u) = 1.
A continuacion se calcula el inverso de e_u enZ^*_þ(nu), es decir, se calcula el entero d_u tal que 1 < d_u < þ(n_u) y e_ud_u equivalente a 1 (mod þ(n_u))

Los números más difíciles de factorizar son los que se factorizan como 2 primos que tienen el mismo número de dígitos.

- Factorización de enteros.

Al usar el RSA queremos que otra parte no rompa el sistema, cualquier persona que conozca la descomposición de un en factores primos puede desencriptar, esto lleva al problema de la factorización de enteros; nadie conoce un método eficiente para factorizar enteros generales.

A envía a B x^eB (mod n_B)

B calcula (x^eB )^dB (mod n_B) = x

Un criptoanalista tiene x^eB (mod n_B), debe hallar la raíz e_Bde x, para esto debe conocer þ(n_B) y para ello debe conocer q_B y d_B.

n = pq = 47·59 = 2773

1 = 257·1225 - 118·2668

257·1225 equivalente a 1 (mod 2668)

Clave pública (2773,1225)

Clave privada (2773,257)

x¹²²⁵ (mod 2773)

Exponenciación binaria:

1225 = (10011001001)₂ = 2¹⁰ + 2⁷ + 2⁶ + 2³ + 2⁰

x¹²²⁵ = x^{(2e10+2e7+2e6+2e3+2e0)} = x^2e10 x^2e7x^2e5 x^2e3 x

c = elevado al cuadrado

(((((((((x²)²)²·x)²·x)²)²)²·x)²)²)²)·x (mod 2773)

Haciendo esto calculamos directamente x¹²²⁵ (mod 2773); hacemos esto con sólo 14 multiplicaciones.

Vamos a ver que se cumplen las condiciones CP1...CP5

- D y E se calculan mediante algoritmos factibles ya que el algoritmo de exponenciación binaria es eficiente. CP2 se cumple.

- CP3 permite asegurar que el RSA es seguro. E_ues fácil de calcular pero obtener D_u a partir de E_u no es factible. Existe la conjetura de que criptoanalizar RSA es equivalente a poder factorizar n. Lo máximo que se ha llegado a factorizar son números de 130 dígitos. Los mejores algoritmos de factorización que se conocen son subexponenciales pero aún así el tiempo de computación es grande. Existe una creencia de que el RSA requiere la factorización de n y esto es difícil.

x --> x¹²²⁵(mod 2773) = c

c --> c²⁵⁷(mod 2773)

257 = (100000001)₂

c²⁵⁷ = (((((((c²)²)²)²)²)²)²)²)c (mod 2773)

- Manejo y distribución de claves. Este sistema de clave pública resuelve este problema inmediatamente ya que 2 partes no tienen necesidad de intercambiarse clave alguna. Un usuario elige los primos y el exponente de Exponenciación y hace pública una clave pero la clave privada no se intercambia con nadie.

- Identificación. Los criptosistemas clásicos no permiten saber que el mensaje proviene de quien realmente dice. Suponiendo que el RSA sea seguro (CP1 ... CP5) se resuelve este problema.

- Seguridad. Este problema está encerrado en la condición CP3. No está demostrado que el RSA es seguro, existen una serie de hechos matemáticos que hacen pensar que el RSA es seguro. La seguridad del RSA se basa en la creencia de que la función de encriptación es una función de dirección única con trampa.

El que RSA sea seguro se basa en 2 premisas:

a) Se cree que romper RSA es equivalente a saber factorizar n. Esta sin demostrar que no puede existir otra forma de romper RSA que no pase por factorizar n. No está demostrado que romper RSA sea equivalente a factorizar n.

b) Si aceptamos la premisa anterior de que romper RSA pasa por factorizar n tenemos que la factorización de n para tamaños grandes de n es un problema intratable d.p.v. computacional.

Se ha demostrado que factorizar el criptosistema de Rabin, que es parecido al RSA, es equivalente a factorizar el módulo. La factorización de enteros equivale a estudiar RSA.

La teoría de la complejidad computacional trata de clasificar los problemas computacionales de acuerdo con su complejidad, esto se corresponde con la idea intuitiva de complejidad.

NFSnet: orca.st.usm.edu/~cwcurry/nfs/nfs.html

No sirve para factorizar números tan grandes como el NFS pero tiene ciertas ventajas para ciertos factores. El tiempo del NFS depende del tamaño del número, no de los factores que lo componen; en cambio ECM encuentra más fácilmente los factores si éstos son más pequeños.

Para romper RSA es mejor el NFS ya que ECM no puede con números de más de 50 dígitos.

www.loira.fr/~zimmerma/records/ecmnet.html

www.cerios.purdme.edu/ssw/cum//index.html

www.npac.sgr.edu/factoring.html

www.utm.edu/research/primes

Aquí se pueden encontrar los primos más grandes que se conocen.

P. Ribenbaim: ?The new book of Prime number records?. Springer- Verlay (1995)

1984: Yates ?Sinkes of the Titanics?

Para ver si un número de esta forma es primo o no se aplica el test de Lucas-Lehmer.

1996 --> M_1398269 (P 90 MHZ) (J Aeannengand, Woltman, GIMPS) (420921 dígitos decimales)

1997 --> M_2976221 (P 100 MHz)

1998 --> M_3021377 (P 200 MHz) (909526 dígitos decimales)

1999 --> M_69672593 (P 350 MHz) (Hajratwala) ( 2098960 dígitos decimales)

Direcciones sobre criptografía:

www.comterpone.com (Bruce Schneier : Cryptogam)

www.certicon.com (Criptografía de curvas elípticas)

www.iec.csic.es/criptonomicon

theory.lcs.mit.edu/~rivest/crypto-security.html

UBASIC (Yuji Kida) --> MPQS (Multiple Polynomial Quadratic Sieve)

http://150.93.96.124/~kida

ftp://rkmath.rikkyo.ac.jp/pub/ubim

www.indigo.ie/~rmscott

MIRALCL ( Multiple Precission Integer and Rational C Library)

www.panillac.inria.fr/algo/morain

www.lix.polytechnique.fr/morain/Prgms/eccp.english.html

www.reality.sgi.com/chango/tech/math/prime/merdigit/index.html

?Problema del logaritmo discreto?: Dados a, n, y encontrar, si existe, un entero x tal que a^x equivalente a y (mod n).

Se piensa que esta función es de dirección única. Esto se usa para alamacenar passwords.

Sea G un grupo finito y g perteneciente a G. Sea <g> el subgrupo de G generado por g. Problema del logaritmo discreto:

Dado y perteneciente a <g> encontrar un entero x tal que g^x = y

No hay algoritmos eficientes que premitan calcular esto.

DIFFIE HELLMAN EXCHANGE:

Se usa el logaritmo discreto para intercambiar claves entre usuarios. La clave es pequeña, así no hay problema en transmitirla, no ocurre esto con los mensajes. La principal desventaja de los criptosistemas de clave pública frente a los de clave privada es la eficiencia, los criptosistemas de clave pública son varios órdenes de magnitud más lentos. El DES, p. ej., permite codificar y descodificar a velocidades enormes, si esto se hiciese con el RSA se necesitaría mucho más tiempo de transmisión y más espacio de almacenamiento. En algunos casos conviene usar un criptosistema de clave privada pero realizando el intercambio de clves mediante un criptisistema de clave pública. Se propuso utilizar el logaritmo discreto para hacer esto.

Sea F_p = Z_p = {0, 1, ... p-1 }

F_p^*= F_p - {0} = {1,2, ... p-1}

F_p^* es un grupo para la multiplicación y es, de hecho, un grupo cíclico (exite g perteneciente a F_p* tal que F_p^* = <g>).

?Dados un generador g perteneciente F_p* y dado y perteneciente a F_p*, hallar x perteneciente a F_p* / g^x = y ?

El canal el público

A <----------------------> E

A y B se ponen de acuerdo en un primo grande p (512 bits), así O conoce p, además, se ponen de acuerdo en un elemento g pertenece a F_p*.