Un poco de aritmética modular (RSA II)

Damián Viernes 27 de Octubre del 2006

public_key_cryptography_and_pgp1.jpg Continuamos rumbo al algoritmo criptográfico RSA, ahora veremos cosas que quizá parezcan dispersas y no se vea muy claro a donde vamos (como todo en matemáticas) pero no se desesperen. Este artículo es la continuación de Un poco de teoría de números (RSA I).

Introducción

En este artículo se abordará la parte medular, que son las congruencias módulo n, se propocionarán métodos para escribir de una manera especial el máximo común divisor de dos números y finalmente se hará un pequeño ejercicio para calcular el residuo de dividir números grotescos entre algún otro número.

Algoritmo de la división

Este más que un algoritmo es un teorema relacionado con el algoritmo “de la casita” para hacer divisiones.

Teorema. Sean a, b números enteros, con b \neq 0, y entonces procedemos a hacer la división de a entre b. El teorema dice que existen q y r números enteros únicos tales que:

i) a = b \cdot q + r (i.e. el dividendo es igual al divisor por el cociente más el residuo, de primaria)

ii) 0 \leq r < |b| (i.e. el residuo es más chico que el divisor)

Observación importante: r “comúnmente” es llamado el residuo de la división, pero a contraposición de lo que enseñan y el operador módulo de algunos lenguajes de programación, el residuo de dividir -12 entre 5 no es -2, es 3, ya que -12 = 5\cdot(-3) + 3 y el teorema nos asegura que sólo se puede llegar a esa igualdad con -3 y 3 sin haber otros números enteros que satisfagan la igualdad.

Esta observación es importante porque en una implementación del algoritmo RSA se ha de tener cuidado al usar el operador módulo.

Algoritmo de Euclides

El algoritmo de Euclides es un método para encontrar de manera automática, sin pensar (así como le gusta a muchos) el máximo común divisor de dos números.

Ahora imaginemos que queremos encontrar el (a,b), hay un resultado que nos dice que (a,b) = (|a|,|b|), y así no nos tendremos que preocupar tanto porque el operador módulo del algún lenguaje de programación no haga lo que queremos.

Por lo que se mencionó entonces vamos a suponer que a\geq0 y b>0, y vamos calcular el mc.d. haciendo muchas divisiones “de casita” empezando por a entre b, luego b entre el residuo de la divisón anterior, luego el primer residuo entre el segundo residuo, el segundo residuo entre el tercero y así hasta que el último residuo sea cero y vamos a usar el algoritmo de la división para escribir mañosamente estas divisiones. Entonces nos quedaría:

a = b \cdot q_{1} + r_{1} … donde 0 < r1 < b
b = r_{1} \cdot q_{2} + r_{2} … donde 0 < r2 < r1
r_{1} = r_{2} \cdot q_{3} + r_{3} … donde 0 < r3 < r2
.
.
.
r_{n-3} = r_{n-2} \cdot q_{n-1} + r_{n-1} … donde 0 < rn-1 < rn-2
r_{n-2} = r_{n-1} \cdot q_{n} + r_{n} … donde rn = 0 (esta sería la condición de parada)

Teorema. (a,b) = r_{n-1}

Def. Un número entero c es combinación lineal de a y b si existen enteros a' y b' tales que c = a' (a) + b' (b)

Teorema. (a,b) simpre puede escribirse como combinación lineal de a y b

Si vemos un rato el algoritmo de euclides podemos darnos cuenta que nos proporciona toda la información para poder escribir el (a,b) como combinación lineal de a y b (sólo haría falta hacer los desarrollos algebraicos). Y si lo vemos unas horas más se nos podría ocurrir el siguiente algoritmo recursivo para obtener a' y b' tales que (a,b) = a' (a) + b' (b).

Este sería el pseudocódigo (este algoritmo y el resultado siguiente van a ser fundamentales para implementar el algoritmo RSA):

integer a_prima (integer a, integer b)
   if a % b = 0 then
	return 0
   else
	return b_prima ( b, a % b )
   endif
end

integer b_prima (integer a, integer b)
   if a % b = 0 then
	return 1
   else
	return a_prima( b , a % b ) - a / b * b_prima (b, a % b)
   endif
end

Donde a / b devuelve el cociente de dividir a entre b (i.e. q en el algoritmo de la división) y a % b devuelve el residuo de dividir a entre b (i.e. r en el algoritmo de la división). Aqui no debe preocuparnos que el operador módulo no esté estrictamente implementado en el lenguaje de programación de su preferencia, ya que estuvimos suponiendo que a \geq 0 yb > 0, y así debemos pasar los parámetros, si no sabe Dios qué hará el algoritmo.

