Criptología


Introducción a la Criptología

Ejemplo de un sistema de clave pública basado en el Logaritmo Discreto

Protocolos criptográficos

Aplicaciones prácticas
 

Presentación sobre Criptología (PDF) en el I Seminario "Informática, Ciencia y Tecnología" (2005) -- E. U. Informática de Segovia

Volver a Investigación


 

Criptología


La Criptología es la rama de la ciencia que trata de la protección de la información confidencial o secreta contra
el acceso a la misma de personas no autorizadas. Consta a su vez de dos disciplinas aparentemente opuesta, pero
en realidad complementarias: la Criptografía, que diseña métodos para cifrar (o enmascarar la información), y el
Criptoanálisis, que trata de romper los métodos anteriores para conseguir la información original.

El esquema fundamental de un proceso de cifrado/descifrado es el siguiente: Un emisor A quiere emitir un mensaje
m (llamado también texto claro) a un receptor B con la posibilidad de que un enemigo o persona no autorizada C
pueda interceptarlo y apoderarse de dicha información. En ese caso, en vez de emitir A el texto claro, emite un
criptograma, que es el resultado de aplicar a m un procedimiento de cifrado controlado por una clave de cifrado.
Al ser B una persona autorizada, conoce la clave de descifrado y puede recuperar el mensaje, y el objetivo es que
C no pueda obtener esa información (desencriptación) sin el conocimiento de dicha clave.
Un buen sistema criptográfico es aquél en el que los algoritmos de cifrado/descifrado son sencillos conocida la clave,
pero que resulte imposible (o en su defecto muy difícil) la desencriptación sin conocer la misma.

En general, hay dos grandes tipos de sistemas criptográficos:
 

    Sistemas de clave privada: en los cuales sólo hay involucrados un emisor y un receptor, que comparten
        una misma clave para cifrar y para descifrar, la cual debe permanecer en secreto (por ejemplo, sucede
        en las comunicaciones militares o en la protección de ficheros de ordenador).

    Sistemas de clave pública: en los cuales hay involucrados muchos usuarios que pueden comunicarse entre sí,
        cada uno de los cuales tiene una clave privada (mantenida en secreto) para poder leer los mensajes que van
        dirigidos a él, y una clave pública (conocida por todos los usuarios) para que cualquiera pueda enviarle un
        mensaje cifrado (este es el caso de redes de usuarios informáticos, por ejemplo).
 

La seguridad de los estos sistemas está basada hoy en día, y debido al gran avance en las posibilidades computacionales
de los ordenadores actuales, en problemas matemáticos de gran complejidad computacional. La idea general es la utilización
de las llamadas funciones trampa, que consisten en funciones matemáticas cuyo cálculo directo es sencillo, pero en las que
el cálculo de la función inversa es muy complejo, es decir, involucra un elevado número (p.e. exponencial) de operaciones.
A modo de ejemplo, consideramos el producto de números primos

(p,q) --> m=p.q

La operación anterior es muy rápida, pero la operación inversa, es decir, dado m hallar p y q, es (en general) de complejidad
exponencial en la longitud de m. Por ejemplo, si m tiene 100 cifras, el número medio de operaciones requeridas para factorizar
m sería 1050 operaciones, con lo que un ordenador que haga 1 millón de operaciones por segundo tardaría ¡más de 1036 años!
En este caso, m sería utilizado como clave pública, mientras que los números primos (p,q) serían la clave privada.

Hay varios tipos de seguridad, según el problema computacional en que nos basemos:

    Seguridad incondicional : cuando el sistema es seguro frente a un atacante con tiempo y recursos computacionales ilimitados

        (por ejemplo, el cifrado de Vernam, basado en secuencias binarias aleatorias).     Seguridad computacional : cuando el sistema es seguro frente a un atacante con tiempo y recursos computacionales limitados         (por ejemplo, el sistema RSA, basado en números primos).     Seguridad probable : cuando el sistema no puede demostrarse seguro, pero en la práctica aún no ha sido violado         (por ejemplo, el sistema DES, basado en "cajas" no lineales).     Seguridad condicional : cuando el sistema es seguro en tanto el enemigo carece de medios para atacarlo         (por ejemplo, métodos clásicos de substitución, vulnerables a un análisis de frecuencias). He aquí varios ejemplos clásicos de sistemas criptográficos sencillos con su correspondiente criptoanálisis:
  (1):        Cifrado de César (siglo I a.C.): toma una letra como clave (por ejemplo la C) y la suma (módulo 26, suponiendo
                que sea éste el número de letras del alfabeto) a todas las letras del mensaje; por ejemplo

