El Algoritmo (RSA III)

Damián Domingo 19 de Noviembre del 2006

Este es el último artículo sobre el algoritmo RSA, ahora sí ya vamos a dar el método para cifrar y descifrar mensajes y se harán algunas observaciones que se deben tomar en cuenta a la hora del a implementación.

Esta es la continuación de los artículos:

Un poco de teoría de números (RSA I)
Un poco de aritmética modular (RSA II)

Introducción

Primero se definirá una función un poco particular, luego se dará el resultado de teoría de números que hace posible este algoritmo criptográfico, finalmente se mostrará el algoritmo, un ejemplo básico de uso y recomendaciones sobre implementación.

La función $\varphi$ de Euler

Def. Para un número $n$ natural, la función $\varphi$ (se lee “fi”) de Euler se define como la cardinalidad del conjunto $\{m \in \mathbb{N} | 1 \leq m \leq n \ y \ (m,n)=1\}$ . O sea $\varphi (n) = \#\{m \in \mathbb{N}| 1 \leq m \leq n \ y \ (m,n)=1\}$

En otras palabras $\varphi (n)$ es el número de números naturales menores a $n$ tales que tienen con $n$ un máximo común divisor de $1$ . Es la cantidad de primos relativos a $n$ que hay entre $1$ y $n$ .

Esta función cumple ciertas propiedades:

Si $p$ es un número natural primo, entonces $\varphi (p)=p-1$
Si $m$ y $n$ son naturales y primos relativos (i.e. $(m,n)=1$ ), entonces $\varphi (m \cdot n)=\varphi (m) \varphi (n)$
De la última propiedad se deduce trivialmente que si $p$ y $q$ son números naturales primos distintos, entonces $\varphi (p \cdot q)=(p-1)(q-1)$

Pequeño Teorema de Fermat (sólo dato cultural)

Este resultado nos dice cosas muy interesantes, que serán generalizadas más adelante.

Teorema. Si $p$ es un número natural primo y $a$ es un entero tal que $a$ no es múltiplo de $p$ , entonces $a^{p-1} \equiv 1 \pmod{n}$ .

Teorema de Euler

Teoremón. Si $n$ es un número natural y $a$ es un número entero tal que $(a,n)=1$ , entonces $a^{\varphi (n)} \equiv 1 \pmod{n}$ .

Primeros pasos para usar el algoritmo RSA

Se eligen dos números naturales primos distintos muy grandes, digamos $p$ y $q$ .
Se calcula $n=pq$ .
Se elige un número entero positivo $e$ tal que $(e,\varphi (n)) = 1$ (i.e. $(e,(p-1)(q-1)) = 1$ ).
Dada la forma en que fue elegido $e$ , entonces 1 se puede escribir como combinación lineal de $e$ y $\varphi (n)$ . Además existe un numero entero positivo y otro negativo, $d$ y $k$ respectivamente, tales que $1=e \cdot d + \varphi (n) \cdot k$ . Lo último es posible por una observación que se hizo en el artículo anterior cuando se habló de las todas las soluciones de una ecuación diofantina.
La llave pública es la pareja $[n,e]$ . La llave privada, que debe mantener secreta, es $d$ . Los valores de los números primos $p$ y $q$ no deben revelarse aunque no es necesario recordarlos, basta recordar $\varphi (n)$ .

Nota: $n$ es llamado comúnmente como módulo RSA, $e$ como el exponente público y $d$ como el exponente privado.

La idea de este algoritmo y de todos los algoritmos de clave pública es la siguiente: publicas en Internet tu llave pública y cuando alguien te quiere mandar algo “confidencial” entonces usa tu llave pública para cifrar el mensaje; si alguien lo interceptara no podrá descifrarlo fácilmente si no conoce tu llave privada.

Ejemplo. Supongamos que:

$n=7789 \cdot 6691=52116199$ , entonces $\varphi (n) = (7789-1)(6691-1)=52101720$ .
Ahora elijo $e=13$ y busco unos enteros tales que $1=13 \cdot s + 52101720 \cdot t$ . Usando el algoritmo llegamos a que $s=-20039123$ y $t=5$ .
Falta encontrar $d$ ; usando el otro algoritmo (mencionado en el artículo anterior) llego a que $d=(-20039123)+(-52101720)q$ . Tomo $q=-1$ y obtenemos que $d=32062597$ .

Cifrado de Mensajes

