Criptografía de clave pública

Autores originales: Graeme L. Cohen (University of Technology, Sydney), Steven Galbraith (University of Auckland) y Edoardo Persichetti (University of Auckland).

¿Cómo podemos enviar de manera segura los datos de nuestra tarjeta de crédito a través de internet o utilizando un teléfono móvil cuando otros pueden interceptar nuestros mensajes? ¿Cómo podemos confiar en las actualizaciones de software sabiendo lo comunes que son los virus en los ordenadores? La criptografía (el estudio de técnicas para la comunicación segura en presencia de enemigos) proporciona respuestas a estas preguntas y tiene sus cimientos en las matemáticas.

Una breve historia

La comunicación segura ha sido importante durante miles de años: existen evidencias de que Julio César usaba un sencillo sistema criptográfico para comunicarse con sus generales. Este esquema se conoce como “cifrado de César” y consiste en desplazar las letras de un mensaje un cierto número prefijado de posiciones para obtener un nuevo documento llamado texto cifrado. El mensaje original puede ser recuperado por el receptor invirtiendo esta operación, es decir, desplazando las letras del texto cifrado recibido en sentido opuesto el mismo número de posiciones.

La idea fundamental es que el emisor y el receptor conocen un valor secreto (en este caso, el número de posiciones) que se asume desconocido para quien intente interceptar el mensaje. El valor secreto de llama clave. En el caso del cifrado de César con clave $K$ es un número entre $0$ y $26$ . El algoritmo de cifrado ${\textsf{Enc}}$ toma como entrada un mensaje $M$ y una clave $K$ ; por ejemplo ${\textsf{Enc}}_3$ (HELLO)=KHOOR. El algoritmo de descrifrado ${\textsf{Dec}}$ toma como entrada un texto cifrado $C$ y la misma clave $K$ ; por ejemplo, ${\textsf{Dec}}_3$ (KHOOR)=HELLO.

Los criptosistemas en los que se usa la misma clave para cifrar y descifrar se llaman
esquemas de clave simétrica.

El cifrado de César es demasiado simple para ser seguro en el mundo moderno, pero existen sistemas modernos de cifrado de clave simétrica que se usan en diversas situaciones; un ejemplo se encuentra es el famoso AES, uno de los estándares del gobierno de EEUU para transmitir datos. Estos sistemas son eficientes y seguros, pero presentan un problema: el emisor y el receptor deben compartir previamente un secreto. ¿Cómo podemos entonces comunicarnos a través de internet con personas que no conocemos?

Una sorprendente idea llamada criptografía de clave pública iniciada en 1976 en el artículo “New directions in cryptography” escrito por Whitfield Diffie y Martin Hellman resuelve este problema. En este contexto, en lugar de usar la misma clave para cifrar y descifrar, existen una clave pública, disponible para todos los posibles usuarios, y una clave privada que permanece en secreto en poder de un usuario específico. En otras palabras, cualquiera puede enviar un mensaje pero solo una persona puede leerlo: cualquiera puede echar una carta en un buzón pero solo la persona que tiene la llave de dicho buzón puede sacar la carta. Para comunicarse de manera segura con Alicia hay que buscar su clave pública y usarla para generar el texto cifrado. Solo Alicia puede descifrar el texto cifrado, ya que solo ella conoce su clave privada.

Los criptosistemas de clave pública deben basarse en problemas computacionales que sean difíciles de resolver. Las matemáticas proporcionan este tipo de problemas. Por ejemplo, el criptosistema RSA se basa en la dificultad de encontrar los factores primos de un número entero muy grande.

Teoría de números

Antes de describir el popular esquema de cifrado de clave pública RSA se necesitan desarrollar algunos resultados de teoría de números. Para ello se requiere una cierta familiriaridad con el teorema del binomio y la aritmética modular.

El aritmética modular se agrupan los números enteros en clases de acuerdo a su resto al dividir por un cierto número $p$ , llamado módulo. Por ejemplo, si $p=7$ se tiene que el 9 está en la clase del 2 y que 5, 12 y 19 pertenecen a la misma clase; lo denotamos como $9 \equiv 2 \pmod 7$ y $12\equiv 19 \equiv 5 \pmod 7$ . Es fácil de ver que hay solo 7 posibles clases cuando se trabaja módulo $7$ : $\{0,1,2,3,4,5,6\}$ . Es posible realizar sumas y multiplicaciones módulo 7: simplemente se reduce el resultado de hacer la operación normalmente, por lo que $3+8=11\equiv 4 \pmod 7$ y $3\cdot 5=15\equiv 1 \pmod 7$ . Notar que si $a \equiv b \pmod{p}$ entonces $(a-b)$ es un múltiplo de $p$ .