VENI VIDI VICI + CCCC CCCC CCCC = AGPL ALFL ALEL

                El descifrado consiste en restar la clave a todas las letras del mensaje recibido.
                Una vez que se conoce el método de cifrado, la desencriptación en muy sencilla incluso a mano, pues en un rato
                podemos ir probando con la totalidad de las posibles claves, hasta dar con un mensaje que tenga sentido.

(2):        Cifrado de Vigenère (1586): es igual al anterior pero ahora la clave que se suma en una palabra de longitud k;
                por ejemplo, tomando como clave LOUP (lobo, en francés) funcionaría de la siguiente manera

PARIS VAUT BIEN UNE MESSE + LOUPL OUPL OUPL OUP LOUPL = AOLXD JUJE PCTY IHT XSMHP

                De la misma manera, el descifrado consiste en restar la palabra clave al mensaje recibido.
                Ahora el número de claves para ensayar es mucho más elevado, pero el método de Kasiski, basado en analizar las
                frecuencias en que estadísticamente aparecen letras y combinaciones de letras en cada idioma permiten determinar
                la longitud k de la clave, y entonces el problema se reduce a resolver k criptogramas sencillos del tipo César.

(3):        Cifrado de Vernam (1911): consiste primeramente en traducir el mensaje a código binario para sumarle luego otra
                sucesión de ceros y unos elegida al azar. El descifrado consiste en volver a sumar la misma clave, puesto que en
                código binario sumar y restar es la misma operación. Este método fue usado durante la segunda guerra mundial
                por espías de distintos bandos con la recomendación de utilizarla una sola vez. Durante mucho tiempo se creyó que
                este sistema era seguro, pero fue Shannon en 1949 el que primero dió una prueba teórica en términos probabilísticos.
 


Por último, según el método de cifrado, los sistemas criptográficos se dividen en dos tipos:
 

    Cifrado en flujo: cuando el mensaje se emite y se cifra a la vez, sin dividir el mensaje en partes.                     Esto es útil para sistemas de aplicación en telecomunicaciones, y el típico ejemplo es el cifrado de Vernam.
      Cifrado en bloque: cuando de emitirse el mensaje se divide en bloques y se cifran los bloques por separado.                     Esto es útil para sistemas de protección de ficheros de ordenador, y el típico ejemplo es el sistema RSA.
 

Referencias:
 

[1]:        A. Fúster y otros, "Técnicas criptográficas de protección de datos", editorial ra-ma (1997).

[2]:        D. Welsh, "Codes and Cryptography", Clarendon Press (1989).
 


 

Volver al Indice
 


 

Logaritmo Discreto

 

El problema del logaritmo discreto

Sea G un grupo cíclico finito de cardinal n generado por un elemento g, es decir
  G={1,g,g2, ... ,gn-1} El problema del logaritmo discreto consiste en lo siguente:
  Dado h en G, hallar k tal que gk=h Los mejores tiempos de computación conocidos para calcular el logaritmo discreto k son de tipo subexponencial,
por lo que este problema puede ser utilizado como función trampa en un sistema criptográfico como el siguiente.

Criptosistema de ElGamal

Sea p un número primo suficientemente grande, y se considera el grupo multiplicativo (módulo p)
  G=Zp*={1,2,3, ... p-1} Se fija un generador g del grupo G, de forma que todo h de G se escriba como h=gk, para cierto k.

Cada usuario A (resp. B) elige un elemento a (resp. b) en G como clave privada que mantiene en secreto,
y calcula ka=ga módulo p (resp. kb=gb módulo p) que da a conocer como clave pública.

Los posibles mensajes entre los distintos usuarios se suponen elementos de G.
Si A quiere mandar el mensaje m a B, el proceso de cifrado es el siguiente:
 

  1. A elige r en G de forma aleatoria y calcula gr (módulo p).
  2. Utilizando la clave pública kb de B, A calcula m·(kb)r=m·gbr (módulo p).
  3. A envía a B el par (gr,m·gbr).
  Para leer B su mensaje, el proceso de descifrado es el siguiente:
 
  1. Utilizando su clave privada b, B calcula (gr)b (módulo p).
  2. B obtiene el mensaje calculando m = (m·gbr) / (gr)b (módulo p).
  Si cualquier usuario C quisiera obtener m, debería calcular b a partir de kb, es decir, calcular un logaritmo discreto,