Supongamos que poseemos un alfabeto numerado (utf-8 o ascii por ej.) y tenemos un mensaje en ese alfabeto. Si mapeamos todo el mensaje con los números que le corresponden a cada caracter y los pegamos, vamos a tener un número entero positivo; llamémosle a ese número $M$ .

Los pasos a seguir para cifrar ese mensaje son:

Divides $M$ en bloques de igual cantidad de dígitos, de tal manera que el número de dígitos que tenga cada bloque sea menor que el número de dígitos que tiene $n$ . Vas a tener un conjunto de $t$ bloques $\{m_1, m_2, \ldots , m_t\}$ .

Nota: Por eso RSA es clasificado como un sistema de llave pública de cifrado por bloques.
Tenemos que verificar que para todo $m_i$ se tenga que $(m_i,n)=1$ . Si no pasa esto entonces tendremos que construir bloques $m_i$ de menos digitos hasta que se logre que todos los bloques cumplan $(m_i,n)=1$ , o buscar otra $n$
Vamos a tener que calcular el residuo de dividir $m_i^e$ entre $n$ para toda $i \in \{1,2,..,t\}$ .
Finalmente mandamos los residuos $\{r_1, r_2, \ldots , r_t\}$ en orden, de $1$ a $t$ , junto con el número de dígitos que tenían los bloques originales. Obsérvese que $m_i^e \equiv r_i \pmod{n}$

Ejemplo. Usaremos lo que se obtuvo en el ejemplo anterior. Imagínese que se tienen las letras de la A a la Z, numeradas de 01 hasta 27. Alguien nos quiere mandar el mensaje: “MIGUEL DE CERVANTES”. Así que esta persona hace el mapeo con el alfabeto y le queda que $M=1309072205120405030519230114210520$ . Ahora separa en bloques de 5 dígitos:
$m_1 = 13090 \\ m_2=72205 \\ m_3=12040 \\ m_4 = 50305 \\ m_5 = 19230 \\ m_6=11421 \\ m_7=0520$

Va a tener que rellenar $m_7$ con un cero, así que quedará $m_7=05200$ . Esto se pudo haber evitado si se escogían bloques de 4 o 6 dígitos. Además tiene que comprobar que todos los bloques cumplen $(m_i,n)=1$ .

Finalmente calcula los residuos:
$r_1 = m_1^{13} \bmod 52116199 = 11703603 \\ r_2 = m_2^{13} \bmod 52116199 = 48856295 \\r_3 = m_3^{13} \bmod 52116199 = 48428627 \\ r_4 = m_4^{13} \bmod 52116199 = 36381337 \\ r_5 = m_5^{13} \bmod 52116199 = 13084126 \\ r_6 = m_6^{13} \bmod 52116199 = 22505145 \\ r_7 = m_7^{13} \bmod 52116199 = 48907094$

Nos envía el mensaje, o sea, los bloques en orden.

Descifrado de Mensajes

Recordemos que $(m_i,n)=1$ , entonces $m_i^{\varphi (n)} \equiv 1 \pmod{n}$ y $\left( m_i^{\varphi (n)} \right) ^{-k} \equiv 1 \pmod{n}$ , por lo tanto $m_i \left( m_i^{\varphi (n)} \right) ^{-k} \equiv m_i \pmod{n}$ . Ahora miremos fijamente a $m_i^e$ y veamos que dada la forma en que elegimos $e$ tenemos que $m_i^{ed}=m_i^{1+(-k)\varphi (n)}=m_i \left( m_i^{\varphi (n)} \right) ^{-k}$ . Con lo anterior hacemos una sustitución y nos queda que: $\left( m_i^e \right) ^{d} \equiv m_i \pmod {n}$ .

Es fácil ver ahora lo importante del Teorema de Euler ya que de lo anterior se deduce que $r_i^d \equiv m_i \pmod{n}$ . Esto nos dice que el residuo de dividir $r_i^d$ entre $n$ es igual al bloque original. O sea que gracias a este resultado podemos descifrar los mensajes.

Resumiendo: para descifrar un mensaje lo que se hace es calcular el residuo de dividir $r_i^d$ entre $n$ . Podemos asegurar que ese residuo es igual a $m_i$ , ya que habíamos pedimos que los bloques del mensaje tengan menos digitos que $n$ . Sólo faltaría completar los ceros a la izquierda de cada residuo obtenido, para después concatenar todos los $r_i$ y así obtener $M$ (el mensaje original).