Sean $p$ y $p$ números primos, $p \ne q$ y sea $t > 0$ in entero que no es múltiplo de $p$ ni de $q$ . Vamos a probar que se cumple la fórmula $t^{(p-1)(q-1)}\equiv1 \pmod{pq}$ . Esta fórmula es un caso particular del teorema de Euler-Fermat.

La demostración comienza con la fórmula para los coeficientes binomiales:

$\binom pi=\frac{p!}{i!(p-i)!},$

donde $i$ es un número entero tal que $0 < i < p$ . De

$i! \ \binom pi= p(p-1)(p-2)\cdots(p-i+1)$

se sigue que $p$ tiene que ser un divisor de $\binom pi$ , ya que $p$ divide al lado derecho de la igualdad pero no divide a $i!$ .

Por tanto, para cualesquiera números enteros $A$ y $B$ , por el teorema del binomio,

$(A+B)^p=A^p+\binom p1 A^{p-1}B+\binom p2 A^{p-2}B^2+\cdots+B^p\equiv A^p+B^p \pmod p .$

Si tomamos otro número entero $C$ ,

$(A+B+C)^p=((A+B)+C)^p\equiv(A+B)^p+C^p\equiv A^p+B^p+C^p \pmod p.$

Y así, para $A_1$ , $A_2$ , …, $A_t$ números enteros,

$(A_1+A_2+\cdots+A_t)^p\equiv A_1^p+A_2^p+\cdots+A_t^p \pmod p.$

Si tomamos $A_1=A_2=\cdots=A_t=1$ obtenemos que

$t^p\equiv t \pmod p.$

Esta ecuación significa que $(t^p - t) = t( t^{p-1} - 1)$ es un múltiplo de $p$ . Como $p$ no divide a $t$ y $p$ es primo, se sigue que

$t^{p-1}\equiv 1 \pmod p.$

Ahora elevamos ambos lados de la ecuación de congruencia a la potencia $q-1$ :

$t^{(p-1)(q-1)}\equiv 1 \pmod p.$

Repintiendo el argumento con $q$ en lugar de $p$ , se tiene que

$t^{(p-1)(q-1)}\equiv 1 \pmod q.$

Esto quiere decir que existen números enteros $h$ y $k$ tales que

$t^{(p-1)(q-1)}=1+ph, \quad t^{(p-1)(q-1)}=1+qk,$

luego $ph=qk$ . Por tanto, $p$ divide a $k$ (ya que $p$ y $q$ son primos distintos) y, por tanto, $k=pl$ , para algún número entero $l$ . Ahora tenemos que $t^{(p-1)(q-1)}=1+pql$ o, lo que es lo mismo,

$t^{(p-1)(q-1)}\equiv1 \pmod {pq}.$

Esto completa la demostración. $\Box$

El criptosistema RSA

El acrónimo RSA proviene de las iniciales de Rivest, Shamir y Adleman, los primeros que propusieron este esquema en 1977. A continuación se explica cómo funciona.

Primero se eligen dos números primos $p$ y $q$ y se calcula $N=pq$ y $\phi=(p-1)(q-1)$ . Se elige aleatoriamente un número entero $e$ entre 3 y $N-2$ tal que $e$ y $\phi$ no tienen factores primos comunes. La clave pública es el par $(N,e)$ . La clave privada $d$ , que el emisor guardará en secreto, se calcula de tal manera que $d\equiv e^{-1}\pmod\phi$ , esto es, el número tal que $de\equiv1\pmod\phi$ (esto de calcula de manera sencilla usando el algoritmo de Euclides). Por ejemplo, tomar $N = 437 = 19 \cdot 23$ , $\phi = 396$ , $e = 5$ y $d = 317$ .

Los mensajes en el sistema RSA son números enteros $x$ tales que $0 < x < N$ . Puede que en un principio no sea claro cómo cifrar mensajes de texto con un esquema que usa números enteros; sin embargo, los esquemas criptográficos se implementan en ordenadores y todos los documentos son simplemente datos binarios, que se pueden codificar utilizando números enteros.

El proceso de cifrado es el siguiente: supongamos que Bob quiere enviarle un mensaje $x$ a Alicia. Lo que hace es buscar la clave pública de Alicia $(N,e)$ , calcular $y\equiv x^e \pmod{N}$ y enviar $y$ a Alicia. Para descifrar el texto cifrado $y$ , Alicia hace uso de su clave privada $d$ y calcula $x\equiv y^d \pmod{N}$ .

Es importante señalar que aunque $e,d$ y $N$ son números enormes es posible calcular de manera eficiente, por ejemplo $y^d \pmod N$ usando una técnica llamada exponenciación modular.

El descrifrado funciona porque $de=1+k\phi$ para cierto número entero $k$ y, como hemos demostrado antes,

$x^\phi=x^{(p-1)(q-1)}\equiv1 \pmod N$

(en la práctica, los casos en los que $x$ es múltiplo de $p$ o de $q$ pueden ser ignorados) y, por tanto,