Ahora imaginemos que nuestra ociosidad tiende al infinito, entonces nos preguntamos ¿es posible encontrar a' y b' tales que a' sea positivo y b' negativo?

Pues la respuesta es sí, y entonces vamos a ver el siguiente resultado.

Teorema. Si hay dos números a' y b' tales que (a,b) = a' (a) + b' (b) entonces para todo número entero q, considerando a_0=a'+(-b)q y b_0=b'+aq, se tiene que (a,b) = a_0 (a) + b_0(b)

Así con eso podemos construir un algoritmo de tal manera que encuentre a_0 positivo y b_0 negativo.

Ej. Imagínese que tenemos (7,120)=1 y con el algoritmo descrito unos parráfos antes obtenemos a'=-17 y b'=1, y ahora queremos obtener un s positivo y un t negativo tales que 1=7s + 120t . Entonces construimos a_0=-17+(-120)q y b_0=1+7q, y nada más tomamos q=-1 para obtener s=103 y t=-6. Ahora nos sorprendemos de la hechicería y comprobamos que (7,120)=1=7(103)+120(-6) .

Encontrar a_0 y b_0 se llama en jerga matemática “hallar todas las soluciones de la ecuación diofantina”.

Congruencias Módulo N

Def. Se dice que a y b son congruentes módulo n y se escribe a \equiv b \pmod{n} si n|a-b.Eso de \pmod{ n} no es ninguna operación ni nada, todo es notación.

Parece complicado pero la idea subyacente es más bien fácil, vean un reloj de manecillas, ¿por qué a la 1 pueden ser las 13 horas del día? pues fácil, es porque un reloj es una congruencia módulo 12 y es fácil ver que 13 \equiv 1 \pmod{12} y ¿por qué a las 12 pueden ser las 0 horas? porque 12 \equiv 0 \pmod{12} ¿qué hora marcaría el reloj a las 36 horas? pues 12, ya que 36 \equiv 12 \pmod{12} o bien podrían ser las cero horas si el reloj empezara en 0 y terminara en 11, ya que 36 \equiv 0 \pmod{12}, ¿o qué hora marcaría el reloj a las 12 si los números de la carátula fueran del 0 al 11? pues el 0 obviamente.

Las congruencias módulo n son como relojes de n horas, lo único complicado es que también aceptan valores negativos ¿las -1 horas en dónde las marcaría el reloj? pues en 11, ya que 11 \equiv -1 \pmod{12}

Propiedades.

  1. a \equiv b \pmod{n} sí y sólo si b \equiv a \pmod{n} (i.e. que da lo mismo poner como se quieran los números)
  2. Si a \equiv b \pmod{n} y c \equiv d \pmod{n} entonces a\cdotc \equiv d\cdotb \pmod{n}
    Ejemplo interesante: Imagínense que alguien ocioso (como yo) los pone a calcular el residuo de dividir 91119763 entre 6. Se puede ver que 91 \equiv 1 \pmod{6} y si multiplicamos 119763 veces esa congruencia consigo misma, entonces 91^{119763} \equiv 1 \pmod{6}, esto nos dice en otras palabras que existe un entero q tal que 6\cdotq = 91^{119763} - 1 , y se parece mucho al algoritmo de la división para dividir 91119763 entre 6, ya que 0 < 1 < 6, ¡así que ya terminamos! el residuo es 1 y sin hacer una sola "casita".
  3. Si tenemos una congruencia a \equiv r \pmod{b} con 0 \leq r < |b| entonces r es el residuo de dividir a entre b y recíprocamente si hacemos la división de a entre b entonces a \equiv r \pmod{b} donde r es el residuo.

Esta última propiedad es fundamental para encriptar los mensajes.

Todos estos resultados aunque parecieran engorrosos, es muy importante que los tenga en la cabeza aquel que va a implementar el algoritmo, porque la verdad es que parece magia ver trabajar al algoritmo, con unas cuantas multiplicaciones y módulos sale todo, pero por lo mismo a veces deja la duda de si en verdad lo están haciendo bien y nunca va a fallar.

Continuará…

Una respuesta to “Un poco de aritmética modular (RSA II)”

  1. # AmarellOcio » Blog Archive » El Algoritmo (RSA III)on 19 Nov 2006 at 13:07

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

Trackback URI | RSS de los comentarios

Deja un Comentario

Posts relacionados