Ejemplo. Vamos a usar los datos de los ejemplos anteriores. Imagínese que nos llegan $\{ r_1 , \ldots , r_7 \}$ bloques cifrados y nos dicen que: los bloques originales eran de 5 dígitos, $M$ es de 34 dígitos y usaron $e=13$ . Cabe mencionar que para un mismo módulo RSA se pueden tener varios exponentes publicos cuando previamente hemos calculado sus respectivos exponetes privados.

Procedemos a descifrar, así que calculamos:
$r_1^{32062597} \bmod 52116199 = 13090 \\ r_2^{32062597} \bmod 52116199 = 72205 \\ \vdots$

Completamos con ceros a la izquierda cuando sea necesario, en este caso en el último residuo vamos a tener que ponerle un cero a la izquierda para que nos quede $05200$ y esté completo el bloque.

Finalmente concatenamos todos los bloques y queda $M'=13090722051204050305192301142105200$ , quitamos el último cero para que el mensaje sea de 34 dígitos y tengamos $M$ .

Recomendaciones para una implementación segura

Los números primos que se escojan deben ser grandes (para evitar que factoricen el módulo RSA), se recomiendan mayores a $10^{100}$ . Actualmente se usan módulos de 1024 bits, lo que significa que son números más grandes que $2^{1023}$
Que no los tiente la opción de escoger un exponente público chico pretendiendo que los cálculos sean más rápidos; los expertos recomiendan $e=2^{16}+1$ . Ya que con un exponente público pequeño se puede comprometer la seguridad, sin necesidad de factorizar el módulo RSA.
Dada la naturaleza de $d$ , se puede dar el caso en donde se obtenga una $d$ pequeña, esto es muy inseguro. Por lo que se recomienda buscar otro $e$ de tal manera que $d$ sea grande. Para módulos RSA de 1024 bits se recomienda que $d$ sea de al menos 256 bits (i.e. mayor a $2^{255}$ )
Es igual de importante mantener secreto $\varphi (n)$ , pues por eso se pide que $p$ y $q$ sean secretos, ya que es más tardado calcular $\varphi (n)$ , conociendo solamente a $n$ , que factorizar $n$ .

Recomendaciones para la exponenciación

En lugar de hacer la exponenciación completa y luego sacar el residuo, se pueden usar multiplicaciones modulares para obtener el residuo sin tener que operar con números tan grandes, obsérvese que si tenemos $a \equiv b \pmod {n}$ y quisieramos conocer $q$ de $a^m \equiv q \pmod {n}$ . Entonces se puede implementar así:

Se calcula el residuo de dividir $a$ entre $n$ y así obtenemos $b$ .
Luego se va multiplicando $b$ consigo misma (tendremos que llegar a multiplicarla $m$ veces), pero si en algún momento (digamos en la $j$ -ésima multiplicación) las multiplicaciones sucesivas de $b$ superan a $n$ (considérese $w=b_1\cdots b_j>n$ ) entonces procedemos a sacar de nuevo el residuo de $w$ entre $n$ y continuamos multiplicando el residuo anterior por $b$ hasta que nos vuelva a pasar que superamos a $n$ o terminamos.

El algoritmo sería el siguiente (un poco optimizado):

expModular (a,m,n)
   b  a % n
   for  do
       
       if b > n then
          b  b % n
       else
          if b = n then
               b  0
          endif
       endif
   endfor
   return b
end

Fin

Aqui termina esta serie de artículos, espero les sirva de algo. Y pido una disculpa si en algún momento dije cosas como “es obvio”, “es fácil ver”, etc… Ahorita ya es obvio para mi, pero me tardé poca más de medio semestre en comprender y demostrar todo esto. Ustedes podrán juzgar si valió la pena ese semestre.

Felices criptogramas.

Seguridad en Información

Una respuesta to “El Algoritmo (RSA III)”

# AmarellOcio » Blog Archive » Firmas Digitaleson 20 Sep 2007 at 20:02

[...] Lo que se va a resolver esta vez es que el documento sea auténtico, y que no ha sido modificado. Para ello vamos a hacer uso de nuestro conocido algoritmo RSA. [...]

Trackback URI | RSS de los comentarios

Porque la ociosidad es la madre de todas las ciencias

El Algoritmo (RSA III)

Una respuesta to “El Algoritmo (RSA III)”

Deja un Comentario

Posts relacionados

Archivos

Tags

Páginas