$y^d\equiv (x^e)^d= x^{1 + \phi k} = x(x^\phi)^k\equiv x\cdot1^k=x \pmod N.$

Un usuario malicioso que no conozca la clave privada $d$ necesitaría factorizar $N$ para recuperar $p$ y $q$ . Esto está más allá de los límites de la computación actual si estos números primos son suficientemente grandes, por ejemplo de 200 dígitos cada uno (los actuales récords del mundo se encuentran en factorizar $N=pq$ cuando $p$ y $q$ constan de alrededor de 100 dígitos cada uno).

Así se define el nivel de seguridad del esquema. La idea fundamental de la criptografía de clave pública es, de hecho, que un sistema criptográfico es seguro siempre que el esfuerzo computacional que se requiere para romperlo esté más allá de los recursos del atacante. Esto se puede fijar a priori (habitualmente $2^{128}$ o $2^{256}$ operaciones a nivel bit) y dependiendo del contexto y el propósito de la comunicación. Claramente, se espera que un mensaje secreto de la CIA y un email entre dos usuarios de internet cumplan unas normas de seguridad muy diferentes.

Firmas

Ahora podemos empezar a trabajar en el problema de las actualizaciones de software. En otras palabras, el problema de la identificación. Como antes, se tienen una clave pública y una clave privada. Alicia, usando su clave privada, crea una firma digital para enviar junto con el documento para probar su autenticidad (la firma depende del documento y no puede ser copiada y pegada de otro documento diferente). El receptor, por tanto, verifica la firma digital usando la clave pública.

Supongamos, por ejmplo, que tu ordenador te dice que ha encontrado una actualización para Adobe. ¿Cómo sabe el odenador que el software proviene de Adobe y no es un virus enmascarado como una actualización? La solución es que la actualización contiene una firma digital respecto a la clave pública de Adobe. Esta clave pública de hecho se encuentra ya instalada en tu ordenador, en el software de Adobe, por lo que tu ordenador puede verificar la firma antes de instalar la actualización; tener éxito en la verificación prueba que la actualización es realmente de Adobe y de nadie más.

A continuación se muestra cómo contruir firmas digitales usando RSA. Las claves pública y privada son la misma que para el cifrado. Cuando Alicia quiere certificar un documento (por ejemplo, una actualización de software) codifica la certificación como un número entero $0 < x < N$ , calcula $\sigma\equiv x^d \pmod{N}$ y añade la firma $\sigma$ al documento. Para verificar la firma, Bob busca la clave pública de Alicia, calcula $x'\equiv \sigma^e \pmod{N}$ y comprueba que $x=x'$ . Es evidente que, de la misma manera que en el criptosistema RSA, un usuario malicioso que quiera crear una firma válida (por ejemplo, un hacker diseñando un virus) necesitaría el exponente $d$ , para lo que se requiere factorizar $N$ .

Investigación en curso

En esta breve nota hemos tratado de dar una pequeña descripción de los esquemas de criptosistema RSA y firma digital, pero hay otros muchos sistemas basados en objetos matemáticos como cuerpos finitos, curvas elípticas, sistemas de ecuaciones multivariantes no lineales, códigos de corrección de errores y mucho más. La criptografía de clave pública es un área de investigación muy activa y hay todavía muchos problemas abiertos en estudio.

Un escenario post-cuántico

¿Se resuelven todos nuestros problemas con RSA? Desafortunadamente, la respuesta es no. La seguridad del esquema RSA, como el de otros muchos sistemas criptográficos, está seriamente amenazado por el potencial desarrollo de los ordenadores cuánticos. El algoritmo de Shor, publicado en un artículo en 1994 con el portentoso título de “Algoritmos de tiempo polinomial para logaritmos discretos y factorización en ordenadores cuánticos”, es capaz de romper el criptosistema RSA siempre se pueda construir un ordenador cuántico suficientemente grande. Los ordenadores cuánticos de pequeño tamaño son de hecho una realidad y es plausible esperar mejoras en un futuro próximo.

Por tanto, es importante disponer de sistemas alternativos cuya seguridad no se vea afectada en el caso en que esta situación se convierta en realidad. La comunidad criptográfica está siendo muy activa en este sentido y la investigación actual se centra en desarrollar nuevos criptosistemas desde diferentes áreas de las matemáticas, basados en problemas computacionales que ojalá no sean igualmente vulnerables frente a algoritmos cuánticos.

Referencias

[1] Simon Singh, The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography (2000), Anchor.

Este mensaje está disponible en: Inglés, Francés, Alemán, Árabe, Khmer

Criptografía de clave pública

Leave a Reply Cancel reply

Receive notice of every new vignette.

List of Vignettes

Sites of the Month

Books of the Month

Search

Meta

Criptografía de clave pública

Share this:

Leave a Reply Cancel reply

Receive notice of every new vignette.

List of Vignettes

Sites of the Month

Books of the Month

Search

Meta