con lo que la seguridad del sistema criptográfico de ElGamal se basa en la dificultad de dicho problema.

 
 

Volver al Indice
 


 

Protocolos criptográficos

 

De clave privada

(1) Autentificación: con el fin de que el receptor del mensaje pueda comprobar que el mensaje recibido
        no ha sido alterado por una tercera persona. La forma más sencilla de hacerlo es enviar el texto claro
        junto con el texto cifrado con la clave privada, de forma que el receptor puede por sí mismo cifrar el
        mensaje en claro con dicha clave y comprobar que coincide con el texto cifrado enviado para cerciorarse
        de que el primero no ha sido manipulado (existen otros métodos más confidenciales, pero la mayoría hacen
        uso de sistemas de clave pública). En caso de que una tercera persona manipule el texto en claro, no sabrá
        cómo modificar el texto cifrado sin que el receptor se entere, puesto que no conoce la clave privada.

(2) Firma digital: es un medio para comprometer al emisor a mantener su palabra sin que el receptor
        pueda alterar el contenido del mensaje recibido. La firma digital puede ser de distintos tipos:
 

    1. Implícita: si está contenida en el propio mensaje.
    2. Explícita: si es añadida como una marca inseparable del mensaje.
    3. Privada: si sólo puede identificar al remitente alguien que comparte un secreto con él.
    4. Pública: si cualquier persona puede identificar al remitente a partir de información pública.
    5. Revocable: si el remitente puede negar a posteriori que la firma le pertenece.
    6. Irrevocable: si el receptor puede demostrar que el remitente escribió el mensaje.


(3) Identificación personal: para que el receptor pueda comprobar si la identidad del emisor es verdadera
        o falsa. Las usuales tarjetas magnéticas están sujetas a fraude por su facilidad de duplicación, alteración
        o falsificación; por eso, tienden a ser substituidas por las llamadas tarjetas inteligentes, que contienen
        en su interior un microprocesador hardware con memoria, con lo que resulta imposible su manipulación.

De clave pública

(1) Autentificación, identificación y firma digital: al igual que en el caso de los sistemas de clave privada.
        Con el uso de la clave pública se aumenta, en general, la confidencialidad, aunque se pierda un poco en
        la velocidad de los protocolos.

(2) Compartición de secretos: cuando una persona posee un secreto valioso y sólo tiene una copia del mismo
        corre el riesgo de perderlo en un accidente, pero si hace varias copias del mismo aumenta el riesgo de que
        caiga en otras manos. Así, sería interesante que dicha persona pueda dividir el secreto en diferentes partes
        (asignadas a distintas personas) de forma que sea posible recuperar la totalidad del secreto cuando se junte
        un número mínimo de partes k, pero que ello no sea posible si sólo se juntan k-1.
        Por ejemplo, dicho secreto podría contener instrucciones para una acción crucial (en política internacional,
        finanzas, etcétera), y se quiere que para poder emprender dicha acción se necesite el consenso de k partes
        cualesquiera, independendientemente de que las otras estén o no de acuerdo.

(3) Venta de secretos: supongamos que A posee cierto número de secretos y quiere vender alguno de ellos a B;
        para que esta venta sea efectiva, debe garantizarse obviamente que el vendedor no pueda saber qué secreto es
        el que ha vendido, a la vez que el comprador debe de poder elegir cuáles son los secretos que quiere comprar.

(4) Esquema electoral: lo que se resuelve es cómo puede un grupo de varias personas emitir sus votos en una red
        de modo que tales votos puedan ser contabilizados en el resultado de la votación, pero de forma que sus votos
        individuales permanezcan secretos.

(5) Firma de un contrato: el objetivo es que dos personas puedan firmar un contrato simultáneamente en una red,
        de manera que ninguna de las dos partes pueda romper el protocolo y disponer de la firma de la otra parte sin
        haber firmado antes el contrato.
 
 

Referencias:
  [1]:        G.J. Simmons et al., "Contemporary Cryptology", IEEE Press (1992).

[2]:        B. Schneier, "Applied Cryptography", Ed. John Wiley & Sons, Inc. (1994).


 
 

Volver al Indice
 


 

Aplicaciones prácticas

 

CLAVE PRIVADA

Productos criptográficos comerciales disponibles actualmente en el mercado:

HARDWARE

SOFTWARE

 

CLAVE PUBLICA

Sistemas criptográficos de seguridad disponibles actualmente en el mercado:

REDES DE COMUNICACIONES

SISTEMAS INFORMATICOS


 

Volver al Indice
 


Buzón de sugerencias